chickadee » slib-wt-tree

slib-wt-tree

This egg is a CHICKEN port of the (slib wt-tree) library. It provides weight-balanced trees, a kind of self-balancing binary trees which are excellent for working with large collections of ordered-key/value-structured data.

While the name of this egg is slib-wt-tree, the module it provides is (slib wt-tree). This difference is due to the names allowed by the Henrietta egg server.

This egg is licensed under the GNU General Public License, version 2.

Library

A weight-balanced tree is a self-balancing binary search tree. Abstractly, it is a dictionary, a set of associations between objects of a key type and of a value type. In this implementation, all keys must be of the same type, but value types may differ within a single tree.

Weight-balanced trees are an easy drop-in replacement for alists, basic binary trees, hash-tables, and other familiar dictionary structures. Since they're also ordered by key, they can also be used to implement queues.

Weight-balanced tree operations marked "O(log n)" in this document run in time proportional to the logarithm of the number of associations in the given tree.

Tree types

wt-trees are constructed in two steps: First, you create a tree type, an object which holds key-type information, and second, you construct a new tree using this type object. A few tree-types are built-in.

make-wt-tree-type key<?procedure

Returns a new tree type based on the ordering predicate key?, which compares two key values and returns a boolean. key? should be a total ordering; for all key values a, b, and c, the following must hold:

(key<? a a)  ; -> #f
(and (key<? a b) (key<? b a))  ; -> #f
(if (and (key<? a b) (key<? b c))
    (key <? a c)
    #t)
 ; -> #t

Two wt-trees are compatible if their tree type objects are eqv?, so trees whose types result from different calls to make-wt-tree-type are always incompatible.

wt-tree-type? objprocedure

Returns #t if obj is a tree type object and #f otherwise.

number-wt-typeconstant

A standard tree type for trees with numeric keys.

string-wt-typeconstant

A standard tree type for trees with string keys.

Constructors

make-wt-tree tree-typeprocedure

Returns a new, empty weight-balanced tree specialized on tree-type.

singleton-wt-tree tree-type key valueprocedure

Reterns a new weight-balanced tree with type tree-type and containing the single association (key, value).

Example:

(singleton-wt-tree number-wt-type 1 2) ; -> wt-tree

alist->wt-tree tree-type alistprocedure

Returns a new weight-balanced tree with type tree-type and containing all the associations of alist.

Example:

(alist->wt-tree number-wt-type '((1 . 2) (2 . 4)
(3 . 6)))
; -> wt-tree

wt-tree/add tree key valueprocedure

Returns a new tree containing all the associations of tree as well as the association (key, value). Any existing association for key is replaced. (O(log n))

Example:

(let ((t (wt-tree/add (alist->wt-tree number-wt-type
                                      '((1 . 2) (2 . 4)))
                      5
                      10)))
  (wt-tree/lookup t 5 #f))  ; -> 10

wt-tree/delete tree keyprocedure

Returns a new tree containing all the associations of tree except for the association for key, if one exists. (O(log n))

wt-tree/delete-min tree keyprocedure

tree must not be empty.

Returns a new tree containing all the associations of tree except the one with the least key in the sorted sequence of keys. (O(log n))

Predicates

wt-tree? objprocedure

Returns #t if obj is a weight-balanced tree and #f otherwise.

wt-tree/empty? treeprocedure

Returns #t if tree contains no associations and #f otherwise.

Size

wt-tree/size treeprocedure

Returns the number of associations in tree.

Accessors

wt-tree/member? key treeprocedure

Returns #t if tree contains an association for key and #f otherwise. (O(log n))

wt-tree/lookup tree key defaultprocedure

Returns the value associated with key in tree, or default (which can be any Scheme value) if there is no such association. (O(log n))

wt-tree/index tree kprocedure

wt-tree/index-datum tree kprocedure

wt-tree/index-pair tree kprocedure

tree must not be empty, and k must be a positive exact integer.

Returns the 0-based kth association of tree in the sorted sequence of keys. wt-tree/index returns the kth key, wt-tree/index-datum returns the value associated with the kth key, and wt-tree/index-pair returns the kth association as a (KEY . VALUE) pair. If k ≥ (wt-tree/size tree), an error is signalled. (O(log n))

Example:

(let ((t (alist->wt-tree string-wt-type
                         '(("rincewind" . 23)
                           ("twoflower" . 11)
                           ("the luggage" . 31)))))
  (list (wt-tree/index t 1)
        (wt-tree/index-datum t 0)
        (wt-tree/index-pair t 2)))
; -> ("the luggage" 23 ("twoflower" . 11))

wt-tree/min treeprocedure

wt-tree/min-datum treeprocedure

wt-tree/min-pair treeprocedure

tree must not be empty.

Returns the association of tree with the least key in the sorted sequence of keys. wt-tree/min returns the least key, wt-tree/min-datum returns the value associated with the least key, and wt-tree/min-pair returns the least association as a (KEY . VALUE) pair. (O(log n))

(wt-tree/min tree) is equivalent to (wt-tree/index tree 0), and similarly for the other forms.

(let ((t (alist->wt-tree string-wt-type
                         '(("rincewind" . 23)
                           ("twoflower" . 11)
                           ("the luggage" . 31)))))
  (list (wt-tree/min t)
        (wt-tree/min-datum t)))
; -> ("rincewind" 23)

wt-tree/rank tree keyprocedure

Returns the 0-based position of key in the sorted sequence of keys of tree. If key has no association in tree, then #f is returned instead.

(let ((t (alist->wt-tree string-wt-type
                         '(("rincewind" . 23)
                           ("twoflower" . 11)
                           ("the luggage" . 31)))))
  (wt-tree/rank "twoflower"))
