The flat-tree Reference Manual

Table of Contents

Next: , Previous: , Up: (dir)   [Contents][Index]

The flat-tree Reference Manual

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.


Next: , Previous: , Up: Top   [Contents][Index]

1 Introduction

flat-tree

Map a binary tree to a list. Common Lisp implementation, adapted from mafintosh/flat-tree.

API

Usage

> (flat-tree:parent 0)
1

Why?

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.

License

MIT


Next: , Previous: , Up: Top   [Contents][Index]

2 Systems

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


Previous: , Up: Systems   [Contents][Index]

2.1 flat-tree

Author

noffle <sww@eight45.net>

License

MIT

Description

A flat-tree implementation in Common Lisp.

Version

0.0.1

Source

flat-tree.asd (file)

Components

Next: , Previous: , Up: Top   [Contents][Index]

3 Files

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


Previous: , Up: Files   [Contents][Index]

3.1 Lisp


Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.1 flat-tree.asd

Location

flat-tree.asd

Systems

flat-tree (system)


Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.2 flat-tree/package.lisp

Parent

flat-tree (system)

Location

package.lisp

Packages

flat-tree


Previous: , Up: Lisp files   [Contents][Index]

3.1.3 flat-tree/flat-tree.lisp

Dependency

package.lisp (file)

Parent

flat-tree (system)

Location

flat-tree.lisp

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Top   [Contents][Index]

4 Packages

Packages are listed by definition order.


Previous: , Up: Packages   [Contents][Index]

4.1 flat-tree

Source

package.lisp (file)

Use List

common-lisp

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Top   [Contents][Index]

5 Definitions

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


Next: , Previous: , Up: Definitions   [Contents][Index]

5.1 Exported definitions


Previous: , Up: Exported definitions   [Contents][Index]

5.1.1 Functions

Function: children 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.

Package

flat-tree

Source

flat-tree.lisp (file)

Function: counts INDEX

Returns how many nodes (including parent nodes) a tree contains.

Package

flat-tree

Source

flat-tree.lisp (file)

Function: depth INDEX

Returns the depth of an index.

Package

flat-tree

Source

flat-tree.lisp (file)

Function: full-roots 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.

Package

flat-tree

Source

flat-tree.lisp (file)

Function: index DEPTH OFFSET

Returns an array index for the tree element at the given depth and offset.

Package

flat-tree

Source

flat-tree.lisp (file)

Function: iterator-depth INSTANCE
Function: (setf iterator-depth) VALUE INSTANCE
Package

flat-tree

Source

flat-tree.lisp (file)

Function: iterator-index INSTANCE
Function: (setf iterator-index) VALUE INSTANCE
Package

flat-tree

Source

flat-tree.lisp (file)

Function: iterator-is-left? ITER

Is the iterator at a left sibling?

Package

flat-tree

Source

flat-tree.lisp (file)

Function: iterator-is-right? ITER

Is the iterator at a right sibling?

Package

flat-tree

Source

flat-tree.lisp (file)

Function: iterator-left-child ITER

Move the iterator to its left child. No change if there is no child.

Package

flat-tree

Source

flat-tree.lisp (file)

Function: iterator-left-span ITER

Move the iterator to the current left span index.

Package

flat-tree

Source

flat-tree.lisp (file)

Function: iterator-next ITER

Move one step right across the tree, at the current depth.

Package

flat-tree

Source

flat-tree.lisp (file)

Function: iterator-offset INSTANCE
Function: (setf iterator-offset) VALUE INSTANCE
Package

flat-tree

Source

flat-tree.lisp (file)

Function: iterator-p OBJECT
Package

flat-tree

Source

flat-tree.lisp (file)

Function: iterator-parent ITER

Move the iterator to its parent.

Package

flat-tree

Source

flat-tree.lisp (file)

Function: iterator-prev ITER

Move one step left across the tree, at the current depth.

Package

flat-tree

Source

flat-tree.lisp (file)

