Tree

package
v0.3.34 Latest Latest
Warning

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

 Go to latest Published: Jun 25, 2024 License: MIT Imports: 8 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

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.

func NewTreeWithHistory added in v0.3.33 

func NewTreeWithHistory[T any](data T) *ud.History[*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.

Types

type Branch added in v0.3.34 

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

Branch is a generic data structure that represents a branch in a tree.

func (*Branch[T]) Copy added in v0.3.34 

func (b *Branch[T]) Copy() uc.Copier

Copy implements the uc.Copier interface.

func (*Branch[T]) Iterator added in v0.3.34 

func (b *Branch[T]) Iterator() uc.Iterater[T]

Iterator implements the uc.Iterable interface.

func (*Branch[T]) Size added in v0.3.34 

func (b *Branch[T]) Size() int

Size returns the number of nodes in the branch.

func (*Branch[T]) Slice added in v0.3.34 

func (b *Branch[T]) Slice() []T

Slice implements the uc.Slicer interface.

type BranchIterator added in v0.3.34 

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

BranchIterator is a generic data structure that represents an iterator for a branch in a tree.

func (*BranchIterator[T]) Consume added in v0.3.34 

func (bi *BranchIterator[T]) Consume() (T, error)

Consume implements the uc.Iterater interface.

This scans from the root node to the leaf node.

func (*BranchIterator[T]) Restart added in v0.3.34 

func (bi *BranchIterator[T]) Restart()

Restart implements the uc.Iterater interface.

func (*BranchIterator[T]) Size added in v0.3.34 

func (bi *BranchIterator[T]) Size() (count int)

Size implements the uc.Iterater interface.

type CleanupCmd added in v0.3.33 

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

CleanupCmd is a command that cleans up the tree.

func NewCleanupCmd added in v0.3.33 

func NewCleanupCmd[T any]() *CleanupCmd[T]

NewCleanupCmd creates a new CleanupCmd.

Returns:

  • *CleanupCmd: A pointer to the new CleanupCmd.

func (*CleanupCmd[T]) Copy added in v0.3.33 

func (c *CleanupCmd[T]) Copy() uc.Copier

Copy implements the Debugging.Commander interface.

func (*CleanupCmd[T]) Execute added in v0.3.33 

func (c *CleanupCmd[T]) Execute(data *Tree[T]) error

Execute implements the Debugging.Commander interface.

Never errors.

func (*CleanupCmd[T]) Undo added in v0.3.33 

func (c *CleanupCmd[T]) Undo(data *Tree[T]) error

Undo implements the Debugging.Commander interface.

Never errors.

type DeleteBranchContainingCmd added in v0.3.33 

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

DeleteBranchContainingCmd is a command that deletes the branch containing the given node.

func NewDeleteBranchContainingCmd added in v0.3.33 

func NewDeleteBranchContainingCmd[T any](tn *TreeNode[T]) *DeleteBranchContainingCmd[T]

NewDeleteBranchContainingCmd creates a new DeleteBranchContainingCmd.

Parameters:

  • tn: The node to delete.

Returns:

  • *DeleteBranchContainingCmd: A pointer to the new DeleteBranchContainingCmd.

func (*DeleteBranchContainingCmd[T]) Copy added in v0.3.33 

func (c *DeleteBranchContainingCmd[T]) Copy() uc.Copier

Copy implements the Debugging.Commander interface.

func (*DeleteBranchContainingCmd[T]) Execute added in v0.3.33 

func (c *DeleteBranchContainingCmd[T]) Execute(data *Tree[T]) error

Execute implements the Debugging.Commander interface.

func (*DeleteBranchContainingCmd[T]) Undo added in v0.3.33 

func (c *DeleteBranchContainingCmd[T]) Undo(data *Tree[T]) error

Undo implements the Debugging.Commander interface.

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 implements the error interface.

Message: "missing root".

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 implements the error interface.

Message: "node is not part of the tree".

type ExtractBranchCmd added in v0.3.34 

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

ExtractBranchCmd is a command that extracts the branch containing the given node.

func NewExtractBranchCmd added in v0.3.34 

func NewExtractBranchCmd[T any](leaf *TreeNode[T]) *ExtractBranchCmd[T]

NewExtractBranchCmd creates a new ExtractBranchCmd.

Parameters:

  • leaf: The leaf to extract the branch from.

Returns:

  • *ExtractBranchCmd: A pointer to the new ExtractBranchCmd.

func (*ExtractBranchCmd[T]) Copy added in v0.3.34 

func (c *ExtractBranchCmd[T]) Copy() uc.Copier

Copy implements the Debugging.Commander interface.

func (*ExtractBranchCmd[T]) Execute added in v0.3.34 

func (c *ExtractBranchCmd[T]) Execute(data *Tree[T]) error

Execute implements the Debugging.Commander interface.

func (*ExtractBranchCmd[T]) Undo added in v0.3.34 

func (c *ExtractBranchCmd[T]) Undo(data *Tree[T]) error

Undo implements the Debugging.Commander interface.

type InsertBranchCmd added in v0.3.34 

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

InsertBranchCmd is a command that inserts a branch into the tree.

func NewInsertBranchCmd added in v0.3.34 

func NewInsertBranchCmd[T any](branch *Branch[T]) *InsertBranchCmd[T]

NewInsertBranchCmd creates a new InsertBranchCmd.

Parameters:

  • branch: The branch to insert.

Returns:

  • *InsertBranchCmd: A pointer to the new InsertBranchCmd.

func (*InsertBranchCmd[T]) Copy added in v0.3.34 

func (c *InsertBranchCmd[T]) Copy() uc.Copier

Copy implements the Debugging.Commander interface.

func (*InsertBranchCmd[T]) Execute added in v0.3.34 

func (c *InsertBranchCmd[T]) Execute(data *Tree[T]) error

Execute implements the Debugging.Commander interface.

func (*InsertBranchCmd[T]) Undo added in v0.3.34 

func (c *InsertBranchCmd[T]) Undo(data *Tree[T]) error

Undo implements the Debugging.Commander interface.

type ProcessLeavesCmd added in v0.3.33 

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

ProcessLeavesCmd is a command that processes the leaves of the tree.

func NewProcessLeavesCmd added in v0.3.33 

func NewProcessLeavesCmd[T any](f uc.EvalManyFunc[T, T]) *ProcessLeavesCmd[T]

NewProcessLeavesCmd creates a new ProcessLeavesCmd.

Parameters:

  • f: The function to apply to the leaves.

Returns:

  • *ProcessLeavesCmd: A pointer to the new ProcessLeavesCmd.

func (*ProcessLeavesCmd[T]) Copy added in v0.3.33 

func (c *ProcessLeavesCmd[T]) Copy() uc.Copier

Copy implements the Debugging.Commander interface.

func (*ProcessLeavesCmd[T]) Execute added in v0.3.33 

func (c *ProcessLeavesCmd[T]) Execute(data *Tree[T]) error

Execute implements the Debugging.Commander interface.

func (*ProcessLeavesCmd[T]) Undo added in v0.3.33 

func (c *ProcessLeavesCmd[T]) Undo(data *Tree[T]) error

Undo implements the Debugging.Commander interface.

type PruneBranchesCmd added in v0.3.33 

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

PruneBranchesCmd is a command that prunes the branches of the tree.

func NewPruneBranchesCmd added in v0.3.33 

func NewPruneBranchesCmd[T any](filter us.PredicateFilter[T]) *PruneBranchesCmd[T]

NewPruneBranchesCmd creates a new PruneBranchesCmd.

Parameters:

  • filter: The filter to apply to prune the branches.

Returns:

  • *PruneBranchesCmd: A pointer to the new PruneBranchesCmd.

func (*PruneBranchesCmd[T]) Copy added in v0.3.33 

func (c *PruneBranchesCmd[T]) Copy() uc.Copier

Copy implements the Debugging.Commander interface.

func (*PruneBranchesCmd[T]) Execute added in v0.3.33 

func (c *PruneBranchesCmd[T]) Execute(data *Tree[T]) error

Execute implements the Debugging.Commander interface.

Never errors.

func (*PruneBranchesCmd[T]) GetOk added in v0.3.33 

func (c *PruneBranchesCmd[T]) GetOk() bool

GetOk returns the value of the ok field.

Call this function after executing the command.

Returns:

  • bool: The value of the ok field.

func (*PruneBranchesCmd[T]) Undo added in v0.3.33 

func (c *PruneBranchesCmd[T]) Undo(data *Tree[T]) error

Undo implements the Debugging.Commander interface.

Never errors.

type PruneTreeCmd added in v0.3.33 

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

PruneTreeCmd is a command that prunes the tree using the given filter.

func NewPruneTreeCmd added in v0.3.33 

func NewPruneTreeCmd[T any](filter us.PredicateFilter[T]) *PruneTreeCmd[T]

NewPruneTreeCmd creates a new PruneTreeCmd.

Parameters:

  • filter: The filter to use to prune the tree.

Returns:

  • *PruneTreeCmd: A pointer to the new PruneTreeCmd.

func (*PruneTreeCmd[T]) Copy added in v0.3.33 

func (c *PruneTreeCmd[T]) Copy() uc.Copier

Copy implements the Debugging.Commander interface.

func (*PruneTreeCmd[T]) Execute added in v0.3.33 

func (c *PruneTreeCmd[T]) Execute(data *Tree[T]) error

Execute implements the Debugging.Commander interface.

func (*PruneTreeCmd[T]) GetOk added in v0.3.33 

func (c *PruneTreeCmd[T]) GetOk() bool

GetOk returns the value of the ok field.

Call this function after executing the command.

Returns:

  • bool: The value of the ok field.

func (*PruneTreeCmd[T]) Undo added in v0.3.33 

func (c *PruneTreeCmd[T]) Undo(data *Tree[T]) error

Undo implements the Debugging.Commander interface.

type RegenerateLeavesCmd added in v0.3.33 

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

RegenerateLeavesCmd is a command that regenerates the leaves of the tree.

func NewRegenerateLeavesCmd added in v0.3.33 

func NewRegenerateLeavesCmd[T any]() *RegenerateLeavesCmd[T]

NewRegenerateLeavesCmd creates a new RegenerateLeavesCmd.

Returns:

  • *RegenerateLeavesCmd: A pointer to the new RegenerateLeavesCmd.

func (*RegenerateLeavesCmd[T]) Copy added in v0.3.33 

func (c *RegenerateLeavesCmd[T]) Copy() uc.Copier

Copy implements the Debugging.Commander interface.

func (*RegenerateLeavesCmd[T]) Execute added in v0.3.33 

func (c *RegenerateLeavesCmd[T]) Execute(data *Tree[T]) error

Execute implements the Debugging.Commander interface.

func (*RegenerateLeavesCmd[T]) Undo added in v0.3.33 

func (c *RegenerateLeavesCmd[T]) Undo(data *Tree[T]) error

Undo implements the Debugging.Commander interface.

type SetChildrenCmd added in v0.3.33 

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

SetChildrenCmd is a command that sets the children of a node.

func NewSetChildrenCmd added in v0.3.33 

func NewSetChildrenCmd[T any](children []*Tree[T]) *SetChildrenCmd[T]

NewSetChildrenCmd creates a new SetChildrenCmd.

Parameters:

  • children: The children to set.

Returns:

  • *SetChildrenCmd: A pointer to the new SetChildrenCmd.

func (*SetChildrenCmd[T]) Copy added in v0.3.33 

func (c *SetChildrenCmd[T]) Copy() uc.Copier

Copy implements the Debugging.Commander interface.

func (*SetChildrenCmd[T]) Execute added in v0.3.33 

func (c *SetChildrenCmd[T]) Execute(data *Tree[T]) error

Execute implements the Debugging.Commander interface.

func (*SetChildrenCmd[T]) Undo added in v0.3.33 

func (c *SetChildrenCmd[T]) Undo(data *Tree[T]) error

Undo implements the Debugging.Commander interface.

type SkipFuncCmd added in v0.3.33 

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

SkipFuncCmd is a command that skips the nodes of the tree that satisfy the given filter.

func NewSkipFuncCmd added in v0.3.33 

func NewSkipFuncCmd[T any](filter us.PredicateFilter[T]) *SkipFuncCmd[T]

NewSkipFuncCmd creates a new SkipFuncCmd.

Parameters:

  • filter: The filter to apply to skip the nodes.

Returns:

  • *SkipFuncCmd: A pointer to the new SkipFuncCmd.

func (*SkipFuncCmd[T]) Copy added in v0.3.33 

func (c *SkipFuncCmd[T]) Copy() uc.Copier

Copy implements the Debugging.Commander interface.

func (*SkipFuncCmd[T]) Execute added in v0.3.33 

func (c *SkipFuncCmd[T]) Execute(data *Tree[T]) error

Execute implements the Debugging.Commander interface.

Never errors.

func (*SkipFuncCmd[T]) GetTrees added in v0.3.33 

func (c *SkipFuncCmd[T]) GetTrees() []*Tree[T]

GetTrees returns the value of the trees field.

Call this function after executing the command.

Returns:

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

func (*SkipFuncCmd[T]) Undo added in v0.3.33 

func (c *SkipFuncCmd[T]) Undo(data *Tree[T]) error

Undo implements the Debugging.Commander interface.

Never errors.

type StatusInfo added in v0.3.34 

type StatusInfo[S uc.Enumer, T any] struct {
	// contains filtered or unexported fields
}

StatusInfo is a generic data structure that represents a status node in a tree.

func NewStatusInfo added in v0.3.34 

func NewStatusInfo[S uc.Enumer, T any](data T, status S) *StatusInfo[S, T]

NewStatusInfo creates a new status node.

Parameters:

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

Returns:

  • *StatusInfo[S, T]: The new status node.

func (*StatusInfo[S, T]) ChangeStatus added in v0.3.34 

func (si *StatusInfo[S, T]) ChangeStatus(status S)

ChangeStatus sets the status of the tree node.

Parameters:

  • status: The status to set.

func (*StatusInfo[S, T]) GetData added in v0.3.34 

func (si *StatusInfo[S, T]) GetData() T

GetData returns the data of the tree node.

Returns:

  • T: The data of the tree node.

func (*StatusInfo[S, T]) GetStatus added in v0.3.34 

func (si *StatusInfo[S, T]) GetStatus() S

GetStatus returns the status of the tree node.

Returns:

  • S: The status of the tree node.

func (*StatusInfo[S, T]) SetData added in v0.3.34 

func (si *StatusInfo[S, T]) SetData(data T)

SetData sets the data of the tree node.

Parameters:

  • data: The data to set.

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 value as the 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]) Copy added in v0.3.33 