; -> 1

Iteration

wt-tree/fold kons knil treeprocedure

Folds tree, applying kons to the key, value, and the accumulated result, in that order, at each step. knil is passed to kons as the initial accumulator value. tree is traversed in reverse order.

Provided kons runs in O(1) time, wt-tree/fold takes time proportional to the size of tree.

Example:

(let ((t (alist->wt-tree string-wt-type
                         '(("rincewind" . 23)
                           ("twoflower" . 11)
                           ("the luggage" . 31)))))
  (list (wt-tree/fold (lambda (_k v sum) (+ v sum)) 0 t)
        (wt-tree/fold (lambda (k _v keys) (cons k keys))
                      '()
                      t)))
; -> (65 ("rincewind" "the luggage" "twoflower"))

wt-tree/for-each proc treeprocedure

Traverses tree in increasing order of key, applying proc to the key and value of each association. Any values returned by proc are ignored.

Provided proc runs in O(1) time, wt-tree/for-each takes time proportional to the size of tree.

(let ((t (alist->wt-tree string-wt-type
                         '(("rincewind" . 23)
                           ("twoflower" . 11)
                           ("the luggage" . 31))))
      (acc 0))
  (wt-tree/for-each (lambda (_k v)
                      (set! acc (+ v acc)))
                    t)
  acc)
; -> 65

Subtrees

wt-tree/split< tree boundprocedure

wt-tree/split> tree boundprocedure

Returns a new tree containing the associations of tree whose keys are less than/greater than bound. (O(log n))

Set theory operations

wt-tree/union tree1 tree2procedure

Returns a new tree containing all the associations from both tree1 and tree2. When both trees have an association for the same key, the returned tree contains the one from tree1.

The worst-case time required by this operation is proportional to the sum of the sizes of both trees. If the minimum key of one tree is greater than the maximum key of the other tree then the time required is at worst proportional to the logarithm of the size of the larger tree.

wt-tree/intersection tree1 tree2procedure

Returns a new tree containing all and only those associations from tree1 which also have associations in tree2. All the associations in the result are drawn from tree1.

The time required by this operation is at worst proportional to the sum of the sizes of the trees.

wt-tree/difference tree1 tree2procedure

Returns a new tree containing all and only those associations from tree1 whose keys do not have an association in tree2.

The time required by this operation is at worst proportional to the sum of the sizes of the trees.

wt-tree/subset? tree1 tree2procedure

Returns #t if the key of each association in tree1 has an association in tree2, and #f otherwise. Note that wt-tree/subset? only compares keys.

The time required by this operation is at worst proportional to the size of tree1.

wt-tree/set-equal? tree1 tree2procedure

Returns #t if and only if the key of each association in tree1 has an association in tree2, and vice-versa. Note that wt-tree/set-equal? only compares keys.

wt-tree/union-merge tree1 tree2 combineprocedure

combine is a procedure of three arguments returning a single value.

Returns a new tree containing all the associations from both tree1 and tree2. When both trees have an association for the same key, combine is applied to the key and to both associated values, in that order, and the result is associated with the key.

Assuming that combine runs in O(1) time, the worst-case time required by this operation is proportional to the sum of the sizes of both trees. If the minimum key of one tree is greater than the maximum key of the other tree then the time required is at worst proportional to the logarithm of the size of the larger tree.

Example:

(let ((t1 (singleton-wt-tree number-wt-type 4 8))
      (t2 (singleton-wt-tree number-wt-type 4 71)))
  (wt-tree/lookup
   (wt-tree/union-merge t1
                        t2
                        (lambda (_key v1 v2)
                          (+ v1 v2)))
   4
   #f))
; -> 79

Destructive operations

All of the following procedures mutate their wt-tree argument and return an unspecified value. They should be called for their effects alone.

wt-tree/add! tree key valueprocedure

Associates key with value in tree. If tree already has an association for key, then it is replaced. (O(log n))

wt-tree/delete! tree keyprocedure

Deletes any association for key from tree. (O(log n))

wt-tree/delete-min! treeprocedure

Deletes the association of tree with the least key, in the sense of the tree's ordering predicate. (O(log n))

Exceptions

Following CHICKEN's libraries, procedures from this egg abort with (exn type) and (exn bounds) conditions when type- and bounds-checking assertions fail, respectively. See the Module (chicken condition) page for more details.

About this egg

Dependencies

The typed-records egg is required.

To run the included tests, you'll also need the test and test-generative eggs.

Author

Stephen Adams.

Ported to CHICKEN 5 and edited by Wolfgang Corcoran-Mathe.

Maintainer

Wolfgang Corcoran-Mathe

Contact: wcm at sigwinch dot xyzzy without the zy

Repository

GitHub

Version history

Versions before 0.1.5 were bookkeeping fixes.

0.1.5

(2022-05-26) Initial release.

0.1.6

(2022-08-11) Rework exceptions, add more checks.

License

GNU GPL version 2