Function: iterator-right-child ITER

Move the iterator to its right child. No change if there is no child.

Package

flat-tree

Source

flat-tree.lisp (file)

Function: iterator-right-span ITER

Move the iterator to the current right span index.

Package

flat-tree

Source

flat-tree.lisp (file)

Function: iterator-seek ITER INDEX

Move the iterator to a specific index.

Package

flat-tree

Source

flat-tree.lisp (file)

Function: iterator-step-size INSTANCE
Function: (setf iterator-step-size) VALUE INSTANCE
Package

flat-tree

Source

flat-tree.lisp (file)

Function: left-span INDEX

Returns the left spanning in index in the tree index spans.

Package

flat-tree

Source

flat-tree.lisp (file)

Function: make-iterator &key (INDEX INDEX) (STEP-SIZE STEP-SIZE) (OFFSET OFFSET) (DEPTH DEPTH)
Package

flat-tree

Source

flat-tree.lisp (file)

Function: offset INDEX

Returns the offset of an index.

Package

flat-tree

Source

flat-tree.lisp (file)

Function: parent INDEX

Returns the index of the parent element in tree.

Package

flat-tree

Source

flat-tree.lisp (file)

Function: right-span INDEX

Returns the right spanning in index in the tree index spans.

Package

flat-tree

Source

flat-tree.lisp (file)

Function: sibling INDEX

Returns the index of this element’s sibling.

Package

flat-tree

Source

flat-tree.lisp (file)

Function: spans INDEX

Returns the range (inclusive) that the tree rooted at ’index’ spans. For example (spans 3) would return (0 6).

Package

flat-tree

Source

flat-tree.lisp (file)


Previous: , Up: Definitions   [Contents][Index]

5.2 Internal definitions


Next: , Previous: , Up: Internal definitions   [Contents][Index]

5.2.1 Macros

Macro: multf PLACE AMT

Like ’incf’, but for multiplication.

Package

flat-tree

Source

flat-tree.lisp (file)


Next: , Previous: , Up: Internal definitions   [Contents][Index]

5.2.2 Functions

Function: copy-iterator INSTANCE
Package

flat-tree

Source

flat-tree.lisp (file)

Function: depth-n? INDEX DEPTH

Returns T if ’index’ is of depth ’depth’.

Package

flat-tree

Source

flat-tree.lisp (file)

Function: iterator-sibling ITER

Move the iterator to its sibling.

Package

flat-tree

Source

flat-tree.lisp (file)

Function: step-size DEPTH

Returns the offset step size, given ’depth’.

Package

flat-tree

Source

flat-tree.lisp (file)


Previous: , Up: Internal definitions   [Contents][Index]

5.2.3 Structures

Structure: iterator ()
Package

flat-tree

Source

flat-tree.lisp (file)

Direct superclasses

structure-object (structure)

Direct slots
Slot: index
Initform

0

Readers

iterator-index (function)

Writers

(setf iterator-index) (function)

Slot: step-size
Initform

2

Readers

iterator-step-size (function)

Writers

(setf iterator-step-size) (function)

Slot: offset
Initform

0

Readers

iterator-offset (function)

Writers

(setf iterator-offset) (function)

Slot: depth
Initform

0

Readers

iterator-depth (function)

Writers

(setf iterator-depth) (function)


Previous: , Up: Top   [Contents][Index]

Appendix A Indexes


Next: , Previous: , Up: Indexes   [Contents][Index]

A.1 Concepts

Jump to:   F   L  
Index Entry  Section

F
File, Lisp, flat-tree.asd: The flat-tree․asd file
File, Lisp, flat-tree/flat-tree.lisp: The flat-tree/flat-tree․lisp file
File, Lisp, flat-tree/package.lisp: The flat-tree/package․lisp file
flat-tree.asd: The flat-tree․asd file
flat-tree/flat-tree.lisp: The flat-tree/flat-tree․lisp file
flat-tree/package.lisp: The flat-tree/package․lisp file

