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.

  1. slib-wt-tree
  2. Library
    1. Tree types
    2. Constructors
    3. Predicates
    4. Size
    5. Accessors
    6. Iteration
    7. Subtrees
    8. Set theory operations
    9. Destructive operations
    10. Exceptions
  3. About this egg
    1. Dependencies
    2. Author
    3. Maintainer
    4. Repository
    5. Version history
    6. License

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.

[procedure] (make-wt-tree-type key<?) -> wt-tree-type

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.

[procedure] (wt-tree-type? obj) -> boolean

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

[constant] number-wt-type

A standard tree type for trees with numeric keys.

[constant] string-wt-type

A standard tree type for trees with string keys.

Constructors

[procedure] (make-wt-tree tree-type) -> wt-tree

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

[procedure] (singleton-wt-tree tree-type key value) -> wt-tree

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
[procedure] (alist->wt-tree tree-type alist) -> wt-tree

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
[procedure] (wt-tree/add tree key value) -> wt-tree

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
[procedure] (wt-tree/delete tree key) -> wt-tree

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

[procedure] (wt-tree/delete-min tree key) -> wt-tree

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

[procedure] (wt-tree? obj) -> boolean

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

[procedure] (wt-tree/empty? tree) -> boolean

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

Size

[procedure] (wt-tree/size tree) -> integer

Returns the number of associations in tree.

Accessors

[procedure] (wt-tree/member? key tree) -> boolean

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

[procedure] (wt-tree/lookup tree key default) -> *

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))

[procedure] (wt-tree/index tree k) -> *
[procedure] (wt-tree/index-datum tree k) -> *
[procedure] (wt-tree/index-pair tree k) -> pair(*, *)

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))
[procedure] (wt-tree/min tree) -> *
[procedure] (wt-tree/min-datum tree) -> *
[procedure] (wt-tree/min-pair tree) -> pair(*, *)

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)
[procedure] (wt-tree/rank tree key) -> integer or #f

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

[procedure] (wt-tree/fold kons knil tree) -> *

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"))
[procedure] (wt-tree/for-each proc tree) -> unspecified

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

[procedure] (wt-tree/split< tree bound) -> wt-tree
[procedure] (wt-tree/split> tree bound) -> wt-tree

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

Set theory operations

[procedure] (wt-tree/union tree1 tree2) -> wt-tree

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.

[procedure] (wt-tree/intersection tree1 tree2) -> wt-tree

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.

[procedure] (wt-tree/difference tree1 tree2) -> wt-tree

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.

[procedure] (wt-tree/subset? tree1 tree2) -> boolean

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.

[procedure] (wt-tree/set-equal? tree1 tree2) -> boolean

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.

[procedure] (wt-tree/union-merge tree1 tree2 combine) -> wt-tree

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.

[procedure] (wt-tree/add! tree key value) -> unspecified

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

[procedure] (wt-tree/delete! tree key) -> unspecified

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

[procedure] (wt-tree/delete-min! tree) -> unspecified

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