func (t *Tree[T]) Copy() uc.Copier

Copy creates a deep copy of the tree.

Returns:

  • uc.Copier: A deep copy of the tree.

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]) ExtractBranch added in v0.3.34 

func (t *Tree[T]) ExtractBranch(leaf *TreeNode[T], delete bool) *Branch[T]

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

Parameters:

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

func (*Tree[T]) FString 

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

FString implements the FString.FStringer interface for the Tree type.

func (*Tree[T]) FilterChildren 

func (t *Tree[T]) FilterChildren(filter us.PredicateFilter[T]) (sols []*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:

  • sols: A slice of pointers to the nodes that satisfy the filter.

func (*Tree[T]) GetChildren 

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

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

Returns:

  • children: A slice of the values of the children of 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]) InsertBranch added in v0.3.34 

func (t *Tree[T]) InsertBranch(branch *Branch[T]) bool

InsertBranch inserts the given branch into the tree.

Parameters:

  • branch: The branch to insert.

Returns:

  • bool: True if the branch was inserted, 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]) Prune added in v0.3.27 

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

PruneTree prunes the tree using the given filter.

Parameters:

  • filter: The filter to use to prune the tree.

Returns:

  • bool: True if no nodes were pruned, false otherwise.

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]) (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:

  • 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:

  • *TreeNode[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 implements the uc.Copier interface.

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

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

FString implements the ffs.FStringer interface.

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() (ancestors []*TreeNode[T])

GetAncestors returns all the ancestors of the node.

This excludes the node itself.

Returns:

  • ancestors: 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]) GetBranch added in v0.3.33 

