Rosetta Code

Sorting algorithms/Tree sort on a linked list: Difference between revisions

Page Discussion

Sorting algorithms/Tree sort on a linked list (view source)

Revision as of 17:05, 15 May 2021

25,479 bytes added ,  3 years ago
m
→‎{{header|Phix}}: added syntax colouring the hard way
(Added Wren)
m (→‎{{header|Phix}}: added syntax colouring the hard way)
Line 571:
=={{header|Phix}}==
{{trans|Kotlin}}
<!--<lang Phix>enum KEY,LEFT,RIGHT(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
function tree_insert(object node, item)
if node=NULL then
node = {item,NULL,NULL}
elsif item<node[KEY] then
node[LEFT] = tree_insert(node[LEFT],item)
else
node[RIGHT] = tree_insert(node[RIGHT],item)
end if
return node
end function
 
function inOrder(object node)
sequence res = {}
if node!=NULL then
res = inOrder(node[LEFT])
res &= node[KEY]
res &= inOrder(node[RIGHT])
end if
return res
end function
procedure treeSort(sequence s)
object tree = NULL
for i=1 to length(s) do tree = tree_insert(tree,s[i]) end for
pp({s," => ",inOrder(tree)})
end procedure
<span style="color: #008080;">enum</span> <span style="color: #000000;">KEY</span><span style="color: #0000FF;">,</span><span style="color: #000000;">LEFT</span><span style="color: #0000FF;">,</span><span style="color: #000000;">RIGHT</span>
treeSort({5, 3, 7, 9, 1})
<span style="color: #008080;">function</span> <span style="color: #000000;">tree_insert</span><span style="color: #0000FF;">(</span><span style="color: #004080;">object</span> <span style="color: #000000;">node</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">item</span><span style="color: #0000FF;">)</span>
treeSort("dceba")</lang>
<span style="color: #008080;">if</span> <span style="color: #000000;">node</span><span style="color: #0000FF;">=</span><span style="color: #004600;">NULL</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">node</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">item</span><span style="color: #0000FF;">,</span><span style="color: #004600;">NULL</span><span style="color: #0000FF;">,</span><span style="color: #004600;">NULL</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">node</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">node</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (one level only needed)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">item</span><span style="color: #0000FF;"><</span><span style="color: #000000;">node</span><span style="color: #0000FF;">[</span><span style="color: #000000;">KEY</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">node</span><span style="color: #0000FF;">[</span><span style="color: #000000;">LEFT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tree_insert</span><span style="color: #0000FF;">(</span><span style="color: #000000;">node</span><span style="color: #0000FF;">[</span><span style="color: #000000;">LEFT</span><span style="color: #0000FF;">],</span><span style="color: #000000;">item</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">node</span><span style="color: #0000FF;">[</span><span style="color: #000000;">RIGHT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tree_insert</span><span style="color: #0000FF;">(</span><span style="color: #000000;">node</span><span style="color: #0000FF;">[</span><span style="color: #000000;">RIGHT</span><span style="color: #0000FF;">],</span><span style="color: #000000;">item</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">node</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">inOrder</span><span style="color: #0000FF;">(</span><span style="color: #004080;">object</span> <span style="color: #000000;">node</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">node</span><span style="color: #0000FF;">!=</span><span style="color: #004600;">NULL</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">inOrder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">node</span><span style="color: #0000FF;">[</span><span style="color: #000000;">LEFT</span><span style="color: #0000FF;">])</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">node</span><span style="color: #0000FF;">[</span><span style="color: #000000;">KEY</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">inOrder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">node</span><span style="color: #0000FF;">[</span><span style="color: #000000;">RIGHT</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">treeSort</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">object</span> <span style="color: #000000;">tree</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">NULL</span>
<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;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> <span style="color: #000000;">tree</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tree_insert</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tree</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">pp</span><span style="color: #0000FF;">({</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" =&gt; "</span><span style="color: #0000FF;">,</span><span style="color: #000000;">inOrder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tree</span><span style="color: #0000FF;">)})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">treeSort</span><span style="color: #0000FF;">({</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">7</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">9</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">})</span>
<span style="color: #000000;">treeSort</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"dceba"</span><span style="color: #0000FF;">)</span>
<!--</lang>-->
{{out}}
<pre>
Line 609 ⟶ 616:
=== version 2 ===
Following my idea of a revised task description, see talk page.
<!--<lang Phix>(phixonline)-- doubly linked list:>
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
enum NEXT,PREV,DATA
constant empty_dll = {{1,1}}
sequence dll
<span style="color: #000080;font-style:italic;">-- doubly linked list:</span>
procedure insert_after(object data, integer pos=1)
<span style="color: #008080;">enum</span> <span style="color: #000000;">NEXT</span><span style="color: #0000FF;">,</span><span style="color: #000000;">PREV</span><span style="color: #0000FF;">,</span><span style="color: #000000;">DATA</span>
integer prv = dll[pos][PREV]
<span style="color: #008080;">constant</span> <span style="color: #000000;">empty_dll</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: #000000;">1</span><span style="color: #0000FF;">}}</span>
dll = append(dll,{pos,prv,data})
<span style="color: #004080;">sequence</span> <span style="color: #000000;">dll</span>
if prv!=0 then
dll[prv][NEXT] = length(dll)
end if
dll[pos][PREV] = length(dll)
end procedure
<span style="color: #008080;">procedure</span> <span style="color: #000000;">insert_after</span><span style="color: #0000FF;">(</span><span style="color: #004080;">object</span> <span style="color: #000000;">data</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">pos</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
procedure append_node(integer node)
<span style="color: #004080;">integer</span> <span style="color: #000000;">prv</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pos</span><span style="color: #0000FF;">][</span><span style="color: #000000;">PREV</span><span style="color: #0000FF;">]</span>
-- (like insert_after, but in situ rebuild)
<span style="color: #000000;">dll</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dll</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">pos</span><span style="color: #0000FF;">,</span><span style="color: #000000;">prv</span><span style="color: #0000FF;">,</span><span style="color: #000000;">data</span><span style="color: #0000FF;">})</span>
integer prev = dll[1][PREV]
<span style="color: #008080;">if</span> <span style="color: #000000;">prv</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
dll[node][NEXT] = 1
<span style="color: #000000;">dll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">prv</span><span style="color: #0000FF;">][</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dll</span><span style="color: #0000FF;">)</span>
dll[node][PREV] = prev
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
dll[prev][NEXT] = node
<span style="color: #000000;">dll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pos</span><span style="color: #0000FF;">][</span><span style="color: #000000;">PREV</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dll</span><span style="color: #0000FF;">)</span>
dll[1][PREV] = node
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
end procedure
 
