The flat-tree Reference Manual

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 4.0 beta 2 "William Riker" on Wed Jun 15 03:40:45 2022 GMT+0.

Table of Contents


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


2 Systems

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


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

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

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   [Contents][Index]

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.


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

3.1.3 flat-tree/flat-tree.lisp

Dependency

package.lisp (file).

Source

flat-tree.asd.

Parent Component

flat-tree (system).

Public Interface
Internals

4 Packages

Packages are listed by definition order.


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

4.1 flat-tree

Source

package.lisp.

Use List

common-lisp.

Public Interface
Internals

5 Definitions

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


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

5.1 Public Interface


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


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

5.2.1 Macros

Macro: multf (place amt)

Like ’incf’, but for multiplication.

Package

flat-tree.

Source

flat-tree.lisp.


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

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


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

A.1 Concepts


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): 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