tree

package
v0.1.21 Latest Latest
Warning

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

 Go to latest Published: Sep 24, 2024 License: MIT Imports: 7 Imported by: 5

Documentation

Index

Constants

This section is empty.

Variables

View Source 
var (
	// NodeNotPartOfTree is an error that is returned when a node is not part of a tree.
	NodeNotPartOfTree error
)

Functions

func ApplyBFS added in v0.1.13 

func ApplyBFS[T interface {
	BackwardChild() iter.Seq[T]
	Child() iter.Seq[T]
	Cleanup() []T
	Copy() T
	LinkChildren(children []T)
	TreeNoder
}](t *Tree[T], trav Traverser[T]) (any, error)

ApplyBFS applies the BFS traversal logic to the tree.

Parameters:

  • t: The tree to apply the traversal logic to.
  • trav: The traverser that holds the traversal logic.

Returns:

  • I: The final traversal info.
  • error: The error that might occur during the traversal.

func ApplyDFS added in v0.1.13 

func ApplyDFS[T interface {
	BackwardChild() iter.Seq[T]
	Child() iter.Seq[T]
	Cleanup() []T
	Copy() T
	LinkChildren(children []T)
	TreeNoder
}](t *Tree[T], trav Traverser[T]) (any, error)

ApplyDFS applies the DFS traversal logic to the tree.

Parameters:

  • t: The tree to apply the traversal logic to.
  • trav: The traverser that holds the traversal logic.

Returns:

  • I: The final traversal info.
  • error: The error that might occur during the traversal.

func Cleanup added in v0.1.13 

func Cleanup[T interface {
	Cleanup() []T
	TreeNoder
}](node T)

Cleanup is used to delete all the children of the given node.

Parameters:

  • node: The node to delete the children of.

func DeepCopy added in v0.1.13 

func DeepCopy[T interface {
	Child() iter.Seq[T]
	Copy() T
	LinkChildren(children []T)
	TreeNoder
}](node T) T

DeepCopy is a method that deep copies the node.

Parameters:

  • node: The node to copy.

Returns:

  • T: The copied node.

func DeleteBranchContaining 

func DeleteBranchContaining[T interface {
	BackwardChild() iter.Seq[T]
	Child() iter.Seq[T]
	Cleanup() []T
	Copy() T
	DeleteChild(child T) []T
	GetParent() (T, bool)
	LinkChildren(children []T)
	TreeNoder
}](tree *Tree[T], n T) error

DeleteBranchContaining deletes the branch containing the given node.

Parameters:

  • tree: The tree to delete the branch from.
  • n: The node to delete.

Returns:

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

func FindBranchingPoint 

func FindBranchingPoint[T interface {
	Child() iter.Seq[T]
	BackwardChild() iter.Seq[T]
	Copy() T
	GetParent() (T, bool)
	LinkChildren(children []T)
	TreeNoder
}](n T) (T, *T, bool)

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

Parameters:

  • n: The node to start the search.

Returns:

  • TreeNoder: The branching point. Nil if no branching point was found.
  • TreeNoder: The parent of the branching point. Nil if n is nil.
  • 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. However, if n is nil, it returns nil, nil, false and if the node has no parent, it returns nil, n, false.

func FindCommonAncestor 

func FindCommonAncestor[T interface {
	GetParent() (T, bool)
	TreeNoder
}](n1, n2 T) (T, bool)

FindCommonAncestor returns the first common ancestor of the two nodes.

This function is expensive as it calls GetNodeAncestors two times.

Parameters:

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

Returns:

  • T: The common ancestor.
  • bool: True if the nodes have a common ancestor, false otherwise.

func GetNodeAncestors 

func GetNodeAncestors[T interface {
	GetParent() (T, bool)
	TreeNoder
}](node T) []T

GetAncestors is used to get all the ancestors of the given node. This excludes the node itself.

Parameters:

  • node: The node to get the ancestors of.

Returns:

  • []T: The ancestors of the node.

This is expensive since ancestors are not stored and so, every time this function is called, it has to traverse the tree to find the ancestors. Thus, it is recommended to call this function once and then store the ancestors somewhere if needed.

Despite the above, this function does not use recursion and is safe to use.

Finally, no nil nodes are returned.

func GetNodeLeaves 

func GetNodeLeaves[T interface {
	Child() iter.Seq[T]
	Copy() T
	TreeNoder
}](node T) []T

GetNodeLeaves returns the leaves of the given node.

This is expensive as leaves are not stored and so, every time this function is called, it has to do a DFS traversal to find the leaves. Thus, it is recommended to call this function once and then store the leaves somewhere if needed.

Despite the above, this function does not use recursion and is safe to use.

Finally, no nil nodes are returned.

func GetNodeSize 

