flattree

README

🌳 flattree

A series of functions to map a binary tree to a list. A port of flat-tree to go.

Install

dep ensure -add github.com/bcomnes/flattree

Usage

You can represent a binary tree in a simple flat list using the following structure

      3
  1       5
0   2   4   6  ...

See Godoc example on godoc.

API

See API example on godoc.

See also

• mafintosh/flat-tree: The node module that this was ported from.
• datrs/flat-tree: A port of the node module to rust.
• mafintosh/print-flat-tree: A node cli that can pretty print flat-trees.

Documentation

Overview

Package flattree implements a series of functions to map a binary tree to a list.

You can represent a binary tree in a simple flat list using the following structure

   3
 1   5
0 2 4 6 ...

This module exposes a series of functions to help you build and maintain this data structure.

See also

flat-tree for node: https://github.com/mafintosh/flat-tree.

print-flat-tree: https://github.com/mafintosh/print-flat-tree.

flat-tree for rust: https://github.com/mafintosh/flat-tree-rs.

Example

package main

import (
	"fmt"

	"github.com/bcomnes/flattree"
)

func main() {
	var list = make([]uint64, 16, 50)

	i := flattree.Index(1, 0) // get array index for depth: 0, offset: 0
	j := flattree.Index(3, 0) // get array index for depth: 1, offset: 0

	// use these indexes to store some data

	list[i] = i
	list[j] = j
	parent := flattree.Parent(j, 0)
	list[parent] = parent

	fmt.Println(i)
	fmt.Println(j)
	fmt.Println(parent)
	fmt.Println(list)
}

Output:

1
7
15
[0 1 0 0 0 0 0 7 0 0 0 0 0 0 0 15]

Index

• func Count(index, depth uint64) uint64
• func Depth(index uint64) uint64
• func FullRoots(index uint64, result []uint64) ([]uint64, error)
• func Index(depth, offset uint64) uint64
• func LeftChild(index, depth uint64) (uint64, error)
• func LeftSpan(index, depth uint64) uint64
• func Offset(index, depth uint64) uint64
• func Parent(index, depth uint64) uint64
• func RightChild(index, depth uint64) (uint64, error)
• func RightSpan(index, depth uint64) uint64
• func Sibling(index, depth uint64) uint64
• type Iterator
  • func NewIterator(index uint64) *Iterator
  • func (i *Iterator) IsLeft() bool
  • func (i *Iterator) IsRight() bool
  • func (i *Iterator) LeftChild() uint64
  • func (i *Iterator) LeftSpan() uint64
  • func (i *Iterator) Next() uint64
  • func (i *Iterator) Parent() uint64
  • func (i *Iterator) Prev() uint64
  • func (i *Iterator) RightChild() uint64
  • func (i *Iterator) RightSpan() uint64
  • func (i *Iterator) Seek(index uint64)
  • func (i *Iterator) Sibling() uint64
• type Range
  • func Children(index, depth uint64) Range
  • func Spans(index, depth uint64) Range

Examples

• Package

Functions

func Count

func Count(index, depth uint64) uint64

Count returns how many nodes (including the parent nodes) a tree contains.

func Depth

func Depth(index uint64) uint64

Depth returns the depth of an element.

func FullRoots

func FullRoots(index uint64, result []uint64) ([]uint64, error)

FullRoots returns a list of all the full roots (subtrees where all nodes have either 2 or 0 children) `<` index. For example `fullRoots(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`.

func Index

func Index(depth, offset uint64) uint64

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

func LeftChild

func LeftChild(index, depth uint64) (uint64, error)

LeftChild returns the left most child at index and depth.

func LeftSpan

func LeftSpan(index, depth uint64) uint64

LeftSpan returns the left spanning in index in the tree `index` spans.

func Offset

func Offset(index, depth uint64) uint64

Offset returns the relative offset of an element.

func Parent

func Parent(index, depth uint64) uint64

Parent returns the index of the parent element in tree.

func RightChild

func RightChild(index, depth uint64) (uint64, error)

RightChild returns the right most child at index and depth.

func RightSpan

func RightSpan(index, depth uint64) uint64

RightSpan returns the right spanning in index in the tree `index` spans.

func Sibling

func Sibling(index, depth uint64) uint64

Sibling returns the index of this elements sibling.

Types

type Iterator

type Iterator struct {
	Index, Offset, Factor uint64
}

Iterator is a stateful iterator type. Use NewIterator to create tree Iterators at a given index.

func NewIterator

func NewIterator(index uint64) *Iterator

NewIterator returns a stateful tree iterator at a given index.

func (*Iterator) IsLeft

func (i *Iterator) IsLeft() bool

IsLeft tests if the iterator at a left sibling.

func (*Iterator) IsRight

func (i *Iterator) IsRight() bool

IsRight tests if the iterator is at a right subling.

func (*Iterator) LeftChild

func (i *Iterator) LeftChild() uint64

LeftChild moves the iterator to the current left child index.

func (*Iterator) LeftSpan

func (i *Iterator) LeftSpan() uint64

LeftSpan moves the iterator to the current left span index.

func (*Iterator) Next

func (i *Iterator) Next() uint64

Next moves the iterator to the next item in the tree.

func (*Iterator) Parent

func (i *Iterator) Parent() uint64

Parent moves the iterator to the current parent index.

func (*Iterator) Prev

func (i *Iterator) Prev() uint64

Prev moves the iterator to the prev item in the tree.

func (*Iterator) RightChild

func (i *Iterator) RightChild() uint64

RightChild moves the iterator to the current right child index.

func (*Iterator) RightSpan

func (i *Iterator) RightSpan() uint64

RightSpan moves the iterator to the current right span index.

func (*Iterator) Seek

func (i *Iterator) Seek(index uint64)

Seek moves the iterator to this specific tree index.

func (*Iterator) Sibling

func (i *Iterator) Sibling() uint64

Sibling moves the iterator to the current sibling.

type Range

type Range []uint64

Range type is an inclusive tree range that is in the form of [start, finish]

func Children

func Children(index, depth uint64) Range

Children returns a Range slice `[leftChild, rightChild]` with indexes of this elements children. If this element does not have any children it returns an empty slice.

func Spans

func Spans(index, depth uint64) Range

Spans returns the Range (inclusive) the tree root at `index` spans. For example `Spans(3)` would return `[]Range{0, 6}`