The functional-trees Reference Manual

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.

Table of Contents


1 Introduction


2 Systems

The main system appears first, followed by any subsystem dependency.


2.1 functional-trees

Tree data structure supporting functional manipulation

Author

GrammaTech

License

MIT

Long Description

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.

Version

0.0.0

Defsystem Dependency

asdf-package-system (system).

Dependency

functional-trees/functional-trees (system).

Source

functional-trees.asd.


2.2 functional-trees/functional-trees

Author

GrammaTech

License

MIT

Dependencies
  • alexandria (system).
  • iterate (system).
  • cl-store (system).
  • bordeaux-threads (system).
  • serapeum (system).
  • fset (system).
  • functional-trees/interval-trees (system).
  • closer-mop (system).
  • atomics (system).
Source

functional-trees.asd.


2.3 functional-trees/interval-trees

Author

GrammaTech

License

MIT

Dependencies
  • alexandria (system).
  • iterate (system).
  • fset (system).
Source

functional-trees.asd.


3 Files

Files are sorted by type and then listed depth-first from the systems components trees.


3.1 Lisp


3.1.1 functional-trees/functional-trees.asd

Source

functional-trees.asd.

Parent Component

functional-trees (system).

ASDF Systems

3.1.2 functional-trees/functional-trees/file-type.lisp

Source

functional-trees.asd.

Parent Component

functional-trees/functional-trees (system).

Packages

functional-trees.

Public Interface
Internals

3.1.3 functional-trees/interval-trees/file-type.lisp

Source

functional-trees.asd.

Parent Component

functional-trees/interval-trees (system).

Packages

functional-trees/interval-trees.

Public Interface
Internals

4 Packages

Packages are listed by definition order.


4.1 functional-trees/interval-trees

Functional implementation of splay trees for integer intervals.

Source

file-type.lisp.

Nickname

ft/it

Use List
  • alexandria.
  • common-lisp.
  • iterate.
Public Interface
Internals

4.2 functional-trees

Prototype implementation of functional trees w. finger objects

Source

file-type.lisp.

Nicknames
  • ft
  • functional-trees/functional-trees
Use List
  • alexandria.
  • bordeaux-threads.
  • cl-store.
  • common-lisp.
  • iterate.
Public Interface
Internals

5 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.


5.1 Public Interface


5.1.1 Macros

Macro: define-methods-for-node-class (class-name method-options)
Package

functional-trees.

Source

file-type.lisp.

Macro: define-node-class (name superclasses slots &rest rest)
Package

functional-trees.

Source

file-type.lisp.

Macro: do-tree ((var tree &key index rebuild value) &body body)

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).

Package

functional-trees.

Source

file-type.lisp.

Macro: with-serial-number-block ((&key) &body body)

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.

Package

functional-trees.

Source

file-type.lisp.


5.1.2 Compiler macros

Compiler Macro: children (node)
Package

functional-trees.

Source

file-type.lisp.

Compiler Macro: mapc (fn container &rest more)
Package

functional-trees.

Source

file-type.lisp.

Compiler Macro: mapcar (fn container &rest more)
Package

functional-trees.

Source

file-type.lisp.


5.1.3 Ordinary functions

Function: descendant-map (obj)
Package

functional-trees.

Source

file-type.lisp.

Function: intervals-of-itree (itree)

Return a fresh list of all the intervals in ITREE

Package

functional-trees/interval-trees.

Source

file-type.lisp.

Function: itree-add-intervals (itree intervals)

Add interval -> data mappings itree. Fails if any interval overlaps one already in the tree.

Package

functional-trees/interval-trees.

Source

file-type.lisp.

Function: itree-delete (tree val &key error)
Package

functional-trees/interval-trees.

Source

file-type.lisp.

Function: itree-delete-node (tree node path)

Delete NODE from end of PATH in TREE. Returns a new tree.

Package

functional-trees/interval-trees.

Source

file-type.lisp.

Function: itree-find (tree key)

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.

Package

functional-trees/interval-trees.

Source

file-type.lisp.

Function: itree-find-node (tree key)

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.

Package

functional-trees/interval-trees.

Source

file-type.lisp.

Function: itree-find-node-path (tree key)

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.

Package

functional-trees/interval-trees.

Source

file-type.lisp.

Function: itree-glb (tree key)
Package

functional-trees/interval-trees.

Source

file-type.lisp.

Function: itree-glb-node (tree key)

Find the highest interval in TREE for which KEY is >= LO, or NIL if none.

Package

functional-trees/interval-trees.

Source

file-type.lisp.

Function: itree-insert (tree lo hi data)

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

Package

functional-trees/interval-trees.

Source

file-type.lisp.

Function: itree-lub (tree key)
Package

functional-trees/interval-trees.

Source

file-type.lisp.

Function: itree-lub-node (tree key)
Package

functional-trees/interval-trees.

Source

file-type.lisp.

Function: itree-remove-interval (itree lo hi)

Remove the interval [LO,HI] from ITREE

Package

functional-trees/interval-trees.

Source

file-type.lisp.

Function: itree-remove-intervals (itree intervals)

Removes the intervals in INTERVALS from ITREE

Package

functional-trees/interval-trees.

Source

file-type.lisp.

Reader: itree-root (instance)
Writer: (setf itree-root) (instance)
Package

functional-trees/interval-trees.

Source

file-type.lisp.

Target Slot

root.

Reader: itree-size (instance)
Writer: (setf itree-size) (instance)
Package

functional-trees/interval-trees.

Source

file-type.lisp.

Target Slot

size.

Reader: node-data (instance)
Writer: (setf node-data) (instance)
Package

functional-trees/interval-trees.

Source

file-type.lisp.

Target Slot

data.

Reader: node-hi (instance)
Writer: (setf node-hi) (instance)
Package

functional-trees/interval-trees.

Source

file-type.lisp.

Target Slot

hi.

Function: node-key (node)
Package

functional-trees/interval-trees.

Source

file-type.lisp.

Reader: node-left (instance)
Writer: (setf node-left) (instance)
Package

functional-trees/interval-trees.

Source

file-type.lisp.

Target Slot

left.

Reader: node-lo (instance)
Writer: (setf node-lo) (instance)
Package

functional-trees/interval-trees.

Source

file-type.lisp.

Target Slot

lo.

Reader: node-right (instance)
Writer: (setf node-right) (instance)
Package

functional-trees/interval-trees.

Source

file-type.lisp.

Target Slot

right.


5.1.4 Generic functions

Generic Function: child-position (value node &key key test)

Like POSITION, but apply to the children of NODE.
Returns the path from NODE to the child, or NIL if not found.

Package

functional-trees.

Source

file-type.lisp.

Methods
Method: child-position (value (node node) &key key test)
Generic Function: child-position-if (predicate node &key key)

Like POSITION-IF, but only apply to the children of NODE

Package

functional-trees.

Source

file-type.lisp.

Methods
Method: child-position-if (predicate (node node) &key key)
Generic Reader: child-slot-specifiers (object)
Package

functional-trees.

Methods
Reader Method: child-slot-specifiers ((node node))

The list CHILD-SLOTS
converted to a list of slot-specifier objects

Source

file-type.lisp.

Target Slot

child-slot-specifiers.

Generic Reader: child-slots (object)
Package

functional-trees.

