tree

README

go-common/tree

This repository contains the go-common/tree library.

To install:

go get github.com/ugorji/go-common/tree

Package Documentation

Package tree implements traversal of tree structures (parent node with child nodes).

The variant types and corresponding functions supports a tree structure (node with child nodes).

You can:

• represent a tree as a 1-dimensional slice
• walk a tree
• write tree out to an input stream as text.

This code has now been updated to remove reference to parents, and prevent the cyclic structure. This allows us to encode a Tree using gob.

REPRESENTATION AS SLICE

A tree can be representated as a 1-dimensional slice.

Given a tree like:

    ROOT
      a1
      a2
        b1
           c1
           c2
           c3
             d1
             d2
             d3
        b2
        b3
      a3

And

    DESC, RET

Encode to an an array like:

    a1, a2, DESC, b1, DESC, c1, c2, DESC, d1, d2, d3, RET, RET, b2, b3, RET, a3

Decode same array to a tree as above.

WALKING

You can walk a slice or write it out to an input stream as text.

During a walk, all the walk events are made available to the walk function.

Walk Algorithm

    Perform EnterEvent operation
    if breadth first, Perform VisitEvent operation
    for i=0 to n-1 do
      Walk child[i], if present
      Perform BackUpEvent operation
    if depth first, Perform VisitEvent operation

Code Generation

any_tree.go is the generic version of the tree.

We auto-generate the specific versions for an int64 tree and a uint64 tree.

You can update gen.sh to auto-generate for other types.

Run go generate (or gen.sh) in this directory to re-generate them.

    Make sure you run this each time any_tree.go is updated.

Exported Package API

var DefDesc = new(struct{}) ...
var Int64DefDesc = int64(math.MinInt64 + 1) ...
var Uint64DefDesc = uint64(math.MaxUint64 - 1) ...
var StopDescent = errors.New("Stop Descent")
type Codec struct{ ... }
    func NewCodec() Codec
type Event int
    const EnterEvent Event = iota + 1 ...
type Int64Codec struct{ ... }
    func NewInt64Codec() Int64Codec
type Int64Node struct{ ... }
type Int64WalkFunc func(n *Int64Node, evt Event) (err error)
type Node struct{ ... }
type Uint64Codec struct{ ... }
    func NewUint64Codec() Uint64Codec
type Uint64Node struct{ ... }
type Uint64WalkFunc func(n *Uint64Node, evt Event) (err error)
type WalkFunc func(n *Node, evt Event) (err error)

Documentation

Overview

Package tree implements traversal of tree structures (parent node with child nodes).

The variant types and corresponding functions supports a tree structure (node with child nodes).

You can:

• represent a tree as a 1-dimensional slice
• walk a tree
• write tree out to an input stream as text.

This code has now been updated to remove reference to parents, and prevent the cyclic structure. This allows us to encode a Tree using gob.

REPRESENTATION AS SLICE

A tree can be representated as a 1-dimensional slice.

Given a tree like:

ROOT
  a1
  a2
    b1
       c1
       c2
       c3
         d1
         d2
         d3
    b2
    b3
  a3

And

DESC, RET

Encode to an an array like:

a1, a2, DESC, b1, DESC, c1, c2, DESC, d1, d2, d3, RET, RET, b2, b3, RET, a3

Decode same array to a tree as above.

WALKING

You can walk a slice or write it out to an input stream as text.

During a walk, all the walk events are made available to the walk function.

Walk Algorithm

Perform EnterEvent operation
if breadth first, Perform VisitEvent operation
for i=0 to n-1 do
  Walk child[i], if present
  Perform BackUpEvent operation
if depth first, Perform VisitEvent operation

Code Generation

any_tree.go is the generic version of the tree.

We auto-generate the specific versions for an int64 tree and a uint64 tree.

You can update gen.sh to auto-generate for other types.

Run `go generate` (or gen.sh) in this directory to re-generate them.

Make sure you run this each time any_tree.go is updated.

