Same fringe: Difference between revisions

The package is generic, which allows Data to be essentially of any type.

 

type Data is private;

package Bin_Trees is

end record;

 

 

The implementation is straightforward.

 

 

package body Bin_Trees is

end 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.

 

with procedure Process_Data(Item: Data);

with function Stop return Boolean;

-- except when Stop becomes true; in this case, the task terminates

end Inorder_Task;

 

task body Inorder_Task is

procedure Inorder(Tree: Tree_Type) is

Finish;

end Inorder_Task;

 

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.

A third auxiliary task just waits until the consumer has finished and the result of the fringe comparison can be read.

 

 

procedure Main is

Ada.Text_IO.New_Line;

end loop;

 

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.

 

=={{header|Bracmat}}==

=

. ( next

, (((a.b).c).x.y.z)

)

Output:

<pre>x,x

=={{header|C}}==

With rudimentary coroutine support based on ucontext. I don't know if it will compile on anything other than GCC.

#include <stdlib.h>

#include <ucontext.h>

 

return 0;

 

=={{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.

using System;

using System.Collections.Generic;

}

}

 

Example output:

True Compare worked

False Compare worked

</pre>

 

''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.

(letfn [(walk [node]

(lazy-seq

(mapcat walk (children node)))

(list node))))]

For this problem, binary trees are represented as vectors, whose nodes are either [''content'' ''left'' ''right''] or just ''content''.

(println (vfringe-seq [10 1 2])) ; (1 2)

Then we can use a general sequence-equality function:

(cond

(and (empty? s1) (empty? s2)) true

(not= (empty? s1) (empty? s2)) false

(= (first s1) (first s2)) (recur (rest s1) (rest s2))

 

=={{header|D}}==

===Short Version===

A short recursive solution that is not lazy (and lacks the const/immutable/pure/nothrow):

T data;

Node* L, R;

auto t3 = new N(1, new N(2, new N(3, new N(40), new N(51))));

writeln(sameFringe(t1, t3));

{{out}}

<pre>true

===Strong Lazy Version===

This version is quite long because it tries to be reliable. The code contains contracts, unit tests, annotations, and so on.

import std.algorithm: equal;

 

writeln("sameFringe(t1, t2): ", sameFringe(t1, t2));

writeln("sameFringe(t1, t3): ", sameFringe(t1, t3));

{{out}}

<pre>fringe(t1): [40, 50]

 

===Range Generator Version (Lazy)===

 

struct Node(T) {

auto t7 = new N(1, new N(2));

sameFringe(t6, t7).writeln;

{{out}}

<pre>true

 

=={{header|Go}}==

 

import "fmt"

&node{int: 13}}

fmt.Println(sameFringe(t1, t2)) // prints true.

 

=={{header|Haskell}}==

 

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:

= Leaf a

| Node (Tree a)

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)))

{{Out}}

<pre>True

The following solution works in both languages:

 

aTree := [1, [2, [4, [7]], [5]], [3, [6, [8], [9]]]]

bTree := [1, [2, [4, [7]], [5]], [3, [6, [8], [9]]]]

procedure preorder(L)

if \L then suspend L | preorder(L[2|3])

 

Output:

=={{header|J}}==

 

 

Note that the time/space optimizations here can change with the language implementation, but current implementations make no effort to treat trees efficiently.

Anyways, here's a recursive routine to convert a flat list into a binary tree:

 

 

And, here are two differently structured trees which represent the same underlying data:

 

 

And, here's our original operation in action (<code>1 {:: ubp</code> is a subtree of ubp which omits a leaf node):

 

1

bp sameFringe 1 {:: ubp

 

=={{header|Java}}==

 

'''Code:'''

 

class SameFringe

}

}

 

'''Output:'''

 

With this data structure, a test for whether two trees, s and t, have the same fringes could be implemented simply as:

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.

# by ensuring that the non-null output of a call to "next" can also serve as input.

#

end;

 

'''Example''':

| [[[[[[1,2],3],4],5],6],7] as $b

| [[[1,2],3],[4,[5,[6,7]]]] as $c

 