func GetNodeSize[T interface {
	Child() iter.Seq[T]
	TreeNoder
}](node T) int

Size implements the *TreeNode[T] interface.

This is expensive as it has to traverse the whole tree to find the size of the tree. Thus, it is recommended to call this function once and then store the size somewhere if needed.

Despite the above, this function does not use recursion and is safe to use.

Finally, the traversal is done in a depth-first manner.

func Prune 

func Prune[T interface {
	BackwardChild() iter.Seq[T]
	Child() iter.Seq[T]
	Cleanup() []T
	Copy() T
	DeleteChild(child T) []T
	GetParent() (T, bool)
	LinkChildren(children []T)
	TreeNoder
}](tree *Tree[T], filter func(node T) bool) bool

PruneTree prunes the tree using the given filter.

Parameters:

  • tree: The tree to prune.
  • filter: The filter to use to prune the tree. Must return true iff the node should be pruned.

Returns:

  • bool: False if the whole tree can be deleted, true otherwise.

func PruneBranches 

func PruneBranches[T interface {
	BackwardChild() iter.Seq[T]
	Child() iter.Seq[T]
	Cleanup() []T
	Copy() T
	DeleteChild(child T) []T
	GetParent() (T, bool)
	LinkChildren(children []T)
	TreeNoder
}](tree *Tree[T], filter func(node T) bool) 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:

  • tree: The tree to prune.
  • filter: The filter to apply. Must return true iff the node should be pruned.

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 PruneFunc 

func PruneFunc[T interface {
	BackwardChild() iter.Seq[T]
	Child() iter.Seq[T]
	Cleanup() []T
	Copy() T
	DeleteChild(child T) []T
	GetParent() (T, bool)
	LinkChildren(children []T)
	TreeNoder
}](tree *Tree[T], filter func(node T) bool) bool

PruneFunc removes all the children of the node that satisfy the given filter including all of their children. If the filter is nil, nothing is removed.

Parameters:

  • filter: The filter to apply. Must return true iff the node should be pruned.

Returns:

  • bool: True if the node satisfies the filter, false otherwise.

Behaviors:

  • The root node is not pruned.

func RootOf added in v0.1.13 

func RootOf[T interface {
	GetParent() (T, bool)
	TreeNoder
}](node T) T

RootOf returns the root of the given node.

Parameters:

  • node: The node to get the root of.

Returns:

  • T: The root of the given node.

Types

type Branch 

type Branch[T interface {
	Child() iter.Seq[T]
	GetParent() (T, bool)
	TreeNoder
}] struct {
	// contains filtered or unexported fields
}

Branch represents a branch in a tree.

func ExtractBranch 

func ExtractBranch[T interface {
	BackwardChild() iter.Seq[T]
	Child() iter.Seq[T]
	Cleanup() []T
	Copy() T
	DeleteChild(child T) []T
	GetParent() (T, bool)
	LinkChildren(children []T)
	TreeNoder
}](tree *Tree[T], leaf T, delete bool) *Branch[T]

ExtractBranch extracts the branch of the tree that contains the given leaf.

Parameters:

  • tree: The tree to search.
  • leaf: The leaf to extract the branch from.
  • delete: If true, the branch is deleted from the tree.

Returns:

  • *Branch[T]: A pointer to the branch extracted. Nil if the leaf is not a part of the tree. Nil if the leaf is not a part of the tree and delete is false.

Behaviors:

  • If delete is true, then the branch is deleted from the tree.

func NewBranch 

func NewBranch[T interface {
	Child() iter.Seq[T]
	GetParent() (T, bool)
	TreeNoder
}](node T) (*Branch[T], error)

NewBranch works like GetAncestors but includes the node itself.

The nodes are returned as a slice where [0] is the root node and [len(branch)-1] is the leaf node.

Parameters:

  • node: The node to get the ancestors of.

Returns:

  • *Branch: The branch from the node to the root.
  • error: An error if the creation fails (i.e., the node is not of type T).

func (Branch[T]) Node added in v0.1.13 

func (b Branch[T]) Node() iter.Seq[T]

Node is a method that scans the branch from the top to the bottom.

Returns:

  • iter.Seq[T]: A sequence of nodes from the top to the bottom.

type Builder added in v0.1.8 

type Builder[T interface {
	AddChild(child T)
	BackwardChild() iter.Seq[T]
	Child() iter.Seq[T]
	Cleanup() []T
	Copy() T
	LinkChildren(children []T)
	TreeNoder
}, I interface {
	Copy() I
}] struct {
	// contains filtered or unexported fields
}

Builder is a struct that builds a tree.

func NewBuilder added in v0.1.13 

