tree

README

tree

Package tree implements a simple tree that can be built from and stored to a row based data format, such as a relational database or csv file.

A tree is here defined as a graph having three properties:

• a single root node with no inbound edges
• all non-root nodes have exactly one inbound edge (parent)
• any node may have any number of outbound edges (children) The nodes of the tree are assumed to have a primary identifier or key by which parent and child relationships can be defined.

Objectives

The goal fo this tree is to implement a generic tree with minimal memory usage and maximal performance for general use cases. This package does not philosophically attempt to avoid panic-ing, as that safety comes at the price of sacrificed performance. Therefore, it would be expected that an implementer will perform nil checks as appropriate.

Development

Documentation can be greated with godoc.

Documentation

Overview

Package tree implements a simple tree that can be serialized and deserialized from a byte-based storage, such as a file or cloud storage.

A tree is here defined as a graph having three properties:

• a single root node with no inbound edges
• all non-root nodes have exactly one inbound edge (parent)
• any node may have any number of outbound edges (children)

The nodes of the tree are assumed to have a primary identifier or key by which parent and child relationships can be defined.

The implemented tree data structure consists of a pointer to the root node and an index allowing fast lookup of nodes by their primary key. Each node holds the primary key of itself and its parent, as well as a pointer to its parent and an array of pointers to its children. All nodes also store an arbitrary set of node data, which can be any structure. Children of a node are not ordered, and therefore are traversed in an order determined by the order in which they are added to the tree.

This package includes tree traversal algorithms for breadth-first and depth- first search.

Index

• type Node
• type TraversalType
• type Tree
  • func Deserialize[T any](stream io.ReadCloser) (*Tree[T], error)
  • func Empty[T any]() *Tree[T]
  • func (t *Tree[T]) Add(nodeID uint, parentID uint, data T) (added bool, exists bool)
  • func (t *Tree[T]) Find(id uint) (n Node[T], ok bool)
  • func (t *Tree[T]) FindParents(id uint) (parents []Node[T], ok bool)
  • func (t *Tree[T]) Merge(other *Tree[T]) bool
  • func (t *Tree[T]) Root() Node[T]
  • func (t *Tree[T]) Serialize(trvsl TraversalType) (io.ReadCloser, <-chan error)
  • func (t *Tree[T]) Traverse(trvsl TraversalType) <-chan Node[T]

Types

type Node

type Node[T any] interface {
	// GetID returns the primary key of this node.
	GetID() uint
	// GetParentID returns the primary key of this node's parent.
	GetParentID() uint

	// GetChildren returns an array of pointers to all children of this node.
	GetChildren() []Node[T]
	// GetParent returns a pointer to the parent node of this node.
	GetParent() Node[T]

	// AddChildren adds a list of Nodes as children of this node.
	AddChildren(...Node[T])
	// ReplaceChildren replaces the current list of children with a new list of
	// Nodes.
	ReplaceChildren(...Node[T])

	// GetData retruns this node's internal data.
	GetData() T
	// SetData replaces this nodes data with the argument. The argument may be any
	// type, but must be serializable via json.
	//
	// This function does not attempt to test json encoding when the data is set;
	// any error with encoding will only occur when the data is serialized
	// to a repository.
	SetData(T)
	// contains filtered or unexported methods
}

Node is the interface for a node within a tree.

This package implementes this interface with an internal struct representation. This interface cannot be implemented by other packages due to unexported fields.

The properties of a Node are that it has a uint primary key, a parent Node and an array of child Nodes. Instantiating a Node through the Tree.Add() function allows the node to be created with a parentID. This represents the primary key ID of a parent that may not be added to the tree yet. This value can be specified to indentify parents added to the tree after their children.

The node also has arbitrary data attached to it; any struct may be inserted as the data. However, because the data is not specified, this trait contains no functionality to modify the data in place. The data should be implemented as a pointer to avoid performance ramifications.

The associated data attached to a node must be serializable using the json encoding. If either node or arbitrary data is not, the Tree.Serialize() function will throw serialization errors when called. There is no serialization checking at the time that a Node is added to a tree or that its data is updated.

When this node is serialized, only the id and parent id, along with associated data are serialized. The internal pointers to parent and children are recreated with the nodes are deserialized.

type TraversalType

type TraversalType int

TraversalType determines the order in which an operation is performed on a tree.

const (
	// TraverseBreadthFirst traverses the tree breadth first. For any node
	// currently being traversed, all children of this node are traversed
	// before any of the children's children are visited.
	TraverseBreadthFirst TraversalType = iota
	// TraverseDepthFrist traverses the tree depth first. For any node
	// currently being traversed, all descendents of any child will be
	// traversed before any subsequent children of the current node are
	// visited.
	TraverseDepthFirst
)