<span style="color: #008080;">procedure</span> <span style="color: #000000;">append_node</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">node</span><span style="color: #0000FF;">)</span>
function dll_collect()
<span style="color: #000080;font-style:italic;">-- (like insert_after, but in situ rebuild)</span>
sequence res = ""
<span style="color: #004080;">integer</span> <span style="color: #000000;">prev</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">PREV</span><span style="color: #0000FF;">]</span>
integer idx = dll[1][NEXT]
<span style="color: #000000;">dll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">node</span><span style="color: #0000FF;">][</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
while idx!=1 do
<span style="color: #000000;">dll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">node</span><span style="color: #0000FF;">][</span><span style="color: #000000;">PREV</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">prev</span>
res = append(res,dll[idx][DATA])
<span style="color: #000000;">dll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">prev</span><span style="color: #0000FF;">][</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">node</span>
idx = dll[idx][NEXT]
<span style="color: #000000;">dll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">PREV</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">node</span>
end while
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
return res
end function
<span style="color: #008080;">function</span> <span style="color: #000000;">dll_collect</span><span style="color: #0000FF;">()</span>
 
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span>
-- tree:
<span style="color: #004080;">integer</span> <span style="color: #000000;">idx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">]</span>
enum LEFT,RIGHT,KEY
<span style="color: #008080;">while</span> <span style="color: #000000;">idx</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
 
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">dll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">][</span><span style="color: #000000;">DATA</span><span style="color: #0000FF;">])</span>
function tree_insert(integer root, object item, integer idx)
<span style="color: #000000;">idx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">][</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">]</span>
if root=NULL then
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
return idx
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
else
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
integer branch = iff(item<dll[root][KEY]?LEFT:RIGHT)
dll[root][branch] = tree_insert(dll[root][branch],item,idx)
<span style="color: #000080;font-style:italic;">-- tree:</span>
return root
<span style="color: #008080;">enum</span> <span style="color: #000000;">LEFT</span><span style="color: #0000FF;">,</span><span style="color: #000000;">RIGHT</span><span style="color: #0000FF;">,</span><span style="color: #000000;">KEY</span>
end if
end function
<span style="color: #008080;">function</span> <span style="color: #000000;">tree_insert</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">root</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">object</span> <span style="color: #000000;">item</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">idx</span><span style="color: #0000FF;">)</span>
 