L
Lisp File, flat-tree.asd: The flat-tree․asd file
Lisp File, flat-tree/flat-tree.lisp: The flat-tree/flat-tree․lisp file
Lisp File, flat-tree/package.lisp: The flat-tree/package․lisp file

Jump to:   F   L  

Next: , Previous: , Up: Indexes   [Contents][Index]

A.2 Functions

Jump to:   (  
C   D   F   I   L   M   O   P   R   S  
Index Entry  Section

(
(setf iterator-depth): Exported functions
(setf iterator-index): Exported functions
(setf iterator-offset): Exported functions
(setf iterator-step-size): Exported functions

C
children: Exported functions
copy-iterator: Internal functions
counts: Exported functions

D
depth: Exported functions
depth-n?: Internal functions

F
full-roots: Exported functions
Function, (setf iterator-depth): Exported functions
Function, (setf iterator-index): Exported functions
Function, (setf iterator-offset): Exported functions
Function, (setf iterator-step-size): Exported functions
Function, children: Exported functions
Function, copy-iterator: Internal functions
Function, counts: Exported functions
Function, depth: Exported functions
Function, depth-n?: Internal functions
Function, full-roots: Exported functions
Function, index: Exported functions
Function, iterator-depth: Exported functions
Function, iterator-index: Exported functions
Function, iterator-is-left?: Exported functions
Function, iterator-is-right?: Exported functions
Function, iterator-left-child: Exported functions
Function, iterator-left-span: Exported functions
Function, iterator-next: Exported functions
Function, iterator-offset: Exported functions
Function, iterator-p: Exported functions
Function, iterator-parent: Exported functions
Function, iterator-prev: Exported functions
Function, iterator-right-child: Exported functions
Function, iterator-right-span: Exported functions
Function, iterator-seek: Exported functions
Function, iterator-sibling: Internal functions
Function, iterator-step-size: Exported functions
Function, left-span: Exported functions
Function, make-iterator: Exported functions
Function, offset: Exported functions
Function, parent: Exported functions
Function, right-span: Exported functions
Function, sibling: Exported functions
Function, spans: Exported functions
Function, step-size: Internal functions

I
index: Exported functions
iterator-depth: Exported functions
iterator-index: Exported functions
iterator-is-left?: Exported functions
iterator-is-right?: Exported functions
iterator-left-child: Exported functions
iterator-left-span: Exported functions
iterator-next: Exported functions
iterator-offset: Exported functions
iterator-p: Exported functions
iterator-parent: Exported functions
iterator-prev: Exported functions
iterator-right-child: Exported functions
iterator-right-span: Exported functions
iterator-seek: Exported functions
iterator-sibling: Internal functions
iterator-step-size: Exported functions

L
left-span: Exported functions

M
Macro, multf: Internal macros
make-iterator: Exported functions
multf: Internal macros

O
offset: Exported functions

P
parent: Exported functions

R
right-span: Exported functions

S
sibling: Exported functions
spans: Exported functions
step-size: Internal functions

Jump to:   (  
C   D   F   I   L   M   O   P   R   S  

Next: , Previous: , Up: Indexes   [Contents][Index]

A.3 Variables

Jump to:   D   I   O   S  
Index Entry  Section

D
depth: Internal structures

I
index: Internal structures

O
offset: Internal structures

S
Slot, depth: Internal structures
Slot, index: Internal structures
Slot, offset: Internal structures
Slot, step-size: Internal structures
step-size: Internal structures

Jump to:   D   I   O   S  

Previous: , Up: Indexes   [Contents][Index]

A.4 Data types

Jump to:   F   I   P   S  
Index Entry  Section

F
flat-tree: The flat-tree system
flat-tree: The flat-tree package

I
iterator: Internal structures

P
Package, flat-tree: The flat-tree package

S
Structure, iterator: Internal structures
System, flat-tree: The flat-tree system

Jump to:   F   I   P   S