Next: Introduction, Previous: (dir), Up: (dir) [Contents][Index]
This is the darts.lib.wbtree Reference Manual, version 0.1, generated automatically by Declt version 3.0 "Montgomery Scott" on Tue Dec 22 13:14:26 2020 GMT+0.
• Introduction | What darts.lib.wbtree is all about | |
• Systems | The systems documentation | |
• Modules | The modules documentation | |
• Files | The files documentation | |
• Packages | The packages documentation | |
• Definitions | The symbols documentation | |
• Indexes | Concepts, functions, variables and data types |
This project provides a few purely functional data structures. Right now, it provides:
Hash Tries: purely functional map, based on hashing. The implementation is derived from Phil Bagwell's paper "Ideal Hash Trees"
Weight-balanced Tree: a purely functional (sorted) map from strings to arbitrary values. The implementation is derived from S. Adams' paper "Implementing Sets Efficiently in a Functional Language"
The tree structures provided by this project are immutable, i.e., cannot be modified once they have been constructed. Mutation operations return newly constructed tree instances (which may actually share state with the original tree, to which the operation was applied).
The system darts.lib.wbtree
provides support for weight-balanced
binary trees, modelled after the paper "Implementing Sets Efficiently
in a Functional Language" by S. Adams.
Applications can define their own subtypes of the wbtree type, with a specialized comparison predicate for the actual key type.
Type wbtree
This is the base type for all weight-balanced binary trees. Every
new tree type introduced by a define-wbtree
form is a subtype
of this type.
Macro define-wbtree
This macro introduces a new subtype of wbtree
, as well as a
bunch of functions. This macro accepts two kinds of usage. The
simplified form exists primarily for backwards compatibility
reasons:
define-wbtree name predicate &optional docstring
It is equivalent to using the complex form
(define-wbtree name
(:test predicate)
(:constructor nil)
(:spread-constructor name)
(:documentation docstring))
The long form has the format
define-wbtree name clauses...
where name
is a symbol naming the new tree type, and each element
of clauses
may be one of
(:test function)
Identifies the test function which is used to compare keys. The given function must be a binary function, which answers true, if its first argument is strictly less than its second argument.
(:key function)
Provides a transformation function
, which is applied to keys
before they are processed further.
(:constructor name)
Declares the name of the generated standard constructor
to be name
. The constructor is a function of a single
optional argument, which is a list of key/value pairs in
property list style. The default constructor is named
make-NAME
. You may generate a constructor with the
default name by omitting this option or using a name of
t
. By specifying this option with a name of nil
, you
can suppress the generation of a constructor function.
(:spread-constructor name)
Declares the name of the generated "spread" constructor.
This function is just like the regular constructor above,
but takes the initial members as &rest
argument. The
default is to not generate a spread constructor, unless
this option is specified explicitly.
If you use a name of t
, the spread constructor is
generated using its default name, which is make-NAME*
.
By giving a name of nil
(the default), generation of
the spread constructor is disabled.
(:predicate name)
Provides the name of the type predicate function, which answers
true for any object, which is a wbtree of the newly defined type,
and false for any other value. If you supply nil
as the name,
then no type predicate is generated. If you supply t
(the default),
the predicate name follows the standard rules used by defstruct
.
(:documentation string)
Function wbtreep object
=> boolean
Answers true, if object
is a wbtree
instance, and false otherwise
Function wbtree-empty-p tree
=> boolean
Answers true, if wbtree instance tree
is empty, i.e., does not
contain any key/value pairs.
Function wbtree-size tree
=> integer
Answers the number of key/value pairs contained in wbtree instance
tree
.
Function wbtree-node-value tree
=> value
Returns the value stored in the tree node tree
. If tree
is empty,
signals a condition of type simple-error
.
Function wbtree-node-key tree
=> key
Returns the key stored in the tree node tree
. If tree
is empty,
signals a condition of type simple-error
.
Function wbtree-node-left-subtree tree
=> subtree
Answers the left subtree under tree node tree
. If tree
is empty,
answer the node itself (i.e., tree
). FIXME: this is a strange idea;
why did I do it this way?
Function wbtree-node-right-subtree tree
=> subtree
Answers the right subtree under tree node tree
. If tree
is empty,
answer the node itself (i.e., tree
). FIXME: this is a strange idea;
why did I do it this way?
Function wbtree-minimum-node tree
=> node
Answers the tree node with the smallest key value (with respect to the
tree's predicate function) in the given wbtree tree
. If the tree is
empty, returns nil
instead.
Function wbtree-maximum-node tree
=> node
Answers the tree node with the largest key value (with respect to the
tree's predicate function) in the given wbtree tree
. If the tree is
empty, returns nil
instead.
Function wbtree-ceiling-node key tree
=> node
Answers the node with the smallest key k
, which is still equal to
or greater than key
in tree
. If there is no matching key in tree
,
this function answer nil
.
Function wbtree-floor-node key tree
=> node
Answers the node with the largest key k
, which is still equal to
or less than key
in tree
. If there is no matching key in tree
,
this function answer nil
.
Function wbtree-update key value tree &optional test
=> new-tree
, indicator
Answers a wbtree, which contains an association of the given key
,
mapping it to value
. The resulting tree is a copy of tree
, potentially
modified to hold the new or updated mapping.
If the value of key
in tree
is already "equal" to value
(as
is determined using test
), the resulting wbtree new-tree
will be
tree
itself.
The secondary return value indicator
can be used to find out,
what changes have been applied to tree
. Possible values are
nil
No changes have been made, since the value found for the
given key
was already "equal" to the new value
according to
test
.
:added
A new key/value pair had to be added, since there was
no previous mapping for key
in tree
.
:replaced
The previous value of key
in tree
has been
replaced by the given value
.
FIXME: A more meaningful convention would be to return one of
nil
(no changes), t
(node added), and "old node" (node
replaced).
Function wbtree-remove key tree
=> new-tree
, indicator
Answers a copy of tree
, which does not contain a key/value pair,
whose key matches key
. The secondary value indicator
indicates,
which changes have been applied to tree
. Possible values are
nil
There was no entry matching key
. The new-tree
is actually
the tree
itself.
The node, which held the old mapping of key
(and which has been
removed in new-tree
)
Function wbtree-find key tree &optional default
=> value
, indicator
Answers the value associated with key
in the wbtree tree
, or default
,
if the key is not present in tree
. The indicator
returned as secondary
value is nil
, if no matching entry is found in tree
, or the actual
tree node, which represent's the association, otherwise.
Function wbtree-find-node key tree
=> node
Answers the tree node, whose key matches key
in tree
, or nil
,
if there is no entry matching key
in tree
.
Function wbtree-map function tree &key direction collectp start end
=> result
Applies function
to every node in wbtree tree
. If collectp
, the
results of each invocation are collected into a freshly allocated list,
which is returned from wbtree-map
after the traversal. If collectp
is omitted or nil
, the results of function
are ignored, and the
result
value is nil
.
If direction
is :forward
(the default), the traversal is performed
in the direction from "smaller" key values to "larger" key values.
If start
is given, the traversal starts at the node with the smallest
key, which is equal to or greater than value start
, and will stop
before reaching any node, whose key is equal to or greater than the
given end
. If no end
is supplied, the traversal stops after all
nodes have been visited.
If direction
is :backward
, the traversal is performed in the direction
from "larger" key values to "smaller" key values. If start
is given,
the traversal starts at the node with the largest key, which is equal to
or less than value start
, and will stop before reaching any node,
whose key is equal to or less than the given end
. If no end
is
supplied, the traversal stops after all nodes have been visited.
Function wbtree-fold function tree &key direction associativity initial-value start end
=> result
Generates a "summary" of tree
by invoking function
for all
nodes. The arguments passed to function
depend on the value of
associativity
as follows:
if associativity
is :left
, which is the default, the function
is called with the previous summary value as first, and the tree
node as second parameter.
if associativity
is :right
, the function is called with the
tree node as first, and the previous summary value as second
argument.
In either case, the value returned by the function will be used
as the new summary value in the next invocation or the final
result
, if all nodes have been processed. On the first invocation,
the value supplied as initial-value
is used; if the tree is
empty, the initial-value
will be returned as result
.
If direction
is :forward
(the default), the traversal is performed
in the direction from "smaller" key values to "larger" key values.
If start
is given, the traversal starts at the node with the smallest
key, which is equal to or greater than value start
, and will stop
before reaching any node, whose key is equal to or greater than the
given end
. If no end
is supplied, the traversal stops after all
nodes have been visited.
If direction
is :backward
, the traversal is performed in the direction
from "larger" key values to "smaller" key values. If start
is given,
the traversal starts at the node with the largest key, which is equal to
or less than value start
, and will stop before reaching any node,
whose key is equal to or less than the given end
. If no end
is
supplied, the traversal stops after all nodes have been visited.
Function wbtree-difference tree1 tree2
=> new-tree
Function wbtree-union tree1 tree2 &key combiner
=> new-tree
Function wbtree-intersection tree1 tree2 &key combiner
=> new-tree
Function wbtree-iterator tree &key direction
=> iterator
Function wbtree-equal tree1 tree2 &key test
=> boolean
Debugging helpers and esoterica
wbtree-check-invariants tree
wbtree-rebalance tree
=> new-tree
Compatibility
wbtree-lower-boundary-node tree
=> node
wbtree-upper-boundary-node tree
=> node
A hash trie is a purely functional data structure, which provides
a mapping from keys to values using hashing. Unlike Common Lisp's
standard hash tables, hash tries are immutable. Any operation,
which changes a hash trie returns a copy. Also, hash tries can
use any equivalence predicate and hash function you care to provide.
The default equivalence predicate is eql
, and the default hash
function is sxhash
.
The implementation of hash tries can be found in package DARTS.LIB.HASHTRIE
.
Type hashtrie
The type hashtrie
is a base type for all application defined
concrete hashtrie implementations. This type is exposed primarily
for the purpose of type discrimination, allowing applications to,
say, specialize generic functions on arbitrary hash tries.
Macro define-hashtrie name &body clauses ...
Supported clauses are:
(:hash function)
Declares function
as the function, which computes
the hash values. The function
must be name a function
taking a single argument and returning a positive integer
in the range of (unsigned-byte 32)
(well, the implementation
uses the bottom-most 32 bits only...).
The default hash function is sxhash
.
(:test function)
Declares the function used to test, whether two keys are
equal. The default test function is eql
.
(:key function)
Declares a transformation function, which is applied to all user-supplied hash key value prior to hashing. The function's result is what gets actually used as the hash key. Note, that if a key transformation is supplied, the original input value is not used or stored by the hash trie (except initially, when it is passed as argument to the transformation function).
Example:
(define-hashtrie uppercase-htrie
(:test string=)
(:key string-upcase))
(setf *x* (make-uppercase-htrie (list "foo" "value-of-FOO" #\A "value-of-A" t "value-of-T")))
(hashtrie-find #\t *x*) ;; => "value-of-T"
(:predicate name)
Declares the name of the generated type predicate to be
name
. The predicate can be used (in addition to or instead
of) (typep ... 'name)
to test, whether a value is an
instance of the newly defined hash trie type.
You can use nil
as name
in order to suppress the
generation of an additional type predicate. By using t
as name, you get a predicate with the default name (which
is also the standard behaviour)
(:constructor name)
Declares the name of the generated standard constructor
to be name
. The constructor is a function of a single
optional argument, which is a list of key/value pairs in
property list style. The default constructor is named
make-NAME
. You may generate a constructor with the
default name by omitting this option or using a name of
t
. By specifying this option with a name of nil
, you
can suppress the generation of a constructor function.
(:spread-constructor name)
Declares the name of the generated "spread" constructor.
This function is just like the regular constructor above,
but takes the initial members as &rest
argument. The
default is to not generate a spread constructor, unless
this option is specified explicitly.
If you use a name of t
, the spread constructor is
generated using its default name, which is make-NAME*
.
By giving a name of nil
(the default), generation of
the spread constructor is disabled.
(:documentation string)
Adds the given string
as documentation string to the
structure type definition, the macro expands into.
After this macro's expansion has been evaluated, name
names a valid lisp structure type; in particular, the
name can be used with typep
as well as for CLOS method
dispatch. The new structure type is a subtype (in the
sense of subtypep
) of hashtrie
.
Example:
(define-hashtrie integer-htrie
(:hash identity)
(:test eql)
(:constructor make-integer-htrie)
(:documentation "A simple hash trie, whose keys
are integers. We use the keys directly as their
own hashes."))
Note, that the values given to the :test
and :hash
options
must both be suitable for having function
wrapped around them.
Literal lambda
expressions are ok, and so are symbols naming
functions.
Function hashtriep value
=> boolean
Answers true, if value
is a hash trie instance, and false
otherwise. Note, that concrete hash trie implementations have
their own specific predicates, too.
Function hashtrie-empty-p trie
=> boolean
Answers true, if hash trie trie
is empty, and false, if it
contains at least one key/value pair.
Function hashtrie-count trie
=> integer
Answers the number of key/value pairs contained in the given
hash trie trie
.
Function hashtrie-fold seed function trie
=> value
Invokes function
for each key/value pair in hash trie trie
,
passing three arguments along: the value returned by the
function on the last invocation (or seed
at the first call),
the key, and its associated value. Hashtrie-fold
returns
the value of the last invocation of function
or seed
,
if the trie
is empty, and function
is never called.
Function hashtrie-map function trie
=> unspecified
Invokes function
once for each key/value pair in trie
,
discarding any results.
Function hashtrie-find key trie &optional default
=> value indicator
Answers the value associated with key
in trie
, or default
,
if there is no mapping for key
in trie
. The secondary value
is a boolean indicator, which is true, if the key has been found,
and false otherwise.
This function defines a setf
form just in the ldb
(for example)
does, i.e., if used with setf
, the trie
must indicate a valid
place, which gets updated to hold the updated trie.
(defvar *trie* (simple-hashtrie))
;; The trie is initially empty (no parameters have been
;; handed down to the constructor).
(hashtrie-find 1 *trie*) ;; Yields nil as
;; result value
(setf (hashtrie-find 1 *trie*) "First") ;; Yields "First" as
;; result value
;; Now, the hash trie has been updated to contain a
;; mapping with key 1
(hashtrie-find 1 *trie*) ;; Yields "First" as
;; result value
Function hashtrie-update key value trie
=> new-trie old-value indicator
Answers a copy of trie
, in which key
is associated with
value
.
Function hashtrie-remove key trie
=> new-trie old-value indicator
Answers a copy of trie
, from which any association of key
has been removed.
Macro do-hashtrie (key value trie) &body body
=> whatever
Enumerates the key/value pairs in the hash trie, form trie
evaluates to. In each iteration, key
and value
are bound
to each pair's key and value, and the forms in body
are
evaluated sequentially with these bindings in place.
The whole expansion is wrapped into an anonymous block
,
allowing the body
to abort the iteration by using return
.
This is the only way to provide a non-nil result value for
the whole do-hashtrie
form.
Next: Modules, Previous: Introduction, Up: Top [Contents][Index]
The main system appears first, followed by any subsystem dependency.
• The darts.lib.wbtree system |
Dirk Esser
Dirk Esser
MIT
Weight-balanced binary tree
0.1
darts.lib.wbtree.asd (file)
src (module)
Modules are listed depth-first from the system components tree.
• The darts.lib.wbtree/src module | ||
• The darts.lib.wbtree/src/wbtree module |
Next: The darts․lib․wbtree/src/wbtree module, Previous: Modules, Up: Modules [Contents][Index]
darts.lib.wbtree (system)
src/
wbtree (module)
Previous: The darts․lib․wbtree/src module, Up: Modules [Contents][Index]
src (module)
src/wbtree/
Files are sorted by type and then listed depth-first from the systems components trees.
• Lisp files |
• The darts.lib.wbtree.asd file | ||
• The darts.lib.wbtree/src/wbtree/package.lisp file | ||
• The darts.lib.wbtree/src/wbtree/implementation.lisp file |
Next: The darts․lib․wbtree/src/wbtree/package․lisp file, Previous: Lisp files, Up: Lisp files [Contents][Index]
darts.lib.wbtree.asd
darts.lib.wbtree (system)
Next: The darts․lib․wbtree/src/wbtree/implementation․lisp file, Previous: The darts․lib․wbtree․asd file, Up: Lisp files [Contents][Index]
wbtree (module)
src/wbtree/package.lisp
Previous: The darts․lib․wbtree/src/wbtree/package․lisp file, Up: Lisp files [Contents][Index]
package.lisp (file)
wbtree (module)
src/wbtree/implementation.lisp
Next: Definitions, Previous: Files, Up: Top [Contents][Index]
Packages are listed by definition order.
• The darts.asdf package | ||
• The darts.lib.wbtree package |
Next: The darts․lib․wbtree package, Previous: Packages, Up: Packages [Contents][Index]
darts.lib.wbtree.asd
Previous: The darts․asdf package, Up: Packages [Contents][Index]
Generalized 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.
package.lisp (file)
common-lisp
Definitions are sorted by export status, category, package, and then by lexicographic order.
• Exported definitions | ||
• Internal definitions |
Next: Internal definitions, Previous: Definitions, Up: Definitions [Contents][Index]
• Exported macros | ||
• Exported functions | ||
• Exported generic functions | ||
• Exported structures |
Next: Exported functions, Previous: Exported definitions, Up: Exported definitions [Contents][Index]
implementation.lisp (file)
implementation.lisp (file)
Next: Exported generic functions, Previous: Exported macros, Up: Exported definitions [Contents][Index]
Tests, whether ‘node’ represents an empty tree.
implementation.lisp (file)
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.
implementation.lisp (file)
(setf wbtree-find) (setf expander)
implementation.lisp (file)
wbtree-find (function)
implementation.lisp (file)
implementation.lisp (file)
Answers the node with the largest (in the sense of the subtype’s comparison function) key present in ‘tree’.
implementation.lisp (file)
Answers the node with the smallest (in the sense of the subtype’s comparison function) key present in ‘tree’.
implementation.lisp (file)
Obtains the key associated with ‘node’ If ‘node’ is the empty tree, raises a condition of type ‘simple-error’.
implementation.lisp (file)
Obtains the left subtree of ‘node’ or ‘node’ itself, if it is the empty tree
implementation.lisp (file)
Obtains the right subtree of ‘node’ or ‘node’ itself, if it is the empty tree
implementation.lisp (file)
Obtains the value associated with ‘node’. If ‘node’ is the empty tree, raises a condition of type ‘simple-error’.
implementation.lisp (file)
Answers the number of valid key/value pairs contained in ‘tree’
implementation.lisp (file)
implementation.lisp (file)
implementation.lisp (file)
Next: Exported structures, Previous: Exported functions, Up: Exported definitions [Contents][Index]
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.
implementation.lisp (file)
implementation.lisp (file)
Answers a copy of ‘tree1’, in which all entries have been removed, which match keys present in ‘tree2’.
implementation.lisp (file)
implementation.lisp (file)
Answers the node of ‘tree‘, whose key matches the given ‘key‘ value or nil, if no matching node exists.
implementation.lisp (file)
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.
implementation.lisp (file)
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.
implementation.lisp (file)
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’.
implementation.lisp (file)
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.
implementation.lisp (file)
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.
implementation.lisp (file)
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.
implementation.lisp (file)
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’.
implementation.lisp (file)
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.
implementation.lisp (file)
Previous: Exported generic functions, Up: Exported definitions [Contents][Index]
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’.
implementation.lisp (file)
structure-object (structure)
print-object (method)
node-key (function)
(setf node-key) (function)
node-value (function)
(setf node-value) (function)
0
node-count (function)
(setf node-count) (function)
node-left (function)
(setf node-left) (function)
node-right (function)
(setf node-right) (function)
Previous: Exported definitions, Up: Definitions [Contents][Index]
• Internal constants | ||
• Internal macros | ||
• Internal functions |
Next: Internal macros, Previous: Internal definitions, Up: Internal definitions [Contents][Index]
implementation.lisp (file)
Next: Internal functions, Previous: Internal constants, Up: Internal definitions [Contents][Index]
implementation.lisp (file)
implementation.lisp (file)
implementation.lisp (file)
Previous: Internal macros, Up: Internal definitions [Contents][Index]
implementation.lisp (file)
implementation.lisp (file)
implementation.lisp (file)
implementation.lisp (file)
implementation.lisp (file)
implementation.lisp (file)
implementation.lisp (file)
implementation.lisp (file)
implementation.lisp (file)
implementation.lisp (file)
implementation.lisp (file)
implementation.lisp (file)
implementation.lisp (file)
implementation.lisp (file)
implementation.lisp (file)
implementation.lisp (file)
implementation.lisp (file)
implementation.lisp (file)
implementation.lisp (file)
implementation.lisp (file)
implementation.lisp (file)
implementation.lisp (file)
implementation.lisp (file)
implementation.lisp (file)
implementation.lisp (file)
implementation.lisp (file)
implementation.lisp (file)
implementation.lisp (file)
implementation.lisp (file)
implementation.lisp (file)
implementation.lisp (file)
Previous: Definitions, Up: Top [Contents][Index]
• Concept index | ||
• Function index | ||
• Variable index | ||
• Data type index |
Next: Function index, Previous: Indexes, Up: Indexes [Contents][Index]
Jump to: | D F L M |
---|
Jump to: | D F L M |
---|
Next: Variable index, Previous: Concept index, Up: Indexes [Contents][Index]
Jump to: | (
C D F G M N R S W |
---|
Jump to: | (
C D F G M N R S W |
---|
Next: Data type index, Previous: Function index, Up: Indexes [Contents][Index]
Jump to: | +
C N S |
---|
Jump to: | +
C N S |
---|
Previous: Variable index, Up: Indexes [Contents][Index]
Jump to: | D P S W |
---|
Jump to: | D P S W |
---|