Same fringe: Difference between revisions

Content added Content deleted
m (→‎{{header|Perl 6}}: Combine into a single file for ease of testing)
(→‎version 1.1: changed some variable names, aligned statements, elided unreferenced variables, added/changed comments and whitespace, used a template for the output section.)
Line 2,194: Line 2,194:


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

<br><br>This version has:
This version has:
:::* elided a subroutine
:::* elided superfluous &nbsp; '''do ── end''' &nbsp; groups
:::* &nbsp; elided a subroutine
:::* elided some stemmed array tails
:::* &nbsp; elided superfluous &nbsp; '''do ── end''' &nbsp; groups
:::* elided some REXX variables &nbsp; (lvl, debug, ···)
:::* &nbsp; elided some stemmed array tails
:::* &nbsp; elided some REXX variables &nbsp; (LVL, DEBUG, ···)
:::* simplified some stem names
:::* displays the tree &nbsp; (as an ASCII display)
:::* &nbsp; simplified some stem names
:::* &nbsp; displays the tree &nbsp; (as an ASCII display)
:::* changed ''tree'' names so as to not conflict with ''leaf'' names
:::* &nbsp; changed ''TREE'' names so as to not conflict with ''LEAF'' names
:::* uses non-case sensitive tree names
:::* &nbsp; uses non─case sensitive tree names
:::* used boolean based variables as ''logicals''
:::* &nbsp; used boolean based variables as ''logicals''
:::* expanded message texts
:::* &nbsp; expanded message texts
:::* combined subroutines &nbsp; '''attleft''' &nbsp; and &nbsp; '''attright''' &nbsp; into one
:::* streamlined the &nbsp; '''make_tree''' &nbsp; subroutine
:::* &nbsp; combined subroutines &nbsp; '''ATTLEFT''' &nbsp; and &nbsp; '''ATTRIGHT''' &nbsp; into one
:::* &nbsp; streamlined the &nbsp; '''MAKE_TREE''' &nbsp; subroutine
<lang rexx>/*REXX program examines the leaves of two binary trees (as shown below).*/
<lang rexx>/*REXX pgm examines the leaves of 2 binary trees (as shown below), and finds inequities.*/
⚫
_=left('',28); say _ " A A "
say _ " / \ ◄════1st tree / \ "
_=left('', 28); say _ " A A "
say _ " / \ / \ "
say _ " / \ ◄════1st tree / \ "
say _ " / \ / \ "
say _ " / \ / \ "
say _ " B C B C "
say _ " / \ / \ "
say _ " / \ / 2nd tree════► / \ / "
say _ " B C B C "
say _ " D E F D E F "
say _ " / \ / 2nd tree════► / \ / "
say _ " / / \ / / \ "
say _ " D E F D E F "
say _ "G H I G δ I "
say _ " / / \ / / \ "
⚫
say _ "G H I G δ I "
say
say
#=0; done.=0; node.=0 /*initialize # leaves,DONE.,NODE.*/
#=0; done.=0; @.=0 /*initialize: #, leaves, DONE., nodes*/
call make_tree 1 /*define tree number 1 (1st tree)*/
call make_tree 1 /*define tree number 1 (the 1st tree).*/
call make_tree 2 /* " " " 2 (2nd " )*/
call make_tree 2 /* " " " 2 (the 2nd " ).*/
z1=root.1; L1=node.1.z1; done.1.z1=1 /*L1 is a leaf on tree number 1. */
z1=root.1; L1=@.1.z1; done.1.z1=1 /*L1: is a leaf on tree number 1. */
z2=z1; L2=node.2.z2; done.2.z2=1 /*L2 " " " " " " 2. */
z2=z1; L2=@.2.z2; done.2.z2=1 /*L2: " " " " " " 2. */


