Next: Introduction, Previous: (dir), Up: (dir) [Contents][Index]
This is the flat-tree Reference Manual, version 0.0.1, generated automatically by Declt version 3.0 "Montgomery Scott" on Mon Dec 02 09:25:35 2019 GMT+0.
• Introduction | What flat-tree is all about | |
• Systems | The systems documentation | |
• Files | The files documentation | |
• Packages | The packages documentation | |
• Definitions | The symbols documentation | |
• Indexes | Concepts, functions, variables and data types |
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: Top [Contents][Index]
The main system appears first, followed by any subsystem dependency.
• The flat-tree system |
noffle <sww@eight45.net>
MIT
A flat-tree implementation in Common Lisp.
0.0.1
flat-tree.asd (file)
Files are sorted by type and then listed depth-first from the systems components trees.
• Lisp files |
• The flat-tree.asd file | ||
• The flat-tree/package.lisp file | ||
• The flat-tree/flat-tree.lisp file |
Next: The flat-tree/package․lisp file, Previous: Lisp files, Up: Lisp files [Contents][Index]
flat-tree.asd
flat-tree (system)
Next: The flat-tree/flat-tree․lisp file, Previous: The flat-tree․asd file, Up: Lisp files [Contents][Index]
Previous: The flat-tree/package․lisp file, Up: Lisp files [Contents][Index]
package.lisp (file)
flat-tree (system)
flat-tree.lisp
Next: Definitions, Previous: Files, Up: Top [Contents][Index]
Packages are listed by definition order.
• The flat-tree package |
package.lisp (file)
common-lisp
Definitions are sorted by export status, category, package, and then by lexicographic order.
• Exported definitions | ||
• Internal definitions |
Next: Internal definitions, Previous: Definitions, Up: Definitions [Contents][Index]
• Exported functions |
Previous: Exported definitions, Up: Exported definitions [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.
flat-tree.lisp (file)
Returns how many nodes (including parent nodes) a tree contains.
flat-tree.lisp (file)
Returns the depth of an index.
flat-tree.lisp (file)
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.
flat-tree.lisp (file)
Returns an array index for the tree element at the given depth and offset.
flat-tree.lisp (file)
flat-tree.lisp (file)
flat-tree.lisp (file)
Is the iterator at a left sibling?
flat-tree.lisp (file)
Is the iterator at a right sibling?
flat-tree.lisp (file)
Move the iterator to its left child. No change if there is no child.
flat-tree.lisp (file)
Move the iterator to the current left span index.
flat-tree.lisp (file)
Move one step right across the tree, at the current depth.
flat-tree.lisp (file)
flat-tree.lisp (file)
flat-tree.lisp (file)
Move the iterator to its parent.
flat-tree.lisp (file)
Move one step left across the tree, at the current depth.
flat-tree.lisp (file)
Move the iterator to its right child. No change if there is no child.
flat-tree.lisp (file)
Move the iterator to the current right span index.
flat-tree.lisp (file)
Move the iterator to a specific index.
flat-tree.lisp (file)
flat-tree.lisp (file)
Returns the left spanning in index in the tree index spans.
flat-tree.lisp (file)
flat-tree.lisp (file)
Returns the offset of an index.
flat-tree.lisp (file)
Returns the index of the parent element in tree.
flat-tree.lisp (file)
Returns the right spanning in index in the tree index spans.
flat-tree.lisp (file)
Returns the index of this element’s sibling.
flat-tree.lisp (file)
Returns the range (inclusive) that the tree rooted at ’index’ spans. For example (spans 3) would return (0 6).
flat-tree.lisp (file)
Previous: Exported definitions, Up: Definitions [Contents][Index]
• Internal macros | ||
• Internal functions | ||
• Internal structures |
Next: Internal functions, Previous: Internal definitions, Up: Internal definitions [Contents][Index]
Like ’incf’, but for multiplication.
flat-tree.lisp (file)
Next: Internal structures, Previous: Internal macros, Up: Internal definitions [Contents][Index]
flat-tree.lisp (file)
Returns T if ’index’ is of depth ’depth’.
flat-tree.lisp (file)
Move the iterator to its sibling.
flat-tree.lisp (file)
Returns the offset step size, given ’depth’.
flat-tree.lisp (file)
Previous: Internal functions, Up: Internal definitions [Contents][Index]
flat-tree.lisp (file)
structure-object (structure)
0
iterator-index (function)
(setf iterator-index) (function)
2
iterator-step-size (function)
(setf iterator-step-size) (function)
0
iterator-offset (function)
(setf iterator-offset) (function)
0
iterator-depth (function)
(setf iterator-depth) (function)
Previous: Definitions, Up: Top [Contents][Index]
• Concept index | ||
• Function index | ||
• Variable index | ||
• Data type index |
Next: Function index, Previous: Indexes, Up: Indexes [Contents][Index]
Jump to: | F L |
---|
Jump to: | F L |
---|
Next: Variable index, Previous: Concept index, Up: Indexes [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 type index, Previous: Function index, Up: Indexes [Contents][Index]
Jump to: | D I O S |
---|
Jump to: | D I O S |
---|
Previous: Variable index, Up: Indexes [Contents][Index]
Jump to: | F I P S |
---|
Jump to: | F I P S |
---|