func NewBuilder[T interface {
	AddChild(child T)
	BackwardChild() iter.Seq[T]
	Child() iter.Seq[T]
	Cleanup() []T
	Copy() T
	LinkChildren(children []T)
	TreeNoder
}, I interface {
	Copy() I
}](info I, f NextsFunc[T, I]) (*Builder[T, I], error)

NewBuilder creates a new builder that builds a tree from the given function.

Parameters:

  • info: The info of the builder.
  • f: The function that, given an element and info, returns the next elements. (i.e., the children of the element).

Returns:

  • *Builder: The builder created from the function.
  • error: An error if the function is nil.

func (*Builder[T, I]) Build added in v0.1.8 

func (b *Builder[T, I]) Build(root T) (*Tree[T], error)

MakeTree creates a tree from the given element.

Parameters:

  • elem: The element to start the tree from.
  • info: The info of the element.
  • f: The function that, given an element and info, returns the next elements. (i.e., the children of the element).

Returns:

  • *Tree: The tree created from the element.
  • error: An error if the next function fails.

Behaviors:

  • The 'info' parameter is copied for each node and it specifies the initial info before traversing the tree.

func (*Builder[T, I]) Reset added in v0.1.8 

func (b *Builder[T, I]) Reset()

Reset resets the builder.

type NextsFunc added in v0.1.8 

type NextsFunc[T interface {
	AddChild(child T)
	BackwardChild() iter.Seq[T]
	Child() iter.Seq[T]
	Copy() T
	LinkChildren(children []T)
	TreeNoder
}, I interface {
	Copy() I
}] func(elem T, info I) ([]T, error)

NextsFunc is a function that returns the next elements.

Parameters:

  • elem: The element to get the next elements from.
  • info: The info of the element.

Returns:

  • []T: The next elements.
  • error: An error if the function fails.

type Pair added in v0.1.13 

type Pair[T interface {
	Child() iter.Seq[T]
	BackwardChild() iter.Seq[T]
	Copy() T
	LinkChildren(children []T)
	TreeNoder
}] struct {
	// Node is the node of the pair.
	Node T

	// Info is the info of the pair.
	Info any
}

Pair is a pair of a node and its info.

func NewPair added in v0.1.13 

func NewPair[T interface {
	Child() iter.Seq[T]
	BackwardChild() iter.Seq[T]
	Copy() T
	LinkChildren(children []T)
	TreeNoder
}](node T, info any) Pair[T]

NewPair creates a new pair of a node and its info.

Parameters:

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

Returns:

  • Pair[T]: The new pair.

type Traverser added in v0.1.13 

type Traverser[T interface {
	Child() iter.Seq[T]
	BackwardChild() iter.Seq[T]
	Copy() T
	LinkChildren(children []T)
	TreeNoder
}] struct {
	// InitFn is the function that initializes the traversal info.
	//
	// Parameters:
	//   - root: The root node of the tree.
	//
	// Returns:
	//   - any: The initial traversal info.
	InitFn func(root T) any

	// DoFn is the function that performs the traversal logic.
	//
	// Parameters:
	//   - node: The current node of the tree.
	//   - info: The traversal info.
	//
	// Returns:
	//   - []Pair[T]: The next traversal info.
	//   - error: The error that might occur during the traversal.
	DoFn func(node T, info any) ([]Pair[T], error)
}

Traverser is the traverser that holds the traversal logic.

type Tree 

type Tree[T interface {
	BackwardChild() iter.Seq[T]
	Child() iter.Seq[T]
	Cleanup() []T
	Copy() T
	LinkChildren(children []T)
	TreeNoder
}] struct {
	// contains filtered or unexported fields
}

Tree is a generic data structure that represents a tree.

func Build added in v0.1.13 

func Build[T interface {
	AddChild(child T)
	BackwardChild() iter.Seq[T]
	Child() iter.Seq[T]
	Cleanup() []T
	Copy() T
	LinkChildren(children []T)
	TreeNoder
}](root T, fn func(elem T) ([]T, error)) (*Tree[T], error)

MakeTree creates a tree from the given element.

Parameters:

  • elem: The element to start the tree from.
  • info: The info of the element.
  • f: The function that, given an element and info, returns the next elements. (i.e., the children of the element).

Returns:

  • *Tree: The tree created from the element.
  • error: An error if the next function fails.

Behaviors:

  • The 'info' parameter is copied for each node and it specifies the initial info before traversing the tree.

func InsertBranch 

func InsertBranch[T interface {
	AddChild(child T)
	BackwardChild() iter.Seq[T]
	Child() iter.Seq[T]
	Cleanup() []T
	Copy() T
	GetFirstChild() (T, bool)
	GetParent() (T, bool)
	LinkChildren(children []T)
	TreeNoder
}](tree *Tree[T], branch *Branch[T]) (*Tree[T], error)

InsertBranch inserts the given branch into the tree.

