(lispkit wt-tree)
Library (lispkit wt-tree) implements weight-balanced binary trees, a persistent, ordered key/value data structure. A wt-tree maps keys to values (like a hash table), but, unlike a hash table, keeps its entries ordered according to a user-supplied ordering predicate on the keys and provides efficient positional (rank-based) access, range splitting, and set-theoretic operations (union, intersection, difference, subset test) on the key sets of two trees. The implementation is an enhanced and bug-corrected variant of Stephen Adams' weight-balanced trees, following Yoichi Hirai and Kazuhiko Yamamoto, "Balancing weight-balanced trees", Journal of Functional Programming, 21(3):287-307, 2011.
WT-trees are persistent: operations such as wt-tree/add or wt-tree/delete return a new tree and leave the argument tree unchanged, sharing structure with it. For performance-sensitive code, destructive counterparts (wt-tree/add!, wt-tree/delete!, wt-tree/delete-min!) are also provided, mutating a tree in place.
Tree types
Every wt-tree is created with respect to a tree type, an object that bundles the strict ordering predicate (key<?) used to compare keys together with the tree-type-specific implementations of all wt-tree operations. Two trees can only be combined with each other (e.g. via wt-tree/union) if they were created with the very same tree type object.
(make-wt-tree-type key<?) 
Returns a new tree type whose keys are ordered by the strict ordering predicate key<?, i.e. a procedure of two arguments returning #t if and only if its first argument is strictly less than its second.
(make-comparator-wt-tree-type comp)
Returns a new tree type whose keys are ordered according to the ordering predicate of comparator comp (see comparator-ordering-predicate of library (lispkit comparator)).
(wt-tree-type? obj)
Returns #t if obj is a tree type (as created by make-wt-tree-type, make-comparator-wt-tree-type, or one of the predefined tree types below), #f otherwise.
wt-tree-type-tag 
Symbol representing the wt-tree-type type. The type-of procedure of library (lispkit type) returns a list starting with this symbol for tree type objects (not for wt-tree instances themselves; use wt-tree-type? respectively wt-tree? to distinguish the two).
number-wt-type
Predefined tree type ordering keys via <, i.e. for using real numbers as keys.
string-wt-type
Predefined tree type ordering keys via string<?, i.e. for using strings as keys.
string-ci-wt-type
Predefined tree type ordering keys via string-ci<?, i.e. for using strings as keys, ignoring case.
char-wt-type
Predefined tree type ordering keys via char<?, i.e. for using characters as keys.
char-ci-wt-type
Predefined tree type ordering keys via char-ci<?, i.e. for using characters as keys, ignoring case.
Constructing WT-Trees
(make-wt-tree)
(make-wt-tree type)
Returns a new, empty wt-tree of tree type type. The default for type is number-wt-type.
(singleton-wt-tree key value)
(singleton-wt-tree type key value)
Returns a new wt-tree of tree type type containing a single entry mapping key to value. The default for type is number-wt-type.
(alist->wt-tree type alist)
Returns a new wt-tree of tree type type, populated with the (key . value) associations of association list alist. If alist contains several entries for the same key, the entry that appears later in alist takes precedence.
(wt-tree? obj)
Returns #t if obj is a wt-tree, #f otherwise.
(wt-tree/copy tree)
Returns a new wt-tree with the same tree type, keys, and values as tree. Since wt-trees are persistent, wt-tree/copy is a cheap, O(1) operation; the copy initially shares its internal representation with tree, but the two trees evolve independently from each other, in particular with respect to the destructive operations wt-tree/add!, wt-tree/delete!, and wt-tree/delete-min!.
(wt-tree/valid? tree)
Returns #t if wt-tree tree satisfies the weight-balance and ordering invariants of the underlying tree implementation, #f otherwise. Since these invariants are maintained automatically by all wt-tree operations, this predicate is primarily useful for testing and debugging purposes.
Basic operations
(wt-tree/empty? tree)
Returns #t if wt-tree tree contains no entries, #f otherwise.
(wt-tree/size tree)
Returns the number of entries in wt-tree tree.
(wt-tree/add tree key value)
Returns a new wt-tree, like tree but with key mapped to value. If key is already present in tree, its associated value is replaced; tree itself remains unchanged.
(wt-tree/add! tree key value)
Destructively adds an entry mapping key to value to wt-tree tree, replacing any value that key was previously mapped to. Returns an unspecified result.
(wt-tree/delete tree key)
Returns a new wt-tree, like tree but with any entry for key removed. If key is not present in tree, a copy of tree is returned. tree itself remains unchanged.
(wt-tree/delete! tree key)
Destructively removes the entry for key, if any, from wt-tree tree. Returns an unspecified result.
(wt-tree/member? key tree)
Returns #t if wt-tree tree contains an entry for key, #f otherwise. Note that, unlike most other procedures of this library, wt-tree/member? expects key as its first and tree as its second argument.
(wt-tree/lookup tree key default)
Returns the value associated with key in wt-tree tree, or default if tree does not contain an entry for key.
Ordered and positional access
Since the entries of a wt-tree are kept in key order, they can also be accessed by their zero-based position (rank) in this order, from the smallest key (position 0) to the largest key (position (- (wt-tree/size tree) 1)).
(wt-tree/index tree index)
Returns the key at position index of wt-tree tree, in ascending key order. Signals an error if index is not in the range [0, (wt-tree/size tree)).
(wt-tree/index-datum tree index)
Like wt-tree/index, but returns the value associated with the key at position index instead of the key itself.
(wt-tree/index-pair tree index)
Like wt-tree/index, but returns a pair (key . value) for the entry at position index.
(wt-tree/rank tree key)
Returns the zero-based position of key within wt-tree tree in ascending key order, or #f if tree does not contain an entry for key. wt-tree/rank is the inverse operation of wt-tree/index.
(wt-tree/min tree)
Returns the smallest key of wt-tree tree. Signals an error if tree is empty.
(wt-tree/min-datum tree)
Returns the value associated with the smallest key of wt-tree tree. Signals an error if tree is empty.
(wt-tree/min-pair tree)
Returns a pair (key . value) for the entry with the smallest key of wt-tree tree. Signals an error if tree is empty.
(wt-tree/delete-min tree)
Returns a new wt-tree, like tree but with the entry for the smallest key removed. tree itself remains unchanged. Signals an error if tree is empty.
(wt-tree/delete-min! tree)
Destructively removes the entry for the smallest key from wt-tree tree. Returns an unspecified result. Signals an error if tree is empty.
Splitting trees
(wt-tree/split< tree key)
Returns a new wt-tree containing all entries of tree whose key is strictly less than key (the entry for key itself, if present, is excluded).
(wt-tree/split> tree key)
Returns a new wt-tree containing all entries of tree whose key is strictly greater than key (the entry for key itself, if present, is excluded).
Set-like operations
The following procedures combine two wt-trees based on their key sets. tree1 and tree2 must have been created with the same tree type object (e.g. both via number-wt-type, or both via the same tree type returned from make-wt-tree-type); otherwise, an error is signalled.
(wt-tree/union tree1 tree2)
Returns a new wt-tree containing all entries whose key is in tree1 or tree2 (or both). For a key present in both trees, the value from tree2 is used.
(wt-tree/union-merge tree1 tree2 merge)
Like wt-tree/union, but for a key present in both trees, the associated value is computed by calling merge with three arguments: the key, the value associated with the key in tree2, and the value associated with the key in tree1.
(wt-tree/intersection tree1 tree2)
Returns a new wt-tree containing all entries whose key is present in both tree1 and tree2. For each such key, the value from tree2 is used.
(wt-tree/difference tree1 tree2)
Returns a new wt-tree containing all entries of tree1 whose key is not present in tree2.
(wt-tree/subset? tree1 tree2)
Returns #t if the set of keys of tree1 is a subset of the set of keys of tree2, #f otherwise. Only key membership is compared; associated values are not taken into account.
(wt-tree/set-equal? tree1 tree2)
Returns #t if tree1 and tree2 have the same set of keys, #f otherwise. Just like wt-tree/subset?, only keys are compared, not values. wt-tree/set-equal? is implemented like this:
Traversal
(wt-tree/fold combiner init tree)
Combines all entries of wt-tree tree, in ascending key order, with combining function combiner, using init as the value for the smallest entry not yet part of the combined result. combiner is a procedure of three arguments, a key, its associated value, and the so-far accumulated result; it returns a new accumulated result. wt-tree/fold corresponds to a right fold over the ascending sequence of entries, i.e. it computes
for a tree with entries k₁ < k₂ < ... < kₙ. For instance, wt-tree/fold can be used to convert a wt-tree into a sorted association list:
(wt-tree/for-each proc tree)
Invokes proc once for every entry of wt-tree tree, in ascending key order, passing the key and the associated value as two arguments. The result of wt-tree/for-each is unspecified.
Last updated