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 ofclauses
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 namedmake-NAME
. You may generate a constructor with the default name by omitting this option or using a name oft
. By specifying this option with a name ofnil
, 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 ismake-NAME*
. By giving a name ofnil
(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 supplyt
(the default), the predicate name follows the standard rules used bydefstruct
. -
(:documentation string)
-
-
Function
wbtreep object
=>boolean
Answers true, if
object
is awbtree
instance, and false otherwise -
Function
wbtree-test
=>function
Answers the binary predicate function that controls the tree structure. The result is a function value and matches whatever was specified as the tree type's
:test
function when it was defined -
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
. Iftree
is empty, signals a condition of typesimple-error
. -
Function
wbtree-node-key tree
=>key
Returns the key stored in the tree node
tree
. Iftree
is empty, signals a condition of typesimple-error
. -
Function
wbtree-node-left-subtree tree
=>subtree
Answers the left subtree under tree node
tree
. Iftree
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
. Iftree
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, returnsnil
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, returnsnil
instead. -
Function
wbtree-ceiling-node key tree
=>node
Answers the node with the smallest key
k
, which is still equal to or greater thankey
intree
. If there is no matching key intree
, this function answernil
. -
Function
wbtree-floor-node key tree
=>node
Answers the node with the largest key
k
, which is still equal to or less thankey
intree
. If there is no matching key intree
, this function answernil
. -
Function
wbtree-update key value tree &optional test
=>new-tree
,indicator
Answers a wbtree, which contains an association of the given
key
, mapping it tovalue
. The resulting tree is a copy oftree
, potentially modified to hold the new or updated mapping.If the value of
key
intree
is already "equal" tovalue
(as is determined usingtest
), the resulting wbtreenew-tree
will betree
itself.The secondary return value
indicator
can be used to find out, what changes have been applied totree
. Possible values are-
nil
No changes have been made, since the value found for the givenkey
was already "equal" to the newvalue
according totest
. -
:added
A new key/value pair had to be added, since there was no previous mapping forkey
intree
. -
:replaced
The previous value ofkey
intree
has been replaced by the givenvalue
.
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 matcheskey
. The secondary valueindicator
indicates, which changes have been applied totree
. Possible values are-
nil
There was no entry matchingkey
. Thenew-tree
is actually thetree
itself. -
The node, which held the old mapping of
key
(and which has been removed innew-tree
)
-
-
Function
wbtree-find key tree &optional default
=>value
,indicator
Answers the value associated with
key
in the wbtreetree
, ordefault
, if the key is not present intree
. Theindicator
returned as secondary value isnil
, if no matching entry is found intree
, 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
intree
, ornil
, if there is no entry matchingkey
intree
. -
Function
wbtree-map function tree &key direction collectp start end
=>result
Applies
function
to every node in wbtreetree
. Ifcollectp
, the results of each invocation are collected into a freshly allocated list, which is returned fromwbtree-map
after the traversal. Ifcollectp
is omitted ornil
, the results offunction
are ignored, and theresult
value isnil
.If
direction
is:forward
(the default), the traversal is performed in the direction from "smaller" key values to "larger" key values. Ifstart
is given, the traversal starts at the node with the smallest key, which is equal to or greater than valuestart
, and will stop before reaching any node, whose key is equal to or greater than the givenend
. If noend
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. Ifstart
is given, the traversal starts at the node with the largest key, which is equal to or less than valuestart
, and will stop before reaching any node, whose key is equal to or less than the givenend
. If noend
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 invokingfunction
for all nodes. The arguments passed tofunction
depend on the value ofassociativity
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 asinitial-value
is used; if the tree is empty, theinitial-value
will be returned asresult
.If
direction
is:forward
(the default), the traversal is performed in the direction from "smaller" key values to "larger" key values. Ifstart
is given, the traversal starts at the node with the smallest key, which is equal to or greater than valuestart
, and will stop before reaching any node, whose key is equal to or greater than the givenend
. If noend
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. Ifstart
is given, the traversal starts at the node with the largest key, which is equal to or less than valuestart
, and will stop before reaching any node, whose key is equal to or less than the givenend
. If noend
is supplied, the traversal stops after all nodes have been visited. -
-
Function
wbtree-scan-range-forward function comparator tree
=> unspecificApplies
function
to the subset of nodes oftree
(in order) for which the givencomparator
function indicates, that they are contained in the desired range. The comparator is a function of one argument (a key found in some tree node) that returns an integer as follows-
the value is negative if the key value is smaller than the first desired value in the range
-
the value is positive if the key value is larger than the last desired value in the range
-
the value is zero if the key value lies within the range to report via
function
This function itself has no interesting return value; it currently always returns the input
tree
. -
-
Function
wbtree-correlate function tree1 tree2 &key test direction
=> unspecific -
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 start end comparator from-end
=>iterator
Answers a function of zero arguments, that on each call produces the next available node (in iterations order) from the given
tree
. If all nodes have been generated, the iterator functions returnsnil
.If
from-end
is true, then iteration is backwards, from larger to smaller nodes, otherwise it matches the tree order (i.e., nodes are produced from smallest to largest). The default forfrom-end
is false.The iterator can be used to produce only a subset (a contiguous range) of nodes by specifying an appropriate
comparator
. The comparator is a function of one element (the key of a node in the tree) that returns-
a negative integer if the key is smaller than any key in the desired range
-
a positive integer if the key is larger than any key in the desired range
-
zero if the key lies in the desired range
Example:
(define-wbtree integer-tree (:test <)) (defvar *tree* (make-integer-tree (list 1 t 2 t 3 t 4 t 5 t))) (loop with iter = (wbtree-iterator *tree* :comparator (lambda (key) (cond ((< key 2) -1) ((<= 4 key) 1) (t 0)))) for node = (funcall iter) then (funcall iter) while node as value = (wbtree-node-key node) do (print value))
prints
2
and3
. For simple use cases, instead of providing a comparator function, client code can also providestart
and/orend
. In this case, iteration starts with the first element in the tree whose key is not less thanstart
, and stops when reaching an element whose key is at leastend
. Iffrom-end
, iteration starts at the largest element not larger thanstart
and stops at the largest element not smaller thanend
. Hence, the example above could have been written as(wbtree-iterator *tree* :start 2 :end 4)
The values for
start
andend
are ignored if acomparator
is explicitly specified. -
-
Function
wbtree-equal tree1 tree2 &key test
=>boolean
Debugging helpers and esoterica
- Function
wbtree-check-invariants tree
- Function
wbtree-rebalance tree
=>new-tree
Compatibility
- Function
wbtree-lower-boundary-node tree
=>node
- Function
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. Thefunction
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
asname
in order to suppress the generation of an additional type predicate. By usingt
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 namedmake-NAME
. You may generate a constructor with the default name by omitting this option or using a name oft
. By specifying this option with a name ofnil
, 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 ismake-NAME*
. By giving a name ofnil
(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 withtypep
as well as for CLOS method dispatch. The new structure type is a subtype (in the sense ofsubtypep
) ofhashtrie
.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 havingfunction
wrapped around them. Literallambda
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 trietrie
, passing three arguments along: the value returned by the function on the last invocation (orseed
at the first call), the key, and its associated value.Hashtrie-fold
returns the value of the last invocation offunction
orseed
, if thetrie
is empty, andfunction
is never called. -
Function
hashtrie-map function trie
=>unspecified
Invokes
function
once for each key/value pair intrie
, discarding any results. -
Function
hashtrie-find key trie &optional default
=>value indicator
Answers the value associated with
key
intrie
, ordefault
, if there is no mapping forkey
intrie
. 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 theldb
(for example) does, i.e., if used withsetf
, thetrie
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 whichkey
is associated withvalue
. -
Function
hashtrie-remove key trie
=>new-trie old-value indicator
Answers a copy of
trie
, from which any association ofkey
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
andvalue
are bound to each pair's key and value, and the forms inbody
are evaluated sequentially with these bindings in place.The whole expansion is wrapped into an anonymous
block
, allowing thebody
to abort the iteration by usingreturn
. This is the only way to provide a non-nil result value for the wholedo-hashtrie
form.