Index

• Variables
• type Codec
  • func NewCodec() Codec
  • func (c Codec) DecodeChildren(n *Node, vals []interface{})
  • func (c Codec) EncodeChildren(n *Node, vals []interface{}) []interface{}
• type Event
• type Int64Codec
  • func NewInt64Codec() Int64Codec
  • func (c Int64Codec) DecodeChildren(n *Int64Node, vals []int64)
  • func (c Int64Codec) EncodeChildren(n *Int64Node, vals []int64) []int64
• type Int64Node
  • func (n *Int64Node) Copy() (n2 *Int64Node)
  • func (n *Int64Node) Walk(depthFirst bool, reverse bool, fn Int64WalkFunc) (err error)
  • func (n *Int64Node) Write(depthFirst bool, reverse bool, w io.Writer, indentStr string) error
• type Int64WalkFunc
• type Node
  • func (n *Node) Copy() (n2 *Node)
  • func (n *Node) Walk(depthFirst bool, reverse bool, fn WalkFunc) (err error)
  • func (n *Node) Write(depthFirst bool, reverse bool, w io.Writer, indentStr string) error
• type Uint64Codec
  • func NewUint64Codec() Uint64Codec
  • func (c Uint64Codec) DecodeChildren(n *Uint64Node, vals []uint64)
  • func (c Uint64Codec) EncodeChildren(n *Uint64Node, vals []uint64) []uint64
• type Uint64Node
  • func (n *Uint64Node) Copy() (n2 *Uint64Node)
  • func (n *Uint64Node) Walk(depthFirst bool, reverse bool, fn Uint64WalkFunc) (err error)
  • func (n *Uint64Node) Write(depthFirst bool, reverse bool, w io.Writer, indentStr string) error
• type Uint64WalkFunc
• type WalkFunc

Variables

var (
	DefDesc = new(struct{})
	DefAsc  = new(struct{})
)

var (
	Int64DefDesc = int64(math.MinInt64 + 1)
	Int64DefAsc  = int64(math.MinInt64 + 2)
)

var (
	Uint64DefDesc = uint64(math.MaxUint64 - 1)
	Uint64DefAsc  = uint64(math.MaxUint64 - 2)
)

var (
	//StopDescent is returned as an error during a Walk to signify
	//that the Walk should not proceed below this node for this edge.
	StopDescent = errors.New("Stop Descent")
)

Types

type Codec

type Codec struct {
	Desc interface{}
	Asc  interface{}
}

A Codec is used to encode or decode a Node into/from a slice. Slices are easier to store and manage, especially in some app environments e.g. Google App Engine.

func NewCodec

func NewCodec() Codec

func (Codec) DecodeChildren

func (c Codec) DecodeChildren(n *Node, vals []interface{})

Decodes the children of Node n from the slice. Note that the "root" ie n is not reflected in the slice.

func (Codec) EncodeChildren

func (c Codec) EncodeChildren(n *Node, vals []interface{}) []interface{}

Encodes the children of Node n into the slice . Note that the "root" ie n is not reflected in the slice. It's okay to pass a nil slice for starters.

type Event

type Event int

A Event is passed to each invocation of WalkFunc.

const (
	//Event done at start of walking each node
	EnterEvent Event = iota + 1
	//Event done after walking each child node (return to parent)
	BackUpEvent
	//Event done to visit node
	VisitEvent
)

type Int64Codec

type Int64Codec struct {
	Desc int64
	Asc  int64
}

A Int64Codec is used to encode or decode a Int64Node into/from a slice. Slices are easier to store and manage, especially in some app environments e.g. Google App Engine.

func NewInt64Codec

func NewInt64Codec() Int64Codec

func (Int64Codec) DecodeChildren

func (c Int64Codec) DecodeChildren(n *Int64Node, vals []int64)

Decodes the children of Int64Node n from the slice. Note that the "root" ie n is not reflected in the slice.

func (Int64Codec) EncodeChildren

