Same fringe: Difference between revisions
Content added Content deleted
(C++ entry) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 11: | Line 11: | ||
The package is generic, which allows Data to be essentially of any type. |
The package is generic, which allows Data to be essentially of any type. |
||
< |
<syntaxhighlight lang="ada">generic |
||
type Data is private; |
type Data is private; |
||
package Bin_Trees is |
package Bin_Trees is |
||
Line 36: | Line 36: | ||
end record; |
end record; |
||
end Bin_Trees;</ |
end Bin_Trees;</syntaxhighlight> |
||
The implementation is straightforward. |
The implementation is straightforward. |
||
< |
<syntaxhighlight lang="ada">with Ada.Unchecked_Deallocation; |
||
package body Bin_Trees is |
package body Bin_Trees is |
||
Line 91: | Line 91: | ||
end Tree; |
end Tree; |
||
end Bin_Trees;</ |
end Bin_Trees;</syntaxhighlight> |
||
Next, we specify and implement package that defines a task type for tree traversal. This allows us to run any number of tree traversals in parallel, even on the same tree. |
Next, we specify and implement package that defines a task type for tree traversal. This allows us to run any number of tree traversals in parallel, even on the same tree. |
||
< |
<syntaxhighlight lang="ada"> generic |
||
with procedure Process_Data(Item: Data); |
with procedure Process_Data(Item: Data); |
||
with function Stop return Boolean; |
with function Stop return Boolean; |
||
Line 105: | Line 105: | ||
-- except when Stop becomes true; in this case, the task terminates |
-- except when Stop becomes true; in this case, the task terminates |
||
end Inorder_Task; |
end Inorder_Task; |
||
end Bin_Trees.Traverse;</ |
end Bin_Trees.Traverse;</syntaxhighlight> |
||
< |
<syntaxhighlight lang="ada"> package body Bin_Trees.Traverse is |
||
task body Inorder_Task is |
task body Inorder_Task is |
||
procedure Inorder(Tree: Tree_Type) is |
procedure Inorder(Tree: Tree_Type) is |
||
Line 129: | Line 129: | ||
Finish; |
Finish; |
||
end Inorder_Task; |
end Inorder_Task; |
||
end Bin_Trees.Traverse;</ |
end Bin_Trees.Traverse;</syntaxhighlight> |
||
When comparing two trees T1 and T2, we will define two tasks, a "Producer.Inorder_Task" and a "Consumer.Inorder_Task". The producer will write data items to a buffer, the consumer will read items from the buffer and compare them with its own data items. Both tasks will terminate when the consumer finds a data item different from the one written by the producer, or when either task has written its last item and the other one has items left. |
When comparing two trees T1 and T2, we will define two tasks, a "Producer.Inorder_Task" and a "Consumer.Inorder_Task". The producer will write data items to a buffer, the consumer will read items from the buffer and compare them with its own data items. Both tasks will terminate when the consumer finds a data item different from the one written by the producer, or when either task has written its last item and the other one has items left. |
||
Line 135: | Line 135: | ||
A third auxiliary task just waits until the consumer has finished and the result of the fringe comparison can be read. |
A third auxiliary task just waits until the consumer has finished and the result of the fringe comparison can be read. |
||
< |
<syntaxhighlight lang="ada">with Ada.Text_IO, Bin_Trees.Traverse; |
||
procedure Main is |
procedure Main is |
||
Line 296: | Line 296: | ||
Ada.Text_IO.New_Line; |
Ada.Text_IO.New_Line; |
||
end loop; |
end loop; |
||
end Main;</ |
end Main;</syntaxhighlight> |
||
Note that we do not call Destroy_Tree to reclaim the dynamic memory. In our case, this is not needed since the memory will be reclaimed at the end of Main, anyway. |
Note that we do not call Destroy_Tree to reclaim the dynamic memory. In our case, this is not needed since the memory will be reclaimed at the end of Main, anyway. |
||
Line 315: | Line 315: | ||
=={{header|Bracmat}}== |
=={{header|Bracmat}}== |
||
< |
<syntaxhighlight lang="bracmat">( ( T |
||
= |
= |
||
. ( next |
. ( next |
||
Line 352: | Line 352: | ||
, (((a.b).c).x.y.z) |
, (((a.b).c).x.y.z) |
||
) |
) |
||
);</ |
);</syntaxhighlight> |
||
Output: |
Output: |
||
<pre>x,x |
<pre>x,x |
||
Line 374: | Line 374: | ||
=={{header|C}}== |
=={{header|C}}== |
||
With rudimentary coroutine support based on ucontext. I don't know if it will compile on anything other than GCC. |
With rudimentary coroutine support based on ucontext. I don't know if it will compile on anything other than GCC. |
||
< |
<syntaxhighlight lang="c">#include <stdio.h> |
||
#include <stdlib.h> |
#include <stdlib.h> |
||
#include <ucontext.h> |
#include <ucontext.h> |
||
Line 494: | Line 494: | ||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
=={{header|c sharp|C#}}== |
=={{header|c sharp|C#}}== |
||
This task is almost custom designed for C# LINQ and is really trivial using that. Most of the following is support code. The only two routines that actually implement the task at hand are CompareTo and GetLeaves at the bottom. GetLeaves is a really simple BinTree procedure to retreive the leaves from left to right into an IEnumerable. That IEnumerable can be zipped with the result of GetLeaves on another tree and the results compared giving us our final answer and since everything is deferred in LINQ, this has the desirable property spoken of in the problem's description that no comparisons are done after a non-matching pair. |
This task is almost custom designed for C# LINQ and is really trivial using that. Most of the following is support code. The only two routines that actually implement the task at hand are CompareTo and GetLeaves at the bottom. GetLeaves is a really simple BinTree procedure to retreive the leaves from left to right into an IEnumerable. That IEnumerable can be zipped with the result of GetLeaves on another tree and the results compared giving us our final answer and since everything is deferred in LINQ, this has the desirable property spoken of in the problem's description that no comparisons are done after a non-matching pair. |
||
< |
<syntaxhighlight lang="csharp"> |
||
using System; |
using System; |
||
using System.Collections.Generic; |
using System.Collections.Generic; |
||
Line 633: | Line 633: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
Example output: |
Example output: |
||
Line 643: | Line 643: | ||
=={{header|C++}}== |
=={{header|C++}}== |
||
Walk through the trees using C++20 coroutines. |
Walk through the trees using C++20 coroutines. |
||
< |
<syntaxhighlight lang="cpp">#include <algorithm> |
||
#include <coroutine> |
#include <coroutine> |
||
#include <iostream> |
#include <iostream> |
||
Line 863: | Line 863: | ||
Compare(tree1, tree2); |
Compare(tree1, tree2); |
||
Compare(tree1, tree3); |
Compare(tree1, tree3); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 878: | Line 878: | ||
''children'' returns the children of a branch node; ''content'' returns the content of a branch node. |
''children'' returns the children of a branch node; ''content'' returns the content of a branch node. |
||
A fringe value is either the content of a branch node without children, or a non-branch node. |
A fringe value is either the content of a branch node without children, or a non-branch node. |
||
< |
<syntaxhighlight lang="clojure">(defn fringe-seq [branch? children content tree] |
||
(letfn [(walk [node] |
(letfn [(walk [node] |
||
(lazy-seq |
(lazy-seq |
||
Line 886: | Line 886: | ||
(mapcat walk (children node))) |
(mapcat walk (children node))) |
||
(list node))))] |
(list node))))] |
||
(walk tree)))</ |
(walk tree)))</syntaxhighlight> |
||
For this problem, binary trees are represented as vectors, whose nodes are either [''content'' ''left'' ''right''] or just ''content''. |
For this problem, binary trees are represented as vectors, whose nodes are either [''content'' ''left'' ''right''] or just ''content''. |
||
< |
<syntaxhighlight lang="clojure">(defn vfringe-seq [v] (fringe-seq vector? #(remove nil? (rest %)) first v)) |
||
(println (vfringe-seq [10 1 2])) ; (1 2) |
(println (vfringe-seq [10 1 2])) ; (1 2) |
||
(println (vfringe-seq [10 [1 nil nil] [20 2 nil]])) ; (1 2)</ |
(println (vfringe-seq [10 [1 nil nil] [20 2 nil]])) ; (1 2)</syntaxhighlight> |
||
Then we can use a general sequence-equality function: |
Then we can use a general sequence-equality function: |
||
< |
<syntaxhighlight lang="clojure">(defn seq= [s1 s2] |
||
(cond |
(cond |
||
(and (empty? s1) (empty? s2)) true |
(and (empty? s1) (empty? s2)) true |
||
(not= (empty? s1) (empty? s2)) false |
(not= (empty? s1) (empty? s2)) false |
||
(= (first s1) (first s2)) (recur (rest s1) (rest s2)) |
(= (first s1) (first s2)) (recur (rest s1) (rest s2)) |
||
:else false))</ |
:else false))</syntaxhighlight> |
||
=={{header|D}}== |
=={{header|D}}== |
||
===Short Version=== |
===Short Version=== |
||
A short recursive solution that is not lazy (and lacks the const/immutable/pure/nothrow): |
A short recursive solution that is not lazy (and lacks the const/immutable/pure/nothrow): |
||
< |
<syntaxhighlight lang="d">struct Node(T) { |
||
T data; |
T data; |
||
Node* L, R; |
Node* L, R; |
||
Line 923: | Line 923: | ||
auto t3 = new N(1, new N(2, new N(3, new N(40), new N(51)))); |
auto t3 = new N(1, new N(2, new N(3, new N(40), new N(51)))); |
||
writeln(sameFringe(t1, t3)); |
writeln(sameFringe(t1, t3)); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>true |
<pre>true |
||
Line 930: | Line 930: | ||
===Strong Lazy Version=== |
===Strong Lazy Version=== |
||
This version is quite long because it tries to be reliable. The code contains contracts, unit tests, annotations, and so on. |
This version is quite long because it tries to be reliable. The code contains contracts, unit tests, annotations, and so on. |
||
< |
<syntaxhighlight lang="d">import std.array: empty; |
||
import std.algorithm: equal; |
import std.algorithm: equal; |
||
Line 1,123: | Line 1,123: | ||
writeln("sameFringe(t1, t2): ", sameFringe(t1, t2)); |
writeln("sameFringe(t1, t2): ", sameFringe(t1, t2)); |
||
writeln("sameFringe(t1, t3): ", sameFringe(t1, t3)); |
writeln("sameFringe(t1, t3): ", sameFringe(t1, t3)); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>fringe(t1): [40, 50] |
<pre>fringe(t1): [40, 50] |
||
Line 1,132: | Line 1,132: | ||
===Range Generator Version (Lazy)=== |
===Range Generator Version (Lazy)=== |
||
< |
<syntaxhighlight lang="d">import std.stdio, std.concurrency, std.range, std.algorithm; |
||
struct Node(T) { |
struct Node(T) { |
||
Line 1,175: | Line 1,175: | ||
auto t7 = new N(1, new N(2)); |
auto t7 = new N(1, new N(2)); |
||
sameFringe(t6, t7).writeln; |
sameFringe(t6, t7).writeln; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>true |
<pre>true |
||
Line 1,185: | Line 1,185: | ||
=={{header|Go}}== |
=={{header|Go}}== |
||
< |
<syntaxhighlight lang="go">package main |
||
import "fmt" |
import "fmt" |
||
Line 1,255: | Line 1,255: | ||
&node{int: 13}} |
&node{int: 13}} |
||
fmt.Println(sameFringe(t1, t2)) // prints true. |
fmt.Println(sameFringe(t1, t2)) // prints true. |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
Line 1,261: | Line 1,261: | ||
To get the fringe, we can simply use the solution for [[Flatten a list#Haskell|Flatten a list]], slightly modified for a binary tree instead of a general tree: |
To get the fringe, we can simply use the solution for [[Flatten a list#Haskell|Flatten a list]], slightly modified for a binary tree instead of a general tree: |
||
< |
<syntaxhighlight lang="haskell">data Tree a |
||
= Leaf a |
= Leaf a |
||
| Node (Tree a) |
| Node (Tree a) |
||
Line 1,289: | Line 1,289: | ||
y = Node (Leaf 0) (Node (Node (Leaf 2) (Leaf 3)) (Node (Leaf 4) (Leaf 5))) |
y = Node (Leaf 0) (Node (Node (Leaf 2) (Leaf 3)) (Node (Leaf 4) (Leaf 5))) |
||
z = Node (Leaf 1) (Node (Leaf 2) (Node (Node (Leaf 4) (Leaf 3)) (Leaf 5))) |
z = Node (Leaf 1) (Node (Leaf 2) (Node (Node (Leaf 4) (Leaf 3)) (Leaf 5))) |
||
mapM_ print $ sameFringe a <$> [a, b, c, x, y, z]</ |
mapM_ print $ sameFringe a <$> [a, b, c, x, y, z]</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>True |
<pre>True |
||
Line 1,302: | Line 1,302: | ||
The following solution works in both languages: |
The following solution works in both languages: |
||
< |
<syntaxhighlight lang="unicon">procedure main() |
||
aTree := [1, [2, [4, [7]], [5]], [3, [6, [8], [9]]]] |
aTree := [1, [2, [4, [7]], [5]], [3, [6, [8], [9]]]] |
||
bTree := [1, [2, [4, [7]], [5]], [3, [6, [8], [9]]]] |
bTree := [1, [2, [4, [7]], [5]], [3, [6, [8], [9]]]] |
||
Line 1,331: | Line 1,331: | ||
procedure preorder(L) |
procedure preorder(L) |
||
if \L then suspend L | preorder(L[2|3]) |
if \L then suspend L | preorder(L[2|3]) |
||
end</ |
end</syntaxhighlight> |
||
Output: |
Output: |
||
Line 1,344: | Line 1,344: | ||
=={{header|J}}== |
=={{header|J}}== |
||
< |
<syntaxhighlight lang="j">sameFringe=: -:&([: ; <S:0)</syntaxhighlight> |
||
Note that the time/space optimizations here can change with the language implementation, but current implementations make no effort to treat trees efficiently. |
Note that the time/space optimizations here can change with the language implementation, but current implementations make no effort to treat trees efficiently. |
||
Line 1,352: | Line 1,352: | ||
Anyways, here's a recursive routine to convert a flat list into a binary tree: |
Anyways, here's a recursive routine to convert a flat list into a binary tree: |
||
< |
<syntaxhighlight lang="j">list2tree=: (<.@-:@# ({. ,&<&list2tree}. ) ])^:(1<#)</syntaxhighlight> |
||
And, here are two differently structured trees which represent the same underlying data: |
And, here are two differently structured trees which represent the same underlying data: |
||
< |
<syntaxhighlight lang="j">bp=: list2tree p: i.11 |
||
ubp=: p:L:0] 10;~list2tree i.10</ |
ubp=: p:L:0] 10;~list2tree i.10</syntaxhighlight> |
||
And, here's our original operation in action (<code>1 {:: ubp</code> is a subtree of ubp which omits a leaf node): |
And, here's our original operation in action (<code>1 {:: ubp</code> is a subtree of ubp which omits a leaf node): |
||
< |
<syntaxhighlight lang="j"> ubp sameFringe bp |
||
1 |
1 |
||
bp sameFringe 1 {:: ubp |
bp sameFringe 1 {:: ubp |
||
0</ |
0</syntaxhighlight> |
||
=={{header|Java}}== |
=={{header|Java}}== |
||
Line 1,371: | Line 1,371: | ||
'''Code:''' |
'''Code:''' |
||
< |
<syntaxhighlight lang="java">import java.util.*; |
||
class SameFringe |
class SameFringe |
||
Line 1,491: | Line 1,491: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
'''Output:''' |
'''Output:''' |
||
Line 1,505: | Line 1,505: | ||
With this data structure, a test for whether two trees, s and t, have the same fringes could be implemented simply as: |
With this data structure, a test for whether two trees, s and t, have the same fringes could be implemented simply as: |
||
< |
<syntaxhighlight lang="jq">(t|flatten) == (s|flatten)</syntaxhighlight> |
||
but this entails generating the lists of leaves. |
but this entails generating the lists of leaves. |
||
To accomplish the "same fringe" task efficiently in jq 1.4 without generating a list of leaves, a special-purpose function is needed. This special-purpose function, which is here named "next", would ordinarily be defined as an inner function of "same_fringe", but for clarity, it is defined as a top-level function. |
To accomplish the "same fringe" task efficiently in jq 1.4 without generating a list of leaves, a special-purpose function is needed. This special-purpose function, which is here named "next", would ordinarily be defined as an inner function of "same_fringe", but for clarity, it is defined as a top-level function. |
||
< |
<syntaxhighlight lang="jq"># "next" allows one to generate successive leaves, one at a time. This is accomplished |
||
# by ensuring that the non-null output of a call to "next" can also serve as input. |
# by ensuring that the non-null output of a call to "next" can also serve as input. |
||
# |
# |
||
Line 1,541: | Line 1,541: | ||
end; |
end; |
||
eq([t,[]]|next; [u,[]]|next) ;</ |
eq([t,[]]|next; [u,[]]|next) ;</syntaxhighlight> |
||
'''Example''': |
'''Example''': |
||
< |
<syntaxhighlight lang="jq"> [1,[2,[3,[4,[5,[6,7]]]]]] as $a |
||
| [[[[[[1,2],3],4],5],6],7] as $b |
| [[[[[[1,2],3],4],5],6],7] as $b |
||
| [[[1,2],3],[4,[5,[6,7]]]] as $c |
| [[[1,2],3],[4,[5,[6,7]]]] as $c |
||
Line 1,552: | Line 1,552: | ||
same_fringe( ["a",["b",["c",[["x","y"],"z"]]]]; |
same_fringe( ["a",["b",["c",[["x","y"],"z"]]]]; |
||
[[["a","b"],"c"],["x",["y","z"]]] )</ |
[[["a","b"],"c"],["x",["y","z"]]] )</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
< |
<syntaxhighlight lang="sh">$ jq -n -f Same_Fringe.jq |
||
true |
true |
||
true |
true |
||
Line 1,565: | Line 1,565: | ||
false |
false |
||
true |
true |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
<syntaxhighlight lang="julia"> |
|||
<lang Julia> |
|||
using Lazy |
using Lazy |
||
Line 1,619: | Line 1,619: | ||
println(equalsfringe(a, y) == false) |
println(equalsfringe(a, y) == false) |
||
println(equalsfringe(a, z) == false) |
println(equalsfringe(a, z) == false) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{output}} |
{{output}} |
||
<pre> |
<pre> |
||
Line 1,644: | Line 1,644: | ||
In this example, an internal node of a tree is either a "branch", a table with exactly two elements, or the distinguished value None -- everything else is a fringe (leaf) value. <i>fringeiter</i> creates an iterator function to produce successive elements of the fringe. |
In this example, an internal node of a tree is either a "branch", a table with exactly two elements, or the distinguished value None -- everything else is a fringe (leaf) value. <i>fringeiter</i> creates an iterator function to produce successive elements of the fringe. |
||
< |
<syntaxhighlight lang="lua">local type, insert, remove = type, table.insert, table.remove |
||
None = {} -- a unique object for a truncated branch (i.e. empty subtree) |
None = {} -- a unique object for a truncated branch (i.e. empty subtree) |
||
Line 1,700: | Line 1,700: | ||
compare_fringe("(t1, t2)", t1, t2) |
compare_fringe("(t1, t2)", t1, t2) |
||
compare_fringe("(t1, t3)", t1, t3) |
compare_fringe("(t1, t3)", t1, t3) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 1,709: | Line 1,709: | ||
We define an iterator “nodes” which yields the successive nodes of a tree. To compare the fringes, we get the successive nodes using an iterator for each tree and stop iterations as soon as a difference is found. |
We define an iterator “nodes” which yields the successive nodes of a tree. To compare the fringes, we get the successive nodes using an iterator for each tree and stop iterations as soon as a difference is found. |
||
< |
<syntaxhighlight lang="nim">import random, sequtils, strutils |
||
type Node = ref object |
type Node = ref object |
||
Line 1,792: | Line 1,792: | ||
let s = if haveSameFringe(tree1, tree2): "have " else: "don’t have " |
let s = if haveSameFringe(tree1, tree2): "have " else: "don’t have " |
||
echo "The trees ", s, "same fringe: ", toSeq(tree1.nodes()).mapIt(it.value).join(", ")</ |
echo "The trees ", s, "same fringe: ", toSeq(tree1.nodes()).mapIt(it.value).join(", ")</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,801: | Line 1,801: | ||
=={{header|OCaml}}== |
=={{header|OCaml}}== |
||
While we could use a lazy datatype such as [http://caml.inria.fr/pub/docs/manual-ocaml/libref/Stream.html Stream] for this problem, this example implements the short-circuit behavior (returning on first mismatch) by tracking the parse state. |
While we could use a lazy datatype such as [http://caml.inria.fr/pub/docs/manual-ocaml/libref/Stream.html Stream] for this problem, this example implements the short-circuit behavior (returning on first mismatch) by tracking the parse state. |
||
< |
<syntaxhighlight lang="ocaml">type 'a btree = Leaf of 'a | BTree of ('a btree * 'a btree) |
||
let rec next = function |
let rec next = function |
||
Line 1,823: | Line 1,823: | ||
let check a b = |
let check a b = |
||
print_endline (if samefringe a b then "same" else "different") in |
print_endline (if samefringe a b then "same" else "different") in |
||
check u v; check v u; check v w;</ |
check u v; check v u; check v w;</syntaxhighlight> |
||
Output: |
Output: |
||
<pre>same |
<pre>same |
||
Line 1,834: | Line 1,834: | ||
The tree iterator is pretty simple: we use array references with index 0 as the left subtree and index 1 holding the right subtree. So as we go down the tree towards the first leaf, we push each right subtree that we will consider later onto the rtree stack. Eventually, we'll hit a leaf and return it. The next time we go into the iterator, we simply pull off the last deferred subtree and continue the process. |
The tree iterator is pretty simple: we use array references with index 0 as the left subtree and index 1 holding the right subtree. So as we go down the tree towards the first leaf, we push each right subtree that we will consider later onto the rtree stack. Eventually, we'll hit a leaf and return it. The next time we go into the iterator, we simply pull off the last deferred subtree and continue the process. |
||
< |
<syntaxhighlight lang="perl"> |
||
#!/usr/bin/perl |
#!/usr/bin/perl |
||
use strict; |
use strict; |
||
Line 1,872: | Line 1,872: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,880: | Line 1,880: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
<!--< |
<!--<syntaxhighlight lang="phix">(notonline)--> |
||
<span style="color: #000080;font-style:italic;">-- |
<span style="color: #000080;font-style:italic;">-- |
||
-- demo\rosetta\Same_Fringe.exw |
-- demo\rosetta\Same_Fringe.exw |
||
Line 1,962: | Line 1,962: | ||
<span style="color: #0000FF;">?</span><span style="color: #008000;">"done"</span> |
<span style="color: #0000FF;">?</span><span style="color: #008000;">"done"</span> |
||
<span style="color: #0000FF;">{}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">wait_key</span><span style="color: #0000FF;">()</span> |
<span style="color: #0000FF;">{}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">wait_key</span><span style="color: #0000FF;">()</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,989: | Line 1,989: | ||
=={{header|PicoLisp}}== |
=={{header|PicoLisp}}== |
||
This uses coroutines to traverse the trees, so it works only in the 64-bit version. |
This uses coroutines to traverse the trees, so it works only in the 64-bit version. |
||
< |
<syntaxhighlight lang="picolisp">(de nextLeaf (Rt Tree) |
||
(co Rt |
(co Rt |
||
(recur (Tree) |
(recur (Tree) |
||
Line 2,007: | Line 2,007: | ||
(NIL (= Node1 Node2)) ) ) |
(NIL (= Node1 Node2)) ) ) |
||
(co "rt1") |
(co "rt1") |
||
(co "rt2") ) )</ |
(co "rt2") ) )</syntaxhighlight> |
||
Test: |
Test: |
||
< |
<syntaxhighlight lang="picolisp">: (balance '*Tree1 (range 1 7)) |
||
-> NIL |
-> NIL |
||
: (for N (5 4 6 3 7 1 2) (idx '*Tree2 N T)) |
: (for N (5 4 6 3 7 1 2) (idx '*Tree2 N T)) |
||
Line 2,035: | Line 2,035: | ||
: (cmpTrees *Tree1 *Tree2) |
: (cmpTrees *Tree1 *Tree2) |
||
-> T</ |
-> T</syntaxhighlight> |
||
=={{header|Python}}== |
=={{header|Python}}== |
||
This solution visits lazily the two trees in lock step like in the Raku example, and stops at the first miss-match. |
This solution visits lazily the two trees in lock step like in the Raku example, and stops at the first miss-match. |
||
< |
<syntaxhighlight lang="python">try: |
||
from itertools import zip_longest as izip_longest # Python 3.x |
from itertools import zip_longest as izip_longest # Python 3.x |
||
except: |
except: |
||
Line 2,073: | Line 2,073: | ||
assert not same_fringe(a, x) |
assert not same_fringe(a, x) |
||
assert not same_fringe(a, y) |
assert not same_fringe(a, y) |
||
assert not same_fringe(a, z)</ |
assert not same_fringe(a, z)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
There is no output, which signifies success. |
There is no output, which signifies success. |
||
Line 2,091: | Line 2,091: | ||
be added to any of the following variations, it's omitted for brevity. |
be added to any of the following variations, it's omitted for brevity. |
||
< |
<syntaxhighlight lang="racket"> |
||
#lang racket |
#lang racket |
||
Line 2,111: | Line 2,111: | ||
(check-false (same-fringe? '((1 2 3) ((4 5 6) (7 8))) |
(check-false (same-fringe? '((1 2 3) ((4 5 6) (7 8))) |
||
'(((1 2 3) (4 6)) (8))))) |
'(((1 2 3) (4 6)) (8))))) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 2,125: | Line 2,125: | ||
that feeds it. |
that feeds it. |
||
< |
<syntaxhighlight lang="racket"> |
||
#lang racket |
#lang racket |
||
Line 2,141: | Line 2,141: | ||
(let ([x1 (channel-get ch1)] [x2 (channel-get ch2)]) |
(let ([x1 (channel-get ch1)] [x2 (channel-get ch2)]) |
||
(and (equal? x1 x2) (or (void? x1) (loop)))))) |
(and (equal? x1 x2) (or (void? x1) (loop)))))) |
||
</syntaxhighlight> |
|||
</lang> |
|||
Channels are just a one of several thread-communication devices which |
Channels are just a one of several thread-communication devices which |
||
Line 2,149: | Line 2,149: | ||
running. |
running. |
||
< |
<syntaxhighlight lang="racket"> |
||
#lang racket |
#lang racket |
||
Line 2,165: | Line 2,165: | ||
(let ([x1 (read i1)] [x2 (read i2)]) |
(let ([x1 (read i1)] [x2 (read i2)]) |
||
(and (equal? x1 x2) (or (eof-object? x1) (loop)))))) |
(and (equal? x1 x2) (or (eof-object? x1) (loop)))))) |
||
</syntaxhighlight> |
|||
</lang> |
|||
=== Generators === |
=== Generators === |
||
Line 2,171: | Line 2,171: | ||
This version is very similar, except that now we use generators: |
This version is very similar, except that now we use generators: |
||
< |
<syntaxhighlight lang="racket"> |
||
#lang racket |
#lang racket |
||
(require racket/generator) |
(require racket/generator) |
||
Line 2,186: | Line 2,186: | ||
(let ([x1 (g1)] [x2 (g2)]) |
(let ([x1 (g1)] [x2 (g2)]) |
||
(and (equal? x1 x2) (or (void? x1) (loop)))))) |
(and (equal? x1 x2) (or (void? x1) (loop)))))) |
||
</syntaxhighlight> |
|||
</lang> |
|||
Line 2,197: | Line 2,197: | ||
delimited continuation operator. |
delimited continuation operator. |
||
< |
<syntaxhighlight lang="racket"> |
||
#lang racket |
#lang racket |
||
Line 2,216: | Line 2,216: | ||
(and (equal? x1 x2) |
(and (equal? x1 x2) |
||
(or (void? x1) (loop iter1 iter2))))))))) |
(or (void? x1) (loop iter1 iter2))))))))) |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
Line 2,222: | Line 2,222: | ||
{{works with|Rakudo|2018.03}} |
{{works with|Rakudo|2018.03}} |
||
Unlike in Perl 5, where <tt>=></tt> is just a synonym for comma, in Raku it creates a true Pair object. So here we use Pair objects for our "cons" cells, just as if we were doing this in Lisp. We use the <tt>gather/take</tt> construct to harvest the leaves lazily as the elements are visited with a standard recursive algorithm, using multiple dispatch to differentiate nodes from leaves. The <tt>eqv</tt> value equivalence is applied to the two lists in parallel. |
Unlike in Perl 5, where <tt>=></tt> is just a synonym for comma, in Raku it creates a true Pair object. So here we use Pair objects for our "cons" cells, just as if we were doing this in Lisp. We use the <tt>gather/take</tt> construct to harvest the leaves lazily as the elements are visited with a standard recursive algorithm, using multiple dispatch to differentiate nodes from leaves. The <tt>eqv</tt> value equivalence is applied to the two lists in parallel. |
||
<lang |
<syntaxhighlight lang="raku" line>sub fringe ($tree) { |
||
multi sub fringey (Pair $node) { fringey $_ for $node.kv; } |
multi sub fringey (Pair $node) { fringey $_ for $node.kv; } |
||
multi sub fringey ( Any $leaf) { take $leaf; } |
multi sub fringey ( Any $leaf) { take $leaf; } |
||
Line 2,247: | Line 2,247: | ||
say not samefringe $a, $x; |
say not samefringe $a, $x; |
||
say not samefringe $a, $y; |
say not samefringe $a, $y; |
||
say not samefringe $a, $z;</ |
say not samefringe $a, $z;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>True |
<pre>True |
||
Line 2,260: | Line 2,260: | ||
===Version 1 using father node === |
===Version 1 using father node === |
||
< |
<syntaxhighlight lang="rexx">/* REXX *************************************************************** |
||
* Same Fringe |
* Same Fringe |
||
* 1 A A |
* 1 A A |
||
Line 2,435: | Line 2,435: | ||
i=mknode('I',t); Call attrite i,f,t |
i=mknode('I',t); Call attrite i,f,t |
||
End |
End |
||
Return</ |
Return</syntaxhighlight> |
||
Output: |
Output: |
||
<pre> |
<pre> |
||
Line 2,449: | Line 2,449: | ||
===Version 2 without using father node === |
===Version 2 without using father node === |
||
< |
<syntaxhighlight lang="rexx">/* REXX *************************************************************** |
||
* Same Fringe |
* Same Fringe |
||
= 1 A A |
= 1 A A |
||
Line 2,587: | Line 2,587: | ||
i=mknode('I',t); Call attrite i,f,t |
i=mknode('I',t); Call attrite i,f,t |
||
End |
End |
||
Return</ |
Return</syntaxhighlight> |
||
Output is the same as for Version 1 |
Output is the same as for Version 1 |
||
Line 2,606: | Line 2,606: | ||
:::* combined subroutines '''ATTLEFT''' and '''ATTRIGHT''' into one |
:::* combined subroutines '''ATTLEFT''' and '''ATTRIGHT''' into one |
||
:::* streamlined the '''MAKE_TREE''' subroutine |
:::* streamlined the '''MAKE_TREE''' subroutine |
||
< |
<syntaxhighlight lang="rexx">/*REXX pgm examines the leaves of 2 binary trees (as shown below), and finds inequities.*/ |
||
_= left('', 28); say _ " A A " |
_= left('', 28); say _ " A A " |
||
say _ " / \ ◄════1st tree / \ " |
say _ " / \ ◄════1st tree / \ " |
||
Line 2,657: | Line 2,657: | ||
son: procedure expose @.; parse arg ?,son,dad,t; LR= '_'?"SON"; @.t.son._dad= dad |
son: procedure expose @.; parse arg ?,son,dad,t; LR= '_'?"SON"; @.t.son._dad= dad |
||
q= @.t.dad.LR; if q\==0 then do; @.t.q._dad= son; @.t.son.LR= q; end |
q= @.t.dad.LR; if q\==0 then do; @.t.q._dad= son; @.t.son.LR= q; end |
||
@.t.dad.LR= son; return</ |
@.t.dad.LR= son; return</syntaxhighlight> |
||
{{out|output}} |
{{out|output}} |
||
<pre> |
<pre> |
||
Line 2,684: | Line 2,684: | ||
Descend provides a list, or stack, of the leftmost ''unvisited'' nodes at each level of the tree. Two such lists are used as cursors to keep track of the remaining nodes. The main loop compares the top of each list (ie the leftmost remaining node) and breaks with ''false'' if different, or calls Ascend to update the lists. Updating may require calling Descend again if more unvisited left-nodes are found. If the end of both lists is reached simultaneously, and therefore the end of both trees, ''true'' is returned. |
Descend provides a list, or stack, of the leftmost ''unvisited'' nodes at each level of the tree. Two such lists are used as cursors to keep track of the remaining nodes. The main loop compares the top of each list (ie the leftmost remaining node) and breaks with ''false'' if different, or calls Ascend to update the lists. Updating may require calling Descend again if more unvisited left-nodes are found. If the end of both lists is reached simultaneously, and therefore the end of both trees, ''true'' is returned. |
||
< |
<syntaxhighlight lang="scheme">; binary tree helpers from "Structure and Interpretation of Computer Programs" 2.3.3 |
||
(define (entry tree) (car tree)) |
(define (entry tree) (car tree)) |
||
(define (left-branch tree) (cadr tree)) |
(define (left-branch tree) (cadr tree)) |
||
Line 2,718: | Line 2,718: | ||
(null? l2) |
(null? l2) |
||
(not (eq? (entry (car l1)) (entry (car l2))))) #f) |
(not (eq? (entry (car l1)) (entry (car l2))))) #f) |
||
(else (next (ascend l1) (ascend l2))))))</ |
(else (next (ascend l1) (ascend l2))))))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,726: | Line 2,726: | ||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
{{trans|Perl}} |
{{trans|Perl}} |
||
< |
<syntaxhighlight lang="ruby">var trees = [ |
||
# 0..2 are same |
# 0..2 are same |
||
[ 'd', [ 'c', [ 'a', 'b', ], ], ], |
[ 'd', [ 'c', [ 'a', 'b', ], ], ], |
||
Line 2,761: | Line 2,761: | ||
say ("tree[#{idx}] vs tree[#{idx+1}]: ", |
say ("tree[#{idx}] vs tree[#{idx+1}]: ", |
||
cmp_fringe(trees[idx], trees[idx+1])) |
cmp_fringe(trees[idx], trees[idx+1])) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,773: | Line 2,773: | ||
{{works with|Tcl|8.6}} |
{{works with|Tcl|8.6}} |
||
{{tcllib|struct::tree}} |
{{tcllib|struct::tree}} |
||
< |
<syntaxhighlight lang="tcl">package require Tcl 8.6 |
||
package require struct::tree |
package require struct::tree |
||
Line 2,805: | Line 2,805: | ||
rename $c2 {} |
rename $c2 {} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
Demonstrating: |
Demonstrating: |
||
< |
<syntaxhighlight lang="tcl"># Make some trees to compare... |
||
struct::tree t1 deserialize { |
struct::tree t1 deserialize { |
||
root {} {} |
root {} {} |
||
Line 2,826: | Line 2,826: | ||
# Print the boolean result of doing the comparison |
# Print the boolean result of doing the comparison |
||
puts [samefringe t1 t2]</ |
puts [samefringe t1 t2]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,836: | Line 2,836: | ||
{{trans|Go}} |
{{trans|Go}} |
||
{{libheader|Wren-dynamic}} |
{{libheader|Wren-dynamic}} |
||
< |
<syntaxhighlight lang="ecmascript">import "/dynamic" for Struct |
||
var Node = Struct.create("Node", ["key", "left", "right"]) |
var Node = Struct.create("Node", ["key", "left", "right"]) |
||
Line 2,909: | Line 2,909: | ||
System.print("tree 1 and tree 2 have the same leaves: %(sameFringe.call(t1, t2))") |
System.print("tree 1 and tree 2 have the same leaves: %(sameFringe.call(t1, t2))") |
||
System.print("tree 1 and tree 3 have the same leaves: %(sameFringe.call(t1, t3))") |
System.print("tree 1 and tree 3 have the same leaves: %(sameFringe.call(t1, t3))") |
||
System.print("tree 2 and tree 3 have the same leaves: %(sameFringe.call(t2, t3))")</ |
System.print("tree 2 and tree 3 have the same leaves: %(sameFringe.call(t2, t3))")</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,920: | Line 2,920: | ||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
{{trans|Icon and Unicon}} |
{{trans|Icon and Unicon}} |
||
< |
<syntaxhighlight lang="zkl">var G=Utils.Generator; |
||
//Tree: (node,left,right) or (leaf) or (node,left) ... |
//Tree: (node,left,right) or (leaf) or (node,left) ... |
||
aTree := T(1, T(2, T(4, T(7)), T(5)), T(3, T(6, T(8), T(9)))); |
aTree := T(1, T(2, T(4, T(7)), T(5)), T(3, T(6, T(8), T(9)))); |
||
Line 2,946: | Line 2,946: | ||
else { genLeaves(tree[1]); genLeaves(tree[2]); } |
else { genLeaves(tree[1]); genLeaves(tree[2]); } |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |