README

🌳 flattree

Build Status Go Reportcard GoDoc

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

Expand ▾ Collapse ▴

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

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

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

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}`

                                                        Source Files