func (n *TreeNode[T]) GetBranch() *Branch[T]

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

Returns:

  • []*TreeNode[T]: A slice of pointers to the nodes in the branch.

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:

  • []*TreeNode[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() (leaves []*TreeNode[T])

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

Returns:

  • leaves: 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:

  • *TreeNode[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() (size int)

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

Returns:

  • size: The number of nodes in the tree.

Behaviors:

  • This function is expensive since size is not stored.

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.

type UpdateLeavesCmd added in v0.3.33 

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

UpdateLeavesCmd is a command that updates the leaves of the tree.

func NewUpdateLeavesCmd added in v0.3.33 

func NewUpdateLeavesCmd[T any]() *UpdateLeavesCmd[T]

NewUpdateLeavesCmd creates a new UpdateLeavesCmd.

Returns:

  • *UpdateLeavesCmd: A pointer to the new UpdateLeavesCmd.

func (*UpdateLeavesCmd[T]) Copy added in v0.3.33 

func (c *UpdateLeavesCmd[T]) Copy() uc.Copier

Copy implements the Debugging.Commander interface.

func (*UpdateLeavesCmd[T]) Execute added in v0.3.33 

func (c *UpdateLeavesCmd[T]) Execute(data *Tree[T]) error

Execute implements the Debugging.Commander interface.

func (*UpdateLeavesCmd[T]) Undo added in v0.3.33 

func (c *UpdateLeavesCmd[T]) Undo(data *Tree[T]) error

Undo implements the Debugging.Commander interface.

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.