https://github.com/oldk1331/fricas/commit/feb5c243a471ce24dc1e614b923129be58607cd0.patch
add missing function hash for Tree,
add missing function hash, map, distance for BinaryTreeCategory,
where distance is copied from Tree.
diff --git a/src/algebra/tree.spad b/src/algebra/tree.spad
index 4734915..870fa6d 100644
--- a/src/algebra/tree.spad
+++ b/src/algebra/tree.spad
@@ -130,6 +130,12 @@ Tree(S : SetCategory) : T==C where
u := [parts c for c in children t]
u = empty() => [value t]
cons(value t,"append"/u)
+ hashUpdate!(s : HashState, t : %) : HashState ==
+ t case empty => s
+ s := hashUpdate!(s, value t)
+ for subt in children t repeat
+ s := hashUpdate!(s, subt)
+ s
---Functions that guard against cycles: =, #, copy-------------
@@ -335,6 +341,9 @@ BinaryTreeCategory(S : SetCategory) : Category ==_
copy t ==
empty? t => empty()
node(copy left t, value t, copy right t)
+ map(f ,t) ==
+ empty? t => empty()
+ node(map(f, left t), f value t, map(f, right t))
map!(f, t) ==
empty? t => t
t.value := f(t.value)
@@ -349,6 +358,21 @@ BinaryTreeCategory(S : SetCategory) : Category ==_
k = cycleTreeMax and cyclic? t => error "cyclic binary tree"
k := treeCount(left t, k)
treeCount(right t, k)
+ distance1(t1 : %, t2 : %) : Integer ==
+ t1 = t2 => 0
+ empty? t2 => -1
+ u := [n for t in children t2 | (n := distance1(t1, t)) >= 0]
+ #u > 0 => 1 + "min"/u
+ -1
+ distance(t1, t2) ==
+ n := distance1(t1, t2)
+ n >= 0 => n
+ distance1(t2, t1)
+ hashUpdate!(s : HashState, t : %) : HashState ==
+ empty? t => s
+ s := hashUpdate!(s, value t)
+ s := hashUpdate!(s, left t)
+ hashUpdate!(s, right t)
)abbrev domain BTREE BinaryTree
++ Description: \spadtype{BinaryTree(S)} is the domain of all
https://github.com/oldk1331/fricas/commit/d0f06984e5db8227f51d7f7b1d9192ff260d67f4.patch
small code fixed in tree.spad
https://github.com/oldk1331/fricas/commit/6d386abc7ad3ddf95368e7d83a8b8549c85937a9.patch
fix typos and documentation errors in tree.spad
https://github.com/oldk1331/fricas/commit/62c23519a805b8e882a00004719704cbb0af7885.patch
use more efficient Rep for BinaryTree
diff --git a/src/algebra/tree.spad b/src/algebra/tree.spad
index bacd254..44b5b53 100644
--- a/src/algebra/tree.spad
+++ b/src/algebra/tree.spad
@@ -390,36 +390,37 @@ BinaryTree(S : SetCategory) : Exports ==
Implementation where
++ binaryTree(l, v, r) creates a binary tree with
++ value v and left subtree l and right subtree r.
Implementation == add
- Rep := List Tree S
- import from List Tree S
+ Rep := Union(node:Record(value: S, left: %, right: %), empty:"empty")
+ import from Record(value: S, left: %, right: %)
- t1 = t2 == (t1::Rep) =$Rep (t2::Rep)
- empty()== ([] ::Rep):: %
- node(l, v, r) == cons(tree(v, l::Rep), r::Rep)
+ empty() == ["empty"]
+ empty? t == t case empty
+ -- equality '=' is implemented by default in BinaryRecursiveAggregate
+ node(l, v, r) == [[v, l, r]]
binaryTree(l, v, r) == node(l, v, r)
binaryTree(v : S) == node(empty(), v, empty())
- empty? t == empty?(t)$Rep
- leaf? t == empty? t or empty? left t and empty? right t
+ leaf? t == empty? t or empty? left t and empty? right t
right t ==
empty? t => error "binaryTree:no right"
- rest t
+ t.node.right
left t ==
empty? t => error "binaryTree:no left"
- children first t
- value t==
+ t.node.left
+ value t ==
empty? t => error "binaryTree:no value"
- value first t
- setvalue! (t, nd)==
+ t.node.value
+ setvalue!(t, nd) ==
empty? t => error "binaryTree:no value to set"
- setvalue!(first(t::Rep), nd)
+ t.node.value := nd
nd
- setleft!(t1, t2) ==
+ setleft!(t1:%, t2:%):% ==
empty? t1 => error "binaryTree:no left to set"
- setchildren!(first(t1::Rep), t2::Rep)
+ t1.node.left := t2
t1
setright!(t1, t2) ==
empty? t1 => error "binaryTree:no right to set"
- setrest!(t1 :: Rep, t2)
+ t1.node.right := t2
+ t1
)abbrev domain BSTREE BinarySearchTree
++ Description: BinarySearchTree(S) is the domain of
https://github.com/oldk1331/fricas/commit/7cace3e5671aae044bbe583f78e2cb4cfc85fb41.patch
some whitespace clean up in tree.spad
--
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.
