Sort an outline at every level: Difference between revisions
m (→{{header|Phix}}: added syntax colouring the hard way) |
|||
Line 1,489: | Line 1,489: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
<!--<lang Phix>(notonline)--> |
|||
<lang Phix>procedure print_children(sequence lines, children, string indent, bool bRev) |
|||
<span style="color: #008080;">procedure</span> <span style="color: #000000;">print_children</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">lines</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">children</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">string</span> <span style="color: #000000;">indent</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">bool</span> <span style="color: #000000;">bRev</span><span style="color: #0000FF;">)</span> |
|||
sequence tags = custom_sort(lines,children) |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">tags</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">custom_sort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lines</span><span style="color: #0000FF;">,</span><span style="color: #000000;">children</span><span style="color: #0000FF;">)</span> |
|||
if bRev then tags = reverse(tags) end if |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">bRev</span> <span style="color: #008080;">then</span> <span style="color: #000000;">tags</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">reverse</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tags</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
for i=1 to length(tags) do |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tags</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
integer ti = tags[i] |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">ti</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tags</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> |
|||
printf(1,"%s%s\n",{indent,lines[ti][1]}) |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s%s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">indent</span><span style="color: #0000FF;">,</span><span style="color: #000000;">lines</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ti</span><span style="color: #0000FF;">][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]})</span> |
|||
print_children(lines,lines[ti][$],lines[ti][2],bRev) |
|||
<span style="color: #000000;">print_children</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lines</span><span style="color: #0000FF;">,</span><span style="color: #000000;">lines</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ti</span><span style="color: #0000FF;">][$],</span><span style="color: #000000;">lines</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ti</span><span style="color: #0000FF;">][</span><span style="color: #000000;">2</span><span style="color: #0000FF;">],</span><span style="color: #000000;">bRev</span><span style="color: #0000FF;">)</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
end procedure |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span> |
|||
constant spaced = """ |
|||
<span style="color: #008080;">constant</span> <span style="color: #000000;">spaced</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""" |
|||
zeta |
|||
zeta |
|||
beta |
|||
beta |
|||
gamma |
|||
lambda |
|||
kappa |
|||
mu |
|||
delta |
|||
alpha |
|||
alpha |
|||
theta |
|||
theta |
|||
iota |
|||
epsilon |
|||
""", |
|||
"""</span><span style="color: #0000FF;">,</span> |
|||
tabbed = substitute(spaced," ","\t"), |
|||
<span style="color: #000000;">tabbed</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">substitute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">spaced</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" "</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\t"</span><span style="color: #0000FF;">),</span> |
|||
confused = substitute_all(spaced,{" gamma"," kappa"},{"gamma","\t kappa"}), |
|||
<span style="color: #000000;">confused</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">substitute_all</span><span style="color: #0000FF;">(</span><span style="color: #000000;">spaced</span><span style="color: #0000FF;">,{</span><span style="color: #008000;">" gamma"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" kappa"</span><span style="color: #0000FF;">},{</span><span style="color: #008000;">"gamma"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\t kappa"</span><span style="color: #0000FF;">}),</span> |
|||
ragged = substitute_all(spaced,{" gamma","kappa"},{"gamma"," kappa"}), |
|||
<span style="color: #000000;">ragged</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">substitute_all</span><span style="color: #0000FF;">(</span><span style="color: #000000;">spaced</span><span style="color: #0000FF;">,{</span><span style="color: #008000;">" gamma"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"kappa"</span><span style="color: #0000FF;">},{</span><span style="color: #008000;">"gamma"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" kappa"</span><span style="color: #0000FF;">}),</span> |
|||
tests = {spaced,tabbed,confused,ragged}, |
|||
<span style="color: #000000;">tests</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">spaced</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tabbed</span><span style="color: #0000FF;">,</span><span style="color: #000000;">confused</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ragged</span><span style="color: #0000FF;">},</span> |
|||
names = "spaced,tabbed,confused,ragged" |
|||
<span style="color: #000000;">names</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"spaced,tabbed,confused,ragged"</span> |
|||
procedure test(sequence lines) |
|||
<span style="color: #008080;">procedure</span> <span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">lines</span><span style="color: #0000FF;">)</span> |
|||
sequence pi = {-1}, -- indents (to locate parents) |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">pi</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},</span> <span style="color: #000080;font-style:italic;">-- indents (to locate parents)</span> |
|||
pdx = {0}, -- indexes for "" |
|||
<span style="color: #000000;">pdx</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},</span> <span style="color: #000080;font-style:italic;">-- indexes for ""</span> |
|||
children = {}, |
|||
<span style="color: #000000;">children</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{},</span> |
|||
roots = {} |
|||
<span style="color: #000000;">roots</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span> |
|||
for i=1 to length(lines) do |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lines</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
string line = trim_tail(lines[i]), |
|||
<span style="color: #004080;">string</span> <span style="color: #000000;">line</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">trim_tail</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lines</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]),</span> |
|||
text = trim_head(line) |
|||
<span style="color: #000000;">text</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">trim_head</span><span style="color: #0000FF;">(</span><span style="color: #000000;">line</span><span style="color: #0000FF;">)</span> |
|||
integer indent = length(line)-length(text) |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">indent</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">line</span><span style="color: #0000FF;">)-</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">text</span><span style="color: #0000FF;">)</span> |
|||
-- remove any completed parents |
|||
<span style="color: #000080;font-style:italic;">-- remove any completed parents</span> |
|||
while length(pi) and indent<=pi[$] do |
|||
<span style="color: #008080;">while</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pi</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">and</span> <span style="color: #000000;">indent</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">pi</span><span style="color: #0000FF;">[$]</span> <span style="color: #008080;">do</span> |
|||
pi = pi[1..$-1] |
|||
<span style="color: #000000;">pi</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">pi</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..$-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> |
|||
pdx = pdx[1..$-1] |
|||
<span style="color: #000000;">pdx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">pdx</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..$-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> |
|||
end while |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
integer parent = 0 |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">parent</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> |
|||
if length(pi) then |
|||
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pi</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> |
|||
parent = pdx[$] |
|||
<span style="color: #000000;">parent</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">pdx</span><span style="color: #0000FF;">[$]</span> |
|||
if parent=0 then |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">parent</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> |
|||
if indent!=0 then |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">indent</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> |
|||
printf(1,"**invalid indent** (%s, line %d)\n\n",{text,i}) |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"**invalid indent** (%s, line %d)\n\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">text</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">})</span> |
|||
return |
|||
<span style="color: #008080;">return</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
roots &= i |
|||
<span style="color: #000000;">roots</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">i</span> |
|||
else |
|||
<span style="color: #008080;">else</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">lines</span><span style="color: #0000FF;">[</span><span style="color: #000000;">parent</span><span style="color: #0000FF;">][$]={}</span> <span style="color: #008080;">then</span> |
|||
lines[parent][2] = line[1..indent] |
|||
<span style="color: #000000;">lines</span><span style="color: #0000FF;">[</span><span style="color: #000000;">parent</span><span style="color: #0000FF;">][</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">line</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">indent</span><span style="color: #0000FF;">]</span> |
|||
elsif lines[parent][2]!=line[1..indent] then |
|||
<span style="color: #008080;">elsif</span> <span style="color: #000000;">lines</span><span style="color: #0000FF;">[</span><span style="color: #000000;">parent</span><span style="color: #0000FF;">][</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]!=</span><span style="color: #000000;">line</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">indent</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span> |
|||
printf(1,"**inconsistent indent** (%s, line %d)\n\n",{text,i}) |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"**inconsistent indent** (%s, line %d)\n\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">text</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">})</span> |
|||
return |
|||
<span style="color: #008080;">return</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
lines[parent][$] &= i -- (update children) |
|||
<span style="color: #000000;">lines</span><span style="color: #0000FF;">[</span><span style="color: #000000;">parent</span><span style="color: #0000FF;">][$]</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">i</span> <span style="color: #000080;font-style:italic;">-- (update children)</span> |
|||
end if |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
end if |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
pi &= indent |
|||
<span style="color: #000000;">pi</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">indent</span> |
|||
pdx &= i |
|||
<span style="color: #000000;">pdx</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">i</span> |
|||
lines[i] = {text,"",children} |
|||
<span style="color: #000000;">lines</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">text</span><span style="color: #0000FF;">,</span><span style="color: #008000;">""</span><span style="color: #0000FF;">,</span><span style="color: #000000;">children</span><span style="color: #0000FF;">}</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
printf(1,"ascending:\n") |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"ascending:\n"</span><span style="color: #0000FF;">)</span> |
|||
print_children(lines,roots,"",false) |
|||
<span style="color: #000000;">print_children</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lines</span><span style="color: #0000FF;">,</span><span style="color: #000000;">roots</span><span style="color: #0000FF;">,</span><span style="color: #008000;">""</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">)</span> |
|||
printf(1,"\ndescending:\n") |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\ndescending:\n"</span><span style="color: #0000FF;">)</span> |
|||
print_children(lines,roots,"",true) |
|||
<span style="color: #000000;">print_children</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lines</span><span style="color: #0000FF;">,</span><span style="color: #000000;">roots</span><span style="color: #0000FF;">,</span><span style="color: #008000;">""</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">)</span> |
|||
printf(1,"\n") |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">)</span> |
|||
end procedure |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span> |
|||
for t=1 to length(tests) do |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
string name = split(names,",")[t] |
|||
<span style="color: #004080;">string</span> <span style="color: #000000;">name</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">split</span><span style="color: #0000FF;">(</span><span style="color: #000000;">names</span><span style="color: #0000FF;">,</span><span style="color: #008000;">","</span><span style="color: #0000FF;">)[</span><span style="color: #000000;">t</span><span style="color: #0000FF;">]</span> |
|||
-- printf(1,"Test %d (%s):\n%s\n",{t,name,tests[t]}) |
|||
printf(1,"Test %d (%s):\n",{t,name}) |
<span style="color: #000080;font-style:italic;">-- printf(1,"Test %d (%s):\n%s\n",{t,name,tests[t]})</span> |
||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Test %d (%s):\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">name</span><span style="color: #0000FF;">})</span> |
|||
sequence lines = split(tests[t],"\n",no_empty:=true) |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">lines</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">split</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">t</span><span style="color: #0000FF;">],</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">no_empty</span><span style="color: #0000FF;">:=</span><span style="color: #004600;">true</span><span style="color: #0000FF;">)</span> |
|||
test(lines) |
|||
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lines</span><span style="color: #0000FF;">)</span> |
|||
end for</lang> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<!--</lang>--> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
Revision as of 20:13, 11 April 2021
You are encouraged to solve this task according to the task description, using any language you may know.
- Task
Write and test a function over an indented plain text outline which either:
- Returns a copy of the outline in which the sub-lists at every level of indentation are sorted, or
- reports that the indentation characters or widths are not consistent enough to make the outline structure clear.
Your code should detect and warn of at least two types of inconsistent indentation:
- inconsistent use of whitespace characters (e.g. mixed use of tabs and spaces)
- inconsistent indent widths. For example, an indentation with an odd number of spaces in an outline in which the unit indent appears to be 2 spaces, or 4 spaces.
Your code should be able to detect and handle both tab-indented, and space-indented (e.g. 4 space, 2 space etc) outlines, without being given any advance warning of the indent characters used, or the size of the indent units.
You should also be able to specify different types of sort, for example, as a minimum, both ascending and descending lexical sorts.
Your sort should not alter the type or size of the indentation units used in the input outline.
(For an application of Indent Respectful Sort, see the Sublime Text package of that name. The Python source text [1] is available for inspection on Github).
Tests
- Sort every level of the (4 space indented) outline below lexically, once ascending and once descending.
zeta beta gamma lambda kappa mu delta alpha theta iota epsilon
- Do the same with a tab-indented equivalent of the same outline.
zeta gamma mu lambda kappa delta beta alpha theta iota epsilon
The output sequence of an ascending lexical sort of each level should be:
alpha epsilon iota theta zeta beta delta gamma kappa lambda mu
The output sequence of a descending lexical sort of each level should be:
zeta gamma mu lambda kappa delta beta alpha theta iota epsilon
- Attempt to separately sort each of the following two outlines, reporting any inconsistencies detected in their indentations by your validation code.
alpha epsilon iota theta zeta beta delta gamma kappa lambda mu
zeta beta gamma lambda kappa mu delta alpha theta iota epsilon
- Related tasks
AutoHotkey
<lang AutoHotkey>Sort_an_outline(data, reverse:=""){ ;----------------------- ; get Delim, Error Check for i, line in StrSplit(data, "`n", "`r") if !Delim RegExMatch(line, "^\h+", Delim) else if RegExMatch(RegExReplace(line, "^(" Delim ")*"), "^\h+") return "Error @ " line ;----------------------- ; ascending lexical sort ancestor:=[], tree:= [], result:="" for i, line in StrSplit(data, "`n", "`r"){ name := StrSplit(line, delim?delim:"`t") n := name.count() son := name[n] if (n>rank) && father ancestor.push(father) loop % rank-n ancestor.pop() for i, father in ancestor Lineage .= father . delim output .= Lineage son "`n" rank:=n, father:=son, Lineage:="" } Sort, output for i, line in StrSplit(output, "`n", "`r") name := StrSplit(line, delim) , result .= indent(name.count()-1, delim) . name[name.count()] "`n" if !reverse return Trim(result, "`n") ;----------------------- ; descending lexical sort ancestor:=[], Lineage:="", result:="" Sort, output, R for i, line in StrSplit(output, "`n", "`r"){ name := StrSplit(line, delim) if !ancestor[Lineage] loop % name.count() result .= indent(A_Index-1, delim) . name[A_Index] "`n" else if (StrSplit(Lineage, ",")[name.count()] <> name[name.count()]) result .= indent(name.count()-1, delim) . name[name.count()] "`n" Lineage := "" loop % name.count()-1 Lineage .= (Lineage ? "," : "") . name[A_Index] , ancestor[Lineage] := true } return result } indent(n, delim){ Loop, % n result.=delim return result }</lang> Examples: "Example of Data_2"<lang AutoHotkey>Data_2 = ( zeta gamma mu lambda kappa delta beta alpha theta iota epsilon ) MsgBox % Sort_an_outline(Data_2) MsgBox % Sort_an_outline(Data_2, 1) return</lang>
Output: tabulated for ease of reading, actual output is text only, Error check returns first line with inconsistent delimiter!
====================================================================================================== Data_1, 4-Space |Output 1 ||Data_2, tab |Output 2 |Output 2, Reverse ====================================================================================================== zeta |alpha ||zeta |alpha |zeta beta | epsilon || gamma | epsilon | gamma gamma | iota || mu | iota | mu lambda | theta || lambda | theta | lambda kappa |zeta || kappa |zeta | kappa mu | beta || delta | beta | delta delta | delta || beta | delta | beta alpha | gamma ||alpha | gamma |alpha theta | kappa || theta | kappa | theta iota | lambda || iota | lambda | iota epsilon | mu || epsilon | mu | epsilon ====================================================================================================== ====================================================================================================== inconsistent_1 ||inconsistent_2 ================================= alpha ||zeta epsilon || beta iota || gamma theta || lambda zeta || kappa beta || mu delta || delta gamma ||alpha kappa || theta lambda || iota mu || epsilon ================================= Error @ iota ||Error @ gamma =================================
Go
<lang go>package main
import (
"fmt" "math" "sort" "strings"
)
func sortedOutline(originalOutline []string, ascending bool) {
outline := make([]string, len(originalOutline)) copy(outline, originalOutline) // make copy in case we mutate it indent := "" del := "\x7f" sep := "\x00" var messages []string if strings.TrimLeft(outline[0], " \t") != outline[0] { fmt.Println(" outline structure is unclear") return } for i := 1; i < len(outline); i++ { line := outline[i] lc := len(line) if strings.HasPrefix(line, " ") || strings.HasPrefix(line, " \t") || line[0] == '\t' { lc2 := len(strings.TrimLeft(line, " \t")) currIndent := line[0 : lc-lc2] if indent == "" { indent = currIndent } else { correctionNeeded := false if (strings.ContainsRune(currIndent, '\t') && !strings.ContainsRune(indent, '\t')) || (!strings.ContainsRune(currIndent, '\t') && strings.ContainsRune(indent, '\t')) { m := fmt.Sprintf("corrected inconsistent whitespace use at line %q", line) messages = append(messages, indent+m) correctionNeeded = true } else if len(currIndent)%len(indent) != 0 { m := fmt.Sprintf("corrected inconsistent indent width at line %q", line) messages = append(messages, indent+m) correctionNeeded = true } if correctionNeeded { mult := int(math.Round(float64(len(currIndent)) / float64(len(indent)))) outline[i] = strings.Repeat(indent, mult) + line[lc-lc2:] } } } } levels := make([]int, len(outline)) levels[0] = 1 margin := "" for level := 1; ; level++ { allPos := true for i := 1; i < len(levels); i++ { if levels[i] == 0 { allPos = false break } } if allPos { break } mc := len(margin) for i := 1; i < len(outline); i++ { if levels[i] == 0 { line := outline[i] if strings.HasPrefix(line, margin) && line[mc] != ' ' && line[mc] != '\t' { levels[i] = level } } } margin += indent } lines := make([]string, len(outline)) lines[0] = outline[0] var nodes []string for i := 1; i < len(outline); i++ { if levels[i] > levels[i-1] { if len(nodes) == 0 { nodes = append(nodes, outline[i-1]) } else { nodes = append(nodes, sep+outline[i-1]) } } else if levels[i] < levels[i-1] { j := levels[i-1] - levels[i] nodes = nodes[0 : len(nodes)-j] } if len(nodes) > 0 { lines[i] = strings.Join(nodes, "") + sep + outline[i] } else { lines[i] = outline[i] } } if ascending { sort.Strings(lines) } else { maxLen := len(lines[0]) for i := 1; i < len(lines); i++ { if len(lines[i]) > maxLen { maxLen = len(lines[i]) } } for i := 0; i < len(lines); i++ { lines[i] = lines[i] + strings.Repeat(del, maxLen-len(lines[i])) } sort.Sort(sort.Reverse(sort.StringSlice(lines))) } for i := 0; i < len(lines); i++ { s := strings.Split(lines[i], sep) lines[i] = s[len(s)-1] if !ascending { lines[i] = strings.TrimRight(lines[i], del) } } if len(messages) > 0 { fmt.Println(strings.Join(messages, "\n")) fmt.Println() } fmt.Println(strings.Join(lines, "\n"))
}
func main() {
outline := []string{ "zeta", " beta", " gamma", " lambda", " kappa", " mu", " delta", "alpha", " theta", " iota", " epsilon", }
outline2 := make([]string, len(outline)) for i := 0; i < len(outline); i++ { outline2[i] = strings.ReplaceAll(outline[i], " ", "\t") }
outline3 := []string{ "alpha", " epsilon", " iota", " theta", "zeta", " beta", " delta", " gamma", " \t kappa", // same length but \t instead of space " lambda", " mu", }
outline4 := []string{ "zeta", " beta", " gamma", " lambda", " kappa", " mu", " delta", "alpha", " theta", " iota", " epsilon", }
fmt.Println("Four space indented outline, ascending sort:") sortedOutline(outline, true)
fmt.Println("\nFour space indented outline, descending sort:") sortedOutline(outline, false)
fmt.Println("\nTab indented outline, ascending sort:") sortedOutline(outline2, true)
fmt.Println("\nTab indented outline, descending sort:") sortedOutline(outline2, false)
fmt.Println("\nFirst unspecified outline, ascending sort:") sortedOutline(outline3, true)
fmt.Println("\nFirst unspecified outline, descending sort:") sortedOutline(outline3, false)
fmt.Println("\nSecond unspecified outline, ascending sort:") sortedOutline(outline4, true)
fmt.Println("\nSecond unspecified outline, descending sort:") sortedOutline(outline4, false)
}</lang>
- Output:
Four space indented outline, ascending sort: alpha epsilon iota theta zeta beta delta gamma kappa lambda mu Four space indented outline, descending sort: zeta gamma mu lambda kappa delta beta alpha theta iota epsilon Tab indented outline, ascending sort: alpha epsilon iota theta zeta beta delta gamma kappa lambda mu Tab indented outline, descending sort: zeta gamma mu lambda kappa delta beta alpha theta iota epsilon First unspecified outline, ascending sort: corrected inconsistent whitespace use at line " \t kappa" alpha epsilon iota theta zeta beta delta gamma kappa lambda mu First unspecified outline, descending sort: corrected inconsistent whitespace use at line " \t kappa" zeta gamma mu lambda kappa delta beta alpha theta epsilon iota Second unspecified outline, ascending sort: corrected inconsistent indent width at line " gamma" corrected inconsistent indent width at line " kappa" alpha epsilon iota theta zeta beta delta gamma kappa lambda mu Second unspecified outline, descending sort: corrected inconsistent indent width at line " gamma" corrected inconsistent indent width at line " kappa" zeta gamma mu lambda kappa delta beta alpha theta iota epsilon
Haskell
<lang haskell>{-# LANGUAGE OverloadedStrings #-}
import Data.Tree (Tree(..), foldTree) import qualified Data.Text.IO as T import qualified Data.Text as T import qualified Data.List as L import Data.Bifunctor (first) import Data.Ord (comparing) import Data.Char (isSpace)
OUTLINE SORTED AT EVERY LEVEL --------------
sortedOutline :: (Tree T.Text -> Tree T.Text -> Ordering)
-> T.Text -> Either T.Text T.Text
sortedOutline cmp outlineText =
let xs = T.lines outlineText in consistentIndentUnit (nonZeroIndents xs) >>= \indentUnit -> let forest = forestFromLineIndents $ indentLevelsFromLines xs sortedForest = subForest $ foldTree (\x xs -> Node x (L.sortBy cmp xs)) (Node "" forest) in Right $ outlineFromForest indentUnit sortedForest
TESTS --------------------------
main :: IO () main =
mapM_ T.putStrLn $ concat $ [ \(comparatorLabel, cmp) -> (\kv -> let section = headedSection (fst kv) comparatorLabel in (either (section . (" -> " <>)) section . sortedOutline cmp . snd) kv) <$> [ ("Four-spaced", spacedOutline) , ("Tabbed", tabbedOutline) , ("First unknown type", confusedOutline) , ("Second unknown type", raggedOutline) ] ] <*> [("(A -> Z)", comparing rootLabel), ("(Z -> A)", flip (comparing rootLabel))]
headedSection :: T.Text -> T.Text -> T.Text -> T.Text headedSection outlineType comparatorName x =
T.concat ["\n", outlineType, " ", comparatorName, ":\n\n", x]
spacedOutline, tabbedOutline, confusedOutline, raggedOutline :: T.Text spacedOutline =
"zeta\n\ \ beta\n\ \ gamma\n\ \ lambda\n\ \ kappa\n\ \ mu\n\ \ delta\n\ \alpha\n\ \ theta\n\ \ iota\n\ \ epsilon"
tabbedOutline =
"zeta\n\ \\tbeta\n\ \\tgamma\n\ \\t\tlambda\n\ \\t\tkappa\n\ \\t\tmu\n\ \\tdelta\n\ \alpha\n\ \\ttheta\n\ \\tiota\n\ \\tepsilon"
confusedOutline =
"zeta\n\ \ beta\n\ \ gamma\n\ \ lambda\n\ \ \t kappa\n\ \ mu\n\ \ delta\n\ \alpha\n\ \ theta\n\ \ iota\n\ \ epsilon"
raggedOutline =
"zeta\n\ \ beta\n\ \ gamma\n\ \ lambda\n\ \ kappa\n\ \ mu\n\ \ delta\n\ \alpha\n\ \ theta\n\ \ iota\n\ \ epsilon"
OUTLINE TREES :: SERIALIZED AND DESERIALIZED ------
forestFromLineIndents :: [(Int, T.Text)] -> [Tree T.Text] forestFromLineIndents = go
where go [] = [] go ((n, s):xs) = Node s (go subOutline) : go rest where (subOutline, rest) = span ((n <) . fst) xs
indentLevelsFromLines :: [T.Text] -> [(Int, T.Text)] indentLevelsFromLines xs = first (`div` indentUnit) <$> pairs
where pairs = first T.length . T.span isSpace <$> xs indentUnit = maybe 1 fst (L.find ((0 <) . fst) pairs)
outlineFromForest :: T.Text -> [Tree T.Text] -> T.Text outlineFromForest tabString forest = T.unlines $ forest >>= go ""
where go indent node = indent <> rootLabel node : (subForest node >>= go (T.append tabString indent))
OUTLINE CHECKING - INDENT CHARACTERS AND WIDTHS -----
consistentIndentUnit :: [T.Text] -> Either T.Text T.Text consistentIndentUnit prefixes = minimumIndent prefixes >>= checked prefixes
where checked xs indentUnit | all ((0 ==) . (`rem` unitLength) . T.length) xs = Right indentUnit | otherwise = Left ("Inconsistent indent depths: " <> T.pack (show (T.length <$> prefixes))) where unitLength = T.length indentUnit
minimumIndent :: [T.Text] -> Either T.Text T.Text minimumIndent prefixes = go $ T.foldr newChar "" $ T.concat prefixes
where newChar c seen | c `L.elem` seen = seen | otherwise = c : seen go cs | 1 < length cs = Left $ "Mixed indent characters used: " <> T.pack (show cs) | otherwise = Right $ L.minimumBy (comparing T.length) prefixes
nonZeroIndents :: [T.Text] -> [T.Text] nonZeroIndents textLines =
[ s | x <- textLines , s <- [T.takeWhile isSpace x] , 0 /= T.length s ]</lang>
- Output:
Four-spaced (A -> Z): alpha epsilon iota theta zeta beta delta gamma kappa lambda mu Tabbed (A -> Z): alpha epsilon iota theta zeta beta delta gamma kappa lambda mu First unknown type (A -> Z): -> Mixed indent characters used: "\t " Second unknown type (A -> Z): -> Inconsistent indent depths: [4,3,8,9,8,4,4,4,4] Four-spaced (Z -> A): zeta gamma mu lambda kappa delta beta alpha theta iota epsilon Tabbed (Z -> A): zeta gamma mu lambda kappa delta beta alpha theta iota epsilon First unknown type (Z -> A): -> Mixed indent characters used: "\t " Second unknown type (Z -> A): -> Inconsistent indent depths: [4,3,8,9,8,4,4,4,4]
Julia
A for
loop was used in the constructor, and recursive functions for sorting and printing.
<lang julia>import Base.print
abstract type Entry end
mutable struct OutlineEntry <: Entry
level::Int text::String parent::Union{Entry, Nothing} children::Vector{Entry}
end
mutable struct Outline
root::OutlineEntry entries::Vector{OutlineEntry} baseindent::String
end
rootentry() = OutlineEntry(0, "", nothing, []) indentchar(ch) = ch == ' ' || ch == '\t' firsttext(s) = something(findfirst(!indentchar, s), length(s) + 1) splitline(s) = begin i = firsttext(s); i == 1 ? ("", s) : (s[1:i-1], s[i:end]) end
const _indents = [" "]
function Base.print(io::IO, oe::OutlineEntry)
println(io, _indents[end]^oe.level, oe.text) for child in oe.children print(io, child) end
end
function Base.print(io::IO, o::Outline)
push!(_indents, o.baseindent) print(io, o.root) pop!(_indents)
end
function firstindent(lines, default = " ")
for lin in lines s1, s2 = splitline(lin) s1 != "" && return s1 end return default
end
function Outline(str::String)
arr, lines = OutlineEntry[], filter(x -> x != "", split(str, r"\r\n|\n|\r")) root, indent, parentindex, lastindents = rootentry(), firstindent(lines), 0, 0 if ' ' in indent && '\t' in indent throw("Mixed tabs and spaces in indent are not allowed") end indentlen, indentregex = length(indent), Regex(indent) for (i, lin) in enumerate(lines) header, txt = splitline(lin) indentcount = length(collect(eachmatch(indentregex, header))) (indentcount * indentlen < length(header)) && throw("Error: bad indent " * string(UInt8.([c for c in header])) * ", expected " * string(UInt8.([c for c in indent]))) if indentcount > lastindents parentindex = i - 1 elseif indentcount < lastindents parentindex = something(findlast(x -> x.level == indentcount - 1, arr), 0) end lastindents = indentcount ent = OutlineEntry(indentcount, txt, parentindex == 0 ? root : arr[parentindex], []) push!(ent.parent.children, ent) push!(arr, ent) end return Outline(root, arr, indent)
end
function sorttree!(ent::OutlineEntry, rev=false, level=0)
for child in ent.children sorttree!(child, rev) end if level == 0 || level == ent.level sort!(ent.children, lt=(x, y) -> x.text < y.text, rev=rev) end return ent
end
outlinesort!(ol::Outline, rev=false, lev=0) = begin sorttree!(ol.root, rev, lev); ol end
const outline4s = Outline(""" zeta
beta gamma lambda kappa mu delta
alpha
theta iota epsilon""")
const outlinet1 = Outline(""" zeta
gamma mu lambda kappa delta beta
alpha
theta iota epsilon""")
println("Given the text:\n", outline4s) println("Sorted outline is:\n", outlinesort!(outline4s)) println("Reverse sorted is:\n", outlinesort!(outline4s, true))
println("Using the text:\n", outlinet1) println("Sorted outline is:\n", outlinesort!(outlinet1)) println("Reverse sorted is:\n", outlinesort!(outlinet1, true)) println("Sorting only third level:\n", outlinesort!(outlinet1, false, 3))
try
println("Trying to parse a bad outline:") outlinebad1 = Outline("""
alpha
epsilon
iota
theta
zeta
beta delta gamma kappa lambda mu""")
catch y
println(y)
end
try
println("Trying to parse another bad outline:") outlinebad2 = Outline("""
zeta
beta gamma lambda kappa mu delta
alpha
theta iota epsilon""")
catch y
println(y)
end
</lang>
- Output:
Given the text: zeta beta gamma lambda kappa mu delta alpha theta iota epsilon Sorted outline is: alpha epsilon iota theta zeta beta delta gamma kappa lambda mu Reverse sorted is: zeta gamma mu lambda kappa delta beta alpha theta iota epsilon Using the text: zeta gamma mu lambda kappa delta beta alpha theta iota epsilon Sorted outline is: alpha epsilon iota theta zeta beta delta gamma kappa lambda mu Reverse sorted is: zeta gamma mu lambda kappa delta beta alpha theta iota epsilon Sorting only third level: zeta beta delta gamma kappa lambda mu alpha epsilon iota theta Trying to parse a bad outline: Error: bad indent UInt8[0x09], expected UInt8[0x20, 0x20, 0x20, 0x20] Trying to parse another bad outline: Error: bad indent UInt8[0x20, 0x20, 0x20], expected UInt8[0x20, 0x20, 0x20, 0x20]
Nim
There are several differences between the Julia original and our transcription. Most are due to the fact that Nim way to do some things is different of the Julia way to do it.
<lang Nim>import algorithm, sequtils, strformat, strutils
type
OutlineEntry = ref object level: Natural text: string parent: OutlineEntry children: seq[OutlineEntry]
Outline = object root: OutlineEntry baseIndent: string
proc splitLine(line: string): (string, string) =
for i, ch in line: if ch notin {' ', '\t'}: return (line[0..<i], line[i..^1]) result = (line, "")
proc firstIndent(lines: seq[string]; default = " "): string =
for line in lines: result = line.splitLine()[0] if result.len != 0: return result = default
proc parent(arr: seq[OutlineEntry]; parentLevel: Natural): int =
for i in countdown(arr.high, 0): if arr[i].level == parentLevel: return i
proc initOutline(str: string): Outline =
let root = OutlineEntry() var arr = @[root] # Outline entry at level 0 is root. let lines = str.splitLines().filterIt(it.len != 0) let indent = lines.firstIndent() var parentIndex = 0 var lastIndents = 0
if ' ' in indent and '\t' in indent: raise newException(ValueError, "Mixed tabs and spaces in indent are not allowed")
let indentLen = indent.len
for i, line in lines: let (header, txt) = line.splitLine() let indentCount = header.count(indent) if indentCount * indentLen != header.len: raise newException( ValueError, &"Error: bad indent 0x{header.toHex}, expected 0x{indent.toHex}") if indentCount > lastIndents: parentIndex = i elif indentCount < lastIndents: parentIndex = arr.parent(indentCount) lastIndents = indentCount let entry = OutlineEntry(level: indentCount + 1, text: txt, parent: arr[parentIndex]) entry.parent.children.add entry arr.add entry
result = Outline(root: root, baseIndent: indent)
proc sort(entry: OutlineEntry; order = Ascending; level = 0) =
## Sort an outline entry in place. for child in entry.children.mitems: child.sort(order) if level == 0 or level == entry.level: entry.children.sort(proc(x, y: OutlineEntry): int = cmp(x.text, y.text), order)
proc sort(outline: var Outline; order = Ascending; level = 0) =
## Sort an outline. outline.root.sort(order, level)
proc `$`(outline: Outline): string =
## Return the string representation of an outline.
proc `$`(entry: OutlineEntry): string = ## Return the string representation of an outline entry. result = repeat(outline.baseIndent, entry.level) & entry.text & '\n' for child in entry.children: result.add $child
result = $outline.root
var outline4s = initOutline("""
zeta
beta gamma lambda kappa mu delta
alpha
theta iota epsilon""")
var outlinet1 = initOutline(""" zeta
gamma mu lambda kappa delta beta
alpha
theta iota epsilon""")
echo "Given the text:\n", outline4s outline4s.sort() echo "Sorted outline is:\n", outline4s outline4s.sort(Descending) echo "Reverse sorted is:\n", outline4s
echo "Using the text:\n", outlinet1 outlinet1.sort() echo "Sorted outline is:\n", outlinet1 outlinet1.sort(Descending) echo "Reverse sorted is:\n", outlinet1 outlinet1.sort(level = 3) echo "Sorting only third level:\n", outlinet1
try:
echo "Trying to parse a bad outline:" var outlinebad1 = initOutline("""
alpha
epsilon
iota
theta
zeta
beta delta gamma kappa lambda mu""")
except ValueError:
echo getCurrentExceptionMsg()
try:
echo "Trying to parse another bad outline:" var outlinebad2 = initOutline("""
zeta
beta gamma lambda kappa mu delta
alpha
theta iota epsilon""")
except ValueError:
echo getCurrentExceptionMsg()</lang>
- Output:
Given the text: zeta beta gamma lambda kappa mu delta alpha theta iota epsilon Sorted outline is: alpha epsilon iota theta zeta beta delta gamma kappa lambda mu Reverse sorted is: zeta gamma mu lambda kappa delta beta alpha theta iota epsilon Using the text: zeta gamma mu lambda kappa delta beta alpha theta iota epsilon Sorted outline is: alpha epsilon iota theta zeta beta delta gamma kappa lambda mu Reverse sorted is: zeta gamma mu lambda kappa delta beta alpha theta iota epsilon Sorting only third level: zeta beta delta gamma kappa lambda mu alpha epsilon iota theta Trying to parse a bad outline: Error: bad indent 0x09, expected 0x20202020 Trying to parse another bad outline: Error: bad indent 0x202020, expected 0x20202020
Perl
<lang perl>#!/usr/bin/perl
use strict; # https://rosettacode.org/wiki/Sort_an_outline_at_every_level use warnings;
for my $test ( split /^(?=#)/m, join , )
{ my ( $id, $outline ) = $test =~ /(\V*?\n)(.*)/s; my $sorted = validateandsort( $outline, $id =~ /descend/ ); print $test, '=' x 20, " answer:\n$sorted\n"; }
sub validateandsort
{ my ($outline, $descend) = @_; $outline =~ /^\h*(?: \t|\t )/m and return "ERROR: mixed tab and space indentaion\n"; my $adjust = 0; $adjust++ while $outline =~ s/^(\h*)\H.*\n\1\K\h(?=\H)//m or $outline =~ s/^(\h*)(\h)\H.*\n\1\K(?=\H)/$2/m; $adjust and print "WARNING: adjusting indentation on some lines\n"; return levelsort($outline, $descend); }
sub levelsort # outline_section, descend_flag
{ my ($section, $descend) = @_; my @parts; while( $section =~ / ((\h*) .*\n) ( (?:\2\h.*\n)* )/gx ) { my ($head, $rest) = ($1, $3); push @parts, $head . ( $rest and levelsort($rest, $descend) ); } join , $descend ? reverse sort @parts : sort @parts; }
__DATA__
- 4 space ascending
zeta
beta gamma lambda kappa mu delta
alpha
theta iota epsilon
- 4 space descending
zeta
beta gamma lambda kappa mu delta
alpha
theta iota epsilon
- mixed tab and space
alpha
epsilon iota theta
zeta
beta delta gamma kappa lambda mu
- off alignment
zeta
beta gamma lambda kappa mu delta
alpha
theta iota epsilon</lang>
- Output:
# 4 space ascending zeta beta gamma lambda kappa mu delta alpha theta iota epsilon ==================== answer: alpha epsilon iota theta zeta beta delta gamma kappa lambda mu # 4 space descending zeta beta gamma lambda kappa mu delta alpha theta iota epsilon ==================== answer: zeta gamma mu lambda kappa delta beta alpha theta iota epsilon # mixed tab and space alpha epsilon iota theta zeta beta delta gamma kappa lambda mu ==================== answer: ERROR: mixed tab and space indentaion WARNING: adjusting indentation on some lines # off alignment zeta beta gamma lambda kappa mu delta alpha theta iota epsilon ==================== answer: alpha epsilon iota theta zeta beta delta gamma kappa lambda mu
Phix
procedure print_children(sequence lines, children, string indent, bool bRev) sequence tags = custom_sort(lines,children) if bRev then tags = reverse(tags) end if for i=1 to length(tags) do integer ti = tags[i] printf(1,"%s%s\n",{indent,lines[ti][1]}) print_children(lines,lines[ti][$],lines[ti][2],bRev) end for end procedure constant spaced = """ zeta beta gamma lambda kappa mu delta alpha theta iota epsilon """, tabbed = substitute(spaced," ","\t"), confused = substitute_all(spaced,{" gamma"," kappa"},{"gamma","\t kappa"}), ragged = substitute_all(spaced,{" gamma","kappa"},{"gamma"," kappa"}), tests = {spaced,tabbed,confused,ragged}, names = "spaced,tabbed,confused,ragged" procedure test(sequence lines) sequence pi = {-1}, -- indents (to locate parents) pdx = {0}, -- indexes for "" children = {}, roots = {} for i=1 to length(lines) do string line = trim_tail(lines[i]), text = trim_head(line) integer indent = length(line)-length(text) -- remove any completed parents while length(pi) and indent<=pi[$] do pi = pi[1..$-1] pdx = pdx[1..$-1] end while integer parent = 0 if length(pi) then parent = pdx[$] if parent=0 then if indent!=0 then printf(1,"**invalid indent** (%s, line %d)\n\n",{text,i}) return end if roots &= i else if lines[parent][$]={} then lines[parent][2] = line[1..indent] elsif lines[parent][2]!=line[1..indent] then printf(1,"**inconsistent indent** (%s, line %d)\n\n",{text,i}) return end if lines[parent][$] &= i -- (update children) end if end if pi &= indent pdx &= i lines[i] = {text,"",children} end for printf(1,"ascending:\n") print_children(lines,roots,"",false) printf(1,"\ndescending:\n") print_children(lines,roots,"",true) printf(1,"\n") end procedure for t=1 to length(tests) do string name = split(names,",")[t] -- printf(1,"Test %d (%s):\n%s\n",{t,name,tests[t]}) printf(1,"Test %d (%s):\n",{t,name}) sequence lines = split(tests[t],"\n",no_empty:=true) test(lines) end for
- Output:
Test 1 (spaced): ascending: alpha epsilon iota theta zeta beta delta gamma kappa lambda mu descending: zeta gamma mu lambda kappa delta beta alpha theta iota epsilon Test 2 (tabbed): ascending: alpha epsilon iota theta zeta beta delta gamma kappa lambda mu descending: zeta gamma mu lambda kappa delta beta alpha theta iota epsilon Test 3 (confused): **inconsistent indent** (gamma, line 3) Test 4 (ragged): **inconsistent indent** (gamma, line 3)
Python
<lang python>Sort an outline at every level
from itertools import chain, product, takewhile, tee
from functools import cmp_to_key, reduce
- ------------- OUTLINE SORTED AT EVERY LEVEL --------------
- sortedOutline :: (Tree String -> Tree String -> Ordering)
- -> String
- -> Either String String
def sortedOutline(cmp):
Either a message reporting inconsistent indentation, or an outline sorted at every level by the supplied comparator function. def go(outlineText): indentTuples = indentTextPairs( outlineText.splitlines() ) return bindLR( minimumIndent(enumerate(indentTuples)) )(lambda unitIndent: Right( outlineFromForest( unitIndent, nest(foldTree( lambda x: lambda xs: Node(x)( sorted(xs, key=cmp_to_key(cmp)) ) )(Node()( forestFromIndentLevels( indentLevelsFromLines( unitIndent )(indentTuples) ) ))) ) )) return go
- -------------------------- TEST --------------------------
- main :: IO ()
def main():
Ascending and descending sorts attempted on space-indented and tab-indented outlines, both well-formed and ill-formed.
ascending = comparing(root) descending = flip(ascending)
spacedOutline =
zeta
beta gamma lambda kappa mu delta
alpha
theta iota epsilon
tabbedOutline =
zeta beta gamma lambda kappa mu delta alpha theta iota epsilon
confusedOutline =
alpha
epsilon
iota
theta
zeta
beta delta gamma kappa lambda mu
raggedOutline =
zeta
beta gamma lambda kappa mu delta
alpha
theta iota epsilon
def displaySort(kcmp): Sort function output with labelled comparator for a set of four labelled outlines. k, cmp = kcmp return [ tested(cmp, k, label)( outline ) for (label, outline) in [ ('4-space indented', spacedOutline), ('tab indented', tabbedOutline), ('Unknown 1', confusedOutline), ('Unknown 2', raggedOutline) ] ]
def tested(cmp, cmpName, outlineName): Print either message or result. def go(outline): print('\n' + outlineName, cmpName + ':') either(print)(print)( sortedOutline(cmp)(outline) ) return go
# Tests applied to two comparators: ap([ displaySort ])([ ("(A -> Z)", ascending), ("(Z -> A)", descending) ])
- ------------- OUTLINE PARSING AND RENDERING --------------
- forestFromIndentLevels :: [(Int, a)] -> [Tree a]
def forestFromIndentLevels(tuples):
A list of trees derived from a list of values paired with integers giving their levels of indentation. def go(xs): if xs: intIndent, v = xs[0] firstTreeLines, rest = span( lambda x: intIndent < x[0] )(xs[1:]) return [Node(v)(go(firstTreeLines))] + go(rest) else: return [] return go(tuples)
- indentLevelsFromLines :: String -> [(String, String)]
- -> [(Int, String)]
def indentLevelsFromLines(indentUnit):
Each input line stripped of leading white space, and tupled with a preceding integer giving its level of indentation from 0 upwards. def go(xs): w = len(indentUnit) return [ (len(x[0]) // w, x[1]) for x in xs ] return go
- indentTextPairs :: [String] -> (String, String)
def indentTextPairs(xs):
A list of (indent, bodyText) pairs. def indentAndText(s): pfx = list(takewhile(lambda c: c.isspace(), s)) return (pfx, s[len(pfx):]) return [indentAndText(x) for x in xs]
- outlineFromForest :: String -> [Tree String] -> String
def outlineFromForest(tabString, forest):
An indented outline serialisation of forest, using tabString as the unit of indentation. def go(indent): def serial(node): return [indent + root(node)] + list( concatMap( go(tabString + indent) )(nest(node)) ) return serial return '\n'.join( concatMap(go())(forest) )
- --------------- MINIMUM INDENT, OR ANOMALY ---------------
- minimumIndent :: [(Int, [Char])]
- -> Either String String
def minimumIndent(indexedPrefixes):
Either a message, if indentation characters are mixed, or indentation widths are inconsistent, or the smallest consistent non-empty indentation. (xs, ts) = tee(indexedPrefixes) (ys, zs) = tee(ts)
def mindentLR(charSet): if list(charSet): def w(x): return len(x[1][0])
unit = min(filter(w, ys), key=w)[1][0] unitWidth = len(unit)
def widthCheck(a, ix): Is there a line number at which an anomalous indent width is seen? wx = len(ix[1][0]) return a if (a or 0 == wx) else ( ix[0] if 0 != wx % unitWidth else a ) oddLine = reduce(widthCheck, zs, None) return Left( 'Inconsistent indentation width at line ' + ( str(1 + oddLine) ) ) if oddLine else Right(.join(unit)) else: return Right()
def tabSpaceCheck(a, ics): Is there a line number at which a variant indent character is used? charSet = a[0].union(set(ics[1][0])) return a if a[1] else ( charSet, ics[0] if 1 < len(charSet) else None )
indentCharSet, mbAnomalyLine = reduce( tabSpaceCheck, xs, (set([]), None) ) return bindLR( Left( 'Mixed indent characters found in line ' + str( 1 + mbAnomalyLine ) ) if mbAnomalyLine else Right(list(indentCharSet)) )(mindentLR)
- ------------------------ GENERIC -------------------------
- Left :: a -> Either a b
def Left(x):
Constructor for an empty Either (option type) value with an associated string. return {'type': 'Either', 'Right': None, 'Left': x}
- Right :: b -> Either a b
def Right(x):
Constructor for a populated Either (option type) value return {'type': 'Either', 'Left': None, 'Right': x}
- Node :: a -> [Tree a] -> Tree a
def Node(v):
Constructor for a Tree node which connects a value of some kind to a list of zero or more child trees. return lambda xs: {'type': 'Tree', 'root': v, 'nest': xs}
- ap (<*>) :: [(a -> b)] -> [a] -> [b]
def ap(fs):
The application of each of a list of functions, to each of a list of values. def go(xs): return [ f(x) for (f, x) in product(fs, xs) ] return go
- bindLR (>>=) :: Either a -> (a -> Either b) -> Either b
def bindLR(m):
Either monad injection operator. Two computations sequentially composed, with any value produced by the first passed as an argument to the second. def go(mf): return ( mf(m.get('Right')) if None is m.get('Left') else m ) return go
- comparing :: (a -> b) -> (a -> a -> Ordering)
def comparing(f):
An ordering function based on a property accessor f. def go(x, y): fx = f(x) fy = f(y) return -1 if fx < fy else (1 if fx > fy else 0) return go
- concatMap :: (a -> [b]) -> [a] -> [b]
def concatMap(f):
A concatenated list over which a function has been mapped. The list monad can be derived by using a function f which wraps its output in a list, (using an empty list to represent computational failure). def go(xs): return chain.from_iterable(map(f, xs)) return go
- either :: (a -> c) -> (b -> c) -> Either a b -> c
def either(fl):
The application of fl to e if e is a Left value, or the application of fr to e if e is a Right value. return lambda fr: lambda e: fl(e['Left']) if ( None is e['Right'] ) else fr(e['Right'])
- flip :: (a -> b -> c) -> b -> a -> c
def flip(f):
The binary function f with its arguments reversed. return lambda a, b: f(b, a)
- foldTree :: (a -> [b] -> b) -> Tree a -> b
def foldTree(f):
The catamorphism on trees. A summary value defined by a depth-first fold. def go(node): return f(root(node))([ go(x) for x in nest(node) ]) return go
- nest :: Tree a -> [Tree a]
def nest(t):
Accessor function for children of tree node. return t.get('nest')
- root :: Tree a -> a
def root(t):
Accessor function for data of tree node. return t.get('root')
- span :: (a -> Bool) -> [a] -> ([a], [a])
def span(p):
The longest (possibly empty) prefix of xs that contains only elements satisfying p, tupled with the remainder of xs. span p xs is equivalent to (takeWhile p xs, dropWhile p xs). def match(ab): b = ab[1] return not b or not p(b[0])
def f(ab): a, b = ab return a + [b[0]], b[1:]
def go(xs): return until(match)(f)(([], xs)) return go
- until :: (a -> Bool) -> (a -> a) -> a -> a
def until(p):
The result of repeatedly applying f until p holds. The initial seed value is x. def go(f): def g(x): v = x while not p(v): v = f(v) return v return g return go
- MAIN ---
if __name__ == '__main__':
main()</lang>
- Output:
4-space indented (A -> Z): alpha epsilon iota theta zeta beta delta gamma kappa lambda mu tab indented (A -> Z): alpha epsilon iota theta zeta beta delta gamma kappa lambda mu Unknown 1 (A -> Z): Mixed indent characters found in line 4 Unknown 2 (A -> Z): Inconsistent indentation width at line 3 4-space indented (Z -> A): zeta gamma mu lambda kappa delta beta alpha theta iota epsilon tab indented (Z -> A): zeta gamma mu lambda kappa delta beta alpha theta iota epsilon Unknown 1 (Z -> A): Mixed indent characters found in line 4 Unknown 2 (Z -> A): Inconsistent indentation width at line 3
Wren
<lang ecmascript>import "/sort" for Sort import "/fmt" for Fmt
var sortedOutline = Fn.new { |originalOutline, ascending|
var outline = originalOutline.toList // make copy in case we mutate it var indent = "" var del = "\x7f" var sep = "\0" var messages = [] if (outline[0].trimStart(" \t") != outline[0]) { System.print(" outline structure is unclear") return } for (i in 1...outline.count) { var line = outline[i] var lc = line.count if (line.startsWith(" ") || line.startsWith(" \t") || line.startsWith("\t")) { var lc2 = line.trimStart(" \t").count var currIndent = line[0...lc-lc2] if (indent == "") { indent = currIndent } else { var correctionNeeded = false if ((currIndent.contains("\t") && !indent.contains("\t")) || (!currIndent.contains("\t") && indent.contains("\t"))) { messages.add(indent + "corrected inconsistent whitespace use at line '%(line)'") correctionNeeded = true } else if (currIndent.count % indent.count != 0) { messages.add(indent + "corrected inconsistent indent width at line '%(line)'") correctionNeeded = true } if (correctionNeeded) { var mult = (currIndent.count / indent.count).round outline[i] = (indent * mult) + line[lc-lc2..-1] } } } } var levels = List.filled(outline.count, 0) levels[0] = 1 var level = 1 var margin = "" while (!levels.all { |l| l > 0 }) { var mc = margin.count for (i in 1...outline.count) { if (levels[i] == 0) { var line = outline[i] if (line.startsWith(margin) && line[mc] != " " && line[mc] != "\t") levels[i] = level } } margin = margin + indent level = level + 1 } var lines = List.filled(outline.count, "") lines[0] = outline[0] var nodes = [] for (i in 1...outline.count) { if (levels[i] > levels[i-1]) { nodes.add((nodes.count == 0) ? outline[i - 1] : sep + outline[i-1]) } else if (levels[i] < levels[i-1]) { var j = levels[i-1] - levels[i] for (k in 1..j) nodes.removeAt(-1) } if (nodes.count > 0) { lines[i] = nodes.join() + sep + outline[i] } else { lines[i] = outline[i] } } if (ascending) { Sort.insertion(lines) } else { var maxLen = lines.reduce(0) { |max, l| (l.count > max) ? l.count : max } for (i in 0...lines.count) lines[i] = Fmt.ljust(maxLen, lines[i], del) Sort.insertion(lines, true) } for (i in 0...lines.count) { var s = lines[i].split(sep) lines[i] = s[-1] if (!ascending) lines[i] = lines[i].trimEnd(del) } if (messages.count > 0) { System.print(messages.join("\n")) System.print() } System.print(lines.join("\n"))
}
var outline = [
"zeta", " beta", " gamma", " lambda", " kappa", " mu", " delta", "alpha", " theta", " iota", " epsilon"
]
var outline2 = outline.map { |s| s.replace(" ", "\t") }.toList
var outline3 = [
"alpha", " epsilon",
" iota",
" theta", "zeta", " beta", " delta", " gamma", " \t kappa", // same length but \t instead of space " lambda", " mu"
]
var outline4 = [
"zeta", " beta", " gamma", " lambda", " kappa", " mu", " delta", "alpha", " theta", " iota", " epsilon"
]
System.print("Four space indented outline, ascending sort:") sortedOutline.call(outline, true)
System.print("\nFour space indented outline, descending sort:") sortedOutline.call(outline, false)
System.print("\nTab indented outline, ascending sort:") sortedOutline.call(outline2, true)
System.print("\nTab indented outline, descending sort:") sortedOutline.call(outline2, false)
System.print("\nFirst unspecified outline, ascending sort:") sortedOutline.call(outline3, true)
System.print("\nFirst unspecified outline, descending sort:") sortedOutline.call(outline3, false)
System.print("\nSecond unspecified outline, ascending sort:") sortedOutline.call(outline4, true)
System.print("\nSecond unspecified outline, descending sort:") sortedOutline.call(outline4, false)</lang>
- Output:
Four space indented outline, ascending sort: alpha epsilon iota theta zeta beta delta gamma kappa lambda mu Four space indented outline, descending sort: zeta gamma mu lambda kappa delta beta alpha theta iota epsilon Tab indented outline, ascending sort: alpha epsilon iota theta zeta beta delta gamma kappa lambda mu Tab indented outline, descending sort: zeta gamma mu lambda kappa delta beta alpha theta iota epsilon First unspecified outline, ascending sort: corrected inconsistent whitespace use at line ' kappa' alpha epsilon iota theta zeta beta delta gamma kappa lambda mu First unspecified outline, descending sort: corrected inconsistent whitespace use at line ' kappa' zeta gamma mu lambda kappa delta beta alpha theta epsilon iota Second unspecified outline, ascending sort: corrected inconsistent indent width at line ' gamma' corrected inconsistent indent width at line ' kappa' alpha epsilon iota theta zeta beta delta gamma kappa lambda mu Second unspecified outline, descending sort: corrected inconsistent indent width at line ' gamma' corrected inconsistent indent width at line ' kappa' zeta gamma mu lambda kappa delta beta alpha theta iota epsilon