type Tree

type Tree[T any] struct {
	// contains filtered or unexported fields
}

Tree is a data structure representing a tree. It contains a pointer to a root node and an index of primary keys implemented as a hash map.

func Deserialize

func Deserialize[T any](stream io.ReadCloser) (*Tree[T], error)

Deserialize decodes a data stream into a tree.

Decode is validated for data streams encoded via the [`Serialize`] method on [`Tree`]. While encoding is implemented with the json packagae, There is no guarantee that it will deserialize data encoded in any other way.

The argument ReadCloser is a stream with data from a serialized tree. If any node of the tree fails to deserialize, this function will abord and return an error.

func Empty

func Empty[T any]() *Tree[T]

Empty creates and returns an empty tree. The empty tree has a nil pointer to its root node and an empty node index.

func (*Tree[T]) Add

func (t *Tree[T]) Add(nodeID uint, parentID uint, data T) (added bool, exists bool)

Add inserts an element into a tree as a node. This function returns two boolean values:

• added - indicates that the element was successfully inserted into the tree
• exists - indicates that the element's primary was already found in the tree

There are two ways that insertion can fail. If the element's parent is not found, then the element is not inserted; added and exists will both be false. If the element's primary key already exists in the index, then added will be false and exists will be true. If the element is added as expected, then added will be true and exists will be false.

If the element to be added has a primary key that matches the parent key of the root node, the tree will be re-rooted by adding this element as the new root. If there is a cyclical reference when attempting to re-root, i.e. the parent of the existing root is the new node and the parent of the new node exists elsewhere in the tree, the element will fail to add.

Do not set a primaryID to zero, as this value should be reserved for the case where a node has no parent.

func (*Tree[T]) Find

func (t *Tree[T]) Find(id uint) (n Node[T], ok bool)

Find looks up a node by its primary key. If the node is found, then ok is true and a Node is returned. If the node is not found, then ok is false an a nil pointer is returned.

func (*Tree[T]) FindParents

func (t *Tree[T]) FindParents(id uint) (parents []Node[T], ok bool)

FindParents finds the list of all parent nodes between a target node and the root of a tree. The node is identified by its primary key. If the primary key cannot be found in the tree, then ok is false and an empty array is returned. If the target node is found in the tree, then ok is true and the parent nodes are returned in an array. If the target node is the root of the tree, the parent nodes array is empty.

The parent nodes array is ordered from immediate parent first to tree root last.

func (*Tree[T]) Merge

func (t *Tree[T]) Merge(other *Tree[T]) bool

Merge another tree (passed in the argument) into the target tree (passed as the subject of this method call). All data from the other tree is added to the target tree, if a relationship can be found between the two trees. A relationship is established if and only if the parent of the head of the other tree is found in the target tree.

If the merge is successful, returns true, otherwise return false. The merge can fail if there are duplicate primary keys between the two trees. The merge can also fail if the parent of the head of the other tree is not found in the target tree.

func (*Tree[T]) Root

func (t *Tree[T]) Root() Node[T]

Root returns the root node of a tree. If the tree has no nodes, this function returns nil.

func (*Tree[T]) Serialize

func (t *Tree[T]) Serialize(trvsl TraversalType) (io.ReadCloser, <-chan error)

Serialize encodes the tree as a byte stream.

The argument TraversalType will determine the traversal order in which the tree is serialized. TraversalType does not matter for deserialization; the internal metadata of the nodes will create the shape of the tree when it is deserialized, not the order in which the nodes are serialized to storage.

The associated data of each node is serialized with it. This data may be set the the caller and may not be serializable. If the associated data cannot be serialzied using the json package, then this function will throw an error. Once any error is thrown, serialization stops.

The serialization is implemented into a goroutine which will populate the ReadCloser return value as elements are consumed from it by the caller. the <-chan error exists to pass any serialization error back from the encoding goroutine.

func (*Tree[T]) Traverse

func (t *Tree[T]) Traverse(trvsl TraversalType) <-chan Node[T]

Traverse visits each node of a tree in a specified order, returning those nodes to an iterator-like chennel.

This function takes as an argumentt a TraversalType which defines the order of traversal. All node in the tree are traversed in this order. The Nodes traversed are pushed to an unbuffered channel and must be consumed by caller.

If a tree is modified after the traversal has begun, any node that is added after its correct place in traversal order will not be visited, nor will any of its children.