Tree

Documentation

Index

• func ExtractData[T any](nodes []*TreeNode[T]) []T
• func FilterNilTree[T any](tree *Tree[T]) bool
• type ErrMissingRoot
  • func NewErrMissingRoot() *ErrMissingRoot
  • func (e *ErrMissingRoot) Error() string
• type ErrNodeNotPartOfTree
  • func NewErrNodeNotPartOfTree() *ErrNodeNotPartOfTree
  • func (e *ErrNodeNotPartOfTree) Error() string
• type Tree
  • func NewTree[T any](data T) *Tree[T]
  • func TreeOf(elem any) *Tree[any]
  • func (t *Tree[T]) Cleanup()
  • func (t *Tree[T]) DeleteBranchContaining(tn *TreeNode[T]) error
  • func (t *Tree[T]) FString(trav *fsp.Traversor) error
  • func (t *Tree[T]) FilterChildren(filter us.PredicateFilter[T]) []*TreeNode[T]
  • func (t *Tree[T]) GetChildren() []T
  • func (t *Tree[T]) GetDirectChildren() []*TreeNode[T]
  • func (t *Tree[T]) GetLeaves() []*TreeNode[T]
  • func (t *Tree[T]) HasChild(filter us.PredicateFilter[T]) bool
  • func (t *Tree[T]) IsSingleton() bool
  • func (t *Tree[T]) ProcessLeaves(f uc.EvalManyFunc[T, T]) error
  • func (t *Tree[T]) PruneBranches(filter us.PredicateFilter[T]) bool
  • func (t *Tree[T]) RegenerateLeaves() []*TreeNode[T]
  • func (t *Tree[T]) Root() *TreeNode[T]
  • func (t *Tree[T]) SearchNodes(f us.PredicateFilter[T]) *TreeNode[T]
  • func (t *Tree[T]) SetChildren(children []*Tree[T]) error
  • func (t *Tree[T]) Size() int
  • func (t *Tree[T]) SkipFilter(filter us.PredicateFilter[T]) []*Tree[T]
  • func (t *Tree[T]) SnakeTraversal() [][]T
  • func (t *Tree[T]) UpdateLeaves() []*TreeNode[T]
• type TreeNode
  • func FindCommonAncestor[T any](n1, n2 *TreeNode[T]) *TreeNode[T]
  • func NewTreeNode[T any](data T) *TreeNode[T]
  • func (n *TreeNode[T]) AddChild(child *TreeNode[T])
  • func (n *TreeNode[T]) AddChildren(children ...*TreeNode[T])
  • func (n *TreeNode[T]) Copy() uc.Copier
  • func (n *TreeNode[T]) DeleteChild(target *TreeNode[T]) []*TreeNode[T]
  • func (t *TreeNode[T]) Equals(other uc.Objecter) bool
  • func (t *TreeNode[T]) FString(trav *ffs.Traversor, opts ...ffs.Option) error
  • func (tn *TreeNode[T]) FindBranchingPoint() (*TreeNode[T], *TreeNode[T], bool)
  • func (n *TreeNode[T]) GetAncestors() []*TreeNode[T]
  • func (n *TreeNode[T]) GetChildren() []*TreeNode[T]
  • func (n *TreeNode[T]) GetData() T
  • func (n *TreeNode[T]) HasChild(target *TreeNode[T]) bool
  • func (n *TreeNode[T]) IsChildOf(target *TreeNode[T]) bool
  • func (n *TreeNode[T]) IsLeaf() bool
  • func (n *TreeNode[T]) IsRoot() bool
  • func (n *TreeNode[T]) Leaves() []*TreeNode[T]
  • func (n *TreeNode[T]) Parent() *TreeNode[T]
  • func (n *TreeNode[T]) Size() int
  • func (t *TreeNode[T]) String() string
  • func (n *TreeNode[T]) ToTree() *Tree[T]
• type Treeer

Functions

func ExtractData

func ExtractData[T any](nodes []*TreeNode[T]) []T

ExtractData returns the values of the nodes in the slice.

Parameters:

• nodes: The nodes to extract the values from.

Returns:

• []T: A slice of the values of the nodes.

func FilterNilTree

func FilterNilTree[T any](tree *Tree[T]) bool

FilterNilTree is a filter that returns true if the tree is not nil.

Parameters:

• tree: The tree to filter.

Returns:

• bool: True if the tree is not nil, false otherwise.

Types

type ErrMissingRoot

type ErrMissingRoot struct{}

ErrMissingRoot is an error that is returned when the root of a tree is missing.

func NewErrMissingRoot

func NewErrMissingRoot() *ErrMissingRoot

NewErrMissingRoot creates a new ErrMissingRoot.

