This is the darts.lib.wbtree Reference Manual, version 0.1, generated automatically by Declt version 4.0 beta 2 "William Riker" on Mon May 15 04:46:17 2023 GMT+0.
The main system appears first, followed by any subsystem dependency.
darts.lib.wbtreeWeight-balanced binary tree
Dirk Esser
Dirk Esser
MIT
0.1
src (module).
Modules are listed depth-first from the system components tree.
darts.lib.wbtree/srcdarts.lib.wbtree (system).
wbtree (module).
darts.lib.wbtree/src/wbtreesrc (module).
package.lisp (file).
implementation.lisp (file).
Files are sorted by type and then listed depth-first from the systems components trees.
darts.lib.wbtree/darts.lib.wbtree.asddarts.lib.wbtree/src/wbtree/package.lispdarts.lib.wbtree/src/wbtree/implementation.lispdarts.lib.wbtree/darts.lib.wbtree.asddarts.lib.wbtree (system).
darts.lib.wbtree/src/wbtree/implementation.lisppackage.lisp (file).
wbtree (module).
define-wbtree (macro).
do-correlated-wbtree-nodes (macro).
do-wbtree (macro).
print-object (method).
wbtree (structure).
wbtree-ceiling-node (generic function).
wbtree-check-invariants (generic function).
wbtree-correlate (function).
wbtree-difference (generic function).
wbtree-empty-p (function).
wbtree-equal (generic function).
(setf wbtree-find) (setf expander).
wbtree-find (function).
wbtree-find-node (generic function).
wbtree-floor-node (generic function).
wbtree-fold (generic function).
wbtree-intersection (generic function).
wbtree-iterator (function).
wbtree-lower-boundary-node (function).
wbtree-map (generic function).
wbtree-maximum-node (function).
wbtree-minimum-node (function).
wbtree-node-key (function).
wbtree-node-left-subtree (function).
wbtree-node-right-subtree (function).
wbtree-node-value (function).
wbtree-rebalance (generic function).
wbtree-remove (generic function).
wbtree-size (function).
wbtree-test (generic function).
wbtree-union (generic function).
wbtree-update (generic function).
wbtree-upper-boundary-node (function).
wbtreep (function).
+weight+ (constant).
choose-right (function).
concat (function).
concat-3 (function).
define-wbtree-really (macro).
delete* (function).
delete-minimum (function).
make-wbtree (function).
node-count (reader).
node-key (reader).
node-left (reader).
node-right (reader).
node-value (reader).
rebalance (function).
rotate-once (function).
rotate-twice (function).
split-gt (function).
split-lt (function).
wbtree-ceiling-node-1 (function).
wbtree-check-invariants-1 (function).
wbtree-difference-1 (function).
wbtree-equal-1 (function).
wbtree-equal-2 (function).
wbtree-find-node-1 (function).
wbtree-floor-node-1 (function).
wbtree-fold-1 (function).
wbtree-intersection-1 (function).
wbtree-load-form (function).
wbtree-map-1 (function).
wbtree-rebalance-1 (function).
wbtree-remove-1 (function).
wbtree-union-1 (function).
wbtree-update-1 (function).
with-function (macro).
with-node (macro).
Packages are listed by definition order.
darts.lib.wbtreeGeneralized weight-balanced binary search trees. This
package provides a variant of the weight-balanced binary trees implemented
in package DARTS.LIB.PTREE. The variant exposed here can be used with arbitrary
key types, provided, a total order is defined on the keys, for which a suitable
predicate function (in the sense of #’<) exists.
common-lisp.
define-wbtree (macro).
do-correlated-wbtree-nodes (macro).
do-wbtree (macro).
wbtree (structure).
wbtree-ceiling-node (generic function).
wbtree-check-invariants (generic function).
wbtree-correlate (function).
wbtree-difference (generic function).
wbtree-empty-p (function).
wbtree-equal (generic function).
(setf wbtree-find) (setf expander).
wbtree-find (function).
wbtree-find-node (generic function).
wbtree-floor-node (generic function).
wbtree-fold (generic function).
wbtree-intersection (generic function).
wbtree-iterator (function).
wbtree-lower-boundary-node (function).
wbtree-map (generic function).
wbtree-maximum-node (function).
wbtree-minimum-node (function).
wbtree-node-key (function).
wbtree-node-left-subtree (function).
wbtree-node-right-subtree (function).
wbtree-node-value (function).
wbtree-rebalance (generic function).
wbtree-remove (generic function).
wbtree-size (function).
wbtree-test (generic function).
wbtree-union (generic function).
wbtree-update (generic function).
wbtree-upper-boundary-node (function).
wbtreep (function).
+weight+ (constant).
choose-right (function).
concat (function).
concat-3 (function).
define-wbtree-really (macro).
delete* (function).
delete-minimum (function).
make-wbtree (function).
node-count (reader).
node-key (reader).
node-left (reader).
node-right (reader).
node-value (reader).
rebalance (function).
rotate-once (function).
rotate-twice (function).
split-gt (function).
split-lt (function).
wbtree-ceiling-node-1 (function).
wbtree-check-invariants-1 (function).
wbtree-difference-1 (function).
wbtree-equal-1 (function).
wbtree-equal-2 (function).
wbtree-find-node-1 (function).
wbtree-floor-node-1 (function).
wbtree-fold-1 (function).
wbtree-intersection-1 (function).
wbtree-load-form (function).
wbtree-map-1 (function).
wbtree-rebalance-1 (function).
wbtree-remove-1 (function).
wbtree-union-1 (function).
wbtree-update-1 (function).
with-function (macro).
with-node (macro).
Definitions are sorted by export status, category, package, and then by lexicographic order.
wbtree-find (function).
Tests, whether ‘node’ represents an empty tree.
Finds the value associated with ‘key’ in ‘tree’. This function
returns two values: the value associated with ‘key’ as primary
value or ‘default’, if no matching node could be found. The second
value is a generalized boolean value, which indicates, whether
the node was found or not.
This function can be used with ‘setf’. In this case, the form
of the ‘tree’ argument must be itself a ‘setf’-able place, which
will be updated to hold the modified copy of the tree; the original
tree value is not modified in any way.
Answers the node with the largest (in the sense of the subtype’s comparison function) key present in ‘tree’.
Answers the node with the smallest (in the sense of the subtype’s comparison function) key present in ‘tree’.
Obtains the key associated with ‘node’ If ‘node’ is the empty tree, raises a condition of type ‘simple-error’.
Obtains the left subtree of ‘node’ or ‘node’ itself, if it is the empty tree
Obtains the right subtree of ‘node’ or ‘node’ itself, if it is the empty tree
Obtains the value associated with ‘node’. If ‘node’ is the empty tree, raises a condition of type ‘simple-error’.
Answers the number of valid key/value pairs contained in ‘tree’
Answers the node in ‘tree‘, whose key is the smallest key
greater than or equal to ‘key‘. Returns nil, if there is no such node in
the given tree.
Answers a copy of ‘tree1’, in which all entries have been removed, which match keys present in ‘tree2’.
Answers the node of ‘tree‘, whose key matches the given ‘key‘ value or nil, if no matching node exists.
Answers the node in ‘tree‘, whose key is the largest key
less than or equal to ‘key‘. Returns nil, if there is no such node in the
given tree.
Applies ‘function’ to all nodes in ‘tree’.
If ‘direction’ is ‘:forward’, then only those nodes are visited,
whose keys are greater than or equal to ‘start’ and less than ‘end’;
traversal will be in proper tree order. This is the default.
If ‘direction’ is ‘:backward’, then only those nodes are visited,
whose keys are less then or equal to ‘start’, and greater then ‘end’,
and the traversal will happen in the opposite of the normal tree
order.
If ‘associativity’ is ‘:left’ (the default), the function is called
with the value of its last invocation as first, and the current
node as second argument. If ‘associativity’ is ‘:right’, then the
arguments are exchanged, i.e., the node will be the first argument,
and the accumulated value will be the second. On the first invocation,
the function receives the ‘initial-value’ as accumulator value.
This function returns the last value returned by ‘function’, or
‘initial-value’, if the function is not called at all (e.g., because
the selected key range is empty).
Example:
(wbtree-fold #’cons some-tree :associativity :right :direction :backward)
will yield a list of all tree nodes in proper tree order.
Answers the tree, which is the intersection of ‘tree1’ and
‘tree2’, which must both be WB trees of the same subtype. The
resulting tree contains entries for all keys, which are present
in ‘tree1’ as well as ‘tree2’.
The ‘combiner’ function determines, which value will be associated
with the keys in the resulting tree. It is called with three arguments,
the key, the associated value in ‘tree1’, and the associated value in
‘tree2’. Whatever value it returns will be used as the value for the
key in the resulting tree.
The default combiner function always answers the value from ‘tree2’, discarding the value in ‘tree1’.
Maps ‘function’ across all nodes of ‘tree’. If the value of
‘direction’ is :forward (the default), then the nodes are visited
in proper tree order (i.e., in ascending key order as determined
by the tree’s comparison function). If the value is :backward, then
the nodes are visited in the opposite order.
If ‘start’ is provided, traversal starts at the smallest key, which
is greater than or equal to ‘start’, when direction is :forward, or
with the node, whose key is the largest still less than or equal to
‘start’, if ‘direction’ is :backward. The start node is passed to
‘function’.
If ‘end’ is provided, traversal stops at the node with smallest key,
which is larger than or equal to ‘end’ when iterating in :forward
direction, or at the node with the largest key still smaller than or
equal to ‘end’, when iterating backwards. In either case, the stop
node is not passed down to ‘function’.
If ‘collectp’, the primary return values of each invocation of ‘function’ are collected into a list, which is then returned as primary (and only) value of ‘wbtree-map’ itself. If not ‘collectp’, return values of ‘function’ are ignored, and wbtree-map returns nil.
Generates a fully balanced tree from ‘tree’. This function answers a tree of the same kind as ‘tree’, which contains the same key/value pairs as ‘tree’. However, the copy returned is fully balanced. Note, that this optimization often does not really pay off.
Answers a copy of ‘tree’, in which any association of ‘key’
has been removed. Returns ‘tree’ instead, if there is no entry
matching ‘key’ in ‘tree’.
This function returns as secondary the WB tree node, which has been removed in the copy returned as primary value, or nil, if no matching node was found.
Answers the tree, which is the union of ‘tree1’ and ‘tree2’, which must both be WB trees of the same subtype. The resulting tree contains entries for all keys, which are present in either ‘tree1’ or ‘tree2’ (or both). If a key is present in both trees, the resulting tree will associate it with the value, which is chosen by function ‘combiner’, which must accept three arguments:
1. the key present in both trees
2. the associated value in ‘tree1’
3. the associated value in ‘tree2’.
The value returned by ‘combiner’ will then be used as the value to associate with the overlapping key in the result tree. The default combiner function always yields the value in ‘tree2’, and discards the value from ‘tree1’.
Returns a copy of tree, in which ‘key’ has been associated with
‘value’, potentially replacing any previous binding for ‘key’ in
‘tree’. If there is already an association of ‘key’ in tree with
a value equal to ‘value’ (which is determined via predicate
function ‘test’), then the original tree is returned instead. The
default value of ‘test’ is eql.
This function returns a secondary value, which indicates, which
changes have been performed in the resulting tree when compared
to the original ‘tree’. Possible values are:
- ‘nil’, if there was already a suitable association for ‘key’ and
‘value’ in ‘tree’.
- ‘t’, if the key was not present in ‘tree’, and a new assocation
has been added.
- a node object, which is the node, that has been replaced by
one containing the new association.
Weight balanced binary tree. This structure defines the basic
building blocks for the nodes of a WB tree. Each node consists
of the following information:
- key: the node’s key value. The value of this field is undefined
for the node representing an empty tree.
- value: the value associated with ‘key’. The actual value is
undefined, if the node is representing the empty tree.
- count: number of key/value pairs in this node, i.e., 0, if this
is the empty node, and 1 + left-count + right-count otherwise.
- left: the left subtree. Either the empty tree, or a proper WB
tree such, that all keys are "less than" this node’s key.
- right: the right subtree. Either the empty tree, or a proper WB
tree such, that all keys are greater than" this node’s key.
Applications deal only with struct types, which are derived from this one via ‘:include’.
| Jump to: | (
C D F G M N P R S W |
|---|
| Jump to: | (
C D F G M N P R S W |
|---|
| Jump to: | +
C N S |
|---|
| Jump to: | +
C N S |
|---|
| Jump to: | D F I M P S W |
|---|
| Jump to: | D F I M P S W |
|---|