The flat-tree Reference Manual

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.

1 Introduction

flat-tree

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

API

Documentation

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

2 Systems

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

flat-tree

2.1 `flat-tree`

A flat-tree implementation in Common Lisp.

Author

noffle <sww@eight45.net>

License

MIT

Version

0.0.1

Source

flat-tree.asd.

Child Components

package.lisp (file).
flat-tree.lisp (file).

3 Files

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

Lisp

3.1.1 `flat-tree/flat-tree.asd`

Source: flat-tree.asd.
Parent Component: flat-tree (system).
ASDF Systems: flat-tree.

3.1.2 `flat-tree/package.lisp`

Source: flat-tree.asd.
Parent Component: flat-tree (system).
Packages: flat-tree.

3.1.3 `flat-tree/flat-tree.lisp`

Dependency

package.lisp (file).

Source

flat-tree.asd.

Parent Component

flat-tree (system).

Public Interface

children (function).
counts (function).
depth (function).
full-roots (function).
index (function).
iterator-depth (reader).
(setf iterator-depth) (writer).
iterator-index (reader).
(setf iterator-index) (writer).
iterator-is-left? (function).
iterator-is-right? (function).
iterator-left-child (function).
iterator-left-span (function).
iterator-next (function).
iterator-offset (reader).
(setf iterator-offset) (writer).
iterator-p (function).
iterator-parent (function).
iterator-prev (function).
iterator-right-child (function).
iterator-right-span (function).
iterator-seek (function).
iterator-step-size (reader).
(setf iterator-step-size) (writer).
left-span (function).
make-iterator (function).
offset (function).
parent (function).
right-span (function).
sibling (function).
spans (function).

Internals

copy-iterator (function).
depth-n? (function).
iterator (structure).
iterator-sibling (function).
multf (macro).
step-size (function).

4 Packages

Packages are listed by definition order.

flat-tree

4.1 `flat-tree`

Source

package.lisp.

Use List

common-lisp.

Public Interface

children (function).
counts (function).
depth (function).
full-roots (function).
index (function).
iterator-depth (reader).
(setf iterator-depth) (writer).
iterator-index (reader).
(setf iterator-index) (writer).
iterator-is-left? (function).
iterator-is-right? (function).
iterator-left-child (function).
iterator-left-span (function).
iterator-next (function).
iterator-offset (reader).
(setf iterator-offset) (writer).
iterator-p (function).
iterator-parent (function).
iterator-prev (function).
iterator-right-child (function).
iterator-right-span (function).
iterator-seek (function).
iterator-step-size (reader).
(setf iterator-step-size) (writer).
left-span (function).
make-iterator (function).
offset (function).
parent (function).
right-span (function).
sibling (function).
spans (function).

Internals

copy-iterator (function).
depth-n? (function).
iterator (structure).
iterator-sibling (function).
multf (macro).
step-size (function).

5 Definitions

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

Public Interface
Internals

5.1 Public Interface

Ordinary functions

5.1.1 Ordinary 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.

Function: counts (index) ¶

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

Package: flat-tree.
Source: flat-tree.lisp.

Function: depth (index) ¶

Returns the depth of an index.

Package: flat-tree.
Source: flat-tree.lisp.

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.

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.

Reader: iterator-depth (instance) ¶

Writer: (setf iterator-depth) (instance) ¶

Package: flat-tree.
Source: flat-tree.lisp.
Target Slot: depth.

Reader: iterator-index (instance) ¶

Writer: (setf iterator-index) (instance) ¶

Package: flat-tree.
Source: flat-tree.lisp.
Target Slot: index.

Function: iterator-is-left? (iter) ¶

Is the iterator at a left sibling?

Package: flat-tree.
Source: flat-tree.lisp.

Function: iterator-is-right? (iter) ¶

Is the iterator at a right sibling?

Package: flat-tree.
Source: flat-tree.lisp.

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.

Function: iterator-left-span (iter) ¶

Move the iterator to the current left span index.

Package: flat-tree.
Source: flat-tree.lisp.

Function: iterator-next (iter) ¶

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

Package: flat-tree.
Source: flat-tree.lisp.

Reader: iterator-offset (instance) ¶

Writer: (setf iterator-offset) (instance) ¶

Package: flat-tree.
Source: flat-tree.lisp.
Target Slot: offset.

Function: iterator-p (object) ¶

Package: flat-tree.
Source: flat-tree.lisp.

Function: iterator-parent (iter) ¶

Move the iterator to its parent.

Package: flat-tree.
Source: flat-tree.lisp.

Function: iterator-prev (iter) ¶

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

Package: flat-tree.
Source: flat-tree.lisp.

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.

Function: iterator-right-span (iter) ¶

Move the iterator to the current right span index.

Package: flat-tree.
Source: flat-tree.lisp.

Function: iterator-seek (iter index) ¶

Move the iterator to a specific index.

Package: flat-tree.
Source: flat-tree.lisp.

Reader: iterator-step-size (instance) ¶

Writer: (setf iterator-step-size) (instance) ¶

Package: flat-tree.
Source: flat-tree.lisp.
Target Slot: step-size.

Function: left-span (index) ¶

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

Package: flat-tree.
Source: flat-tree.lisp.

Function: make-iterator (&key index step-size offset depth) ¶

Package: flat-tree.
Source: flat-tree.lisp.

