$SPAD/src/input tree.input

Timothy Daly December 3, 2016

Abstract

Contents

2

1 License

— license —

--Copyright The Numerical Algorithms Group Limited 1991.

———-

— * —

)set break resume
)spool tree.output
)set message test on
)set message auto off
)clear all
--S 1 of 35
bt := BinaryTree INT
--R
--R
--R   (1)  BinaryTree(Integer)
--R                                                                 Type: Domain
--E 1
--S 2 of 35
ebtree:=empty()$(BTREE INT)
--R
--R
--R   (2)  []
--R                                                    Type: BinaryTree(Integer)
--E 2
--S 3 of 35
insleaf:(INT,bt)->bt
--R
--R                                                                   Type: Void
--E 3
--S 4 of 35
insleaf(x,t)==
     empty? t=> binaryTree(x)$(BTREE INT)
     x> value t => binaryTree(left t,value t,insleaf(x,right t))
     binaryTree(insleaf(x,left t),value t,right t)
--R
--R                                                                   Type: Void
--E 4
--S 5 of 35
b:bt:=reduce(insleaf,[8,3,5,4,6,2,1,5,7],ebtree)
--R
--R   Compiling function insleaf with type (Integer,BinaryTree(Integer))

--R       -> BinaryTree(Integer)
--R
--R   (5)  [[[1,2,.],3,[[.,4,5],5,[.,6,7]]],8,.]
--R                                                    Type: BinaryTree(Integer)
--E 5
--S 6 of 35
bleaf x == reduce(insleaf,x,ebtree)
--R
--R                                                                   Type: Void
--E 6
--S 7 of 35
fln:bt-> List INT
--R
--R                                                                   Type: Void
--E 7
--S 8 of 35
fln t==
    empty? t => empty()$(List INT)
    concat(fln left t,concat(value t,fln right t))
--R
--R                                                                   Type: Void
--E 8
--S 9 of 35
fln b
--R
--R   Compiling function fln with type BinaryTree(Integer) -> List(Integer
--R      )
--R
--R   (9)  [1,2,3,4,5,5,6,7,8]
--R                                                          Type: List(Integer)
--E 9
--S 10 of 35
split:(INT,bt)->List bt
--R
--R                                                                   Type: Void
--E 10
--S 11 of 35
split(x,t)==
     empty? t=> [ebtree,ebtree]
     x> value t =>
            a:=split(x,right t)
            [binaryTree(left t,value t,a.1),a.2]
     a:=split(x,left t)
     [a.1,binaryTree(a.2,value t,right t)]

--R
--R                                                                   Type: Void
--E 11
--S 12 of 35
split(3,b)
--R
--R   Compiling function split with type (Integer,BinaryTree(Integer)) ->
--R      List(BinaryTree(Integer))
--R
--R   (12)  [[1,2,.],[[.,3,[[.,4,5],5,[.,6,7]]],8,.]]
--R                                              Type: List(BinaryTree(Integer))
--E 12
--S 13 of 35
insroot:(INT,bt)->bt
--R
--R                                                                   Type: Void
--E 13
--S 14 of 35
insroot(x,t)==
      a:=split(x,t)
      binaryTree(a.1,x,a.2)
--R
--R                                                                   Type: Void
--E 14
--S 15 of 35
broot x == reduce(insroot,x,ebtree)
--R
--R                                                                   Type: Void
--E 15
--S 16 of 35
a:List INT:=[8,3,9,4,6,2,1,5,7]
--R
--R
--R   (16)  [8,3,9,4,6,2,1,5,7]
--R                                                          Type: List(Integer)
--E 16
--S 17 of 35
l1:=bleaf a
--R
--R   Compiling function bleaf with type List(Integer) -> BinaryTree(
--R      Integer)
--R
--R   (17)  [[[1,2,.],3,[.,4,[5,6,7]]],8,9]
--R                                                    Type: BinaryTree(Integer)

--E 17
--S 18 of 35
r1:=broot reverse a
--R
--R   Compiling function broot with type List(Integer) -> BinaryTree(
--R      Integer)
--R   Compiling function insroot with type (Integer,BinaryTree(Integer))
--R       -> BinaryTree(Integer)
--R
--R   (18)  [[[1,2,.],3,[.,4,[5,6,7]]],8,9]
--R                                                    Type: BinaryTree(Integer)
--E 18
--S 19 of 35
(l1=r1)::Boolean
--R
--R
--R   (19)  true
--R                                                                Type: Boolean
--E 19
--S 20 of 35
broot a
--R
--R
--R   (20)  [[[.,1,[.,2,[3,4,.]]],5,6],7,[8,9,.]]
--R                                                    Type: BinaryTree(Integer)
--E 20
--S 21 of 35
bleaf reverse a
--R
--R
--R   (21)  [[[.,1,[.,2,[3,4,.]]],5,6],7,[8,9,.]]
--R                                                    Type: BinaryTree(Integer)
--E 21
--S 22 of 35
mg:(bt,bt)->bt
--R
--R                                                                   Type: Void
--E 22
--S 23 of 35
mg(x,y)==
    empty? x => y
    empty? y => x
    value x > value y => binaryTree(mg(y,left x),value x,right x)
    binaryTree(left y,value y,mg(x,right y))

--S 24 of 35
mg1:(INT,bt)->bt
--R
--R                                                                   Type: Void
--E 24
--S 25 of 35
mg1(x,t)==mg(binaryTree x,t)
--R
--R                                                                   Type: Void
--E 25
--S 26 of 35
btourn:List INT-> bt
--R
--R                                                                   Type: Void
--E 26
--S 27 of 35
btourn x == reduce(mg1,x,ebtree)
--R
--R                                                                   Type: Void
--E 27
--S 28 of 35
btourn a
--R
--R   Compiling function btourn with type List(Integer) -> BinaryTree(
--R      Integer)
--R   Compiling function mg with type (BinaryTree(Integer),BinaryTree(
--R      Integer)) -> BinaryTree(Integer)
--R   Compiling function mg1 with type (Integer,BinaryTree(Integer)) ->
--R      BinaryTree(Integer)
--R
--R   (28)  [[.,8,3],9,[[4,6,[[.,2,1],5,.]],7,.]]
--R                                                    Type: BinaryTree(Integer)
--E 28
--S 29 of 35
cmp:(List INT,List INT)-> Boolean
--R
--R                                                                   Type: Void
--E 29
--S 30 of 35
cmp(x,y)== x.2<y.2

--S 31 of 35
sort2 : List List INT -> List List INT
--R
--R                                                                   Type: Void
--E 31
--S 32 of 35
sort2 x== sort(cmp,x)
--R
--R                                                                   Type: Void
--E 32
--S 33 of 35
invert x==[i.1 for i in  sort2  [[k,l]
          for k in 1..#x for  l in x]]
--R
--R                                                                   Type: Void
--E 33
--S 34 of 35
broot a
--R
--R
--R   (34)  [[[.,1,[.,2,[3,4,.]]],5,6],7,[8,9,.]]
--R                                                    Type: BinaryTree(Integer)
--E 34
--S 35 of 35
btourn invert a
--R
--R   Compiling function sort2 with type List(List(Integer)) -> List(List(
--R      Integer))
--R   Compiling function invert with type List(Integer) -> List(Integer)
--R   Compiling function cmp with type (List(Integer),List(Integer)) ->
--R      Boolean
--R
--R   (35)  [[[.,7,[.,6,[2,4,.]]],8,5],9,[1,3,.]]
--R                                                    Type: BinaryTree(Integer)
--E 35
)spool
)lisp (bye)

———-

References^{[1] nothing}

9