Tree

Documentation

Index

• type NextsFunc
• type Node
  • func NewNode[T any](data T) *Node[T]
  • func (n *Node[T]) AddChild(child *Node[T])
  • func (n *Node[T]) DeleteChild(target *Node[T]) []*Node[T]
  • func (n *Node[T]) FindBranchingPoint() *Node[T]
  • func (n *Node[T]) GetChildren() []*Node[T]
  • func (n *Node[T]) HasChild(target *Node[T]) bool
  • func (n *Node[T]) MakeChildren(children ...T)
  • func (n *Node[T]) Parent() *Node[T]
• type ObserverFunc
• type Traverser
  • func NewTraverser[T any](observer ObserverFunc[T], nexts NextsFunc[T]) Traverser[T]
  • func (t *Traverser[T]) BFS(node T) error
  • func (t *Traverser[T]) DFS(node T) error
  • func (t *Traverser[T]) MakeTree(elem T) (*Tree[T], error)
• type Tree
  • func NewTree[T any](root *Node[T]) *Tree[T]
  • func (t *Tree[T]) BFSTraversal(observer itff.ObserverFunc[T]) error
  • func (t *Tree[T]) Cleanup()
  • func (t *Tree[T]) DFSTraversal(observer itff.ObserverFunc[T]) error
  • func (t *Tree[T]) GetChildren() []T
  • func (t *Tree[T]) GetLeaves() []T
  • func (t *Tree[T]) HasChild(filter slext.PredicateFilter[T]) *Node[T]
  • func (t *Tree[T]) HasChildren(filter slext.PredicateFilter[T]) []*Node[T]
  • func (t *Tree[T]) PruneFunc(filter slext.PredicateFilter[T])
  • func (t *Tree[T]) SkipFunc(filter slext.PredicateFilter[T])
  • func (t *Tree[T]) SnakeTraversal() [][]T

Types

type NextsFunc

type NextsFunc[T any] func(node T) ([]T, error)

NextsFunc is a function that returns the children of a node.

Parameters:

• node: The node to compute the children of.

Returns:

• []T: The children of the node.
• error: An error if children cannot be computed.

type Node

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

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

func NewNode

func NewNode[T any](data T) *Node[T]

NewNode 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 (*Node[T]) AddChild

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

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

Parameters:

• data: The value of the new child.

func (*Node[T]) DeleteChild

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

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

Parameters:

• target: The child to remove.

Returns:

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

Behaviors:

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

func (*Node[T]) FindBranchingPoint

func (n *Node[T]) FindBranchingPoint() *Node[T]

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

Returns:

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

func (*Node[T]) GetChildren

func (n *Node[T]) GetChildren() []*Node[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 (*Node[T]) HasChild

func (n *Node[T]) HasChild(target *Node[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 (*Node[T]) MakeChildren

func (n *Node[T]) MakeChildren(children ...T)

MakeChildren adds zero or more children to the node with the given data.

Parameters:

• children: The values of the new children.

func (*Node[T]) Parent

func (n *Node[T]) Parent() *Node[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.

type ObserverFunc

type ObserverFunc[T any] func(node T) error

ObserverFunc is a function that observes a node.

Parameters:

• node: The node to observe.

Returns:

• error: An error if the observation fails.

type Traverser

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

Traverser is a struct that traverses a tree.

func NewTraverser

func NewTraverser[T any](observer ObserverFunc[T], nexts NextsFunc[T]) Traverser[T]

NewTraverser creates a new traverser with the given observer and nexts functions.

Parameters:

• observer: The function that observes a node.
• nexts: The function that computes the children of a node.

Returns:

• Traverser[T]: The newly created traverser.

func (*Traverser[T]) BFS

func (t *Traverser[T]) BFS(node T) error

BFS traverses the tree in breadth-first order.

Parameters:

• node: The root node of the tree.

Returns:

• error: An error if the traversal fails.

func (*Traverser[T]) DFS

func (t *Traverser[T]) DFS(node T) error

DFS traverses the tree in depth-first order.

Parameters:

• node: The root node of the tree.

Returns:

• error: An error if the traversal fails.

func (*Traverser[T]) MakeTree

func (t *Traverser[T]) MakeTree(elem T) (*Tree[T], error)

MakeTree creates a tree from the given element.

Parameters:

• elem: The element to start the tree from.

Returns:

• *Tree[T]: The tree created from the element.
• error: An error if the tree cannot be created.

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](root *Node[T]) *Tree[T]

NewTree creates a new tree with the given root.

Parameters:

• root: The root of the tree.

Returns:

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

func (*Tree[T]) BFSTraversal

func (t *Tree[T]) BFSTraversal(observer itff.ObserverFunc[T]) error

BFSTraversal traverses the tree in BFS order.

Parameters:

• observer: The observer function to apply to the nodes of the tree.

Returns:

• error: An error returned by the observer.

Behaviors:

• The traversal stops as soon as the observer returns an error.

func (*Tree[T]) Cleanup

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

Cleanup removes every node in the tree.

func (*Tree[T]) DFSTraversal

func (t *Tree[T]) DFSTraversal(observer itff.ObserverFunc[T]) error

DFSTraversal traverses the tree rooted at n in a DFS order.

Parameters:

• observer: The observer function to apply to the nodes of the tree.

Returns:

• error: An error returned by the observer.

Behaviors:

• The traversal stops as soon as the observer returns an error.

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]) GetLeaves

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

GetLeaves returns all the leaves of the tree rooted at n in a BFS order.

Returns:

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

Behaviors:

• If the tree does not have a root, it returns nil.

func (*Tree[T]) HasChild

func (t *Tree[T]) HasChild(filter slext.PredicateFilter[T]) *Node[T]

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:

• *Node[T]: The node that satisfies the filter, nil otherwise.

func (*Tree[T]) HasChildren

func (t *Tree[T]) HasChildren(filter slext.PredicateFilter[T]) []*Node[T]

HasChildren 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]) PruneFunc

func (t *Tree[T]) PruneFunc(filter slext.PredicateFilter[T])

PruneFunc 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.

Behaviors:

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

func (*Tree[T]) SkipFunc

func (t *Tree[T]) SkipFunc(filter slext.PredicateFilter[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.

Behaviors:

• This function is recursive.

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.