same_fringe( ["a",["b",["c",[["x","y"],"z"]]]];

{{out}}

true

true

false

true

 

=={{header|Julia}}==

using Lazy

 

println(equalsfringe(a, y) == false)

println(equalsfringe(a, z) == false)

{{output}}

<pre>

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.

 

 

None = {} -- a unique object for a truncated branch (i.e. empty subtree)

compare_fringe("(t1, t2)", t1, t2)

compare_fringe("(t1, t3)", t1, t3)

 

{{out}}

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.

 

 

type Node = ref object

 

let s = if haveSameFringe(tree1, tree2): "have " else: "don’t have "

 

{{out}}

=={{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.

 

let rec next = function

let check a b =

print_endline (if samefringe a b then "same" else "different") in

Output:

<pre>same

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.

 

#!/usr/bin/perl

use strict;

}

}

{{out}}

<pre>

 

=={{header|Phix}}==

{{out}}

<pre>

task[1] sets sdata[1] to 1

task[2] sets sdata[2] to 1

task[1] sets sdata[1] to 2

task[2] sets sdata[2] to 2

task[1] ends

task[2] ends

test(1,1):0

test(1,2):0

test(3,2):1

test(3,3):0

</pre>

 

=={{header|PicoLisp}}==

This uses coroutines to traverse the trees, so it works only in the 64-bit version.

(co Rt

(recur (Tree)

(NIL (= Node1 Node2)) ) )

(co "rt1")

Test:

-> NIL

: (for N (5 4 6 3 7 1 2) (idx '*Tree2 N T))

 

: (cmpTrees *Tree1 *Tree2)

 

=={{header|Python}}==

This solution visits lazily the two trees in lock step like in the Raku example, and stops at the first miss-match.

from itertools import zip_longest as izip_longest # Python 3.x

except:

assert not same_fringe(a, x)

assert not same_fringe(a, y)

{{out}}

There is no output, which signifies success.

be added to any of the following variations, it's omitted for brevity.

 

#lang racket

 

(check-false (same-fringe? '((1 2 3) ((4 5 6) (7 8)))

'(((1 2 3) (4 6)) (8)))))

 

{{out}}

that feeds it.

 

#lang racket

 

(let ([x1 (channel-get ch1)] [x2 (channel-get ch2)])

(and (equal? x1 x2) (or (void? x1) (loop))))))

 

Channels are just a one of several thread-communication devices which

running.

 

#lang racket

 

(let ([x1 (read i1)] [x2 (read i2)])

(and (equal? x1 x2) (or (eof-object? x1) (loop))))))

 

=== Generators ===

This version is very similar, except that now we use generators:

 

#lang racket

(require racket/generator)

(let ([x1 (g1)] [x2 (g2)])

(and (equal? x1 x2) (or (void? x1) (loop))))))

 

 

delimited continuation operator.

 

#lang racket

 

(and (equal? x1 x2)

(or (void? x1) (loop iter1 iter2)))))))))

 

=={{header|Raku}}==

{{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.

multi sub fringey (Pair $node) { fringey $_ for $node.kv; }

multi sub fringey ( Any $leaf) { take $leaf; }

say not samefringe $a, $x;

say not samefringe $a, $y;

{{out}}

<pre>True

===Version 1 using father node ===

 

* Same Fringe

* 1 A A

i=mknode('I',t); Call attrite i,f,t

End

Output:

<pre>

 

===Version 2 without using father node ===

* Same Fringe

= 1 A A

i=mknode('I',t); Call attrite i,f,t

End

Output is the same as for Version 1

 

This REXX example is a re─written program that mimics the first version (above).

 

:::* &nbsp; elided a subroutine

:::* &nbsp; elided superfluous &nbsp; '''do ── end''' &nbsp; groups

:::* &nbsp; elided some stemmed array tails

:::* &nbsp; simplified some stem names

:::* &nbsp; displays the tree &nbsp; (as an ASCII display)

:::* &nbsp; combined subroutines &nbsp; '''ATTLEFT''' &nbsp; and &nbsp; '''ATTRIGHT''' &nbsp; into one

:::* &nbsp; streamlined the &nbsp; '''MAKE_TREE''' &nbsp; subroutine

_= left('', 28); say _ " A A "

say _ " / \ ◄════1st tree / \ "

say _ " / / \ / / \ "

say _ "G H I G δ I " ; say

do t#=1 for 2; call make_tree t#; end /*define tree numbers 1 and 2. */

z1= root.1; L1= @.1.z1; done.1.z1= 1 /*L1: is a leaf on tree number 1. */

z2= z1; L2= @.2.z2; done.2.z2= 1 /*L2: " " " " " " 2. */

end

/*──────────────────────────────────────────────────────────────────────────────────────*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

@.t.q= name; @.t.q._Lson= 0; @.t.0= q

/*──────────────────────────────────────────────────────────────────────────────────────*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

{{out|output}}

<pre>

G H I G δ I

 

A difference is: H ¬= δ

</pre>

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.

 

(define (entry tree) (car tree))

(define (left-branch tree) (cadr tree))

(null? l2)

(not (eq? (entry (car l1)) (entry (car l2))))) #f)

 

{{out}}

=={{header|Sidef}}==

{{trans|Perl}}

# 0..2 are same

[ 'd', [ 'c', [ 'a', 'b', ], ], ],

say ("tree[#{idx}] vs tree[#{idx+1}]: ",

cmp_fringe(trees[idx], trees[idx+1]))

 

{{out}}

{{works with|Tcl|8.6}}

{{tcllib|struct::tree}}

package require struct::tree

 

rename $c2 {}

}

Demonstrating:

struct::tree t1 deserialize {

root {} {}

 

# Print the boolean result of doing the comparison

{{out}}

<pre>

c != cc

0

</pre>

 

=={{header|zkl}}==

{{trans|Icon and Unicon}}

//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))));

else { genLeaves(tree[1]); genLeaves(tree[2]); }

}

{{out}}

<pre>