Returns:

• *ErrMissingRoot: The newly created error.

func (*ErrMissingRoot) Error

func (e *ErrMissingRoot) Error() string

Error returns the error message: "missing root".

Returns:

• string: The error message.

type ErrNodeNotPartOfTree

type ErrNodeNotPartOfTree struct{}

ErrNodeNotPartOfTree is an error that is returned when a node is not part of a tree.

func NewErrNodeNotPartOfTree

func NewErrNodeNotPartOfTree() *ErrNodeNotPartOfTree

NewErrNodeNotPartOfTree creates a new ErrNodeNotPartOfTree.

Returns:

• *ErrNodeNotPartOfTree: The newly created error.

func (*ErrNodeNotPartOfTree) Error

func (e *ErrNodeNotPartOfTree) Error() string

Error returns the error message: "node is not part of the tree".

Returns:

• string: The error message.

type Tree

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

Tree is a generic data structure that represents a tree.

func NewTree

func NewTree[T any](data T) *Tree[T]

NewTree creates a new tree with the given root.

Parameters:

• data: The value of the root.

Returns:

• *Tree[T]: A pointer to the newly created tree.

func TreeOf

func TreeOf(elem any) *Tree[any]

TreeOf converts the element to a tree.

Parameters:

• elem: The element to convert.

Returns:

• *Tree[T]: A pointer to the tree.

Behaviors:

• If the element is nil, the function returns nil.
• If the element implements the Treeer interface, the function calls the TreeOf method.
• Otherwise, the function creates a new tree with the element as the root.

func (*Tree[T]) Cleanup

func (t *Tree[T]) Cleanup()

Cleanup removes every node in the tree.

Behaviors:

• This function is recursive and so, it is expensive.

func (*Tree[T]) DeleteBranchContaining

func (t *Tree[T]) DeleteBranchContaining(tn *TreeNode[T]) error

DeleteBranchContaining deletes the branch containing the given node.

Parameters:

• tn: The node to delete.

Returns:

• error: An error if the node is not a part of the tree.

func (*Tree[T]) FString

func (t *Tree[T]) FString(trav *fsp.Traversor) error

FString returns a formatted string representation of the tree.

Parameters:

• indentLevel: The level of indentation to use.

Returns:

• []string: A slice of strings that represent the tree.

func (*Tree[T]) FilterChildren

func (t *Tree[T]) FilterChildren(filter us.PredicateFilter[T]) []*TreeNode[T]

FilterChildren returns all the children of the tree that satisfy the given filter in a BFS order.

Parameters:

• filter: The filter to apply.

Returns:

• []*Node[T]: A slice of pointers to the children of the node.

func (*Tree[T]) GetChildren

func (t *Tree[T]) GetChildren() []T

GetChildren returns all the children of the tree in a DFS order.

Returns:

• []T: A slice of the values of the nodes in the tree.

Behaviors:

• The root is the first element in the slice.
• If the tree does not have a root, it returns nil.

func (*Tree[T]) GetDirectChildren

func (t *Tree[T]) GetDirectChildren() []*TreeNode[T]

GetDirectChildren returns the direct children of the root of the tree.

Returns:

• []*Node[T]: A slice of pointers to the direct children of the root.

func (*Tree[T]) GetLeaves

func (t *Tree[T]) GetLeaves() []*TreeNode[T]

GetLeaves returns all the leaves of the tree.

Returns:

• []*Node[T]: A slice of pointers to the leaves of the tree.

Behaviors:

• Always returns at least one leaf.
• It returns the leaves that are stored in the tree. Make sure to call any update function before calling this function if the tree has been modified unexpectedly.

func (*Tree[T]) HasChild

func (t *Tree[T]) HasChild(filter us.PredicateFilter[T]) bool

HasChild returns true if the tree has the given child in any of its nodes in a BFS order.

Parameters:

• filter: The filter to apply.

Returns:

• bool: True if the tree has the child, false otherwise.

func (*Tree[T]) IsSingleton

func (t *Tree[T]) IsSingleton() bool

IsSingleton returns true if the tree has only one node.

Returns:

• bool: True if the tree has only one node, false otherwise.

func (*Tree[T]) ProcessLeaves

func (t *Tree[T]) ProcessLeaves(f uc.EvalManyFunc[T, T]) error

ProcessLeaves applies the given function to the leaves of the tree and replaces the leaves with the children returned by the function.

Parameters:

• f: The function to apply to the leaves.

Returns:

• error: An error returned by the function.

Behaviors:

• The function is applied to the leaves in order.
• The function must return a slice of values of type T.
• If the function returns an error, the process stops and the error is returned.
• The leaves are replaced with the children returned by the function.