Function: offset (index) ¶

Returns the offset of an index.

Package: flat-tree.
Source: flat-tree.lisp.

Function: parent (index) ¶

Returns the index of the parent element in tree.

Package: flat-tree.
Source: flat-tree.lisp.

Function: right-span (index) ¶

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

Package: flat-tree.
Source: flat-tree.lisp.

Function: sibling (index) ¶

Returns the index of this element’s sibling.

Package: flat-tree.
Source: flat-tree.lisp.

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.

5.2 Internals

Macros
Ordinary functions
Structures

5.2.1 Macros

Macro: multf (place amt) ¶

Like ’incf’, but for multiplication.

Package: flat-tree.
Source: flat-tree.lisp.

5.2.2 Ordinary functions

Function: copy-iterator (instance) ¶

Package: flat-tree.
Source: flat-tree.lisp.

Function: depth-n? (index depth) ¶

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

Package: flat-tree.
Source: flat-tree.lisp.

Function: iterator-sibling (iter) ¶

Move the iterator to its sibling.

Package: flat-tree.
Source: flat-tree.lisp.

Function: step-size (depth) ¶

Returns the offset step size, given ’depth’.

Package: flat-tree.
Source: flat-tree.lisp.

5.2.3 Structures

Structure: iterator ¶

Package

flat-tree.

Source

flat-tree.lisp.

Direct superclasses

structure-object.

Direct slots

Slot: index ¶

Initform: 0
Readers: iterator-index.
Writers: (setf iterator-index).

Slot: step-size ¶

Initform: 2
Readers: iterator-step-size.
Writers: (setf iterator-step-size).

Slot: offset ¶

Initform: 0
Readers: iterator-offset.
Writers: (setf iterator-offset).

Slot: depth ¶

Initform: 0
Readers: iterator-depth.
Writers: (setf iterator-depth).

Appendix A Indexes

Concepts
Functions
Variables
Data types

A.1 Concepts

A.2 Functions

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

	Index Entry	Section

(
	`(setf iterator-depth)`:	Public ordinary functions
	`(setf iterator-index)`:	Public ordinary functions
	`(setf iterator-offset)`:	Public ordinary functions
	`(setf iterator-step-size)`:	Public ordinary functions

C
	`children`:	Public ordinary functions
	`copy-iterator`:	Private ordinary functions
	`counts`:	Public ordinary functions

D
	`depth`:	Public ordinary functions
	`depth-n?`:	Private ordinary functions

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

I
	`index`:	Public ordinary functions
	`iterator-depth`:	Public ordinary functions
	`iterator-index`:	Public ordinary functions
	`iterator-is-left?`:	Public ordinary functions
	`iterator-is-right?`:	Public ordinary functions
	`iterator-left-child`:	Public ordinary functions
	`iterator-left-span`:	Public ordinary functions
	`iterator-next`:	Public ordinary functions
	`iterator-offset`:	Public ordinary functions
	`iterator-p`:	Public ordinary functions
	`iterator-parent`:	Public ordinary functions
	`iterator-prev`:	Public ordinary functions
	`iterator-right-child`:	Public ordinary functions
	`iterator-right-span`:	Public ordinary functions
	`iterator-seek`:	Public ordinary functions
	`iterator-sibling`:	Private ordinary functions
	`iterator-step-size`:	Public ordinary functions

L
	`left-span`:	Public ordinary functions

M
	`Macro, multf`:	Private macros
	`make-iterator`:	Public ordinary functions
	`multf`:	Private macros

O
	`offset`:	Public ordinary functions

P
	`parent`:	Public ordinary functions

R
	`right-span`:	Public ordinary functions

S
	`sibling`:	Public ordinary functions
	`spans`:	Public ordinary functions
	`step-size`:	Private ordinary functions

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

A.3 Variables

Jump to:	D I O S

	Index Entry	Section

D
	`depth`:	Private structures

I
	`index`:	Private structures

O
	`offset`:	Private structures

S
	`Slot, depth`:	Private structures
	`Slot, index`:	Private structures
	`Slot, offset`:	Private structures
	`Slot, step-size`:	Private structures
	`step-size`:	Private structures

Jump to:	D I O S

A.4 Data types

Jump to:	F I P S

	Index Entry	Section

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

I
	`iterator`:	Private structures

P
	`Package, flat-tree`:	The flat-tree package
	`package.lisp`:	The flat-tree/package․lisp file

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

Jump to:	F I P S

The flat-tree Reference Manual

The flat-tree Reference Manual

Table of Contents

1 Introduction

flat-tree

API

Usage

Why?

License

2 Systems

2.1 flat-tree

3 Files

3.1 Lisp

3.1.1 flat-tree/flat-tree.asd

3.1.2 flat-tree/package.lisp

3.1.3 flat-tree/flat-tree.lisp

4 Packages

4.1 flat-tree

5 Definitions

5.1 Public Interface

5.1.1 Ordinary functions

5.2 Internals

5.2.1 Macros

5.2.2 Ordinary functions

5.2.3 Structures

Appendix A Indexes

A.1 Concepts

A.2 Functions

A.3 Variables

A.4 Data types

2.1 `flat-tree`

3.1.1 `flat-tree/flat-tree.asd`

3.1.2 `flat-tree/package.lisp`

3.1.3 `flat-tree/flat-tree.lisp`

4.1 `flat-tree`