## 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.

## TOC »

## 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<?`procedureReturns 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?``obj`procedureReturns

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

`number-wt-type`constantA standard tree type for trees with numeric keys.

`string-wt-type`constantA standard tree type for trees with string keys.

### Constructors

`make-wt-tree``tree-type`procedureReturns a new, empty weight-balanced tree specialized on

*tree-type*.

`singleton-wt-tree``tree-type``key``value`procedureReterns 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``alist`procedureReturns 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``value`procedureReturns 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``key`procedureReturns 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``key`procedure*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?``obj`procedureReturns

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

`wt-tree/empty?``tree`procedureReturns

`#t`if*tree*contains no associations and`#f`otherwise.

### Size

`wt-tree/size``tree`procedureReturns the number of associations in

*tree*.

### Accessors

`wt-tree/member?``key``tree`procedureReturns

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

`wt-tree/lookup``tree``key``default`procedureReturns 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``k`procedure`wt-tree/index-datum``tree``k`procedure`wt-tree/index-pair``tree``k`procedure*tree*must not be empty, and*k*must be a positive exact integer.Returns the 0-based

*k*th association of*tree*in the sorted sequence of keys.`wt-tree/index`returns the*k*th key,`wt-tree/index-datum`returns the value associated with the*k*th key, and`wt-tree/index-pair`returns the*k*th 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``tree`procedure`wt-tree/min-datum``tree`procedure`wt-tree/min-pair``tree`procedure*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``key`procedureReturns 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``tree`procedureFolds

*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``tree`procedureTraverses

*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``bound`procedure`wt-tree/split>``tree``bound`procedureReturns 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``tree2`procedureReturns 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``tree2`procedureReturns 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``tree2`procedureReturns 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``tree2`procedureReturns

`#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``tree2`procedureReturns

`#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``combine`procedure*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``value`procedureAssociates

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

`wt-tree/delete!``tree``key`procedureDeletes any association for

*key*from*tree*. (O(log*n*))

`wt-tree/delete-min!``tree`procedureDeletes 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

### 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.