/usr/share/axiom-20170501/src/algebra/BRAGG.spad is in axiom-source 20170501-3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 | )abbrev category BRAGG BinaryRecursiveAggregate
++ Author: Michael Monagan; revised by Manuel Bronstein and Richard Jenks
++ Date Created: August 87 through August 88
++ Date Last Updated: April 1991
++ Description:
++ A binary-recursive aggregate has 0, 1 or 2 children and serves
++ as a model for a binary tree or a doubly-linked aggregate structure
BinaryRecursiveAggregate(S) : Category == SIG where
S : Type
SIG ==> RecursiveAggregate S with
-- needs preorder, inorder and postorder iterators
left : % -> %
++ left(u) returns the left child.
elt : (%,"left") -> %
++ elt(u,"left") (also written: \axiom{a . left}) is
++ equivalent to \axiom{left(a)}.
right : % -> %
++ right(a) returns the right child.
elt : (%,"right") -> %
++ elt(a,"right") (also written: \axiom{a . right})
++ is equivalent to \axiom{right(a)}.
if % has shallowlyMutable then
setelt : (%,"left",%) -> %
++ setelt(a,"left",b) (also written \axiom{a . left := b}) is
++ equivalent to \axiom{setleft!(a,b)}.
setleft_! : (%,%) -> %
++ setleft!(a,b) sets the left child of \axiom{a} to be b.
setelt : (%,"right",%) -> %
++ setelt(a,"right",b) (also written \axiom{b . right := b})
++ is equivalent to \axiom{setright!(a,b)}.
setright_! : (%,%) -> %
++ setright!(a,x) sets the right child of t to be x.
add
cycleMax ==> 1000
elt(x,"left") == left x
elt(x,"right") == right x
leaf? x == empty? x or empty? left x and empty? right x
leaves t ==
empty? t => empty()$List(S)
leaf? t => [value t]
concat(leaves left t,leaves right t)
nodes x ==
l := empty()$List(%)
empty? x => l
concat(nodes left x,concat([x],nodes right x))
children x ==
l := empty()$List(%)
empty? x => l
empty? left x => [right x]
empty? right x => [left x]
[left x, right x]
if % has SetAggregate(S) and S has SetCategory then
node?(u,v) ==
empty? v => false
u = v => true
for y in children v repeat node?(u,y) => return true
false
x = y ==
empty?(x) => empty?(y)
empty?(y) => false
value x = value y and left x = left y and right x = right y
if % has finiteAggregate then
member?(x,u) ==
empty? u => false
x = value u => true
member?(x,left u) or member?(x,right u)
if S has SetCategory then
coerce(t:%): OutputForm ==
empty? t => "[]"::OutputForm
v := value(t):: OutputForm
empty? left t =>
empty? right t => v
r := coerce(right t)@OutputForm
bracket ["."::OutputForm, v, r]
l := coerce(left t)@OutputForm
r :=
empty? right t => "."::OutputForm
coerce(right t)@OutputForm
bracket [l, v, r]
if % has finiteAggregate then
aggCount: (%,NonNegativeInteger) -> NonNegativeInteger
#x == aggCount(x,0)
aggCount(x,k) ==
empty? x => 0
k := k + 1
k = cycleMax and cyclic? x => error "cyclic tree"
for y in children x repeat k := aggCount(y,k)
k
isCycle?: (%, List %) -> Boolean
eqMember?: (%, List %) -> Boolean
cyclic? x == not empty? x and isCycle?(x,empty()$(List %))
isCycle?(x,acc) ==
empty? x => false
eqMember?(x,acc) => true
for y in children x | not empty? y repeat
isCycle?(y,acc) => return true
false
eqMember?(y,l) ==
for x in l repeat eq?(x,y) => return true
false
if % has shallowlyMutable then
setelt(x,"left",b) == setleft_!(x,b)
setelt(x,"right",b) == setright_!(x,b)
|