insert and delete

1 files changed, 72 insertions, 13 deletions

diff --git a/doc/mcgoron.weight-balanced-trees.internal.scm b/doc/mcgoron.weight-balanced-trees.internal.scm
index 8baf5e7..231ee7b 100644
--- a/doc/mcgoron.weight-balanced-trees.internal.scm
+++ b/doc/mcgoron.weight-balanced-trees.internal.scm
@@ -1,6 +1,7 @@
 (((name . "wb-tree-node?")
   (signature lambda (x) => boolean?)
-  (desc "Returns true if `x` is a node in a weight-balanced tree."))
+  (desc "Returns true if `x` is a node in a weight-balanced tree.
+This porcedure does not check that the node itself is balanced: see `balanced?`."))
  ((name . "non-null-wb-tree-node?")
   (signature lambda (x) => boolean?)
   (desc "Returns true if `x` is a node with data and children."))
@@ -20,7 +21,7 @@
   (signature lambda ((wb-tree-node? x)) => boolean?)
   (desc "Recursively traverses `x` and checks if it is weight balanced."))
  ((name . "in-order-vector->node")
-  (signature lambda ((vector? x)) => wb-tree-node?)
+  (signature lambda ((vector? x)) => balanced?)
   (desc "
 * It is an error if `x` is not in order.
 
@@ -30,8 +31,7 @@ elements of `x`."))
   (signature lambda ((wb-tree-node? x)) => list?)
   (desc "Returns a list of all elements of `x` in order."))
  ((name . "join")
-  (signature lambda (data (wb-tree-node? left) (wb-tree-node? right))
-             => non-null-wb-tree-node?)
+  (signature lambda (data (balanced? left) (balanced? right)) balanced?)
   (desc "
 * It is an error if `left` or `right` are not balanced.
 * It is an error if any element of `left` is greater than or equal to
@@ -44,21 +44,20 @@ elements of `x`."))
 Returns a balanced tree containing all elements of `left` and `right`
 with `data`."))
  ((name . "join2")
-  (signature lambda ((wb-tree-node? left) (wb-tree-node? right))
-             => wb-tree-node?)
+  (signature lambda ((balanced? left) (balanced? right)) balanced?)
   (desc "
 * It is an error if any element in `left` is greater than or equal to any
   element in `right`.
 
 Returns a new tree with the elements of `left` and `right`."))
  ((name . "split")
-  (signature lambda ((comparator? cmp) (wb-tree-node? tree) key (procedure? default))
-             => (values wb-tree-node? * wb-tree-node?))
+  (signature lambda ((comparator? cmp) (balanced? tree) key (procedure? default))
+             => (values balanced? * balanced?))
+  (subsigs (default lambda (() *)))
   "
 * It is an error if any element of `tree` is not comparable by `cmp`.
 * It is an error if `key` is not comparable by `cmp`.
 * It is an error if `cmp` does not have an order.
-* It is an error if `default` is not a thunk.
 
 Returns two trees, one of all values to the left of `key`, and one with
 all values to the right of `key`.
@@ -66,12 +65,72 @@ all values to the right of `key`.
 If a value that compares equal to `key` is found, that value is returned.
 Otherwise the result of calling `default` with no arguments is returned.")
  ((name . "search")
-  (signature case-lambda ((((wb-tree-node? tree) (comparator? cmp) key) *)
-                          (((wb-tree-node? tree) (comparator? cmp) key (procedure? default)) *)))
+  (signature case-lambda ((((comparator? cmp) (balanced? tree) key) *)
+                          (((comparator? cmp) (balanced? tree) key (procedure? default)) *)))
+  (subsigs (default (lambda () *)))
   (desc "
 * It is an error if `cmp` does not order `key` and all elements in `tree`.
-* It is an error if `default` is not a thunk.
 
 Searches `tree` for `key` using `cmp`. If a node contains data that compares equal
 to `key`, return that data. Otherwise, tail call `default.` If `default` is not
-supplied, the function returns `#f`.")))
\ No newline at end of file
+supplied, the function returns `#f`."))
+ ((name . "union")
+  (signature lambda ((comparator? cmp) (balanced? left) (balanced? right)) balanced?)
+  (desc "
+* It is an error if `cmp` does not order the elements in `left` and `right`.
+
+Return a weight-balanced tree with the elements of `left` and `right`. If
+there is an element in `left` that compares equal to an element in `right`,
+then the element in `left` is kept and the element in `right` is discarded.
+"))
+ ((name . "intersection")
+  (signature lambda ((comparator? cmp) (balanced? left) (balanced? right)) balanced?)
+  (desc "
+* It is an error if `cmp` does not order the elements in `left` and `right`.
+
+Return a weight-balanced tree with only the elements of `left` that compare
+equal to an element of `right`.
+"))
+ ((name . "difference")
+  (signature lambda ((comparator? cmp) (balanced? left) (balanced? right)) balanced?)
+  (desc "
+* It is an error if `cmp` does not order the elements in `left` and `right`.
+
+Return a weight-balanced tree with only the elements of `left` that do not
+compare equal to an element of `right`.
+"))
+ ((name . "update")
+  (signature
+   lambda ((comparator? cmp) (balanced? set) to-search (procedure? on-found) (procedure? on-not-found)) balanced?)
+  (subsigs
+   (on-not-found lambda () balanced?)
+   (on-found lambda (*) *))
+  (desc "
+* It is an error if `cmp` does not order the elements of `set`, the
+  elements of the tree returned from `on-found`, and the element
+  returned from `on-not-found`.
+
+Search `set` for an element that compares equal to `to-search`. If an
+element `E` is found that compares equal to `to-search`, then
+`(on-found E)` is evaluated and the resulting value is placed into the
+tree. If no element is found, then `(on-not-found)` is evaluated and the
+resulting node is inserted into the tree.
+"))
+ ((name . "delete")
+  (signature
+   lambda ((comparator? cmp) element (balanced? set)) balanced?)
+  (desc "
+* It is an error if `cmp` does not order the elements of `set` and the
+  value `element`.
+
+Search `set` for an element `E` that compares equal to `element`. If `E`
+is found, the returned tree does not have `E`. Otherwise the returned
+tree has the same number of elements."))
+ ((name . "every")
+  (signature
+   lambda ((procedure? predicate?) (wb-tree-node? tree)) *)
+  (subsigs
+   (predicate? lambda (*) *))
+  (desc "
+Calls `predicate?` on each element of `tree` in an arbitrary order. If all
+calls return a truthy value, return a truthy value. Otherwise return `#f`.")))
\ No newline at end of file