actTree

README

actTree

actTree is a Golang package which implements a double-linked tree data structure.

Nodes in actTree are double-linked together. Therefore it is efficient to travel between immediate nodes back and forth, making it a good fit for taking on "timeline review" kind of features.

actTree takes a small footprint both on code and at runtime. The code was initially a part of a board game for holding the player moves and reference diagrams, and then extracted and used by many projects for it is almost the least code to have when people need a tree structure.

Documentation

Overview

Package actTree implements a double-linked tree data structure. Features: (tiny footprint intended)

• create a new tree: actTree.New()
• add a node or merge a subtree: Add(), AddNode()
• go over all nodes by preferred order: WalkThrough()
• goto a neighbor node: Prev(), Next()
• split the tree at a node being the root of a subtree: Cut()
• remove a node and its kids: Remove()

Index

• func WalkThrough(n *Node, enter func(*Node) bool, leave func(*Node) bool)
• type Node
  • func (n *Node) Add(v interface{}) (added *Node)
  • func (n *Node) HasSib() bool
  • func (n *Node) Next() (kid *Node, nextSibling *Node)
  • func (n *Node) Prev() (parent *Node, prevSibling *Node)
• type Tree
  • func New() *Tree
  • func (t *Tree) Add(v interface{}, prev *Node) (added *Node)
  • func (t *Tree) AddNode(n, prev *Node) (added *Node)
  • func (t *Tree) Cut(n *Node) (subTree *Tree)
  • func (t *Tree) Remove(n *Node) int

Functions

func WalkThrough

func WalkThrough(n *Node, enter func(*Node) bool, leave func(*Node) bool)

WalkThrough iterates over "n" and its kid nodes. enter() and leave() called before and after visiting all kid nodes. return from enter() and leave(): true = end WalkThrough; false = continue.

Types

type Node

type Node struct {
	Value interface{} //user-defined content value to associate with the node
	// contains filtered or unexported fields
}

func (*Node) Add

func (n *Node) Add(v interface{}) (added *Node)

func (*Node) HasSib

func (n *Node) HasSib() bool

func (*Node) Next

func (n *Node) Next() (kid *Node, nextSibling *Node)

func (*Node) Prev

func (n *Node) Prev() (parent *Node, prevSibling *Node)

type Tree

type Tree struct {
	Root *Node //first node of the tree
}

func New

func New() *Tree

func (*Tree) Add

func (t *Tree) Add(v interface{}, prev *Node) (added *Node)

Add is a convenience wrapper for AddNode(&Node{Value: v}, prev)

func (*Tree) AddNode

func (t *Tree) AddNode(n, prev *Node) (added *Node)

AddNode adds a new kid or sibling node to the tree. The new node will be added after the prev node. When the prev node has no kid, new node is added as firstKid, or it is added as a sibling of firstKid. Note that the new node can be the root of another tree, making it a merge(join) function of trees.

func (*Tree) Cut

func (t *Tree) Cut(n *Node) (subTree *Tree)

Cut cuts a subtree off the original, with the given node being root of the new tree.

func (*Tree) Remove

func (t *Tree) Remove(n *Node) int

Remove deletes a node and all its kids from tree.