<span style="color: #008080;">if</span> <span style="color: #000000;">root</span><span style="color: #0000FF;">=</span><span style="color: #004600;">NULL</span> <span style="color: #008080;">then</span>
procedure traverse(integer node)
<span style="color: #008080;">return</span> <span style="color: #000000;">idx</span>
if node!=NULL then
<span style="color: #008080;">else</span>
traverse(dll[node][LEFT])
<span style="color: #004080;">integer</span> <span style="color: #000000;">branch</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">item</span><span style="color: #0000FF;"><</span><span style="color: #000000;">dll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">root</span><span style="color: #0000FF;">][</span><span style="color: #000000;">KEY</span><span style="color: #0000FF;">]?</span><span style="color: #000000;">LEFT</span><span style="color: #0000FF;">:</span><span style="color: #000000;">RIGHT</span><span style="color: #0000FF;">)</span>
integer right = dll[node][RIGHT]
<span style="color: #000000;">dll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">root</span><span style="color: #0000FF;">][</span><span style="color: #000000;">branch</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tree_insert</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">root</span><span style="color: #0000FF;">][</span><span style="color: #000000;">branch</span><span style="color: #0000FF;">],</span><span style="color: #000000;">item</span><span style="color: #0000FF;">,</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">)</span>
append_node(node)
<span style="color: #008080;">return</span> <span style="color: #000000;">root</span>
traverse(right)
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
end procedure
 
