The flat-tree Reference Manual

Table of Contents

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 Wed Oct 13 09:35:57 2021 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.

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

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

3 Files

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

3.1 Lisp

3.1.1 flat-tree.asd

Location

flat-tree.asd

Systems

flat-tree (system)

3.1.2 flat-tree/package.lisp

Parent

flat-tree (system)

Location

package.lisp

Packages

flat-tree

3.1.3 flat-tree/flat-tree.lisp

Dependency

package.lisp (file)

Parent

flat-tree (system)

Location

flat-tree.lisp

Exported Definitions

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

Internal Definitions

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

4 Packages

Packages are listed by definition order.

4.1 flat-tree

Source

package.lisp (file)

Use List

common-lisp

Exported Definitions

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

Internal Definitions

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

5.1 Exported definitions

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)

5.2 Internal definitions

5.2.1 Macros

Macro: multf PLACE AMT

Like ’incf’, but for multiplication.

Package

flat-tree

Source

flat-tree.lisp (file)

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)

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)

Appendix A Indexes

A.1 Concepts

A.2 Functions

A.3 Variables

A.4 Data types