func (*Tree[T]) PruneBranches

func (t *Tree[T]) PruneBranches(filter us.PredicateFilter[T]) bool

PruneBranches removes all the children of the node that satisfy the given filter. The filter is a function that takes the value of a node and returns a boolean. If the filter returns true for a child, the child is removed along with its children.

Parameters:

• filter: The filter to apply.

Returns:

• bool: True if the whole tree can be deleted, false otherwise.

Behaviors:

• If the root satisfies the filter, the tree is cleaned up.
• It is a recursive function.

func (*Tree[T]) RegenerateLeaves

func (t *Tree[T]) RegenerateLeaves() []*TreeNode[T]

RegenerateLeaves regenerates the leaves of the tree and returns them.

Returns:

• []*Node[T]: A slice of pointers to the leaves of the tree.

Behaviors:

• The leaves are updated in a DFS order.
• Expensive operation; use it only when necessary (i.e., leaves changed unexpectedly.)
• This also updates the size of the tree.

func (*Tree[T]) Root

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

Root returns the root of the tree.

Returns:

• *Node[T]: A pointer to the root of the tree.

func (*Tree[T]) SearchNodes

func (t *Tree[T]) SearchNodes(f us.PredicateFilter[T]) *TreeNode[T]

SearchNodes searches for the first node that satisfies the given filter in a BFS order.

Parameters:

• f: The filter to apply.

Returns:

• *treeNode[T]: A pointer to the node that satisfies the filter.

func (*Tree[T]) SetChildren

func (t *Tree[T]) SetChildren(children []*Tree[T]) error

SetChildren sets the children of the root of the tree.

Parameters:

• children: The children to set.

Returns:

• error: An error of type *ErrMissingRoot if the tree does not have a root.

func (*Tree[T]) Size

func (t *Tree[T]) Size() int

Size returns the number of nodes in the tree.

Returns:

• int: The number of nodes in the tree.

func (*Tree[T]) SkipFilter

func (t *Tree[T]) SkipFilter(filter us.PredicateFilter[T]) []*Tree[T]

SkipFunc removes all the children of the tree that satisfy the given filter without removing any of their children. Useful for removing unwanted nodes from the tree.

Parameters:

• filter: The filter to apply.

Returns:

• []*Tree[T]: A slice of pointers to the trees obtained after removing the nodes.

Behaviors:

• If this function returns only one tree, this is the updated tree. But, if it returns more than one tree, then we have deleted the root of the tree and obtained a forest.

func (*Tree[T]) SnakeTraversal

func (t *Tree[T]) SnakeTraversal() [][]T

SnakeTraversal returns all the paths from the root to the leaves of the tree.

Returns:

• [][]T: A slice of slices of the values of the nodes in the paths.

Behaviors:

• The paths are returned in the order of a DFS traversal.
• If the tree is empty, it returns an empty slice.

func (*Tree[T]) UpdateLeaves

func (t *Tree[T]) UpdateLeaves() []*TreeNode[T]

UpdateLeaves updates the leaves of the tree and returns them.

Returns:

• []*Node[T]: A slice of pointers to the leaves of the tree.

Behaviors:

• The leaves are updated in a DFS order.
• Less expensive than RegenerateLeaves. However, if nodes has been deleted from the tree, this may give unexpected results.
• This also updates the size of the tree.

type TreeNode

type TreeNode[T any] struct {
	// Data is the value of the node.
	Data T
	// contains filtered or unexported fields
}

TreeNode is a generic data structure that represents a node in a tree.

func FindCommonAncestor

func FindCommonAncestor[T any](n1, n2 *TreeNode[T]) *TreeNode[T]

CommonAncestor returns the first common ancestor of the two nodes.

Parameters:

• n1: The first node.
• n2: The second node.

Returns:

• *Node[T]: A pointer to the common ancestor. Nil if no such node is found.

func NewTreeNode

func NewTreeNode[T any](data T) *TreeNode[T]

NewTreeNode creates a new node with the given data.

Parameters:

• data: The value of the node.

Returns:

• *Node[T]: A pointer to the newly created node.

func (*TreeNode[T]) AddChild

func (n *TreeNode[T]) AddChild(child *TreeNode[T])

AddChild adds a new child to the node with the given data.

Parameters:

• child: The child to add.

func (*TreeNode[T]) AddChildren

func (n *TreeNode[T]) AddChildren(children ...*TreeNode[T])

AddChildren adds zero or more children to the node.

Parameters:

• children: The children to add.

Behaviors:

• This is just a more efficient way to add multiple children.

func (*TreeNode[T]) Copy

func (n *TreeNode[T]) Copy() uc.Copier

Copy returns a deep copy of the node.