<span style="color: #008080;">procedure</span> <span style="color: #000000;">traverse</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">node</span><span style="color: #0000FF;">)</span>
bool detailed = true
<span style="color: #008080;">if</span> <span style="color: #000000;">node</span><span style="color: #0000FF;">!=</span><span style="color: #004600;">NULL</span> <span style="color: #008080;">then</span>
procedure treeSort()
<span style="color: #000000;">traverse</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">node</span><span style="color: #0000FF;">][</span><span style="color: #000000;">LEFT</span><span style="color: #0000FF;">])</span>
if detailed then
<span style="color: #004080;">integer</span> <span style="color: #000000;">right</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">node</span><span style="color: #0000FF;">][</span><span style="color: #000000;">RIGHT</span><span style="color: #0000FF;">]</span>
?{"initial dll",dll}
<span style="color: #000000;">append_node</span><span style="color: #0000FF;">(</span><span style="color: #000000;">node</span><span style="color: #0000FF;">)</span>
end if
<span style="color: #000000;">traverse</span><span style="color: #0000FF;">(</span><span style="color: #000000;">right</span><span style="color: #0000FF;">)</span>
object tree = NULL
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
integer idx = dll[1][NEXT]
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
while idx!=1 do
integer next = dll[idx][NEXT]
<span style="color: #004080;">bool</span> <span style="color: #000000;">detailed</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>
dll[idx][NEXT] = NULL
<span style="color: #008080;">procedure</span> <span style="color: #000000;">treeSort</span><span style="color: #0000FF;">()</span>
dll[idx][PREV] = NULL
<span style="color: #008080;">if</span> <span style="color: #000000;">detailed</span> <span style="color: #008080;">then</span>
tree = tree_insert(tree,dll[idx][DATA],idx)
<span style="color: #0000FF;">?{</span><span style="color: #008000;">"initial dll"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">dll</span><span style="color: #0000FF;">}</span>
idx = next
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end while
<span style="color: #004080;">integer</span> <span style="color: #000000;">tree</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">NULL</span><span style="color: #0000FF;">,</span>
dll[1] = {tree,0} -- (0 is meaningless, but aligns output)
<span style="color: #000000;">idx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">]</span>
if detailed then
<span style="color: #008080;">while</span> <span style="color: #000000;">idx</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
?{"tree insitu",dll}
<span style="color: #004080;">integer</span> <span style="color: #000000;">next</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">][</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">]</span>
end if
<span style="color: #000000;">dll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">][</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">NULL</span>
dll[1] = empty_dll[1]
<span style="color: #000000;">dll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">][</span><span style="color: #000000;">PREV</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">NULL</span>
traverse(tree)
<span style="color: #000000;">tree</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tree_insert</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tree</span><span style="color: #0000FF;">,</span><span style="color: #000000;">dll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">][</span><span style="color: #000000;">DATA</span><span style="color: #0000FF;">],</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">)</span>
if detailed then
<span style="color: #000000;">idx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">next</span>
?{"rebuilt dll",dll}
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
end if
<span style="color: #000000;">dll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">tree</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}</span> <span style="color: #000080;font-style:italic;">-- (0 is meaningless, but aligns output)</span>
end procedure
<span style="color: #008080;">if</span> <span style="color: #000000;">detailed</span> <span style="color: #008080;">then</span>
<span style="color: #0000FF;">?{</span><span style="color: #008000;">"tree insitu"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">dll</span><span style="color: #0000FF;">}</span>
procedure test(sequence s)
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
dll = empty_dll
<span style="color: #000000;">dll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">empty_dll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span>
for i=1 to length(s) do insert_after(s[i]) end for
<span style="color: #000000;">traverse</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tree</span><span style="color: #0000FF;">)</span>
?{"unsorted",dll_collect()}
<span style="color: #008080;">if</span> <span style="color: #000000;">detailed</span> <span style="color: #008080;">then</span>
treeSort()
<span style="color: #0000FF;">?{</span><span style="color: #008000;">"rebuilt dll"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">dll</span><span style="color: #0000FF;">}</span>
?{"sorted",dll_collect()}
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end procedure
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
 
test({5, 3, 7, 9, 1})
<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;">s</span><span style="color: #0000FF;">)</span>
detailed = false
<span style="color: #000000;">dll</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">empty_dll</span><span style="color: #0000FF;">)</span>
test("dceba")
<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;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> <span style="color: #000000;">insert_after</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
test({"d","c","e","b","a"})</lang>
<span style="color: #0000FF;">?{</span><span style="color: #008000;">"unsorted"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">dll_collect</span><span style="color: #0000FF;">()}</span>
<span style="color: #000000;">treeSort</span><span style="color: #0000FF;">()</span>
<span style="color: #0000FF;">?{</span><span style="color: #008000;">"sorted"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">dll_collect</span><span style="color: #0000FF;">()}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">({</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">7</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">9</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">})</span>
<span style="color: #000000;">detailed</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"dceba"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">({</span><span style="color: #008000;">"d"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"c"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"e"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"b"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"a"</span><span style="color: #0000FF;">})</span>
<!--</lang>-->
{{out}}
<pre>
Petelomax
7,820

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/245174"