Some example for the missing functions:
1) -> y := binarySearchTree [3,2,6,4,5,1]
(1) [[1,2,.],3,[[.,4,5],6,.]]
Type:
BinarySearchTree(PositiveInteger)
(2) -> map(x+->x+1,y)
Internal Error
The function map with signature hashcode is missing from domain
BinarySearchTree(PositiveInteger)
(2) -> hash y
Function: hashUpdate! : (HashState,%) -> HashState is missing from domain:
BinarySearchTree(PositiveInteger)
Internal Error
The function hashUpdate! with signature (HashState)(HashState)$ is
missing from domain BinarySearchTree(PositiveInteger)
(2) -> distance(y,y)
Internal Error
The function distance with signature hashcode is missing from domain
BinarySearchTree(PositiveInteger)
About the 'split' function for BinarySearchTree:
I modified the documentation of split to returns
[less, greater or equal]. I want to know if changes doc and
implementation to [less, greater, equal] is better.
What's the point of BinarySearchTree if we can't search?
I added search function for it:
diff --git a/src/algebra/tree.spad b/src/algebra/tree.spad
index c6d53d0..bd6eaa1 100644
--- a/src/algebra/tree.spad
+++ b/src/algebra/tree.spad
@@ -442,6 +442,9 @@ BinarySearchTree(S : OrderedSet) : Exports ==
Implementation where
++ split(x, b) splits binary search tree b into two trees,
++ one with elements less than x, the other with elements
++ greater than or equal to x.
+ search : (S, %) -> Union(S, "failed")
+ ++ search(x, b) returns value equals to x in binary search tree b,
+ ++ or fails when no such value exists.
Implementation == BinaryTree(S) add
Rep := BinaryTree(S)
binarySearchTree(u : List S) ==
@@ -466,6 +469,12 @@ BinarySearchTree(S : OrderedSet) : Exports ==
Implementation where
insertRoot!(x, t) ==
a := split(x, t)
node(a.less, x, a.greater)
+ search(x, t) ==
+ empty? t => "failed"
+ val := value t
+ x = val => val
+ x < val => search(x, left t)
+ search(x, right t)
)abbrev domain BTOURN BinaryTournament
++ Description: \spadtype{BinaryTournament(S)} is the domain of
It is intended to use for some Key-Value pair domains.
--
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.
