dartsclhashtree
20231021
No Description
Upstream URL
Author
Maintainer
License
Functional Maps and Trees
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"

Weightbalanced 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).
WeightBalanced Binary Trees
The system darts.lib.wbtree
provides support for weightbalanced
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 weightbalanced binary trees. Every new tree type introduced by a
definewbtree
form is a subtype of this type. 
Macro
definewbtree
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:definewbtree name predicate &optional docstring
It is equivalent to using the complex form
(definewbtree name (:test predicate) (:constructor nil) (:spreadconstructor name) (:documentation docstring))
The long form has the format
definewbtree 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 namedmakeNAME
. 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. 
(:spreadconstructor 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 ismakeNAME*
. 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
wbtreetest
=>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
wbtreeemptyp tree
=>boolean
Answers true, if wbtree instance
tree
is empty, i.e., does not contain any key/value pairs. 
Function
wbtreesize tree
=>integer
Answers the number of key/value pairs contained in wbtree instance
tree
. 
Function
wbtreenodevalue tree
=>value
Returns the value stored in the tree node
tree
. Iftree
is empty, signals a condition of typesimpleerror
. 
Function
wbtreenodekey tree
=>key
Returns the key stored in the tree node
tree
. Iftree
is empty, signals a condition of typesimpleerror
. 
Function
wbtreenodeleftsubtree 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
wbtreenoderightsubtree 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
wbtreeminimumnode 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
wbtreemaximumnode 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
wbtreeceilingnode 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
wbtreefloornode 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
wbtreeupdate key value tree &optional test
=>newtree
,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 wbtreenewtree
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
wbtreeremove key tree
=>newtree
,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
. Thenewtree
is actually thetree
itself. 
The node, which held the old mapping of
key
(and which has been removed innewtree
)


Function
wbtreefind 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
wbtreefindnode key tree
=>node
Answers the tree node, whose key matches
key
intree
, ornil
, if there is no entry matchingkey
intree
. 
Function
wbtreemap 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 fromwbtreemap
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
wbtreefold function tree &key direction associativity initialvalue 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 asinitialvalue
is used; if the tree is empty, theinitialvalue
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
wbtreescanrangeforward 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
wbtreecorrelate function tree1 tree2 &key test direction
=> unspecific 
Function
wbtreedifference tree1 tree2
=>newtree

Function
wbtreeunion tree1 tree2 &key combiner
=>newtree

Function
wbtreeintersection tree1 tree2 &key combiner
=>newtree

Function
wbtreeiterator tree &key start end comparator fromend
=>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
fromend
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 forfromend
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:
(definewbtree integertree (:test <)) (defvar *tree* (makeintegertree (list 1 t 2 t 3 t 4 t 5 t))) (loop with iter = (wbtreeiterator *tree* :comparator (lambda (key) (cond ((< key 2) 1) ((<= 4 key) 1) (t 0)))) for node = (funcall iter) then (funcall iter) while node as value = (wbtreenodekey 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
. Iffromend
, 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(wbtreeiterator *tree* :start 2 :end 4)
The values for
start
andend
are ignored if acomparator
is explicitly specified. 

Function
wbtreeequal tree1 tree2 &key test
=>boolean
Debugging helpers and esoterica
 Function
wbtreecheckinvariants tree
 Function
wbtreerebalance tree
=>newtree
Compatibility
 Function
wbtreelowerboundarynode tree
=>node
 Function
wbtreeupperboundarynode tree
=>node
Hash Tries
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
definehashtrie 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(unsignedbyte 32)
(well, the implementation uses the bottommost 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 usersupplied 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:
(definehashtrie uppercasehtrie (:test string=) (:key stringupcase)) (setf *x* (makeuppercasehtrie (list "foo" "valueofFOO" #\A "valueofA" t "valueofT"))) (hashtriefind #\t *x*) ;; => "valueofT"

(: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 namedmakeNAME
. 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. 
(:spreadconstructor 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 ismakeNAME*
. 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:
(definehashtrie integerhtrie (:hash identity) (:test eql) (:constructor makeintegerhtrie) (: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
hashtrieemptyp trie
=>boolean
Answers true, if hash trie
trie
is empty, and false, if it contains at least one key/value pair. 
Function
hashtriecount trie
=>integer
Answers the number of key/value pairs contained in the given hash trie
trie
. 
Function
hashtriefold 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.Hashtriefold
returns the value of the last invocation offunction
orseed
, if thetrie
is empty, andfunction
is never called. 
Function
hashtriemap function trie
=>unspecified
Invokes
function
once for each key/value pair intrie
, discarding any results. 
Function
hashtriefind 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* (simplehashtrie)) ;; The trie is initially empty (no parameters have been ;; handed down to the constructor). (hashtriefind 1 *trie*) ;; Yields nil as ;; result value (setf (hashtriefind 1 *trie*) "First") ;; Yields "First" as ;; result value ;; Now, the hash trie has been updated to contain a ;; mapping with key 1 (hashtriefind 1 *trie*) ;; Yields "First" as ;; result value

Function
hashtrieupdate key value trie
=>newtrie oldvalue indicator
Answers a copy of
trie
, in whichkey
is associated withvalue
. 
Function
hashtrieremove key trie
=>newtrie oldvalue indicator
Answers a copy of
trie
, from which any association ofkey
has been removed. 
Macro
dohashtrie (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 nonnil result value for the wholedohashtrie
form.