This patch changes the Rep of Tree from
Union(node:Record(value: S, args: List %),empty:"empty")
to
Record(val : S, args: List %)
and uses "NIL$Lisp" to represent empty tree.
Before this patch,
(1) -> tree [1,2,3] pretend SEX
(1) (0 1 (0 2) (0 3))
And after:
(1) -> tree [1,2,3] pretend SEX
(1) (1 (2) (3))
So this patch can save some (maybe a third) memory.
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/fricas-devel.
For more options, visit https://groups.google.com/d/optout.
diff --git a/src/algebra/tree.spad b/src/algebra/tree.spad
index 07b140d3..3882da3e 100644
--- a/src/algebra/tree.spad
+++ b/src/algebra/tree.spad
@@ -21,54 +21,63 @@ Tree(S : SetCategory) : T==C where
tree : S -> %
++ tree(nd) creates a tree with value nd, and no children.
C== add
- Rep := Union(node:Record(value: S, args: List %),empty:"empty")
+ Rep := Record(val : S, args: List %)
- import from Record(value: S, args: List %)
-
- empty? t == t case empty
- empty() == ["empty"]
+ empty() == NIL$Lisp
+ empty? t == NULL(t)$Lisp
children t ==
- t case empty => error "cannot take the children of an empty tree"
- (t.node.args)@List(%)
+ empty? t => error "cannot take the children of an empty tree"
+ t.args
+
setchildren!(t, lt) ==
- t case empty => error "cannot set children of an empty tree"
- (t.node.args := lt;t pretend %)
+ empty? t => error "cannot set children of an empty tree"
+ t.args := lt
+ t
+
setvalue!(t, s) ==
- t case empty => error "cannot set value of an empty tree"
- (t.node.value := s;s)
+ empty? t => error "cannot set value of an empty tree"
+ t.val := s
+
count(n : S, t : %) ==
- t case empty => 0
+ empty? t => 0
i := +/[count(n, c) for c in children t]
value t = n => i + 1
i
+
count(fn : S -> Boolean, t : %) : NonNegativeInteger ==
- t case empty => 0
+ empty? t => 0
i := +/[count(fn, c) for c in children t]
fn value t => i + 1
i
+
map(fn, t) ==
- t case empty => t
+ empty? t => t
tree(fn value t, [map(fn, c) for c in children t])
+
map!(fn, t) ==
- t case empty => t
+ empty? t => t
setvalue!(t, fn value t)
for c in children t repeat map!(fn, c)
t
- tree(s : S, lt : List %) == [[s, lt]]
- tree(s : S) == [[s, []]]
+
+ tree(s : S, lt : List %) == [s, lt]
+ tree(s : S) == [s, []]
tree(ls : List S) ==
empty? ls => empty()
tree(first ls, [tree s for s in rest ls])
+
value t ==
- t case empty => error "cannot take the value of an empty tree"
- t.node.value
+ empty? t => error "cannot take the value of an empty tree"
+ t.val
+
child?(t1, t2) ==
empty? t2 => false
member?(t1, children t2)
+
distance1(t1 : %, t2 : %) : Integer ==
t1 = t2 => 0
- t2 case empty => -1
+ empty? t2 => -1
u := [n for t in children t2 | (n := distance1(t1, t)) >= 0]
#u > 0 => 1 + "min"/u
-1
@@ -76,30 +85,36 @@ Tree(S : SetCategory) : T==C where
n := distance1(t1, t2)
n >= 0 => n
distance1(t2, t1)
+
node?(t1, t2) ==
t1 = t2 => true
- t2 case empty => false
+ empty? t2 => false
any?((t : %) : Boolean +-> node?(t1, t), children t2)
+
any?(fn, t) == ---bug fixed
- t case empty => false
+ empty? t => false
fn value t => true
for c in children t | any?(fn, c) repeat return true
false
+
every?(fn, t) ==
- t case empty => true
+ empty? t => true
not fn value t => false
for c in children t | not every?(fn, c) repeat return false
true
+
member?(n, t) ==
- t case empty => false
+ empty? t => false
n = value t or any?((c : %) : Boolean +-> member?(n, c), children t)
+
parts t == --buggy?
- t case empty => empty()
+ empty? t => empty()
u := [parts c for c in children t]
- u = empty() => [value t]
+ empty? u => [value t]
cons(value t,"append"/u)
+
hashUpdate!(s : HashState, t : %) : HashState ==
- t case empty => s
+ empty? t => s
s := hashUpdate!(s, value t)
for subt in children t repeat
s := hashUpdate!(s, subt)
