This is the functional-trees Reference Manual, version 0.0.0, generated automatically by Declt version 4.0 beta 2 "William Riker" on Sun Dec 15 06:09:20 2024 GMT+0.
The main system appears first, followed by any subsystem dependency.
functional-treesTree data structure supporting functional manipulation
GrammaTech
MIT
Tree data structure supporting functional (or
applicative) manipulation. This system allows the walking and
rewriting of parts of trees in a functional manner, along with
translation of references to internal nodes that can be carried from
one tree to its successors.
0.0.0
asdf-package-system (system).
functional-trees/functional-trees (system).
functional-trees/functional-treesGrammaTech
MIT
alexandria (system).
iterate (system).
cl-store (system).
bordeaux-threads (system).
serapeum (system).
fset (system).
functional-trees/interval-trees (system).
closer-mop (system).
atomics (system).
Files are sorted by type and then listed depth-first from the systems components trees.
functional-trees/functional-trees.asdfunctional-trees/functional-trees/file-type.lispfunctional-trees/interval-trees/file-type.lispfunctional-trees/functional-trees.asdfunctional-trees (system).
functional-trees/functional-trees/file-type.lispfunctional-trees/functional-trees (system).
child-position (generic function).
child-position-if (generic function).
child-slot-specifiers (reader method).
child-slots (reader method).
children (compiler macro).
children (generic function).
children-alist (generic function).
children-slot-specifier-alist (generic function).
convert (method).
convert (method).
convert (method).
copy (generic function).
copy-with-children-alist (generic function).
count (method).
count-if (method).
count-if-not (method).
define-methods-for-node-class (macro).
define-node-class (macro).
descendant-map (function).
do-tree (macro).
filter (method).
find (method).
find-if (method).
find-if-not (method).
initialize-instance (method).
insert (method).
insert (method).
insert (method).
insert (method).
insert (method).
internal-store-object (method).
less (method).
less (method).
less (method).
less (method).
less (method).
lookup (method).
lookup (method).
lookup (method).
lookup (method).
lookup (method).
mapc (compiler macro).
mapc (generic function).
mapcar (compiler macro).
mapcar (generic function).
node (class).
parent (generic function).
path (type).
path-equalp (generic function).
path-equalp-butlast (generic function).
path-later-p (generic function).
path-of-node (generic function).
position (method).
position-if (method).
position-if-not (method).
predecessor (generic function).
print-object (method).
print-object (method).
reduce (method).
remove (method).
remove-if (method).
remove-if (method).
remove-if-not (method).
rpath-to-node (generic function).
size (reader method).
slot-unbound (method).
slot-unbound (method).
slot-unbound (method).
splice (method).
splice (method).
splice (method).
splice (method).
splice (method).
subst (generic function).
subst-if (generic function).
subst-if-not (generic function).
substitute (method).
substitute-if (method).
substitute-if-not (method).
successor (generic function).
swap (generic function).
tree-copy (generic function).
with (method).
with (method).
with (method).
with (method).
with (method).
with-serial-number-block (macro).
*current-serial-number-block* (special variable).
*fallback-block-mapping* (special variable).
*node-obj-code* (special variable).
*serial-number-index* (special variable).
+serial-number-block-size+ (symbol macro).
add-slot-to-intervals (function).
allocate-fallback-block (function).
allocate-serial-number-block (function).
assert (macro).
call/serial-number-block (function).
child-list (function).
child-slot-with-sn (function).
childs-list (function).
clear-serial-number-block (function).
compute-descendant-map (generic function).
cons-0-de (macro).
copy-serial-number-block (function).
current-serial-number-block (function).
def-map-children/i (macro).
define-map-compiler-macro (macro).
descend (macro).
descendant-map-mixin (class).
dump (macro).
encapsulate (function).
equal? (generic function).
expand-children-defmethod (function).
expand-lookup-specialization (function).
expand-setf-error-methods (function).
get-actual-slot (function).
intervals-of-node (generic function).
lexicographic-< (function).
make-serial-number-block (function).
make-slot-specifier (function).
map-children (method).
map-children (method).
map-children/i (generic function).
map-only-children/i (generic function).
mapcar-children (generic function).
next-serial-number (function).
node-can-implant (generic function).
node-identity-ordering-mixin (class).
node-valid (generic function).
nodes-disjoint (generic function).
parse-specialized-lambda-list (function).
path-element-= (generic function).
path-element-> (generic function).
path-p (function).
prefix? (function).
pure-traverse-tree (generic function).
pure-traverse-tree/i (generic function).
serial-number-block (structure).
serial-number-block-end (reader).
serial-number-block-index (reader).
(setf serial-number-block-index) (writer).
serial-number-block-p (function).
serial-number-block-thread (reader).
(setf serial-number-block-thread) (writer).
set-difference/hash (function).
slot-position-in-node (generic function).
slot-setf-expander (function).
slot-spec-arity (function).
slot-spec-of-slot (generic function).
slot-spec-slot (function).
slot-specifier (class).
slot-specifier-arity (reader method).
slot-specifier-class (reader method).
slot-specifier-for-slot (generic function).
slot-specifier-slot (reader method).
store-actual-slot (function).
store-actual-slots (function).
store-nodes (function).
test-handler (macro).
traverse-tree (generic function).
vars-of-specialized-lambda-list (function).
with-encapsulation (macro).
functional-trees/interval-trees/file-type.lispfunctional-trees/interval-trees (system).
convert (method).
convert (method).
interval-collision-error (condition).
intervals-of-itree (function).
itree (structure).
itree-add-intervals (function).
itree-delete (function).
itree-delete-node (function).
itree-find (function).
itree-find-node (function).
itree-find-node-path (function).
itree-glb (function).
itree-glb-node (function).
itree-insert (function).
itree-lub (function).
itree-lub-node (function).
itree-merge-root-nodes (generic function).
itree-remove-interval (function).
itree-remove-intervals (function).
itree-root (reader).
(setf itree-root) (writer).
itree-size (reader).
(setf itree-size) (writer).
node (reader method).
(setf node) (writer method).
node (structure).
node-data (reader).
(setf node-data) (writer).
node-hi (reader).
(setf node-hi) (writer).
node-key (function).
node-left (reader).
(setf node-left) (writer).
node-lo (reader).
(setf node-lo) (writer).
node-right (reader).
(setf node-right) (writer).
print-object (method).
print-object (method).
bound (type).
collision (function).
copy-itree (function).
copy-node (function).
data (reader method).
hi1 (reader method).
hi2 (reader method).
insert-node (function).
interval-range (function).
itree-find-node-splay (function).
itree-insert* (function).
itree-lub-node-path (function).
itree-p (function).
itree-replace-node (function).
key-type (type).
lift-least-node (function).
lo1 (reader method).
lo2 (reader method).
make-itree (function).
make-node (function).
max-node (function).
merge-intervals (function).
min-node (function).
move-node (function).
next-node (function).
node-p (function).
nodes (generic function).
Packages are listed by definition order.
functional-trees/interval-treesFunctional implementation of splay trees for integer intervals.
ft/it
alexandria.
common-lisp.
iterate.
interval-collision-error (condition).
intervals-of-itree (function).
itree (structure).
itree-add-intervals (function).
itree-delete (function).
itree-delete-node (function).
itree-find (function).
itree-find-node (function).
itree-find-node-path (function).
itree-glb (function).
itree-glb-node (function).
itree-insert (function).
itree-lub (function).
itree-lub-node (function).
itree-merge-root-nodes (generic function).
itree-remove-interval (function).
itree-remove-intervals (function).
itree-root (reader).
(setf itree-root) (writer).
itree-size (reader).
(setf itree-size) (writer).
node (generic reader).
(setf node) (generic writer).
node (structure).
node-data (reader).
(setf node-data) (writer).
node-hi (reader).
(setf node-hi) (writer).
node-key (function).
node-left (reader).
(setf node-left) (writer).
node-lo (reader).
(setf node-lo) (writer).
node-right (reader).
(setf node-right) (writer).
bound (type).
collision (function).
copy-itree (function).
copy-node (function).
data (generic reader).
hi1 (generic reader).
hi2 (generic reader).
insert-node (function).
interval-range (function).
itree-find-node-splay (function).
itree-insert* (function).
itree-lub-node-path (function).
itree-p (function).
itree-replace-node (function).
key-type (type).
lift-least-node (function).
lo1 (generic reader).
lo2 (generic reader).
make-itree (function).
make-node (function).
max-node (function).
merge-intervals (function).
min-node (function).
move-node (function).
next-node (function).
node-p (function).
nodes (generic function).
functional-treesPrototype implementation of functional trees w. finger objects
ft
functional-trees/functional-trees
alexandria.
bordeaux-threads.
cl-store.
common-lisp.
iterate.
child-position (generic function).
child-position-if (generic function).
child-slot-specifiers (generic reader).
child-slots (generic reader).
children (compiler macro).
children (generic function).
children-alist (generic function).
children-slot-specifier-alist (generic function).
copy (generic function).
copy-with-children-alist (generic function).
define-methods-for-node-class (macro).
define-node-class (macro).
descendant-map (function).
do-tree (macro).
mapc (compiler macro).
mapc (generic function).
mapcar (compiler macro).
mapcar (generic function).
node (class).
parent (generic function).
path (type).
path-equalp (generic function).
path-equalp-butlast (generic function).
path-later-p (generic function).
path-of-node (generic function).
predecessor (generic function).
rpath-to-node (generic function).
subst (generic function).
subst-if (generic function).
subst-if-not (generic function).
successor (generic function).
swap (generic function).
tree-copy (generic function).
with-serial-number-block (macro).
*current-serial-number-block* (special variable).
*fallback-block-mapping* (special variable).
*node-obj-code* (special variable).
*serial-number-index* (special variable).
+serial-number-block-size+ (symbol macro).
add-slot-to-intervals (function).
allocate-fallback-block (function).
allocate-serial-number-block (function).
assert (macro).
call/serial-number-block (function).
child-list (function).
child-slot-with-sn (function).
childs-list (function).
clear-serial-number-block (function).
compute-descendant-map (generic function).
cons-0-de (macro).
copy-serial-number-block (function).
current-serial-number-block (function).
def-map-children/i (macro).
define-map-compiler-macro (macro).
descend (macro).
descendant-map-mixin (class).
dump (macro).
encapsulate (function).
equal? (generic function).
expand-children-defmethod (function).
expand-lookup-specialization (function).
expand-setf-error-methods (function).
get-actual-slot (function).
intervals-of-node (generic function).
lexicographic-< (function).
make-serial-number-block (function).
make-slot-specifier (function).
map-children (generic function).
map-children/i (generic function).
map-only-children/i (generic function).
mapcar-children (generic function).
next-serial-number (function).
node-can-implant (generic function).
node-identity-ordering-mixin (class).
node-valid (generic function).
nodes-disjoint (generic function).
parse-specialized-lambda-list (function).
path-element-= (generic function).
path-element-> (generic function).
path-p (function).
prefix? (function).
pure-traverse-tree (generic function).
pure-traverse-tree/i (generic function).
serial-number-block (structure).
serial-number-block-end (reader).
serial-number-block-index (reader).
(setf serial-number-block-index) (writer).
serial-number-block-p (function).
serial-number-block-thread (reader).
(setf serial-number-block-thread) (writer).
set-difference/hash (function).
slot-position-in-node (generic function).
slot-setf-expander (function).
slot-spec-arity (function).
slot-spec-of-slot (generic function).
slot-spec-slot (function).
slot-specifier (class).
slot-specifier-arity (generic reader).
slot-specifier-class (generic reader).
slot-specifier-for-slot (generic function).
slot-specifier-slot (generic reader).
store-actual-slot (function).
store-actual-slots (function).
store-nodes (function).
test-handler (macro).
traverse-tree (generic function).
vars-of-specialized-lambda-list (function).
with-encapsulation (macro).
Definitions are sorted by export status, category, package, and then by lexicographic order.
Generalized tree traversal used to implement common lisp sequence functions.
VALUE is the value to return upon completion. INDEX may hold a
variable bound in BODY to the *reversed* path leading to the current
node. If REBUILD then the body should return the new node that will
replace NODE, NODE itself if it is not to be replaced, and NIL if NODE
is to be deleted (from a variable arity list of children in its parent).
Run BODY with ‘*current-serial-number-block*’ bound to the current thread’s serial number block, even without a thread-local binding.
Avoids BODY needing to lookup the block in a global table every time it requests a new serial number.
Return a fresh list of all the intervals in ITREE
Add interval -> data mappings itree. Fails if any interval overlaps one already in the tree.
Delete NODE from end of PATH in TREE. Returns a new tree.
Find the interval in TREE containins KEY. Returns three values: the lo key, the hi key (giving the interval [lo,hi]) and the datum. If no such interval is found, return NIL.
Return the NODE whose interval contains KEY, or NIL if none. Also return the depth of the node (or the NIL leaf) in the tree.
Return the NODE whose interval contains KEY, or NIL if none, and the reversed path to that node (or NIL leaf). Also return the depth of the node, which is the length of the path.
Find the highest interval in TREE for which KEY is >= LO, or NIL if none.
Insert an interval [lo,hi] mapping to data into tree. Return the new tree. If the interval overlaps an interval already in the tree signal an error
Remove the interval [LO,HI] from ITREE
Removes the intervals in INTERVALS from ITREE
root.
size.
data.
left.
Like POSITION, but apply to the children of NODE.
Returns the path from NODE to the child, or NIL if not found.
Like POSITION-IF, but only apply to the children of NODE
node)) ¶List of child slots with optional arity.
This field should be specified as :allocation :class if defined by a
subclass of ‘node’. List of either symbols specifying a slot holding
a list of children or a cons of (symbol . number) where number
specifies a specific number of children held in the slot.
Return all children of NODE.
Return an alist mapping child slots of NODE to their members.
Return an alist mapping child slot specifiers of NODE to their members
Generic COPY method.
array) &key &allow-other-keys) ¶hash-table) &key &allow-other-keys) ¶list) &key &allow-other-keys) ¶sequence) &key &allow-other-keys) ¶symbol) &key &allow-other-keys) ¶Perform a copy of node OBJ, with children-alist being used to initialize some children
Merge the root node with preceding or following nodes if they (1) have abutting intervals, and (2) have data satisfying the TEST comparison function.
Map FUNCTION over CONTAINER.
Map FUNCTION over CONTAINER.
node) &rest more) ¶Map FUNCTION over TREE collecting the results into a new tree. Non-nil return values of FUNCTION replace the current node in the tree and nil return values of FUNCTION leave the existing node.
null) &rest more) ¶sequence) &rest more) ¶seq) &rest more) ¶list) &rest more) ¶interval-collision-error)) ¶interval-collision-error)) ¶node.
Return the parent of NODE.
Return nil if NODE is equal to ROOT or is not in the subtree of ROOT.
Are path-a and path-b the same path?
Are path-a and path-b the same, except possibly for their last entries?
Does PATH-A from NODE represent an NODE path after
PATH-B from NODE? Use this to sort NODE nodes for mutations that perform
multiple operations.
Return the path from ROOT to NODE, in a form
suitable for use by @ or LOOKUP. If the node is not in the tree
return NIL, unless ERROR is true, in which case error.
Return the predecessor of NODE with respect to ROOT if one exists.
Returns the (reversed) path from ROOT to a node
with the same serial number as NODE, as a list of nodes. Note that this does
not include NODE itself.
Also return the node found. If no such node is in the tree, return NIL NIL, or signal an error if ERROR is true.
If TREE is not a node, this simply calls ‘cl:subst’.
If TREE is not a node, this simply calls ‘cl:subst-if’. Also works on a functional tree node.
Complements the test, and calls ‘subst-if’. Also works on a functional tree node.
Return the successor of NODE with respect to ROOT if one exists.
Swap the contents of LOCATION-1 and LOCATION-2 in TREE.
Copy method that descends into a tree and copies all its nodes.
(eql gmap:alist)) (node node) &key value-fn &allow-other-keys) ¶fset.
(eql list)) (node node) &key &allow-other-keys) ¶Convert NODE of type node to a list.
fset.
node) &key from-end end start key &allow-other-keys) ¶fset.
node-identity-ordering-mixin) &key serial-number &allow-other-keys) ¶cl-store) (obj node) stream) ¶Definition for storing an object of type NODE with backend CL-STORE
cl-store.
node) &rest args &key &allow-other-keys) ¶fset.
slot-specifier) stream) ¶node)) ¶Number of nodes in tree rooted here.
fset.
size.
node) (slot (eql functional-trees:child-slot-specifiers))) ¶node) &key test test-not key copy &allow-other-keys) ¶fset.
node) &key copy key &allow-other-keys) ¶fset.
node) &key key copy &allow-other-keys) ¶fset.
Error thrown when an inserted interval overlaps an existing interval
structure-object.
(or null functional-trees/interval-trees:node)
(or null functional-trees/interval-trees:node)
functional-trees/interval-trees::bound
functional-trees/interval-trees::bound
A node in a tree.
child-position.
child-position-if.
child-slot-specifiers.
child-slots.
children.
children-alist.
children-slot-specifier-alist.
compute-descendant-map.
convert.
convert.
convert.
copy.
copy-with-children-alist.
count.
count-if.
count-if-not.
equal?.
filter.
find.
find-if.
find-if-not.
insert.
insert.
insert.
insert.
insert.
internal-store-object.
intervals-of-node.
less.
less.
less.
less.
less.
lookup.
lookup.
lookup.
lookup.
lookup.
map-children.
map-children/i.
map-only-children/i.
mapc.
mapcar.
mapcar-children.
node-can-implant.
node-valid.
nodes-disjoint.
parent.
path-element->.
path-later-p.
path-later-p.
path-later-p.
path-of-node.
path-of-node.
position.
position-if.
position-if-not.
predecessor.
print-object.
pure-traverse-tree.
pure-traverse-tree/i.
reduce.
remove.
remove-if.
remove-if.
remove-if-not.
rpath-to-node.
rpath-to-node.
size.
slot-position-in-node.
slot-spec-of-slot.
slot-specifier-for-slot.
slot-specifier-for-slot.
slot-unbound.
slot-unbound.
slot-unbound.
splice.
splice.
splice.
splice.
splice.
subst.
subst-if.
substitute.
substitute-if.
substitute-if-not.
successor.
swap.
swap.
swap.
swap.
traverse-tree.
tree-copy.
with.
with.
with.
with.
with.
Number of nodes in tree rooted here.
fset.
(integer 1)
size.
This slot is read-only.
List of child slots with optional arity.
This field should be specified as :allocation :class if defined by a
subclass of ‘node’. List of either symbols specifying a slot holding
a list of children or a cons of (symbol . number) where number
specifies a specific number of children held in the slot.
list
:class
This slot is read-only.
The list CHILD-SLOTS
converted to a list of slot-specifier objects
list
:class
This slot is read-only.
Define a method for a map-children-like method. There was much code duplication here before.
Define a compiler macro for mapping functions.
Define generic functions which descend (and return) through functional trees.
This is useful to define standard FSet functions such as ‘with’,
‘less’, etc... Keyword arguments control specifics of how the
recursion works and how the generic functions are defined. OTHER-ARGS
specifies additional arguments that are used. EXTRA-ARGS defines
additional arguments that are not used. REPLACE is a boolean flagging
if NEW replaces the target or is added alongside the target. SPLICE
is a boolean flagging if NEW is inserted or spliced. CHECKS allows
for the specification of checks to run at the beginning of the
functions. MISSING specifies what to do if a node argument
is not present in the tree: :ERROR means signal an error,
:NOOP means do nothing (return the unchanged tree), and :ROOT
act on the root of the tree (the previous behavior).
This macro is an idiom that occurs in many methods. It handles checking and normalization of :TEST and :TEST-NOT arguments.
Returns a fresh list of (interval slot) pairs
Allocate a serial number block using ‘*fallback-block-mapping*’.
Get the (boxed) serial number block for the current thread, creating or advancing it as necessary.
Apply REWRITE-FN to TREE, producing a new tree. The new tree has its predecessor set to TREE.
Generate (setf <slot>) methods for CLASS that just signal errors telling the user to use (setf (@ ... :<slot>) ...)
Given a node X that has been inserted at the end of RPATH, rebalance nodes back along that reversed path. Returns the root node.
Find the node in TREE that has the interval containing KEY, or NIL if none. At the same time, splay that node to the root of TREE. The structure TREE is modified, but the tree is updated functionally.
Like ITREE-INSERT, but also merge any compatible nodes that abut the newly inserted node.
Find the lowest interval in TREE for which KEY is <= HI, or NIL if none. Returns the path to the node (list of ancestors of node, in decreasing order of depth) if it exists.
Replaces the node that was reached by PATH in ITREE with new-node. SIZE-DELTA is the change in size of the itree
Lexicographic comparison of lists of reals, symbols, or pairs. Symbols are considered to be less than reals, and symbols are compared with each other using fset:compare
Rotate the least node of the tree rooted at NODE to the root.
Returns the rightmost node in tree rooted at NODE, and the rpath to it
Combine intervals with the same datum. Assumes INTERVAL-LIST is fresh and can be modified.
Returns the leftmost node in tree rooted at NODE, and the rpath to it
Copy a node, changing its left and right children.
Find the next node in the tree after the last node in PATH, where PATH is a (reversed) list of nodes from the root down to some node. Return NIL if there is no next node.
Return the next serial number in the current thread’s block
Similar to Alexandria’s PARSE-ORDINARY-LAMBDA-LIST, but can handle lambda lists for method argments.
True if list P1 is a prefix of P2
Like ‘set-difference’, but use a hash table if the set is large enough. Duplicates are allowed in both lists.
List of the variables bound by a lambda list
interval-collision-error)) ¶data.
Test equality of A and B.
interval-collision-error)) ¶hi1.
interval-collision-error)) ¶hi2.
Compute a fresh list of intervals for the subtree rooted at NODE.
interval-collision-error)) ¶lo1.
interval-collision-error)) ¶lo2.
Call FN on each child of NODE, along with the INDEX
augmented by the label of that child, and descrend into subtrees in
depth first order
Call FN on each child of NODE, along with
the INDEX augmented by the label of that child. Do not descend
into subtrees.
Apply traverse-children recursively to children of NODE, returning a plist suitable for passing to COPY
function)) ¶Check if new-node can replace the subtree rooted at at-node below ROOT and produce a valid tree.
True if the tree rooted at NODE have EQL unique
serial-numbers, and no node occurs on two different paths in the tree
Returns the nodes in TREE
null)) ¶Return true if NODE1 and NODE2 do not share any serial-number
Equality function for elements of a path, taking into account the representation of named children
real) (b real)) ¶cons) (b real)) ¶real) (b cons)) ¶symbol) (b symbol)) ¶symbol) b) ¶symbol)) ¶cons) (b cons)) ¶Ordering function for elements of paths
real) (b real)) ¶symbol) (b symbol)) ¶symbol) b) ¶symbol)) ¶cons) (b real)) ¶real) (b cons)) ¶Traverse tree at and below NODE in preorder, calling FN on each node.
function)) ¶Traverse tree below NODE in preorder, calling
FN on each node (and with the reversed path INDEX to that node).
list) (fn function)) ¶Returns the slot spec pair of a slot in OBJ. If ERROR? is
true (the default) signal an error if SLOT is not a child slot of OBJ.
Otherwise, in that case return NIL.
slot-specifier)) ¶The arity of the slot
slot-specifier)) ¶The class to which the slot belongs
Returns the child slot SLOT in node OBJ. If it is not
the name of a child slot, return NIL if error? is NIL and error if error?
is true (the default.)
node) (slot slot-specifier) &optional error?) ¶slot-specifier)) ¶The name of the slot
slot.
Traverse tree rooted at NODE in preorder. At each
node, call FN. If the returned value is non-nil, it replaces the node
and traversal continues. If the returned value is nil stop traversal.
If any child is replaced also replace the parent node (as the trees
are applicative.)
function)) ¶structure-object.
(alexandria:required-argument :end)
This slot is read-only.
(alexandria:required-argument :index)
bordeaux-threads.
(bordeaux-threads:current-thread)
Mixin for the descendant-map slot
identity-ordering-mixin.
node.
Object that represents the slots of a class
The class to which the slot belongs
common-lisp.
:class
This slot is read-only.
The name of the slot
symbol
:slot
This slot is read-only.
The arity of the slot
(integer 0)
:arity
This slot is read-only.
| Jump to: | (
A C D E F G H I L M N P R S T V W |
|---|
| Jump to: | (
A C D E F G H I L M N P R S T V W |
|---|
| Jump to: | *
+
A C D E H I L N R S T |
|---|
| Jump to: | *
+
A C D E H I L N R S T |
|---|
| Jump to: | B C D F I K N P S T |
|---|
| Jump to: | B C D F I K N P S T |
|---|