do # % 2 /*loop for the number of leaves. */
do # % 2 /*loop for the number of (tree) leaves.*/
if L1==L2 then do
if L1==L2 then do
if L1==0 then call sayX 'The trees are equal.'
if L1==0 then call sayX 'The trees are equal.'
say ' The ' L1 " leaf is identical in both trees."
say ' The ' L1 " leaf is identical in both trees."
do until \done.1.z1
do until \done.1.z1; z1=go_next(z1, 1); L1=@.1.z1; end
z1=go_next(z1,1); L1=node.1.z1
⚫
end
done.1.z1=1
done.1.z1=1
do until \done.2.z2
do until \done.2.z2; z2=go_next(z2, 2); L2=@.2.z2; end
z2=go_next(z2,2); L2=node.2.z2
end
done.2.z2=1
done.2.z2=1
end
end
else select
else select
when L1==0 then call sayX L2 'exceeds leaves in 1st tree'
when L1==0 then call sayX L2 'exceeds leaves in 1st tree'
when L2==0 then call sayX L1 'exceeds leaves in 2nd tree'
when L2==0 then call sayX L1 'exceeds leaves in 2nd tree'
otherwise call sayX 'A difference is: ' L1 '¬=' L2
otherwise call sayX 'A difference is: ' L1 '¬=' L2
end /*select*/
end /*select*/
end /*# % 2*/
end /*# % 2*/
exit
exit
/*──────────────────────────────────────────────────────────────────────────────────────*/
/*──────────────────────────────────GO_NEXT subroutine──────────────────*/
go_next: procedure expose node.; arg q,t /*find next node.*/
go_next: procedure expose @.; arg q,t; next=. /*find next node in the tree. */
if @.t.q._Lson\==0 &, /*there a left branch in tree?*/
next=.
if node.t.q._Lson\==0 &, /*is there a left branch in tree?*/
@.t.q._Lson.vis==0 then do /*has this node been visited? */
node.t.q._Lson.vis==0 then do /*has this node been visited yet?*/
next= @.t.q._Lson /*point to the ──► next node.*/
next=node.t.q._Lson /*──► next node. */
@.t.q._Lson.vis= 1 /*the leftside is completed. */
node.t.q._Lson.vis=1 /*leftside done. */
end
end
if next==. &,
@.t.q._Rson\==0 &, /*there a right tree branch ? */
if next==. &,
node.t.q._Rson\==0 &, /*is there a right tree branch ? */
@.t.q._Rson.vis==0 then do /*has this node been visited? */
node.t.q._Rson.vis==0 then do /*has this node been VISited yet?*/
next= @.t.q._Rson /*──► next node. */
next=node.t.q._Rson /*──► next node. */
@.t.q._Rson.vis= 1 /*the rightside is completed. */
node.t.q._Rson.vis=1 /*rightside done.*/
end
end
if next==. then next= @.t.q._dad /*process the father node. */
if next==. then next=node.t.q._dad /*process the father node. */
return next /*next node (or 0, if done).*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
return next /*the next node (or 0, if done).*/
⚫
make_node: parse arg name,t; #=# +1; q= @.t.0 +1 /*make new node/branch on tree*/
/*──────────────────────────────────MAKE_NODE subroutine────────────────*/
@.t.q= name; @.t.q._Lson= 0; @.t.0= q
⚫
make_node: parse arg name,t; # = #+1 /*make a new node/branch on tree.*/
q = node.t.0 + 1 ; node.t.q = name ; node.t.q._dad = 0
@.t.q._dad=0; @.t.q._Rson= 0; return q /*number of node just created.*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
node.t.q._Lson = 0 ; node.t.q._Rson = 0 ; node.t.0 = q
⚫
make_tree: procedure expose @. root. #; parse arg tree /*construct a couple of trees.*/
return q /*number of the node just created*/
if tree==1 then hhh='H' /* [↓] must be a wood duck*/
/*──────────────────────────────────MAKE_TREE subroutine────────────────*/
else hhh='δ' /*the odd duck in the tree. */
⚫
make_tree: procedure expose node. root. #; parse arg tree /*build trees*/
if tree==1 then hhh='H' /* [↓] must be a wood duck*/
a=make_node('A', tree); root.tree=a
else hhh='δ' /*the odd duck in the whole tree.*/
b=make_node('B', tree); call son 'L', b, a, tree
a=make_node('A', tree); root.tree=a
c=make_node('C', tree); call son 'R', c, a, tree
b=make_node('B', tree); call son 'L', b,a,tree
d=make_node('D', tree); call son 'L', d, b, tree
c=make_node('C', tree); call son 'R', c,a,tree
e=make_node('E', tree); call son 'R', e, b, tree
d=make_node('D', tree); call son 'L', d,b,tree
f=make_node('F', tree); call son 'L', f, c, tree
e=make_node('E', tree); call son 'R', e,b,tree
g=make_node('G', tree); call son 'L', g, d, tree
f=make_node('F', tree); call son 'L', f,c,tree
/*quacks like a duck?*/ h=make_node(hhh, tree); call son 'L', h, f, tree
g=make_node('G', tree); call son 'L', g,d,tree
i=make_node('I', tree); call son 'R', i, f, tree
return
/*quacks like a duck?*/ h=make_node(hhh, tree); call son 'L', h,f,tree
/*──────────────────────────────────────────────────────────────────────────────────────*/
i=make_node('I', tree); call son 'R', i,f,tree
⚫
sayX: say; say arg(1); say; exit /*display a message and exit. */
return
/*──────────────────────────────────────────────────────────────────────────────────────*/
/*──────────────────────────────────SAYX subroutine─────────────────────*/
⚫
son: procedure expose @.; parse arg ?,son,dad,t; LR= '_'?"SON"
⚫
sayX: say; say arg(1); say; exit /*tell msg and exit.*/
@.t.son._dad= dad; q= @.t.dad.LR /* [↓] define which son. */
/*──────────────────────────────────SON subroutine──────────────────────*/
⚫
if q\==0 then do; @.t.q._dad= son; @.t.son.LR= q; end
⚫
son: procedure expose node.; parse arg ?,son,dad,t; LR = '_'?"SON"
node.t.son._dad=dad; q=node.t.dad.LR /*define which son [↑] */
@.t.dad.LR= son; return</lang>
⚫
{{out|output}}
if q\==0 then do; node.t.q._dad=son; node.t.son.LR=q; end
node.t.dad.LR=son
if ?=='R' & node.t.dad.LR>0 then node.t.le._brother=node.t.dad.LR
return</lang>
⚫
'''output'''
<pre>
<pre>
A A
A A
/ \ ◄────1st tree / \
/ \ ◄════1st tree / \
/ \ / \
/ \ / \
/ \ / \
/ \ / \
B C B C
B C B C
/ \ / 2nd tree────► / \ /
/ \ / 2nd tree════► / \ /
D E F D E F
D E F D E F
/ / \ / / \
/ / \ / / \
G H I G δ I
G H I G δ I


The A leaf is identical in both trees.
The A leaf is identical in both trees.
Retrieved from "https://rosettacode.org/wiki/Same_fringe"