func (c Int64Codec) EncodeChildren(n *Int64Node, vals []int64) []int64

Encodes the children of Int64Node n into the slice . Note that the "root" ie n is not reflected in the slice. It's okay to pass a nil slice for starters.

type Int64Node

type Int64Node struct {
	//don't keep a reference to the parent.
	Value    int64
	Children []*Int64Node
}

func (*Int64Node) Copy

func (n *Int64Node) Copy() (n2 *Int64Node)

Copy returns a deep copy of Int64Node n. This just means that a copy of the node and copies of the children are returned. However, the "Value" in each node stays the same.

func (*Int64Node) Walk

func (n *Int64Node) Walk(depthFirst bool, reverse bool, fn Int64WalkFunc) (err error)

Walk Int64Node n, depth first or breadth first, and call fn for every event during the Walk.

func (*Int64Node) Write

func (n *Int64Node) Write(depthFirst bool, reverse bool, w io.Writer, indentStr string) error

Write a Int64Node into a Writer, using the indent string given to signify indents.

type Int64WalkFunc

type Int64WalkFunc func(n *Int64Node, evt Event) (err error)

Function called for each event during a TreeWalk. Return StopDescent if you don't want to walk down a node further.

type Node

type Node struct {
	//don't keep a reference to the parent.
	Value    interface{}
	Children []*Node
}

func (*Node) Copy

func (n *Node) Copy() (n2 *Node)

Copy returns a deep copy of Node n. This just means that a copy of the node and copies of the children are returned. However, the "Value" in each node stays the same.

func (*Node) Walk

func (n *Node) Walk(depthFirst bool, reverse bool, fn WalkFunc) (err error)

Walk Node n, depth first or breadth first, and call fn for every event during the Walk.

func (*Node) Write

func (n *Node) Write(depthFirst bool, reverse bool, w io.Writer, indentStr string) error

Write a Node into a Writer, using the indent string given to signify indents.

type Uint64Codec

type Uint64Codec struct {
	Desc uint64
	Asc  uint64
}

A Uint64Codec is used to encode or decode a Uint64Node into/from a slice. Slices are easier to store and manage, especially in some app environments e.g. Google App Engine.

func NewUint64Codec

func NewUint64Codec() Uint64Codec

func (Uint64Codec) DecodeChildren

func (c Uint64Codec) DecodeChildren(n *Uint64Node, vals []uint64)

Decodes the children of Uint64Node n from the slice. Note that the "root" ie n is not reflected in the slice.

func (Uint64Codec) EncodeChildren

func (c Uint64Codec) EncodeChildren(n *Uint64Node, vals []uint64) []uint64

Encodes the children of Uint64Node n into the slice . Note that the "root" ie n is not reflected in the slice. It's okay to pass a nil slice for starters.

type Uint64Node

type Uint64Node struct {
	//don't keep a reference to the parent.
	Value    uint64
	Children []*Uint64Node
}

func (*Uint64Node) Copy

func (n *Uint64Node) Copy() (n2 *Uint64Node)

Copy returns a deep copy of Uint64Node n. This just means that a copy of the node and copies of the children are returned. However, the "Value" in each node stays the same.

func (*Uint64Node) Walk

func (n *Uint64Node) Walk(depthFirst bool, reverse bool, fn Uint64WalkFunc) (err error)

Walk Uint64Node n, depth first or breadth first, and call fn for every event during the Walk.

func (*Uint64Node) Write

func (n *Uint64Node) Write(depthFirst bool, reverse bool, w io.Writer, indentStr string) error

Write a Uint64Node into a Writer, using the indent string given to signify indents.

type Uint64WalkFunc

type Uint64WalkFunc func(n *Uint64Node, evt Event) (err error)

Function called for each event during a TreeWalk. Return StopDescent if you don't want to walk down a node further.

type WalkFunc

type WalkFunc func(n *Node, evt Event) (err error)

Function called for each event during a TreeWalk. Return StopDescent if you don't want to walk down a node further.