Parameters:

  • tree: The tree to insert the branch into.
  • branch: The branch to insert.

Returns:

  • T: The updated tree.
  • error: An error if the insertion fails.

func NewTree 

func NewTree[T interface {
	BackwardChild() iter.Seq[T]
	Child() iter.Seq[T]
	Cleanup() []T
	Copy() T
	LinkChildren(children []T)
	TreeNoder
}](root T) *Tree[T]

NewTree creates a new tree from the given root.

Parameters:

  • root: The root of the tree.

Returns:

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

func SkipFilter 

func SkipFilter[T interface {
	BackwardChild() iter.Seq[T]
	Child() iter.Seq[T]
	Cleanup() []T
	Copy() T
	GetParent() (T, bool)
	LinkChildren(children []T)
	RemoveNode() []T
	TreeNoder
}](tree *Tree[T], filter func(node T) bool) (forest []*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:

  • tree: The tree to prune.
  • filter: The filter to apply.

Returns:

  • forest: 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]) BFS added in v0.1.13 

func (t *Tree[T]) BFS() iter.Seq[T]

BFS applies the BFS traversal logic to the tree.

Returns:

  • iter.Seq[T]: The traversal sequence.

func (*Tree[T]) Cleanup 

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

Cleanup is a method that cleans up the tree.

func (*Tree[T]) DFS added in v0.1.13 

func (t *Tree[T]) DFS() iter.Seq[T]

DFS applies the DFS traversal logic to the tree.

Returns:

  • iter.Seq[T]: The traversal sequence.

func (*Tree[T]) DeepCopy added in v0.1.13 

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

DeepCopy is a method that deeply copies the tree.

Returns:

  • *Tree: A copy of the tree. Never returns nil.

func (*Tree[T]) FilterChildren added in v0.1.13 

func (tree *Tree[T]) FilterChildren(filter func(node T) bool) []T

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

Parameters:

  • filter: The filter to apply. Must return true iff the node is the one we want to keep. This function must assume node is never nil.

Returns:

  • []T: A slice of the children that satisfy the filter.

If either tree or filter is nil, an empty slice and false are returned.

func (*Tree[T]) GetDirectChildren 

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

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

Children are never nil.

Returns:

  • []T: A slice of the direct children of the root. Nil if the tree does not have a root.

func (*Tree[T]) HasChild added in v0.1.13 

func (tree *Tree[T]) HasChild(filter func(node T) bool) 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. Must return true iff the node is the one we are looking for. This function must assume node is never nil.

Returns:

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

If either tree or filter is nil, false is returned.

func (*Tree[T]) Leaves 

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

Leaves returns the leaves of the tree.

Returns:

  • []T: The leaves of the tree.

func (*Tree[T]) ProcessLeaves added in v0.1.13 

func (tree *Tree[T]) ProcessLeaves(f func(node T) ([]T, error)) 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]) RegenerateLeaves added in v0.1.13 

func (tree *Tree[T]) RegenerateLeaves()

RegenerateLeaves regenerates the leaves of the tree. No op if the tree is nil.

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() T

Root returns the root of the tree.

Returns:

  • T: The root of the tree.

func (*Tree[T]) SearchNodes added in v0.1.13 

func (tree *Tree[T]) SearchNodes(filter func(node T) bool) (T, bool)

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

Parameters:

  • tree: The tree to search.
  • filter: The filter to apply. Must return true iff the node is the one we are looking for. This function must assume node is never nil.

Returns:

  • T: The node that satisfies the filter.
  • bool: True if the node was found, false otherwise.

Nodes that are not of type T will be ignored. If either tree or filter is nil, false is returned.

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]) SnakeTraversal added in v0.1.13 

func (tree *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 elements. Nil if the tree is empty.

Behaviors:

  • The paths are returned in the order of a BFS traversal.

func (Tree[T]) String added in v0.1.9 

func (t Tree[T]) String() string

String implements the fmt.Stringer interface.

Format: 

root
├── node1
│   ├── node2
│   └── node3
└── node4
|   └── node5
|
| // ...
// ...

func (*Tree[T]) UpdateLeaves added in v0.1.13 

func (tree *Tree[T]) UpdateLeaves()

UpdateLeaves updates the leaves of the tree. No op if the tree is nil.

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

type TreeNoder interface {
	comparable

	// String returns the string representation of the node.
	//
	// Returns:
	//   - string: the string representation of the node.
	String() string

	// IsLeaf checks if the node is a leaf.
	//
	// Returns:
	//   - bool: True if the node is a leaf, false otherwise.
	IsLeaf() bool

	// IsSingleton checks whether the node is a singleton.
	//
	// Returns:
	//   - bool: True if the node is a singleton, false otherwise.
	IsSingleton() bool
}

TreeNoder is an interface for nodes in the 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.