Methods
Reader Method: child-slots ((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.

Source

file-type.lisp.

Target Slot

child-slots.

Generic Function: children (node)

Return all children of NODE.

Package

functional-trees.

Source

file-type.lisp.

Methods
Method: children ((node node))
Generic Function: children-alist (node)

Return an alist mapping child slots of NODE to their members.

Package

functional-trees.

Source

file-type.lisp.

Methods
Method: children-alist ((node node))
Generic Function: children-slot-specifier-alist (node)

Return an alist mapping child slot specifiers of NODE to their members

Package

functional-trees.

Source

file-type.lisp.

Methods
Method: children-slot-specifier-alist ((node node))
Generic Function: copy (obj &key &allow-other-keys)

Generic COPY method.

Package

functional-trees.

Source

file-type.lisp.

Methods
Method: copy ((node node) &rest keys)
Method: copy (obj &key &allow-other-keys)
Method: copy ((obj array) &key &allow-other-keys)
Method: copy ((obj hash-table) &key &allow-other-keys)
Method: copy ((obj list) &key &allow-other-keys)
Method: copy ((obj sequence) &key &allow-other-keys)
Method: copy ((obj symbol) &key &allow-other-keys)
Generic Function: copy-with-children-alist (obj children-alist &rest args)

Perform a copy of node OBJ, with children-alist being used to initialize some children

Package

functional-trees.

Source

file-type.lisp.

Methods
Method: copy-with-children-alist ((obj node) (children-alist list) &rest args)
Generic Function: itree-merge-root-nodes (tree &key test)

Merge the root node with preceding or following nodes if they (1) have abutting intervals, and (2) have data satisfying the TEST comparison function.

Package

functional-trees/interval-trees.

Source

file-type.lisp.

Methods
Method: itree-merge-root-nodes ((tree itree) &key test)
Generic Function: mapc (function container &rest more)

Map FUNCTION over CONTAINER.

Package

functional-trees.

Source

file-type.lisp.

Methods
Method: mapc (function (tree node) &rest more)
Method: mapc (function (nothing null) &rest more)
Method: mapc (function anything &rest more)
Method: mapc (function (sequence sequence) &rest more)
Generic Function: mapcar (function container &rest more)

Map FUNCTION over CONTAINER.

Package

functional-trees.

Source

file-type.lisp.

Methods
Method: mapcar (function (tree 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.

Method: mapcar (function (nothing null) &rest more)
Method: mapcar (function anything &rest more)
Method: mapcar (function (sequence sequence) &rest more)
Method: mapcar (predicate (seq seq) &rest more)
Method: mapcar (function (sequence list) &rest more)
Generic Reader: node (condition)
Generic Writer: (setf node) (condition)
Package

functional-trees/interval-trees.

Methods
Reader Method: node ((condition interval-collision-error))
Writer Method: (setf node) ((condition interval-collision-error))
Source

file-type.lisp.

Target Slot

node.

Generic Function: parent (root node)

Return the parent of NODE.
Return nil if NODE is equal to ROOT or is not in the subtree of ROOT.

Package

functional-trees.

Source

file-type.lisp.

Methods
Method: parent ((root node) (node node))
Generic Function: path-equalp (path-a path-b)

Are path-a and path-b the same path?

Package

functional-trees.

Source

file-type.lisp.

Methods
Method: path-equalp (path-a path-b)
Generic Function: path-equalp-butlast (path-a path-b)

Are path-a and path-b the same, except possibly for their last entries?

Package

functional-trees.

Source

file-type.lisp.

Methods
Method: path-equalp-butlast (path-a path-b)
Generic Function: path-later-p (node path-a path-b)

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.

Package

functional-trees.

Source

file-type.lisp.

Methods
Method: path-later-p (node (path-a null) (path-b null))
Method: path-later-p ((node node) (path-a null) (path-b null))
Method: path-later-p (node (path-a null) (path-b cons))
Method: path-later-p ((node node) (path-a null) (path-b cons))
Method: path-later-p (node (path-a cons) (path-b null))
Method: path-later-p ((node node) (path-a cons) (path-b null))
Method: path-later-p (node (path-a list) (path-b list))
Generic Function: path-of-node (root node &key error)

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.

Package

functional-trees.

Source

file-type.lisp.

Methods
Method: path-of-node ((root node) (node node) &key error)
Method: path-of-node ((root node) (serial-number integer) &key error)
Generic Function: predecessor (root node)

Return the predecessor of NODE with respect to ROOT if one exists.

Package

functional-trees.

Source

file-type.lisp.

Methods
Method: predecessor ((root node) (node node))
Generic Function: rpath-to-node (root node &key error)

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.

Package

functional-trees.

Source

file-type.lisp.

Methods
Method: rpath-to-node ((root node) (node node) &key error)
Method: rpath-to-node ((root node) (sn integer) &key error)
Generic Function: subst (new old tree &key key test test-not copy &allow-other-keys)

If TREE is not a node, this simply calls ‘cl:subst’.

Package

functional-trees.

Source

file-type.lisp.

Methods
Method: subst (new old (tree node) &rest rest &key &allow-other-keys)
Method: subst (new old tree &rest rest &key &allow-other-keys)
Generic Function: subst-if (new test tree &key key copy &allow-other-keys)

If TREE is not a node, this simply calls ‘cl:subst-if’. Also works on a functional tree node.

Package

functional-trees.

Source

file-type.lisp.

Methods
Method: subst-if (new test (tree node) &rest rest &key &allow-other-keys)
Method: subst-if (new test tree &rest rest &key &allow-other-keys)
Generic Function: subst-if-not (new test tree &key key copy)

Complements the test, and calls ‘subst-if’. Also works on a functional tree node.

Package

functional-trees.

Source

file-type.lisp.

Methods
Method: subst-if-not (new test tree &key key copy)
Generic Function: successor (root node)

Return the successor of NODE with respect to ROOT if one exists.

Package

functional-trees.

Source

file-type.lisp.

Methods
Method: successor ((root node) (node node))
Generic Function: swap (tree location-1 location-2)

Swap the contents of LOCATION-1 and LOCATION-2 in TREE.

Package

functional-trees.

Source

file-type.lisp.

Methods
Method: swap ((tree node) (location-1 list) (location-2 list))
Method: swap ((tree node) (location-1 node) location-2)
Method: swap ((tree node) location-1 (location-2 node))
Method: swap :around ((tree node) location-1 location-2)
Generic Function: tree-copy (obj)

Copy method that descends into a tree and copies all its nodes.

Package

functional-trees.

Source

file-type.lisp.

Methods
Method: tree-copy ((node node))
Method: tree-copy (obj)
Method: tree-copy ((obj list))

5.1.5 Standalone methods

Method: convert ((to-type (eql list)) (node node) &key)
Package

fset.

Source

file-type.lisp.

Method: convert ((to-type (eql list)) (tree itree) &key)
Package

fset.

Source

file-type.lisp.

Method: convert ((to-type (eql gmap:alist)) (node node) &key value-fn &allow-other-keys)
Package

fset.

Source

file-type.lisp.

Method: convert ((to-type (eql list)) (node node) &key &allow-other-keys)

Convert NODE of type node to a list.

Package

fset.

Source

file-type.lisp.

Method: convert ((to-type (eql functional-trees:node)) (node node) &key)
Package

fset.

Source

file-type.lisp.

Method: count (item (node node) &key test test-not key &allow-other-keys)
Package

fset.

Source

file-type.lisp.

Method: count-if (predicate (node node) &key from-end end start key &allow-other-keys)
Package

fset.

Source

file-type.lisp.

Method: count-if-not (predicate (node node) &key key &allow-other-keys)
Package

fset.

Source

file-type.lisp.

Method: filter (predicate (node node))
Package

fset.

Source

file-type.lisp.

Method: find (item (node node) &key test test-not key &allow-other-keys)
Package

fset.

Source

file-type.lisp.

Method: find-if (predicate (node node) &key from-end end start key)
Package

fset.

Source

file-type.lisp.

Method: find-if-not (predicate (node node) &key key &allow-other-keys)
Package

fset.

Source

file-type.lisp.

Method: initialize-instance :after ((node node-identity-ordering-mixin) &key serial-number &allow-other-keys)
Source

file-type.lisp.

Method: insert ((tree node) (i integer) value)
Package

fset.

Source

file-type.lisp.

Method: insert ((tree node) (path cons) value)
Package

fset.

Source

file-type.lisp.

Method: insert ((tree node) (slot symbol) value)
Package

fset.

Source

file-type.lisp.

Method: insert ((tree node) (location node) value)
Package

fset.

Source

file-type.lisp.

Method: insert ((tree node) (path null) value)
Package

fset.

Source

file-type.lisp.

Method: internal-store-object ((g0 cl-store) (obj node) stream)

Definition for storing an object of type NODE with backend CL-STORE

Package

cl-store.

Source

file-type.lisp.

Method: less ((tree node) (i integer) &optional arg2)
Package

fset.

Source

file-type.lisp.

Method: less ((tree node) (path cons) &optional arg2)
Package

fset.

Source

file-type.lisp.

Method: less ((tree node) (slot symbol) &optional arg2)
Package

fset.

Source

file-type.lisp.

Method: less ((tree node) (location node) &optional arg2)
Package

fset.

Source

file-type.lisp.

Method: less ((tree node) (path null) &optional arg2)
Package

fset.

Source

file-type.lisp.

Method: lookup ((node node) (i integer))
Package

fset.

Source

file-type.lisp.

Method: lookup ((node node) (slot symbol))
Package

fset.

Source

file-type.lisp.

Method: lookup ((node node) (slot null))
Package

fset.

Source

file-type.lisp.

Method: lookup ((node node) (path cons))
Package

fset.

Source

file-type.lisp.

Method: lookup (node (location node))
Package

fset.

Source

file-type.lisp.

Method: position (item (node node) &key test test-not key &allow-other-keys)
Package

fset.

Source

file-type.lisp.

Method: position-if (predicate (node node) &key from-end end start key)
Package

fset.

Source

file-type.lisp.

Method: position-if-not (predicate (node node) &rest args &key &allow-other-keys)
Package

fset.

Source

file-type.lisp.

Method: print-object ((node node) s)
Source

file-type.lisp.

Method: print-object ((obj itree) s)
Source

file-type.lisp.

Method: print-object ((obj node) stream)
Source

file-type.lisp.

Method: print-object ((obj slot-specifier) stream)
Source

file-type.lisp.

Method: reduce (fn (node node) &key key initial-value &allow-other-keys)
Package

fset.

Source

file-type.lisp.

Method: remove (item (node node) &key test test-not key &allow-other-keys)
Package

fset.

Source

file-type.lisp.

Method: remove-if :around (predicate (node node) &key &allow-other-keys)
Package

fset.

Source

file-type.lisp.

Method: remove-if (predicate (node node) &key key &allow-other-keys)
Package

fset.

Source

file-type.lisp.

Method: remove-if-not (predicate (node node) &key key &allow-other-keys)
Package

fset.

Source

file-type.lisp.

Reader Method: size ((node node))

Number of nodes in tree rooted here.

Package

fset.

Source

file-type.lisp.

Target Slot

size.

Method: slot-unbound (class (node node) (slot (eql functional-trees:descendant-map)))
Source

file-type.lisp.

Method: slot-unbound (class (obj node) (slot-name (eql fset:size)))
Source

file-type.lisp.

Method: slot-unbound (class (obj node) (slot (eql functional-trees:child-slot-specifiers)))
Source

file-type.lisp.

Method: splice ((tree node) (i integer) (values list))
Package

fset.

Source

file-type.lisp.

Method: splice ((tree node) (path cons) (values list))
Package

fset.

Source

file-type.lisp.

Method: splice ((tree node) (slot symbol) (values list))
Package

fset.

Source

file-type.lisp.

Method: splice ((tree node) (location node) (values list))
Package

fset.

Source

file-type.lisp.

Method: splice ((tree node) (path null) (values list))
Package

fset.

Source

file-type.lisp.

Method: substitute (newitem olditem (node node) &key test test-not key copy &allow-other-keys)
Package

fset.

Source

file-type.lisp.

Method: substitute-if (newitem predicate (node node) &key copy key &allow-other-keys)
Package

fset.

Source

file-type.lisp.

Method: substitute-if-not (newitem predicate (node node) &key key copy &allow-other-keys)
Package

fset.

Source

file-type.lisp.

Method: with ((tree node) (i integer) &optional value)
Package

fset.

Source

file-type.lisp.

Method: with ((tree node) (path cons) &optional value)
Package

fset.

Source

file-type.lisp.

Method: with ((tree node) (slot symbol) &optional value)
Package

fset.

Source

file-type.lisp.

Method: with ((tree node) (location node) &optional value)
Package

fset.

Source

file-type.lisp.

Method: with ((tree node) (path null) &optional value)
Package

fset.

Source

file-type.lisp.


5.1.6 Conditions

Condition: interval-collision-error

Error thrown when an inserted interval overlaps an existing interval

Package

functional-trees/interval-trees.

Source

file-type.lisp.

Direct superclasses

error.

Direct methods
Direct Default Initargs
InitargValue
:datanil
Direct slots
Slot: lo1
Initargs

:lo1

Readers

lo1.

Writers

This slot is read-only.

Slot: hi1
Initargs

:hi1

Readers

hi1.

Writers

This slot is read-only.

Slot: lo2
Initargs

:lo2

Readers

lo2.

Writers

This slot is read-only.

Slot: hi2
Initargs

:hi2

Readers

hi2.

Writers

This slot is read-only.

Slot: data
Initargs

:data

Readers

data.

Writers

This slot is read-only.

Slot: node
Initform

(quote nil)

Readers

node.

Writers

(setf node).


5.1.7 Structures

Structure: itree
Package

functional-trees/interval-trees.

Source

file-type.lisp.

Direct superclasses

structure-object.

Direct methods
Direct slots
Slot: root
Type

(or null functional-trees/interval-trees:node)

Readers

itree-root.

Writers

(setf itree-root).

Slot: size
Type

functional-trees/interval-trees::bound

Initform

0

Readers

itree-size.

Writers

(setf itree-size).

Structure: node
Package

functional-trees/interval-trees.

Source

file-type.lisp.

Direct superclasses

structure-object.

Direct methods
Direct slots
Slot: left
Type

(or null functional-trees/interval-trees:node)

Readers

node-left.

Writers

(setf node-left).

Slot: right
Type

(or null functional-trees/interval-trees:node)

Readers

node-right.

Writers

(setf node-right).

Slot: lo
Type

functional-trees/interval-trees::bound

Readers

node-lo.

Writers

(setf node-lo).

Slot: hi
Type

functional-trees/interval-trees::bound

Readers

node-hi.

Writers

(setf node-hi).

Slot: data
Readers

node-data.

Writers

(setf node-data).


5.1.8 Classes

Class: node

A node in a tree.

Package

functional-trees.

Source

file-type.lisp.

Direct superclasses
Direct methods
Direct slots
Slot: size

Number of nodes in tree rooted here.

Package

fset.

Type

(integer 1)

Readers

size.

Writers

This slot is read-only.

Slot: child-slots

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.

Type

list

Allocation

:class

Readers

child-slots.

Writers

This slot is read-only.

Slot: child-slot-specifiers

The list CHILD-SLOTS
converted to a list of slot-specifier objects

Type

list

Allocation

:class

Readers

child-slot-specifiers.

Writers

This slot is read-only.


5.1.9 Types

Type: path ()
Package

functional-trees.

Source

file-type.lisp.


5.2 Internals


5.2.1 Special variables

Special Variable: *current-serial-number-block*
Package

functional-trees.

Source

file-type.lisp.

Special Variable: *fallback-block-mapping*
Package

functional-trees.

Source

file-type.lisp.

Special Variable: *node-obj-code*
Package

functional-trees.

Source

file-type.lisp.

Special Variable: *serial-number-index*
Package

functional-trees.

Source

file-type.lisp.


5.2.2 Symbol macros

Symbol Macro: +serial-number-block-size+
Package

functional-trees.

Source

file-type.lisp.


5.2.3 Macros

Macro: assert (&body body)
Package

functional-trees.

Source

file-type.lisp.

Macro: cons-0-de ((&rest syms) &body body)
Package

functional-trees.

Source

file-type.lisp.

Macro: def-map-children/i (name child-op)

Define a method for a map-children-like method. There was much code duplication here before.

Package

functional-trees.

Source

file-type.lisp.

Macro: define-map-compiler-macro (ft-fn cl-fn)

Define a compiler macro for mapping functions.

Package

functional-trees.

Source

file-type.lisp.

Macro: descend ((name &key other-args extra-args replace splice checks missing) &body new)

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).

Package

functional-trees.

Source

file-type.lisp.

Macro: dump (&body forms)
Package

functional-trees.

Source

file-type.lisp.

Macro: test-handler (fn)

This macro is an idiom that occurs in many methods. It handles checking and normalization of :TEST and :TEST-NOT arguments.

Package

functional-trees.

Source

file-type.lisp.

Macro: with-encapsulation (tree &body body)
Package

functional-trees.

Source

file-type.lisp.


5.2.4 Ordinary functions

Function: add-slot-to-intervals (intervals slot)

Returns a fresh list of (interval slot) pairs

Package

functional-trees.

Source

file-type.lisp.

Function: allocate-fallback-block ()

Allocate a serial number block using ‘*fallback-block-mapping*’.

Package

functional-trees.

Source

file-type.lisp.

Function: allocate-serial-number-block ()
Package

functional-trees.

Source

file-type.lisp.

Function: call/serial-number-block (fn)
Package

functional-trees.

Source

file-type.lisp.

Function: child-list (node slot-spec)
Package

functional-trees.

Source

file-type.lisp.

Function: child-slot-with-sn (node sn)
Package

functional-trees.

Source

file-type.lisp.

Function: childs-list (node slot)
Package

functional-trees.

Source

file-type.lisp.

Function: clear-serial-number-block ()
Package

functional-trees.

Source

file-type.lisp.

Function: collision (node lo hi data)
Package

functional-trees/interval-trees.

Source

file-type.lisp.

Function: copy-itree (instance)
Package

functional-trees/interval-trees.

Source

file-type.lisp.

Function: copy-node (instance)
Package

functional-trees/interval-trees.

Source

file-type.lisp.

Function: copy-serial-number-block (instance)
Package

functional-trees.

Source

file-type.lisp.

Function: current-serial-number-block ()

Get the (boxed) serial number block for the current thread, creating or advancing it as necessary.

Package

functional-trees.

Source

file-type.lisp.

Function: encapsulate (tree rewrite-fn)

Apply REWRITE-FN to TREE, producing a new tree. The new tree has its predecessor set to TREE.

Package

functional-trees.

Source

file-type.lisp.

Function: expand-children-defmethod (class child-slots)
Package

functional-trees.

Source

file-type.lisp.

Function: expand-lookup-specialization (class child-slots)
Package

functional-trees.

Source

file-type.lisp.

Function: expand-setf-error-methods (class child-slots)

Generate (setf <slot>) methods for CLASS that just signal errors telling the user to use (setf (@ ... :<slot>) ...)

Package

functional-trees.

Source

file-type.lisp.

Function: get-actual-slot (slot)
Package

functional-trees.

Source

file-type.lisp.

Function: insert-node (x rpath)

Given a node X that has been inserted at the end of RPATH, rebalance nodes back along that reversed path. Returns the root node.

Package

functional-trees/interval-trees.

Source

file-type.lisp.

Function: interval-range (interval)
Package

functional-trees/interval-trees.

Source

file-type.lisp.

Function: itree-find-node-splay (tree key)

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.

Package

functional-trees/interval-trees.

Source

file-type.lisp.

Function: itree-insert* (tree lo hi data &key test)

Like ITREE-INSERT, but also merge any compatible nodes that abut the newly inserted node.

Package

functional-trees/interval-trees.

Source

file-type.lisp.

Function: itree-lub-node-path (tree key)

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.

Package

functional-trees/interval-trees.

Source

file-type.lisp.

Function: itree-p (object)
Package

functional-trees/interval-trees.

Source

file-type.lisp.

Function: itree-replace-node (itree new-node path &optional size-delta)

Replaces the node that was reached by PATH in ITREE with new-node. SIZE-DELTA is the change in size of the itree

Package

functional-trees/interval-trees.

Source

file-type.lisp.

Function: lexicographic-< (list1 list2)

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

Package

functional-trees.

Source

file-type.lisp.

Function: lift-least-node (node)

Rotate the least node of the tree rooted at NODE to the root.

Package

functional-trees/interval-trees.

Source

file-type.lisp.

Function: make-itree (&key root size)
Package

functional-trees/interval-trees.

Source

file-type.lisp.

Function: make-node (&key left right lo hi data)
Package

functional-trees/interval-trees.

Source

file-type.lisp.

Function: make-serial-number-block (&key end index thread)
Package

functional-trees.

Source

file-type.lisp.

Function: make-slot-specifier (&rest args)
Package

functional-trees.

Source

file-type.lisp.

Function: max-node (node)

Returns the rightmost node in tree rooted at NODE, and the rpath to it

Package

functional-trees/interval-trees.

Source

file-type.lisp.

Function: merge-intervals (interval-list)

Combine intervals with the same datum. Assumes INTERVAL-LIST is fresh and can be modified.

Package

functional-trees/interval-trees.

Source

file-type.lisp.

Function: min-node (node)

Returns the leftmost node in tree rooted at NODE, and the rpath to it

Package

functional-trees/interval-trees.

Source

file-type.lisp.

Function: move-node (node left right)

Copy a node, changing its left and right children.

Package

functional-trees/interval-trees.

Source

file-type.lisp.

Function: next-node (path)

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.

Package

functional-trees/interval-trees.

Source

file-type.lisp.

Function: next-serial-number ()

Return the next serial number in the current thread’s block

Package

functional-trees.

Source

file-type.lisp.

Function: node-p (object)
Package

functional-trees/interval-trees.

Source

file-type.lisp.

Function: parse-specialized-lambda-list (lambda-list)

Similar to Alexandria’s PARSE-ORDINARY-LAMBDA-LIST, but can handle lambda lists for method argments.

Package

functional-trees.

Source

file-type.lisp.

Function: path-p (list)
Package

functional-trees.

Source

file-type.lisp.

Function: prefix? (p1 p2)

True if list P1 is a prefix of P2

Package

functional-trees.

Source

file-type.lisp.

Reader: serial-number-block-end (instance)
Package

functional-trees.

Source

file-type.lisp.

Target Slot

end.

Reader: serial-number-block-index (instance)
Writer: (setf serial-number-block-index) (instance)
Package

functional-trees.

Source

file-type.lisp.

Target Slot

index.

Function: serial-number-block-p (object)
Package

functional-trees.

Source

file-type.lisp.

Reader: serial-number-block-thread (instance)
Writer: (setf serial-number-block-thread) (instance)
Package

functional-trees.

Source

file-type.lisp.

Target Slot

thread.

Function: set-difference/hash (list1 list2)

Like ‘set-difference’, but use a hash table if the set is large enough. Duplicates are allowed in both lists.

Package

functional-trees.

Source

file-type.lisp.

Function: slot-setf-expander (node slot-name env)
Package

functional-trees.

Source

file-type.lisp.

Function: slot-spec-arity (slot-spec)
Package

functional-trees.

Source

file-type.lisp.

Function: slot-spec-slot (slot-spec)
Package

functional-trees.

Source

file-type.lisp.

Function: store-actual-slot (key actual-slot)
Package

functional-trees.

Source

file-type.lisp.

Function: store-actual-slots (slot-names)
Package

functional-trees.

Source

file-type.lisp.

Function: store-nodes (node table)
Package

functional-trees.

Source

file-type.lisp.

Function: vars-of-specialized-lambda-list (lambda-list)

List of the variables bound by a lambda list

Package

functional-trees.

Source

file-type.lisp.


5.2.5 Generic functions

Generic Function: compute-descendant-map (old-node new-node)
Package

functional-trees.

Source

file-type.lisp.

Methods
Method: compute-descendant-map (old-node new-node)
Method: compute-descendant-map ((old-node node) (new-node node))
Generic Reader: data (condition)
Package

functional-trees/interval-trees.

Methods
Reader Method: data ((condition interval-collision-error))
Source

file-type.lisp.

Target Slot

data.

Generic Function: equal? (a b)

Test equality of A and B.

Package

functional-trees.

Source

file-type.lisp.

Methods
Method: equal? (a b)
Method: equal? ((node1 node) (node2 node))
Generic Reader: hi1 (condition)
Package

functional-trees/interval-trees.

Methods
Reader Method: hi1 ((condition interval-collision-error))
Source

file-type.lisp.

Target Slot

hi1.

Generic Reader: hi2 (condition)
Package

functional-trees/interval-trees.

Methods
Reader Method: hi2 ((condition interval-collision-error))
Source

file-type.lisp.

Target Slot

hi2.

Generic Function: intervals-of-node (node)

Compute a fresh list of intervals for the subtree rooted at NODE.

Package

functional-trees.

Source

file-type.lisp.

Methods
Method: intervals-of-node ((node node))
Method: intervals-of-node (node)
Generic Reader: lo1 (condition)
Package

functional-trees/interval-trees.

Methods
Reader Method: lo1 ((condition interval-collision-error))
Source

file-type.lisp.

Target Slot

lo1.

Generic Reader: lo2 (condition)
Package

functional-trees/interval-trees.

Methods
Reader Method: lo2 ((condition interval-collision-error))
Source

file-type.lisp.

Target Slot

lo2.

Generic Function: map-children (node fn)
Package

functional-trees.

Methods
Method: map-children ((node node) (fn function))
Source

file-type.lisp.

Method: map-children (node (fn function))
Source

file-type.lisp.

Generic Function: map-children/i (node index fn)

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

Package

functional-trees.

Source

file-type.lisp.

Methods
Method: map-children/i ((node node) (index list) (fn function))
Generic Function: map-only-children/i (node index fn)

Call FN on each child of NODE, along with
the INDEX augmented by the label of that child. Do not descend into subtrees.

Package

functional-trees.

Source

file-type.lisp.

Methods
Method: map-only-children/i ((node node) (index list) (fn function))
Generic Function: mapcar-children (node fn)

Apply traverse-children recursively to children of NODE, returning a plist suitable for passing to COPY

Package

functional-trees.

Source

file-type.lisp.

Methods
Method: mapcar-children ((node node) (fn function))
Method: mapcar-children (node (fn function))
Generic Function: node-can-implant (root at-node new-node)

Check if new-node can replace the subtree rooted at at-node below ROOT and produce a valid tree.

Package

functional-trees.

Source

file-type.lisp.

Methods
Method: node-can-implant ((root node) (at-node node) (new-node node))
Generic Function: node-valid (node)

True if the tree rooted at NODE have EQL unique
serial-numbers, and no node occurs on two different paths in the tree

Package

functional-trees.

Source

file-type.lisp.

Methods
Method: node-valid ((node node))
Generic Function: nodes (tree)

Returns the nodes in TREE

Package

functional-trees/interval-trees.

Source

file-type.lisp.

Methods
Method: nodes ((obj itree))
Method: nodes ((obj null))
Method: nodes ((obj node))
Generic Function: nodes-disjoint (node1 node2)

Return true if NODE1 and NODE2 do not share any serial-number

Package

functional-trees.

Source

file-type.lisp.

Methods
Method: nodes-disjoint ((node1 node) (node2 node))
Generic Function: path-element-= (a b)

Equality function for elements of a path, taking into account the representation of named children

Package

functional-trees.

Source

file-type.lisp.

Methods
Method: path-element-= ((a real) (b real))
Method: path-element-= ((a cons) (b real))
Method: path-element-= ((a real) (b cons))
Method: path-element-= ((a symbol) (b symbol))
Method: path-element-= ((a symbol) b)
Method: path-element-= (a (b symbol))
Method: path-element-= ((a cons) (b cons))
Generic Function: path-element-> (node a b)

Ordering function for elements of paths

Package

functional-trees.

Source

file-type.lisp.

Methods
Method: path-element-> (node (a real) (b real))
Method: path-element-> ((node node) (a cons) (b cons))
Method: path-element-> (node (a symbol) (b symbol))
Method: path-element-> (node (a symbol) b)
Method: path-element-> (node a (b symbol))
Method: path-element-> (node (a cons) (b real))
Method: path-element-> (node (a real) (b cons))
Generic Function: pure-traverse-tree (node fn)

Traverse tree at and below NODE in preorder, calling FN on each node.

Package

functional-trees.

Source

file-type.lisp.

Methods
Method: pure-traverse-tree ((node node) (fn function))
Method: pure-traverse-tree (node (fn function))
Generic Function: pure-traverse-tree/i (node index fn)

Traverse tree below NODE in preorder, calling
FN on each node (and with the reversed path INDEX to that node).

Package

functional-trees.

Source

file-type.lisp.

Methods
Method: pure-traverse-tree/i ((node node) (index list) (fn function))
Method: pure-traverse-tree/i (node (index list) (fn function))
Generic Function: slot-position-in-node (node slot)
Package

functional-trees.

Source

file-type.lisp.

Methods
Method: slot-position-in-node ((node node) (slot symbol))
Generic Function: slot-spec-of-slot (obj slot &optional error?)

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.

Package

functional-trees.

Source

file-type.lisp.

Methods
Method: slot-spec-of-slot ((obj node) (slot symbol) &optional error?)
Generic Reader: slot-specifier-arity (object)
Package

functional-trees.

Methods
Reader Method: slot-specifier-arity ((slot-specifier slot-specifier))

The arity of the slot

Source

file-type.lisp.

Target Slot

arity.

Generic Reader: slot-specifier-class (object)
Package

functional-trees.

Methods
Reader Method: slot-specifier-class ((slot-specifier slot-specifier))

The class to which the slot belongs

Source

file-type.lisp.

Target Slot

class.

Generic Function: slot-specifier-for-slot (obj slot &optional error?)

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.)

Package

functional-trees.

Source

file-type.lisp.

Methods
Method: slot-specifier-for-slot ((obj node) (slot slot-specifier) &optional error?)
Method: slot-specifier-for-slot ((obj node) (slot symbol) &optional error?)
Generic Reader: slot-specifier-slot (object)
Package

functional-trees.

Methods
Reader Method: slot-specifier-slot ((slot-specifier slot-specifier))

The name of the slot

Source

file-type.lisp.

Target Slot

slot.

Generic Function: traverse-tree (node fn)

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.)

Package

functional-trees.

Source

file-type.lisp.

Methods
Method: traverse-tree ((node node) (fn function))
Method: traverse-tree (node (fn function))

5.2.6 Structures

Structure: serial-number-block
Package

functional-trees.

Source

file-type.lisp.

Direct superclasses

structure-object.

Direct slots
Slot: end
Initform

(alexandria:required-argument :end)

Readers

serial-number-block-end.

Writers

This slot is read-only.

Slot: index
Initform

(alexandria:required-argument :index)

Readers

serial-number-block-index.

Writers

(setf serial-number-block-index).

Slot: thread
Package

bordeaux-threads.

Initform

(bordeaux-threads:current-thread)

Readers

serial-number-block-thread.

Writers

(setf serial-number-block-thread).


5.2.7 Classes

Class: descendant-map-mixin

Mixin for the descendant-map slot

Package

functional-trees.

Source

file-type.lisp.

Direct subclasses

node.

Direct slots
Slot: descendant-map

Map from serial numbers to child slots

Initargs

:descendant-map

Class: node-identity-ordering-mixin
Package

functional-trees.

Source

file-type.lisp.

Direct superclasses

identity-ordering-mixin.

Direct subclasses

node.

Direct methods

initialize-instance.

Class: slot-specifier

Object that represents the slots of a class

Package

functional-trees.

Source

file-type.lisp.

Direct methods
Direct slots
Slot: class

The class to which the slot belongs

Package

common-lisp.

Initargs

:class

Readers

slot-specifier-class.

Writers

This slot is read-only.

Slot: slot

The name of the slot

Type

symbol

Initargs

:slot

Readers

slot-specifier-slot.

Writers

This slot is read-only.

Slot: arity

The arity of the slot

Type

(integer 0)

Initargs

:arity

Readers

slot-specifier-arity.

Writers

This slot is read-only.


5.2.8 Types

Type: bound ()

The type of endpoints of the intervals

Package

functional-trees/interval-trees.

Source

file-type.lisp.

Type: key-type ()

The type of keys in the interval tree, which should subsume BOUND

Package

functional-trees/interval-trees.

Source

file-type.lisp.


Appendix A Indexes


A.1 Concepts


A.2 Functions

Jump to:   (  
A   C   D   E   F   G   H   I   L   M   N   P   R   S   T   V   W  
Index Entry  Section

(
(setf itree-root): Public ordinary functions
(setf itree-size): Public ordinary functions
(setf node): Public generic functions
(setf node): Public generic functions
(setf node-data): Public ordinary functions
(setf node-hi): Public ordinary functions
(setf node-left): Public ordinary functions
(setf node-lo): Public ordinary functions
(setf node-right): Public ordinary functions
(setf serial-number-block-index): Private ordinary functions
(setf serial-number-block-thread): Private ordinary functions

A
add-slot-to-intervals: Private ordinary functions
allocate-fallback-block: Private ordinary functions
allocate-serial-number-block: Private ordinary functions
assert: Private macros

C
call/serial-number-block: Private ordinary functions
child-list: Private ordinary functions
child-position: Public generic functions
child-position: Public generic functions
child-position-if: Public generic functions
child-position-if: Public generic functions
child-slot-specifiers: Public generic functions
child-slot-specifiers: Public generic functions
child-slot-with-sn: Private ordinary functions
child-slots: Public generic functions
child-slots: Public generic functions
children: Public compiler macros
children: Public generic functions
children: Public generic functions
children-alist: Public generic functions
children-alist: Public generic functions
children-slot-specifier-alist: Public generic functions
children-slot-specifier-alist: Public generic functions
childs-list: Private ordinary functions
clear-serial-number-block: Private ordinary functions
collision: Private ordinary functions
Compiler Macro, children: Public compiler macros
Compiler Macro, mapc: Public compiler macros
Compiler Macro, mapcar: Public compiler macros
compute-descendant-map: Private generic functions
compute-descendant-map: Private generic functions
compute-descendant-map: Private generic functions
cons-0-de: Private macros
convert: Public standalone methods
convert: Public standalone methods
convert: Public standalone methods
convert: Public standalone methods
convert: Public standalone methods
copy: Public generic functions
copy: Public generic functions
copy: Public generic functions
copy: Public generic functions
copy: Public generic functions
copy: Public generic functions
copy: Public generic functions
copy: Public generic functions
copy-itree: Private ordinary functions
copy-node: Private ordinary functions
copy-serial-number-block: Private ordinary functions
copy-with-children-alist: Public generic functions
copy-with-children-alist: Public generic functions
count: Public standalone methods
count-if: Public standalone methods
count-if-not: Public standalone methods
current-serial-number-block: Private ordinary functions

D
data: Private generic functions
data: Private generic functions
def-map-children/i: Private macros
define-map-compiler-macro: Private macros
define-methods-for-node-class: Public macros
define-node-class: Public macros
descend: Private macros
descendant-map: Public ordinary functions
do-tree: Public macros
dump: Private macros

E
encapsulate: Private ordinary functions
equal?: Private generic functions
equal?: Private generic functions
equal?: Private generic functions
expand-children-defmethod: Private ordinary functions
expand-lookup-specialization: Private ordinary functions
expand-setf-error-methods: Private ordinary functions

F
filter: Public standalone methods
find: Public standalone methods
find-if: Public standalone methods
find-if-not: Public standalone methods
Function, (setf itree-root): Public ordinary functions
Function, (setf itree-size): Public ordinary functions
Function, (setf node-data): Public ordinary functions
Function, (setf node-hi): Public ordinary functions
Function, (setf node-left): Public ordinary functions
Function, (setf node-lo): Public ordinary functions
Function, (setf node-right): Public ordinary functions
Function, (setf serial-number-block-index): Private ordinary functions
Function, (setf serial-number-block-thread): Private ordinary functions
Function, add-slot-to-intervals: Private ordinary functions
Function, allocate-fallback-block: Private ordinary functions
Function, allocate-serial-number-block: Private ordinary functions
Function, call/serial-number-block: Private ordinary functions
Function, child-list: Private ordinary functions
Function, child-slot-with-sn: Private ordinary functions
Function, childs-list: Private ordinary functions
Function, clear-serial-number-block: Private ordinary functions
Function, collision: Private ordinary functions
Function, copy-itree: Private ordinary functions
Function, copy-node: Private ordinary functions
Function, copy-serial-number-block: Private ordinary functions
Function, current-serial-number-block: Private ordinary functions
Function, descendant-map: Public ordinary functions
Function, encapsulate: Private ordinary functions
Function, expand-children-defmethod: Private ordinary functions
Function, expand-lookup-specialization: Private ordinary functions
Function, expand-setf-error-methods: Private ordinary functions
Function, get-actual-slot: Private ordinary functions
Function, insert-node: Private ordinary functions
Function, interval-range: Private ordinary functions
Function, intervals-of-itree: Public ordinary functions
Function, itree-add-intervals: Public ordinary functions
Function, itree-delete: Public ordinary functions
Function, itree-delete-node: Public ordinary functions
Function, itree-find: Public ordinary functions
Function, itree-find-node: Public ordinary functions
Function, itree-find-node-path: Public ordinary functions
Function, itree-find-node-splay: Private ordinary functions
Function, itree-glb: Public ordinary functions
Function, itree-glb-node: Public ordinary functions
Function, itree-insert: Public ordinary functions
Function, itree-insert*: Private ordinary functions
Function, itree-lub: Public ordinary functions
Function, itree-lub-node: Public ordinary functions
Function, itree-lub-node-path: Private ordinary functions
Function, itree-p: Private ordinary functions
Function, itree-remove-interval: Public ordinary functions
Function, itree-remove-intervals: Public ordinary functions
Function, itree-replace-node: Private ordinary functions
Function, itree-root: Public ordinary functions
Function, itree-size: Public ordinary functions
Function, lexicographic-<: Private ordinary functions
Function, lift-least-node: Private ordinary functions
Function, make-itree: Private ordinary functions
Function, make-node: Private ordinary functions
Function, make-serial-number-block: Private ordinary functions
Function, make-slot-specifier: Private ordinary functions
Function, max-node: Private ordinary functions
Function, merge-intervals: Private ordinary functions
Function, min-node: Private ordinary functions
Function, move-node: Private ordinary functions
Function, next-node: Private ordinary functions
Function, next-serial-number: Private ordinary functions
Function, node-data: Public ordinary functions
Function, node-hi: Public ordinary functions
Function, node-key: Public ordinary functions
Function, node-left: Public ordinary functions
Function, node-lo: Public ordinary functions
Function, node-p: Private ordinary functions
Function, node-right: Public ordinary functions
Function, parse-specialized-lambda-list: Private ordinary functions
Function, path-p: Private ordinary functions
Function, prefix?: Private ordinary functions
Function, serial-number-block-end: Private ordinary functions
Function, serial-number-block-index: Private ordinary functions
Function, serial-number-block-p: Private ordinary functions
Function, serial-number-block-thread: Private ordinary functions
Function, set-difference/hash: Private ordinary functions
Function, slot-setf-expander: Private ordinary functions
Function, slot-spec-arity: Private ordinary functions
Function, slot-spec-slot: Private ordinary functions
Function, store-actual-slot: Private ordinary functions
Function, store-actual-slots: Private ordinary functions
Function, store-nodes: Private ordinary functions
Function, vars-of-specialized-lambda-list: Private ordinary functions

G
Generic Function, (setf node): Public generic functions
Generic Function, child-position: Public generic functions
Generic Function, child-position-if: Public generic functions
Generic Function, child-slot-specifiers: Public generic functions
Generic Function, child-slots: Public generic functions
Generic Function, children: Public generic functions
Generic Function, children-alist: Public generic functions
Generic Function, children-slot-specifier-alist: Public generic functions
Generic Function, compute-descendant-map: Private generic functions
Generic Function, copy: Public generic functions
Generic Function, copy-with-children-alist: Public generic functions
Generic Function, data: Private generic functions
Generic Function, equal?: Private generic functions
Generic Function, hi1: Private generic functions
Generic Function, hi2: Private generic functions
Generic Function, intervals-of-node: Private generic functions
Generic Function, itree-merge-root-nodes: Public generic functions
Generic Function, lo1: Private generic functions
Generic Function, lo2: Private generic functions
Generic Function, map-children: Private generic functions
Generic Function, map-children/i: Private generic functions
Generic Function, map-only-children/i: Private generic functions
Generic Function, mapc: Public generic functions
Generic Function, mapcar: Public generic functions
Generic Function, mapcar-children: Private generic functions
Generic Function, node: Public generic functions
Generic Function, node-can-implant: Private generic functions
Generic Function, node-valid: Private generic functions
Generic Function, nodes: Private generic functions
Generic Function, nodes-disjoint: Private generic functions
Generic Function, parent: Public generic functions
Generic Function, path-element-=: Private generic functions
Generic Function, path-element->: Private generic functions
Generic Function, path-equalp: Public generic functions
Generic Function, path-equalp-butlast: Public generic functions
Generic Function, path-later-p: Public generic functions
Generic Function, path-of-node: Public generic functions
Generic Function, predecessor: Public generic functions
Generic Function, pure-traverse-tree: Private generic functions
Generic Function, pure-traverse-tree/i: Private generic functions
Generic Function, rpath-to-node: Public generic functions
Generic Function, slot-position-in-node: Private generic functions
Generic Function, slot-spec-of-slot: Private generic functions
Generic Function, slot-specifier-arity: Private generic functions
Generic Function, slot-specifier-class: Private generic functions
Generic Function, slot-specifier-for-slot: Private generic functions
Generic Function, slot-specifier-slot: Private generic functions
Generic Function, subst: Public generic functions
Generic Function, subst-if: Public generic functions
Generic Function, subst-if-not: Public generic functions
Generic Function, successor: Public generic functions
Generic Function, swap: Public generic functions
Generic Function, traverse-tree: Private generic functions
Generic Function, tree-copy: Public generic functions
get-actual-slot: Private ordinary functions

H
hi1: Private generic functions
hi1: Private generic functions
hi2: Private generic functions
hi2: Private generic functions

I
initialize-instance: Public standalone methods
insert: Public standalone methods
insert: Public standalone methods
insert: Public standalone methods
insert: Public standalone methods
insert: Public standalone methods
insert-node: Private ordinary functions
internal-store-object: Public standalone methods
interval-range: Private ordinary functions
intervals-of-itree: Public ordinary functions
intervals-of-node: Private generic functions
intervals-of-node: Private generic functions
intervals-of-node: Private generic functions
itree-add-intervals: Public ordinary functions
itree-delete: Public ordinary functions
itree-delete-node: Public ordinary functions
itree-find: Public ordinary functions
itree-find-node: Public ordinary functions
itree-find-node-path: Public ordinary functions
itree-find-node-splay: Private ordinary functions
itree-glb: Public ordinary functions
itree-glb-node: Public ordinary functions
itree-insert: Public ordinary functions
itree-insert*: Private ordinary functions
itree-lub: Public ordinary functions
itree-lub-node: Public ordinary functions
itree-lub-node-path: Private ordinary functions
itree-merge-root-nodes: Public generic functions
itree-merge-root-nodes: Public generic functions
itree-p: Private ordinary functions
itree-remove-interval: Public ordinary functions
itree-remove-intervals: Public ordinary functions
itree-replace-node: Private ordinary functions
itree-root: Public ordinary functions
itree-size: Public ordinary functions

L
less: Public standalone methods
less: Public standalone methods
less: Public standalone methods
less: Public standalone methods
less: Public standalone methods
lexicographic-<: Private ordinary functions
lift-least-node: Private ordinary functions
lo1: Private generic functions
lo1: Private generic functions
lo2: Private generic functions
lo2: Private generic functions
lookup: Public standalone methods
lookup: Public standalone methods
lookup: Public standalone methods
lookup: Public standalone methods
lookup: Public standalone methods

M
Macro, assert: Private macros
Macro, cons-0-de: Private macros
Macro, def-map-children/i: Private macros
Macro, define-map-compiler-macro: Private macros
Macro, define-methods-for-node-class: Public macros
Macro, define-node-class: Public macros
Macro, descend: Private macros
Macro, do-tree: Public macros
Macro, dump: Private macros
Macro, test-handler: Private macros
Macro, with-encapsulation: Private macros
Macro, with-serial-number-block: Public macros
make-itree: Private ordinary functions
make-node: Private ordinary functions
make-serial-number-block: Private ordinary functions
make-slot-specifier: Private ordinary functions
map-children: Private generic functions
map-children: Private generic functions
map-children: Private generic functions
map-children/i: Private generic functions
map-children/i: Private generic functions
map-only-children/i: Private generic functions
map-only-children/i: Private generic functions
mapc: Public compiler macros
mapc: Public generic functions
mapc: Public generic functions
mapc: Public generic functions
mapc: Public generic functions
mapc: Public generic functions
mapcar: Public compiler macros
mapcar: Public generic functions
mapcar: Public generic functions
mapcar: Public generic functions
mapcar: Public generic functions
mapcar: Public generic functions
mapcar: Public generic functions
mapcar: Public generic functions
mapcar-children: Private generic functions
mapcar-children: Private generic functions
mapcar-children: Private generic functions
max-node: Private ordinary functions
merge-intervals: Private ordinary functions
Method, (setf node): Public generic functions
Method, child-position: Public generic functions
Method, child-position-if: Public generic functions
Method, child-slot-specifiers: Public generic functions
Method, child-slots: Public generic functions
Method, children: Public generic functions
Method, children-alist: Public generic functions
Method, children-slot-specifier-alist: Public generic functions
Method, compute-descendant-map: Private generic functions
Method, compute-descendant-map: Private generic functions
Method, convert: Public standalone methods
Method, convert: Public standalone methods
Method, convert: Public standalone methods
Method, convert: Public standalone methods
Method, convert: Public standalone methods
Method, copy: Public generic functions
Method, copy: Public generic functions
Method, copy: Public generic functions
Method, copy: Public generic functions
Method, copy: Public generic functions
Method, copy: Public generic functions
Method, copy: Public generic functions
Method, copy-with-children-alist: Public generic functions
Method, count: Public standalone methods
Method, count-if: Public standalone methods
Method, count-if-not: Public standalone methods
Method, data: Private generic functions
Method, equal?: Private generic functions
Method, equal?: Private generic functions
Method, filter: Public standalone methods
Method, find: Public standalone methods
Method, find-if: Public standalone methods
Method, find-if-not: Public standalone methods
Method, hi1: Private generic functions
Method, hi2: Private generic functions
Method, initialize-instance: Public standalone methods
Method, insert: Public standalone methods
Method, insert: Public standalone methods
Method, insert: Public standalone methods
Method, insert: Public standalone methods
Method, insert: Public standalone methods
Method, internal-store-object: Public standalone methods
Method, intervals-of-node: Private generic functions
Method, intervals-of-node: Private generic functions
Method, itree-merge-root-nodes: Public generic functions
Method, less: Public standalone methods
Method, less: Public standalone methods
Method, less: Public standalone methods
Method, less: Public standalone methods
Method, less: Public standalone methods
Method, lo1: Private generic functions
Method, lo2: Private generic functions
Method, lookup: Public standalone methods
Method, lookup: Public standalone methods
Method, lookup: Public standalone methods
Method, lookup: Public standalone methods
Method, lookup: Public standalone methods
Method, map-children: Private generic functions
Method, map-children: Private generic functions
Method, map-children/i: Private generic functions
Method, map-only-children/i: Private generic functions
Method, mapc: Public generic functions
Method, mapc: Public generic functions
Method, mapc: Public generic functions
Method, mapc: Public generic functions
Method, mapcar: Public generic functions
Method, mapcar: Public generic functions
Method, mapcar: Public generic functions
Method, mapcar: Public generic functions
Method, mapcar: Public generic functions
Method, mapcar: Public generic functions
Method, mapcar-children: Private generic functions
Method, mapcar-children: Private generic functions
Method, node: Public generic functions
Method, node-can-implant: Private generic functions
Method, node-valid: Private generic functions
Method, nodes: Private generic functions
Method, nodes: Private generic functions
Method, nodes: Private generic functions
Method, nodes-disjoint: Private generic functions
Method, parent: Public generic functions
Method, path-element-=: Private generic functions
Method, path-element-=: Private generic functions
Method, path-element-=: Private generic functions
Method, path-element-=: Private generic functions
Method, path-element-=: Private generic functions
Method, path-element-=: Private generic functions
Method, path-element-=: Private generic functions
Method, path-element->: Private generic functions
Method, path-element->: Private generic functions
Method, path-element->: Private generic functions
Method, path-element->: Private generic functions
Method, path-element->: Private generic functions
Method, path-element->: Private generic functions
Method, path-element->: Private generic functions
Method, path-equalp: Public generic functions
Method, path-equalp-butlast: Public generic functions
Method, path-later-p: Public generic functions
Method, path-later-p: Public generic functions
Method, path-later-p: Public generic functions
Method, path-later-p: Public generic functions
Method, path-later-p: Public generic functions
Method, path-later-p: Public generic functions
Method, path-later-p: Public generic functions
Method, path-of-node: Public generic functions
Method, path-of-node: Public generic functions
Method, position: Public standalone methods
Method, position-if: Public standalone methods
Method, position-if-not: Public standalone methods
Method, predecessor: Public generic functions
Method, print-object: Public standalone methods
Method, print-object: Public standalone methods
Method, print-object: Public standalone methods
Method, print-object: Public standalone methods
Method, pure-traverse-tree: Private generic functions
Method, pure-traverse-tree: Private generic functions
Method, pure-traverse-tree/i: Private generic functions
Method, pure-traverse-tree/i: Private generic functions
Method, reduce: Public standalone methods
Method, remove: Public standalone methods
Method, remove-if: Public standalone methods
Method, remove-if: Public standalone methods
Method, remove-if-not: Public standalone methods
Method, rpath-to-node: Public generic functions
Method, rpath-to-node: Public generic functions
Method, size: Public standalone methods
Method, slot-position-in-node: Private generic functions
Method, slot-spec-of-slot: Private generic functions
Method, slot-specifier-arity: Private generic functions
Method, slot-specifier-class: Private generic functions
Method, slot-specifier-for-slot: Private generic functions
Method, slot-specifier-for-slot: Private generic functions
Method, slot-specifier-slot: Private generic functions
Method, slot-unbound: Public standalone methods
Method, slot-unbound: Public standalone methods
Method, slot-unbound: Public standalone methods
Method, splice: Public standalone methods
Method, splice: Public standalone methods
Method, splice: Public standalone methods
Method, splice: Public standalone methods
Method, splice: Public standalone methods
Method, subst: Public generic functions
Method, subst: Public generic functions
Method, subst-if: Public generic functions
Method, subst-if: Public generic functions
Method, subst-if-not: Public generic functions
Method, substitute: Public standalone methods
Method, substitute-if: Public standalone methods
Method, substitute-if-not: Public standalone methods
Method, successor: Public generic functions
Method, swap: Public generic functions
Method, swap: Public generic functions
Method, swap: Public generic functions
Method, swap: Public generic functions
Method, traverse-tree: Private generic functions
Method, traverse-tree: Private generic functions
Method, tree-copy: Public generic functions
Method, tree-copy: Public generic functions
Method, tree-copy: Public generic functions
Method, with: Public standalone methods
Method, with: Public standalone methods
Method, with: Public standalone methods
Method, with: Public standalone methods
Method, with: Public standalone methods
min-node: Private ordinary functions
move-node: Private ordinary functions

N
next-node: Private ordinary functions
next-serial-number: Private ordinary functions
node: Public generic functions
node: Public generic functions
node-can-implant: Private generic functions
node-can-implant: Private generic functions
node-data: Public ordinary functions
node-hi: Public ordinary functions
node-key: Public ordinary functions
node-left: Public ordinary functions
node-lo: Public ordinary functions
node-p: Private ordinary functions
node-right: Public ordinary functions
node-valid: Private generic functions
node-valid: Private generic functions
nodes: Private generic functions
nodes: Private generic functions
nodes: Private generic functions
nodes: Private generic functions
nodes-disjoint: Private generic functions
nodes-disjoint: Private generic functions

P
parent: Public generic functions
parent: Public generic functions
parse-specialized-lambda-list: Private ordinary functions
path-element-=: Private generic functions
path-element-=: Private generic functions
path-element-=: Private generic functions
path-element-=: Private generic functions
path-element-=: Private generic functions
path-element-=: Private generic functions
path-element-=: Private generic functions
path-element-=: Private generic functions
path-element->: Private generic functions
path-element->: Private generic functions
path-element->: Private generic functions
path-element->: Private generic functions
path-element->: Private generic functions
path-element->: Private generic functions
path-element->: Private generic functions
path-element->: Private generic functions
path-equalp: Public generic functions
path-equalp: Public generic functions
path-equalp-butlast: Public generic functions
path-equalp-butlast: Public generic functions
path-later-p: Public generic functions
path-later-p: Public generic functions
path-later-p: Public generic functions
path-later-p: Public generic functions
path-later-p: Public generic functions
path-later-p: Public generic functions
path-later-p: Public generic functions
path-later-p: Public generic functions
path-of-node: Public generic functions
path-of-node: Public generic functions
path-of-node: Public generic functions
path-p: Private ordinary functions
position: Public standalone methods
position-if: Public standalone methods
position-if-not: Public standalone methods
predecessor: Public generic functions
predecessor: Public generic functions
prefix?: Private ordinary functions
print-object: Public standalone methods
print-object: Public standalone methods
print-object: Public standalone methods
print-object: Public standalone methods
pure-traverse-tree: Private generic functions
pure-traverse-tree: Private generic functions
pure-traverse-tree: Private generic functions
pure-traverse-tree/i: Private generic functions
pure-traverse-tree/i: Private generic functions
pure-traverse-tree/i: Private generic functions

R
reduce: Public standalone methods
remove: Public standalone methods
remove-if: Public standalone methods
remove-if: Public standalone methods
remove-if-not: Public standalone methods
rpath-to-node: Public generic functions
rpath-to-node: Public generic functions
rpath-to-node: Public generic functions

S
serial-number-block-end: Private ordinary functions
serial-number-block-index: Private ordinary functions
serial-number-block-p: Private ordinary functions
serial-number-block-thread: Private ordinary functions
set-difference/hash: Private ordinary functions
size: Public standalone methods
slot-position-in-node: Private generic functions
slot-position-in-node: Private generic functions
slot-setf-expander: Private ordinary functions
slot-spec-arity: Private ordinary functions
slot-spec-of-slot: Private generic functions
slot-spec-of-slot: Private generic functions
slot-spec-slot: Private ordinary functions
slot-specifier-arity: Private generic functions
slot-specifier-arity: Private generic functions
slot-specifier-class: Private generic functions
slot-specifier-class: Private generic functions
slot-specifier-for-slot: Private generic functions
slot-specifier-for-slot: Private generic functions
slot-specifier-for-slot: Private generic functions
slot-specifier-slot: Private generic functions
slot-specifier-slot: Private generic functions
slot-unbound: Public standalone methods
slot-unbound: Public standalone methods
slot-unbound: Public standalone methods
splice: Public standalone methods
splice: Public standalone methods
splice: Public standalone methods
splice: Public standalone methods
splice: Public standalone methods
store-actual-slot: Private ordinary functions
store-actual-slots: Private ordinary functions
store-nodes: Private ordinary functions
subst: Public generic functions
subst: Public generic functions
subst: Public generic functions
subst-if: Public generic functions
subst-if: Public generic functions
subst-if: Public generic functions
subst-if-not: Public generic functions
subst-if-not: Public generic functions
substitute: Public standalone methods
substitute-if: Public standalone methods
substitute-if-not: Public standalone methods
successor: Public generic functions
successor: Public generic functions
swap: Public generic functions
swap: Public generic functions
swap: Public generic functions
swap: Public generic functions
swap: Public generic functions

T
test-handler: Private macros
traverse-tree: Private generic functions
traverse-tree: Private generic functions
traverse-tree: Private generic functions
tree-copy: Public generic functions
tree-copy: Public generic functions
tree-copy: Public generic functions
tree-copy: Public generic functions

V
vars-of-specialized-lambda-list: Private ordinary functions

W
with: Public standalone methods
with: Public standalone methods
with: Public standalone methods
with: Public standalone methods
with: Public standalone methods
with-encapsulation: Private macros
with-serial-number-block: Public macros


A.3 Variables

Jump to:   *   +  
A   C   D   E   H   I   L   N   R   S   T  
Index Entry  Section

*
*current-serial-number-block*: Private special variables
*fallback-block-mapping*: Private special variables
*node-obj-code*: Private special variables
*serial-number-index*: Private special variables

+
+serial-number-block-size+: Private symbol macros

A
arity: Private classes

C
child-slot-specifiers: Public classes
child-slots: Public classes
class: Private classes

D
data: Public conditions
data: Public structures
descendant-map: Private classes

E
end: Private structures

H
hi: Public structures
hi1: Public conditions
hi2: Public conditions

I
index: Private structures

L
left: Public structures
lo: Public structures
lo1: Public conditions
lo2: Public conditions

N
node: Public conditions

R
right: Public structures
root: Public structures

S
size: Public structures
size: Public classes
slot: Private classes
Slot, arity: Private classes
Slot, child-slot-specifiers: Public classes
Slot, child-slots: Public classes
Slot, class: Private classes
Slot, data: Public conditions
Slot, data: Public structures
Slot, descendant-map: Private classes
Slot, end: Private structures
Slot, hi: Public structures
Slot, hi1: Public conditions
Slot, hi2: Public conditions
Slot, index: Private structures
Slot, left: Public structures
Slot, lo: Public structures
Slot, lo1: Public conditions
Slot, lo2: Public conditions
Slot, node: Public conditions
Slot, right: Public structures
Slot, root: Public structures
Slot, size: Public structures
Slot, size: Public classes
Slot, slot: Private classes
Slot, thread: Private structures
Special Variable, *current-serial-number-block*: Private special variables
Special Variable, *fallback-block-mapping*: Private special variables
Special Variable, *node-obj-code*: Private special variables
Special Variable, *serial-number-index*: Private special variables
Symbol Macro, +serial-number-block-size+: Private symbol macros

T
thread: Private structures


A.4 Data types

Jump to:   B   C   D   F   I   K   N   P   S   T  
Index Entry  Section

B
bound: Private types

C
Class, descendant-map-mixin: Private classes
Class, node: Public classes
Class, node-identity-ordering-mixin: Private classes
Class, slot-specifier: Private classes
Condition, interval-collision-error: Public conditions

D
descendant-map-mixin: Private classes

F
File, file-type.lisp: The functional-trees/functional-trees/file-type․lisp file
File, file-type.lisp: The functional-trees/interval-trees/file-type․lisp file
File, functional-trees.asd: The functional-trees/functional-trees․asd file
file-type.lisp: The functional-trees/functional-trees/file-type․lisp file
file-type.lisp: The functional-trees/interval-trees/file-type․lisp file
functional-trees: The functional-trees system
functional-trees: The functional-trees package
functional-trees.asd: The functional-trees/functional-trees․asd file
functional-trees/functional-trees: The functional-trees/functional-trees system
functional-trees/interval-trees: The functional-trees/interval-trees system
functional-trees/interval-trees: The functional-trees/interval-trees package

I
interval-collision-error: Public conditions
itree: Public structures

K
key-type: Private types

N
node: Public structures
node: Public classes
node-identity-ordering-mixin: Private classes

P
Package, functional-trees: The functional-trees package
Package, functional-trees/interval-trees: The functional-trees/interval-trees package
path: Public types

S
serial-number-block: Private structures
slot-specifier: Private classes
Structure, itree: Public structures
Structure, node: Public structures
Structure, serial-number-block: Private structures
System, functional-trees: The functional-trees system
System, functional-trees/functional-trees: The functional-trees/functional-trees system
System, functional-trees/interval-trees: The functional-trees/interval-trees system

T
Type, bound: Private types
Type, key-type: Private types
Type, path: Public types