flattree

README

flat-tree

API for operating on a binary tree as an array.

Adapted from https://github.com/datrs/flat-tree.

Installation

go get github.com/kiambogo/flat-tree

Usage

import github.com/kiambogo/flat-tree

flattree.Index(0, 0) // 0
flattree.Depth(0) // 0

License

MIT

Documentation

Index

• func Children(n uint64) (left uint64, right uint64, exists bool)
• func Count(n uint64) uint64
• func Depth(n uint64) uint64
• func FullRoots(index uint64) (roots []uint64, err error)
• func Index(depth, offset uint64) uint64
• func LeftChild(n uint64) (uint64, bool)
• func LeftSpan(n uint64) uint64
• func NewIterator(index uint64) *iterator
• func Offset(n uint64) uint64
• func Parent(n uint64) uint64
• func RightChild(n uint64) (uint64, bool)
• func RightSpan(n uint64) uint64
• func Sibling(n uint64) uint64
• func Spans(n uint64) (left uint64, right uint64)
• func Uncle(n uint64) uint64

Functions

func Children

func Children(n uint64) (left uint64, right uint64, exists bool)

Children returns the children of the provided node, if it exists Returns the children and a bool indicating if they exist

func Count

func Count(n uint64) uint64

Count returns the number of nodes under the given node, including the provided node itself

func Depth

func Depth(n uint64) uint64

Depth returns the depth of a given node

func FullRoots

func FullRoots(index uint64) (roots []uint64, err error)

FullRoots returns a list of all roots less than the provided index A root is a subtrees where all nodes have either 2 or 0 children

func Index

func Index(depth, offset uint64) uint64

Index returns the flat-tree of the node at the provided depth and offset

func LeftChild

func LeftChild(n uint64) (uint64, bool)

LeftChild returns the left child of the provided node, if it exists Returns the left child and a bool indicating if it exists

func LeftSpan

func LeftSpan(n uint64) uint64

LeftSpan returns the left most node in the tree which the provided node spans

func NewIterator

func NewIterator(index uint64) *iterator

NewIterator will construct a new iterator at the designated position

func Offset

func Offset(n uint64) uint64

Offset returns the offset of a given node The offset is the distance from the left edge of the tree

func Parent

func Parent(n uint64) uint64

Parent returns the parent node of the provided node

func RightChild

func RightChild(n uint64) (uint64, bool)

RightChild returns the left child of the provided node, if it exists Returns the right child and a bool indicating if it exists

func RightSpan

func RightSpan(n uint64) uint64

RightSpan returns the right most node in the tree which the provided node spans

func Sibling

func Sibling(n uint64) uint64

Sibling returns the sibling of the provided node

func Spans

func Spans(n uint64) (left uint64, right uint64)

Spans returns the left and right most nodes in the tree which the provided node spans

func Uncle

func Uncle(n uint64) uint64

Uncle returns the parent's sibling of the provided node