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 fricas-devel+unsubscr...@googlegroups.com. To post to this group, send email to fricas-devel@googlegroups.com. 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)