Next: Introduction, Previous: (dir), Up: (dir) [Contents][Index]
This is the flat-tree Reference Manual, version 0.0.1, generated automatically by Declt version 4.0 beta 2 "William Riker" on Wed Jun 15 03:40:45 2022 GMT+0.
Next: Systems, Previous: The flat-tree Reference Manual, Up: The flat-tree Reference Manual [Contents][Index]
Map a binary tree to a list. Common Lisp implementation, adapted from mafintosh/flat-tree.
> (flat-tree:parent 0)
1
You can represent a binary tree in a simple flat list using the following structure:
3
1 5
0 2 4 6 ...
Each number represents an index in a flat list. So a tree:
A
B C
D E F G ...
would be represented as a list: [D B E A F C G]
Furthermore, indexes 0
, 2
, 4
, 6
are on depth 0
. 1
, 5
, 9
on depth 1
. And so forth.
depth = 2 ^ 3
depth = 1 | 1 5
depth = 0 | 0 2 4 6 ...
In some cases it is also useful to calculate an offset. Indexes 0
, 1
, 3
, 7
have an offset 0
:
(7)
(3)
(1) 5
(0) 2 4 6 ...
2
, 5
, 11
, 23
offset 1
:
7
3 (11)
1 (5) 9 13
0 (2) 4 6 10 12 14 15
This module exposes a series of functions to help you build and maintain this data structure.
Next: Files, Previous: Introduction, Up: The flat-tree Reference Manual [Contents][Index]
The main system appears first, followed by any subsystem dependency.
A flat-tree implementation in Common Lisp.
noffle <sww@eight45.net>
MIT
0.0.1
Next: Packages, Previous: Systems, Up: The flat-tree Reference Manual [Contents][Index]
Files are sorted by type and then listed depth-first from the systems components trees.
Next: flat-tree/package.lisp, Previous: Lisp, Up: Lisp [Contents][Index]
flat-tree (system).
Next: flat-tree/flat-tree.lisp, Previous: flat-tree/flat-tree.asd, Up: Lisp [Contents][Index]
flat-tree (system).
Previous: flat-tree/package.lisp, Up: Lisp [Contents][Index]
package.lisp (file).
flat-tree (system).
Next: Definitions, Previous: Files, Up: The flat-tree Reference Manual [Contents][Index]
Packages are listed by definition order.
common-lisp.
Next: Indexes, Previous: Packages, Up: The flat-tree Reference Manual [Contents][Index]
Definitions are sorted by export status, category, package, and then by lexicographic order.
Next: Internals, Previous: Definitions, Up: Definitions [Contents][Index]
Previous: Public Interface, Up: Public Interface [Contents][Index]
Returns a list (leftChild rightChild) with the indexes of this element’s children. If this element does not have any children it returns NIL.
Returns how many nodes (including parent nodes) a tree contains.
Returns the depth of an index.
Returns a list of all the full roots (subtrees where all nodes have either 2 or 0 children) < index.
For example (full-roots 8) returns (3), since the subtree rooted at 3 spans 0 -> 6 and the tree rooted at 7 has a child located at 9 which is >= 8.
Returns an array index for the tree element at the given depth and offset.
Is the iterator at a left sibling?
Is the iterator at a right sibling?
Move the iterator to its left child. No change if there is no child.
Move the iterator to the current left span index.
Move one step right across the tree, at the current depth.
Move the iterator to its parent.
Move one step left across the tree, at the current depth.
Move the iterator to its right child. No change if there is no child.
Move the iterator to the current right span index.
Move the iterator to a specific index.
Returns the left spanning in index in the tree index spans.
Returns the offset of an index.
Returns the index of the parent element in tree.
Returns the right spanning in index in the tree index spans.
Returns the index of this element’s sibling.
Returns the range (inclusive) that the tree rooted at ’index’ spans. For example (spans 3) would return (0 6).
Previous: Public Interface, Up: Definitions [Contents][Index]
Next: Ordinary functions, Previous: Internals, Up: Internals [Contents][Index]
Like ’incf’, but for multiplication.
Next: Structures, Previous: Macros, Up: Internals [Contents][Index]
Returns T if ’index’ is of depth ’depth’.
Move the iterator to its sibling.
Returns the offset step size, given ’depth’.
Previous: Ordinary functions, Up: Internals [Contents][Index]
Previous: Definitions, Up: The flat-tree Reference Manual [Contents][Index]
Jump to: | (
C D F I L M O P R S |
---|
Jump to: | (
C D F I L M O P R S |
---|
Next: Data types, Previous: Functions, Up: Indexes [Contents][Index]
Jump to: | D I O S |
---|
Jump to: | D I O S |
---|
Jump to: | F I P S |
---|
Jump to: | F I P S |
---|