Tree

package
v0.3.1 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: May 21, 2024 License: MIT Imports: 8 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func ExtractData added in v0.2.36 

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 added in v0.2.36 

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 added in v0.2.36 

type ErrMissingRoot struct{}

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

func NewErrMissingRoot added in v0.2.36 

func NewErrMissingRoot() *ErrMissingRoot

NewErrMissingRoot creates a new ErrMissingRoot.

Returns:

  • *ErrMissingRoot: The newly created error.

func (*ErrMissingRoot) Error added in v0.2.36 

func (e *ErrMissingRoot) Error() string

Error returns the error message: "missing root".

Returns:

  • string: The error message.

type ErrNodeNotPartOfTree added in v0.2.37 

type ErrNodeNotPartOfTree struct{}

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

func NewErrNodeNotPartOfTree added in v0.2.37 

func NewErrNodeNotPartOfTree() *ErrNodeNotPartOfTree

NewErrNodeNotPartOfTree creates a new ErrNodeNotPartOfTree.

Returns:

  • *ErrNodeNotPartOfTree: The newly created error.

func (*ErrNodeNotPartOfTree) Error added in v0.2.37 

func (e *ErrNodeNotPartOfTree) Error() string

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

Returns:

  • string: The error message.

type NextsFunc 

type NextsFunc[T any, I intf.Copier] func(elem T, info I) ([]T, error)

NextsFunc is a function that returns the next elements.

Parameters:

  • elem: The current element.
  • info: The info of the current element.

Returns:

  • []T: The next elements.
  • error: An error if the next elements cannot be found.

type NoInfo added in v0.2.38 

type NoInfo struct{}

NoInfo is a struct that contains no information.

func NewNoInfo added in v0.2.38 

func NewNoInfo() *NoInfo

NewNoInfo creates a new NoInfo. This is useful for when traversing a tree but no additional information is needed.

Returns:

  • *NoInfo: The NoInfo.

func (*NoInfo) Copy added in v0.2.38 

func (n *NoInfo) Copy() intf.Copier

Copy creates a copy of the NoInfo.

Returns:

  • Copier: The copy of the NoInfo.

type NoInfoNextsFunc added in v0.2.38 

type NoInfoNextsFunc[T any] func(elem T) ([]T, error)

NextsFunc is a function that returns the next elements.

Parameters:

  • elem: The current element.
  • info: The info of the current element.

Returns:

  • []T: The next elements.
  • error: An error if the next elements cannot be found.

type NoInfoObserverFunc added in v0.2.38 

type NoInfoObserverFunc[T any] func(data T) (bool, error)

ObserverFunc is a function that observes a node.

Parameters:

  • data: The data of the node.
  • info: The info of the node.

Returns:

  • bool: True if the traversal should continue, otherwise false.
  • error: An error if the observation fails.

type NoInfoTraversor added in v0.2.38 

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

NoInfoTraversor is a struct that traverses a tree.

func NoInfoTraverse added in v0.2.38 

func NoInfoTraverse[T any](tree *Tree[T], f NoInfoObserverFunc[T]) *NoInfoTraversor[T]

Traverse creates a new traversor for the tree.

Parameters:

  • tree: The tree to traverse.
  • init: The initial info.
  • f: The observer function.

Returns:

  • Traversor[T, I]: The traversor.

func (*NoInfoTraversor[T]) BFS added in v0.2.38 

func (t *NoInfoTraversor[T]) BFS() error

BFS traverses the tree in breadth-first order.

Returns:

  • error: An error if the traversal fails.

Behavior:

  • Use *ers.ErrNoError to stop the traversal without an error.

func (*NoInfoTraversor[T]) DFS added in v0.2.38 

func (t *NoInfoTraversor[T]) DFS() error

DFS traverses the tree in depth-first order.

Returns:

  • error: An error if the traversal fails.

Behavior:

  • Use *ers.ErrNoError to stop the traversal without an error.

type ObserverFunc 

type ObserverFunc[T any, I intf.Copier] func(data T, info I) (bool, error)

ObserverFunc is a function that observes a node.

Parameters:

  • data: The data of the node.
  • info: The info of the node.

Returns:

  • bool: True if the traversal should continue, otherwise false.
  • error: An error if the observation fails.

type Traversor added in v0.2.37 

type Traversor[T any, I intf.Copier] struct {
	// contains filtered or unexported fields
}

Traversor is a struct that traverses a tree.

func Traverse added in v0.2.37 

func Traverse[T any, I intf.Copier](tree *Tree[T], init I, f ObserverFunc[T, I]) *Traversor[T, I]

Traverse creates a new traversor for the tree.

Parameters:

  • tree: The tree to traverse.
  • init: The initial info.
  • f: The observer function.

Returns:

  • Traversor[T, I]: The traversor.

func (*Traversor[T, I]) BFS added in v0.2.37 

func (t *Traversor[T, I]) BFS() error

BFS traverses the tree in breadth-first order.

Returns:

  • error: An error if the traversal fails.

func (*Traversor[T, I]) DFS added in v0.2.37 

func (t *Traversor[T, I]) DFS() error

DFS traverses the tree in depth-first order.

Returns:

  • error: An error if the traversal fails.

type Tree 

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

Tree is a generic data structure that represents a tree.

func MakeTree added in v0.2.37 

func MakeTree[T any, I intf.Copier](elem T, info I, f NextsFunc[T, I]) (*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.

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 NoInfoMakeTree added in v0.2.38 

func NoInfoMakeTree[T any](elem T, f NoInfoNextsFunc[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.

func TreeOf added in v0.2.38 

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 added in v0.2.37 

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 added in v0.2.37 

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

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 added in v0.2.36 

func (t *Tree[T]) FilterChildren(filter slext.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 added in v0.2.40 

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 slext.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 added in v0.2.36 

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 added in v0.2.37 

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 added in v0.2.36 

func (t *Tree[T]) PruneBranches(filter slext.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 added in v0.2.36 

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 added in v0.2.36 

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 added in v0.2.37 

func (t *Tree[T]) SearchNodes(f slext.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 added in v0.2.37 

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 added in v0.2.36 

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 added in v0.2.36 

func (t *Tree[T]) SkipFilter(filter slext.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 added in v0.2.36 

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 added in v0.2.37 

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 added in v0.2.36 

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 (*TreeNode[T]) AddChild added in v0.2.37 

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 added in v0.2.37 

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 added in v0.2.37 

func (n *TreeNode[T]) Copy() intf.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 added in v0.2.37 

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]) FString added in v0.2.37 

func (t *TreeNode[T]) FString(trav *ffs.Traversor)

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 added in v0.2.37 

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 added in v0.2.37 

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 added in v0.2.37 

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 added in v0.2.40 

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 added in v0.2.37 

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 added in v0.2.37 

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 added in v0.2.37 

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 added in v0.2.37 

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 added in v0.2.37 

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 added in v0.2.37 

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 added in v0.2.37 

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]) ToTree added in v0.2.37 

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

ToTree converts the node to a tree.

Returns:

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

type Treeer added in v0.2.38 

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.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.