Returns:

• *Node[T]: A pointer to the deep copy of the node.

Behaviors:

• This function is recursive.
• The parent is not copied.
• The data is shallow copied.

func (*TreeNode[T]) DeleteChild

func (n *TreeNode[T]) DeleteChild(target *TreeNode[T]) []*TreeNode[T]

DeleteChild removes the given child from the children of the node.

Parameters:

• target: The child to remove.

Returns:

• []*treeNode[T]: A slice of pointers to the children of the node.

Behaviors:

• If the node has no children, it returns nil.

func (*TreeNode[T]) Equals

func (t *TreeNode[T]) Equals(other uc.Objecter) bool

Equals implements common.Objecter.

func (*TreeNode[T]) FString

func (t *TreeNode[T]) FString(trav *ffs.Traversor, opts ...ffs.Option) error

FString returns a formatted string representation of the node.

Parameters:

• indentLevel: The level of indentation to use.

Returns:

• []string: A slice of strings that represent the node.

func (*TreeNode[T]) FindBranchingPoint

func (tn *TreeNode[T]) FindBranchingPoint() (*TreeNode[T], *TreeNode[T], bool)

FindBranchingPoint returns the first node in the path from n to the root such that has more than one sibling.

Returns:

• *treeNode[T]: A pointer to the one node before the branching point.
• *treeNode[T]: A pointer to the branching point.
• bool: True if the node has a branching point, false otherwise.

Behaviors:

• If there is no branching point, it returns the root of the tree.

func (*TreeNode[T]) GetAncestors

func (n *TreeNode[T]) GetAncestors() []*TreeNode[T]

GetAncestors returns all the ancestors of the node.

Returns:

• []*Node[T]: A slice of pointers to the ancestors of the node.

Behaviors:

• The ancestors are returned in the opposite order of a DFS traversal. Therefore, the first element is the parent of the node.

func (*TreeNode[T]) GetChildren

func (n *TreeNode[T]) GetChildren() []*TreeNode[T]

GetChildren returns all the children of the node. If the node has no children, it returns nil.

Returns:

• []*Node[T]: A slice of pointers to the children of the node.

func (*TreeNode[T]) GetData

func (n *TreeNode[T]) GetData() T

GetData is a getter for the data of the node.

Returns:

• T: The data of the node.

func (*TreeNode[T]) HasChild

func (n *TreeNode[T]) HasChild(target *TreeNode[T]) bool

HasChild returns true if the node has the given child.

Parameters:

• target: The child to check for.

Returns:

• bool: True if the node has the child, false otherwise.

func (*TreeNode[T]) IsChildOf

func (n *TreeNode[T]) IsChildOf(target *TreeNode[T]) bool

IsChildOf returns true if the node is a child of the parent.

Parameters:

• target: The target parent to check for.

Returns:

• bool: True if the node is a child of the parent, false otherwise.

func (*TreeNode[T]) IsLeaf

func (n *TreeNode[T]) IsLeaf() bool

IsLeaf returns true if the node is a leaf.

Returns:

• bool: True if the node is a leaf, false otherwise.

func (*TreeNode[T]) IsRoot

func (n *TreeNode[T]) IsRoot() bool

IsRoot returns true if the node does not have a parent.

Returns:

• bool: True if the node is the root, false otherwise.

func (*TreeNode[T]) Leaves

func (n *TreeNode[T]) Leaves() []*TreeNode[T]

Leaves returns all the leaves of the tree rooted at n.

Returns:

• []*Node[T]: A slice of pointers to the leaves of the tree.

Behaviors:

• The leaves are returned in the order of a DFS traversal.

func (*TreeNode[T]) Parent

func (n *TreeNode[T]) Parent() *TreeNode[T]

Parent is a getter for the parent of the node.

Returns:

• *Node[T]: A pointer to the parent of the node. Nil if the node has no parent.

func (*TreeNode[T]) Size

func (n *TreeNode[T]) Size() int

Size returns the number of nodes in the tree rooted at n.

Returns:

• int: The number of nodes in the tree.

Behaviors:

• This function is expensive since size is not stored.

func (*TreeNode[T]) String

func (t *TreeNode[T]) String() string

String implements common.Objecter.

func (*TreeNode[T]) ToTree

func (n *TreeNode[T]) ToTree() *Tree[T]

ToTree converts the node to a tree.

Returns:

• *Tree[T]: A pointer to the tree.

type Treeer

type Treeer[T any] interface {
	// TreeOf converts the type to a tree.
	//
	// Returns:
	//   - *Tree[T]: A pointer to the tree.
	TreeOf() *Tree[T]
}

Treeer is an interface for types that can be converted to a tree.