Tree

package
v0.3.38 Latest Latest
Warning

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

 Go to latest Published: Jul 13, 2024 License: MIT Imports: 11 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

View Source 
var (
	// FilterNonNilTree 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.
	FilterNonNilTree us.PredicateFilter[*Tree]
)

Functions

func BFS added in v0.3.37 

func BFS(tree *Tree, init Infoer, f ObserverFunc) error

BFS traverses the tree in breadth-first order.

Parameters:

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

Returns:

  • error: An error if the traversal fails.

func DFS added in v0.3.37 

func DFS(tree *Tree, init Infoer, f ObserverFunc) error

DFS traverses the tree in depth-first order.

Parameters:

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

Returns:

  • error: An error if the traversal fails.

func ExtractData 

func ExtractData[T any](nodes []Noder) []T

ExtractData returns the values of the nodes in the slice. This only works if the nodes are of type *TreeNode[T].

Parameters:

  • nodes: The nodes to extract the values from.

Returns:

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

func FindBranchingPoint added in v0.3.37 

func FindBranchingPoint(n Noder) (Noder, Noder, bool)

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

Returns:

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

func NewTreeWithHistory added in v0.3.33 

func NewTreeWithHistory(root Noder) *ud.History[*Tree]

NewTree creates a new tree with the given root.

Parameters:

  • root: The root of the tree.

Returns:

  • *Debugging.History[*Tree]: A pointer to the history of the tree.

func PrintTree added in v0.3.37 

func PrintTree(tree *Tree) ([]string, error)

PrintTree prints the tree.

Parameters:

  • tree: The tree to print.

Returns:

  • []string: The lines of the tree.
  • error: An error if the tree cannot be printed.

Types

type Branch added in v0.3.34 

type Branch struct {
	// contains filtered or unexported fields
}

Branch represents a branch in a tree.

func NewBranch added in v0.3.37 

func NewBranch(n Noder) *Branch

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.

Returns:

  • *Branch: The branch from the node to the root.

func (*Branch) Copy added in v0.3.34 

func (b *Branch) Copy() uc.Copier

Copy implements the uc.Copier interface.

func (*Branch) Iterator added in v0.3.34 

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

Iterator implements the uc.Iterable interface.

func (*Branch) Slice added in v0.3.34 

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

Slice implements the uc.Slicer interface.

type BranchIterator added in v0.3.34 

type BranchIterator struct {
	// contains filtered or unexported fields
}

BranchIterator is the pull-based iterator for the branch.

func (*BranchIterator) Consume added in v0.3.34 

func (bi *BranchIterator) Consume() (Noder, error)

Consume implements the common.Iterater interface.

This scans from the root node to the leaf node.

Noder is never nil.

func (*BranchIterator) Restart added in v0.3.34 

func (bi *BranchIterator) Restart()

Restart implements the common.Iterater interface.

type Builder added in v0.3.37 

type Builder struct {
	// contains filtered or unexported fields
}

Builder is a struct that builds a tree.

func (*Builder) Build added in v0.3.37 

func (b *Builder) Build(elem Noder) (*Tree, 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) Reset added in v0.3.37 

func (b *Builder) Reset()

Reset resets the builder.

func (*Builder) SetInfo added in v0.3.37 

func (b *Builder) SetInfo(info Infoer)

SetInfo sets the info of the builder.

Parameters:

  • info: The info to set.

func (*Builder) SetNextFunc added in v0.3.37 

func (b *Builder) SetNextFunc(f NextsFunc)

SetNextFunc sets the next function of the builder.

Parameters:

  • f: The function to set.

type CleanupCmd added in v0.3.33 

type CleanupCmd struct {
	// contains filtered or unexported fields
}

CleanupCmd is a command that cleans up the tree.

func NewCleanupCmd added in v0.3.33 

func NewCleanupCmd() *CleanupCmd

NewCleanupCmd creates a new CleanupCmd.

Returns:

  • *CleanupCmd: A pointer to the new CleanupCmd.

func (*CleanupCmd) Copy added in v0.3.33 

func (cmd *CleanupCmd) Copy() uc.Copier

Copy implements the Debugging.Commander interface.

func (*CleanupCmd) Execute added in v0.3.33 

func (cmd *CleanupCmd) Execute(data *Tree) error

Execute implements the Debugging.Commander interface.

Never errors.

func (*CleanupCmd) Undo added in v0.3.33 

func (cmd *CleanupCmd) Undo(data *Tree) error

Undo implements the Debugging.Commander interface.

Never errors.

type DeleteBranchContainingCmd added in v0.3.33 

type DeleteBranchContainingCmd 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(tn Noder) *DeleteBranchContainingCmd

NewDeleteBranchContainingCmd creates a new DeleteBranchContainingCmd.

Parameters:

  • tn: The node to delete.

Returns:

  • *DeleteBranchContainingCmd: A pointer to the new DeleteBranchContainingCmd.

func (*DeleteBranchContainingCmd) Copy added in v0.3.33 

func (cmd *DeleteBranchContainingCmd) Copy() uc.Copier

Copy implements the Debugging.Commander interface.

func (*DeleteBranchContainingCmd) Execute added in v0.3.33 

func (cmd *DeleteBranchContainingCmd) Execute(data *Tree) error

Execute implements the Debugging.Commander interface.

func (*DeleteBranchContainingCmd) Undo added in v0.3.33 

func (cmd *DeleteBranchContainingCmd) Undo(data *Tree) 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 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(leaf Noder) *ExtractBranchCmd

NewExtractBranchCmd creates a new ExtractBranchCmd.

Parameters:

  • leaf: The leaf to extract the branch from.

Returns:

  • *ExtractBranchCmd: A pointer to the new ExtractBranchCmd.

func (*ExtractBranchCmd) Copy added in v0.3.34 

func (cmd *ExtractBranchCmd) Copy() uc.Copier

Copy implements the Debugging.Commander interface.

func (*ExtractBranchCmd) Execute added in v0.3.34 

func (cmd *ExtractBranchCmd) Execute(data *Tree) error

Execute implements the Debugging.Commander interface.

func (*ExtractBranchCmd) GetBranch added in v0.3.35 

func (cmd *ExtractBranchCmd) GetBranch() *Branch

GetBranch returns the value of the branch field.

Call this function after executing the command.

Returns:

  • *Branch[T]: A pointer to the branch extracted.

func (*ExtractBranchCmd) Undo added in v0.3.34 

func (cmd *ExtractBranchCmd) Undo(data *Tree) error

Undo implements the Debugging.Commander interface.

type InfPrinter added in v0.3.37 

type InfPrinter struct {
	// contains filtered or unexported fields
}

InfPrinter is a struct that prints the tree.

func NewInfPrinter added in v0.3.37 

func NewInfPrinter() *InfPrinter

NewInfPrinter creates a new InfPrinter.

Returns:

  • *InfPrinter: The new InfPrinter.

func (*InfPrinter) Copy added in v0.3.37 

func (ip *InfPrinter) Copy() uc.Copier

Copy implements the common.Copier interface.

func (*InfPrinter) IncIndent added in v0.3.37 

func (ip *InfPrinter) IncIndent()

IncIndent increments the indentation level.

type Infoer added in v0.3.37 

type Infoer interface {
	uc.Copier
}

Infoer is an interface that provides the info of the element.

type InsertBranchCmd added in v0.3.34 

type InsertBranchCmd 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(branch *Branch) *InsertBranchCmd

NewInsertBranchCmd creates a new InsertBranchCmd.

Parameters:

  • branch: The branch to insert.

Returns:

  • *InsertBranchCmd: A pointer to the new InsertBranchCmd.

func (*InsertBranchCmd) Copy added in v0.3.34 

func (cmd *InsertBranchCmd) Copy() uc.Copier

Copy implements the Debugging.Commander interface.

func (*InsertBranchCmd) Execute added in v0.3.34 

func (cmd *InsertBranchCmd) Execute(data *Tree) error

Execute implements the Debugging.Commander interface.

func (*InsertBranchCmd) Undo added in v0.3.34 

func (cmd *InsertBranchCmd) Undo(data *Tree) error

Undo implements the Debugging.Commander interface.

type NextsFunc added in v0.3.37 

type NextsFunc func(elem Noder, info Infoer) ([]Noder, 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:

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

type Noder added in v0.3.37 

type Noder interface {
	// SetParent sets the parent of the node.
	//
	// Parameters:
	//   - parent: The parent node.
	//
	// Returns:
	//   - bool: True if the parent is set, false otherwise.
	SetParent(parent Noder) bool

	// GetParent returns the parent of the node.
	//
	// Returns:
	//   - Noder: The parent node.
	GetParent() Noder

	// LinkWithParent links the parent with the children. It also links the children
	// with each other.
	//
	// Parameters:
	//   - parent: The parent node.
	//   - children: The children nodes.
	//
	// Behaviors:
	//   - Only valid children are linked while the rest are ignored.
	LinkChildren(children []Noder)

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

	// IsSingleton returns true if the node is a singleton (i.e., has only one child).
	//
	// Returns:
	//   - bool: True if the node is a singleton, false otherwise.
	IsSingleton() bool

	// GetLeaves returns all the leaves of the tree rooted at the node.
	//
	// Should be a DFS traversal.
	//
	// Returns:
	//   - []Noder: A slice of pointers to the leaves of the tree.
	//
	// Behaviors:
	//   - The leaves are returned in the order of a DFS traversal.
	GetLeaves() []Noder

	// GetAncestors returns all the ancestors of the node.
	//
	// This excludes the node itself.
	//
	// Returns:
	//   - []Noder: 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.
	GetAncestors() []Noder

	// GetFirstChild returns the first child of the node.
	//
	// Returns:
	//   - Noder: The first child of the node. Nil if the node has no children.
	GetFirstChild() Noder

	// DeleteChild removes the given child from the children of the node.
	//
	// Parameters:
	//   - target: The child to remove.
	//
	// Returns:
	//   - []Noder: A slice of pointers to the children of the node. Nil if the node has no children.
	DeleteChild(target Noder) []Noder

	// Size returns the number of nodes in the tree rooted at n.
	//
	// Returns:
	//   - size: The number of nodes in the tree.
	Size() int

	// AddChild adds a new child to the node with the given data.
	//
	// Parameters:
	//   - child: The child to add.
	//
	// Behaviors:
	//   - If the child is not valid, it is ignored.
	AddChild(child Noder)

	// removeNode removes the node from the tree and shifts the children up
	// in the space occupied by the node.
	//
	// Returns:
	//   - []Noder: A slice of pointers to the children of the node if
	//     the node is the root. Nil otherwise.
	RemoveNode() []Noder

	uc.Iterable[Noder]
	uc.Copier
	ffs.FStringer
	uto.Cleaner
}

Noder is an interface that represents a node in a tree.

func FindCommonAncestor 

func FindCommonAncestor(n1, n2 Noder) Noder

FindCommonAncestor returns the first common ancestor of the two nodes.

Parameters:

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

Returns:

  • Noder: A pointer to the common ancestor. Nil if no such node is found.

type ObserverFunc added in v0.3.37 

type ObserverFunc func(data Noder, info Infoer) (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 ProcessLeavesCmd added in v0.3.33 

type ProcessLeavesCmd 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(f uc.EvalManyFunc[Noder, Noder]) *ProcessLeavesCmd

NewProcessLeavesCmd creates a new ProcessLeavesCmd.

Parameters:

  • f: The function to apply to the leaves.

Returns:

  • *ProcessLeavesCmd: A pointer to the new ProcessLeavesCmd.

func (*ProcessLeavesCmd) Copy added in v0.3.33 

func (cmd *ProcessLeavesCmd) Copy() uc.Copier

Copy implements the Debugging.Commander interface.

func (*ProcessLeavesCmd) Execute added in v0.3.33 

func (cmd *ProcessLeavesCmd) Execute(data *Tree) error

Execute implements the Debugging.Commander interface.

func (*ProcessLeavesCmd) Undo added in v0.3.33 

func (cmd *ProcessLeavesCmd) Undo(data *Tree) error

Undo implements the Debugging.Commander interface.

type PruneBranchesCmd added in v0.3.33 

type PruneBranchesCmd 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(filter us.PredicateFilter[Noder]) *PruneBranchesCmd

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) Copy added in v0.3.33 

func (cmd *PruneBranchesCmd) Copy() uc.Copier

Copy implements the Debugging.Commander interface.

func (*PruneBranchesCmd) Execute added in v0.3.33 

func (cmd *PruneBranchesCmd) Execute(data *Tree) error

Execute implements the Debugging.Commander interface.

Never errors.

func (*PruneBranchesCmd) GetOk added in v0.3.33 

func (cmd *PruneBranchesCmd) 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) Undo added in v0.3.33 

func (cmd *PruneBranchesCmd) Undo(data *Tree) error

Undo implements the Debugging.Commander interface.

Never errors.

type PruneTreeCmd added in v0.3.33 

type PruneTreeCmd 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(filter us.PredicateFilter[Noder]) *PruneTreeCmd

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) Copy added in v0.3.33 

func (cmd *PruneTreeCmd) Copy() uc.Copier

Copy implements the Debugging.Commander interface.

func (*PruneTreeCmd) Execute added in v0.3.33 

func (cmd *PruneTreeCmd) Execute(data *Tree) error

Execute implements the Debugging.Commander interface.

func (*PruneTreeCmd) GetOk added in v0.3.33 

func (cmd *PruneTreeCmd) 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) Undo added in v0.3.33 

func (cmd *PruneTreeCmd) Undo(data *Tree) error

Undo implements the Debugging.Commander interface.

type RegenerateLeavesCmd added in v0.3.33 

type RegenerateLeavesCmd 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() *RegenerateLeavesCmd

NewRegenerateLeavesCmd creates a new RegenerateLeavesCmd.

Returns:

  • *RegenerateLeavesCmd: A pointer to the new RegenerateLeavesCmd.

func (*RegenerateLeavesCmd) Copy added in v0.3.33 

func (cmd *RegenerateLeavesCmd) Copy() uc.Copier

Copy implements the Debugging.Commander interface.

func (*RegenerateLeavesCmd) Execute added in v0.3.33 

func (cmd *RegenerateLeavesCmd) Execute(data *Tree) error

Execute implements the Debugging.Commander interface.

func (*RegenerateLeavesCmd) Undo added in v0.3.33 

func (cmd *RegenerateLeavesCmd) Undo(data *Tree) error

Undo implements the Debugging.Commander interface.

type SetChildrenCmd added in v0.3.33 

type SetChildrenCmd 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(children []*Tree) *SetChildrenCmd

NewSetChildrenCmd creates a new SetChildrenCmd.

Parameters:

  • children: The children to set.

Returns:

  • *SetChildrenCmd: A pointer to the new SetChildrenCmd.

func (*SetChildrenCmd) Copy added in v0.3.33 

func (cmd *SetChildrenCmd) Copy() uc.Copier

Copy implements the Debugging.Commander interface.

func (*SetChildrenCmd) Execute added in v0.3.33 

func (cmd *SetChildrenCmd) Execute(data *Tree) error

Execute implements the Debugging.Commander interface.

func (*SetChildrenCmd) Undo added in v0.3.33 

func (cmd *SetChildrenCmd) Undo(data *Tree) error

Undo implements the Debugging.Commander interface.

Never errors.

type SkipFuncCmd added in v0.3.33 

type SkipFuncCmd 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(filter us.PredicateFilter[Noder]) *SkipFuncCmd

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) Copy added in v0.3.33 

func (cmd *SkipFuncCmd) Copy() uc.Copier

Copy implements the Debugging.Commander interface.

func (*SkipFuncCmd) Execute added in v0.3.33 

func (cmd *SkipFuncCmd) Execute(data *Tree) error

Execute implements the Debugging.Commander interface.

Never errors.

func (*SkipFuncCmd) GetTrees added in v0.3.33 

func (cmd *SkipFuncCmd) GetTrees() []*Tree

GetTrees returns the value of the trees field.

Call this function after executing the command.

Returns:

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

func (*SkipFuncCmd) Undo added in v0.3.33 

func (cmd *SkipFuncCmd) Undo(data *Tree) error

Undo implements the Debugging.Commander interface.

Never errors.

type StatusNode added in v0.3.38 

type StatusNode[S uc.Enumer, T any] struct {
	// Parent, FirstChild, NextSibling, LastChild, PrevSibling are pointers to
	// the parent, first child, next sibling, last child, and previous sibling
	// of the node respectively.
	Parent, FirstChild, NextSibling, LastChild, PrevSibling *StatusNode[S, T]

	// Data is the value of the node.
	Data T

	// Status is the status of the node.
	Status S
}

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

func NewStatusNode added in v0.3.38 

func NewStatusNode[S uc.Enumer, T any](status S, data T) *StatusNode[S, T]

NewTreeNode creates a new node with the given data.

Parameters:

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

Returns:

  • *StatusNode[S, T]: A pointer to the newly created node.

func (*StatusNode[S, T]) AddChild added in v0.3.38 

func (n *StatusNode[S, T]) AddChild(child Noder)

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

Parameters:

  • child: The child to add.

Behaviors:

  • If the child is nil, it does nothing.

func (*StatusNode[S, T]) AddChildren added in v0.3.38 

func (n *StatusNode[S, T]) AddChildren(children ...*StatusNode[S, 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 (*StatusNode[S, T]) Cleanup added in v0.3.38 

func (tn *StatusNode[S, T]) Cleanup()

Cleanup implements the Noder interface.

Uses DFS traversal, does not use recursion, and does not remove the node itself.

func (*StatusNode[S, T]) Copy added in v0.3.38 

func (n *StatusNode[S, T]) Copy() uc.Copier

Copy implements the Noder interface.

func (*StatusNode[S, T]) DeleteChild added in v0.3.38 

func (n *StatusNode[S, T]) DeleteChild(target Noder) []Noder

DeleteChild implements the Noder interface.

func (*StatusNode[S, T]) FString added in v0.3.38 

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

FString implements the Noder interface.

func (*StatusNode[S, T]) GetAncestors added in v0.3.38 

func (n *StatusNode[S, T]) GetAncestors() []Noder

GetAncestors implements the Noder interface.

func (*StatusNode[S, T]) GetChildren added in v0.3.38 

func (n *StatusNode[S, T]) GetChildren() []Noder

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

Returns:

  • []Noder: A slice of pointers to the children of the node.

func (*StatusNode[S, T]) GetData added in v0.3.38 

func (n *StatusNode[S, T]) GetData() T

GetData is a getter for the data of the node.

Returns:

  • T: The data of the node.

func (*StatusNode[S, T]) GetFirstChild added in v0.3.38 

func (n *StatusNode[S, T]) GetFirstChild() Noder

GetFirstChild implements the Noder interface.

func (*StatusNode[S, T]) GetFirstSibling added in v0.3.38 

func (n *StatusNode[S, T]) GetFirstSibling() *StatusNode[S, T]

GetFirstSibling returns the first sibling of the node. If it has a parent, it returns the first child of the parent. Otherwise, it returns the first sibling of the node.

Returns:

  • *StatusNode[S, T]: A pointer to the first sibling. The node itself if it has no previous sibling.

func (*StatusNode[S, T]) GetLastSibling added in v0.3.38 

func (n *StatusNode[S, T]) GetLastSibling() *StatusNode[S, T]

GetLastSibling returns the last sibling of the node. If it has a parent, it returns the last child of the parent. Otherwise, it returns the last sibling of the node.

Returns:

  • *StatusNode[S, T]: A pointer to the last sibling. The node itself if it has no next sibling.

func (*StatusNode[S, T]) GetLeaves added in v0.3.38 

func (n *StatusNode[S, T]) GetLeaves() []Noder

GetLeaves implements the Noder interface.

func (*StatusNode[S, T]) GetParent added in v0.3.38 

func (n *StatusNode[S, T]) GetParent() Noder

GetParent implements the Noder interface.

func (*StatusNode[S, T]) HasChild added in v0.3.38 

func (n *StatusNode[S, T]) HasChild(target *StatusNode[S, 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 (*StatusNode[S, T]) IsChildOf added in v0.3.38 

func (n *StatusNode[S, T]) IsChildOf(target *StatusNode[S, 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 (*StatusNode[S, T]) IsLeaf added in v0.3.38 

func (n *StatusNode[S, T]) IsLeaf() bool

IsLeaf implements the Noder interface.

func (*StatusNode[S, T]) IsRoot added in v0.3.38 

func (n *StatusNode[S, 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 (*StatusNode[S, T]) IsSingleton added in v0.3.38 

func (n *StatusNode[S, T]) IsSingleton() bool

IsSingleton implements the Noder interface.

func (*StatusNode[S, T]) Iterator added in v0.3.38 

func (t *StatusNode[S, T]) Iterator() uc.Iterater[Noder]

Iterator implements Noder.

func (*StatusNode[S, T]) LinkChildren added in v0.3.38 

func (tn *StatusNode[S, T]) LinkChildren(children []Noder)

LinkWithParent implements the Noder interface.

Children that are not *StatusNode[S, T] are ignored.

func (*StatusNode[S, T]) RemoveNode added in v0.3.38 

func (n *StatusNode[S, T]) RemoveNode() []Noder

RemoveNode removes the node from the tree and shifts the children up in the space occupied by the node.

Returns:

  • []Noder: A slice of pointers to the children of the node if the node is the root. Nil otherwise.

func (*StatusNode[S, T]) SetParent added in v0.3.38 

func (n *StatusNode[S, T]) SetParent(parent Noder) bool

SetParent implements the Noder interface.

func (*StatusNode[S, T]) Size added in v0.3.38 

func (n *StatusNode[S, T]) Size() int

Size implements the Noder interface.

This function is expensive since size is not stored.

func (*StatusNode[S, T]) TreeOf added in v0.3.38 

func (n *StatusNode[S, T]) TreeOf() *Tree

ToTree implements the Noder interface.

type StatusNodeIterator added in v0.3.38 

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

StatusNodeIterator is a iterator that iterates over the children of a tree node.

func NewStatusNodeIterator added in v0.3.38 

func NewStatusNodeIterator[S uc.Enumer, T any](node *StatusNode[S, T]) *StatusNodeIterator[S, T]

NewStatusNodeIterator creates a new iterator for the given node.

Parameters:

  • node: The node whose children are being iterated over.

Returns:

  • *StatusNodeIterator[S, T]: A pointer to the iterator. Nil if the node is nil.

func (*StatusNodeIterator[S, T]) Consume added in v0.3.38 

func (t *StatusNodeIterator[S, T]) Consume() (Noder, error)

Size implements the common.Iterater interface.

func (*StatusNodeIterator[S, T]) Restart added in v0.3.38 

func (t *StatusNodeIterator[S, T]) Restart()

Restart implements the common.Iterater interface.

type Tree 

type Tree struct {
	// contains filtered or unexported fields
}

Tree is a generic data structure that represents a tree.

func NewTree 

func NewTree(root Noder) *Tree

NewTree creates a new tree with the given value as the root.

Parameters:

  • data: The value of the root.

Returns:

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

func (*Tree) Cleanup 

func (t *Tree) Cleanup()

Cleanup implements the object.Cleaner interface.

func (*Tree) Copy added in v0.3.33 

func (t *Tree) Copy() uc.Copier

Copy implements the common.Copier interface.

func (*Tree) DeleteBranchContaining 

func (t *Tree) DeleteBranchContaining(n Noder) error

DeleteBranchContaining deletes the branch containing the given node.

Parameters:

  • n: The node to delete.

Returns:

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

func (*Tree) ExtractBranch added in v0.3.34 

func (t *Tree) ExtractBranch(leaf Noder, delete bool) (*Branch, error)

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[Noder]: A pointer to the branch extracted. Nil if the leaf is not a part of the tree.

func (*Tree) FString 

func (t *Tree) FString(trav *ffs.Traversor, opts ...ffs.Option) error

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

func (*Tree) FilterChildren 

func (t *Tree) FilterChildren(filter us.PredicateFilter[Noder]) ([]Noder, error)

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

The filter must assume that the node is never nil.

Parameters:

  • filter: The filter to apply.

Returns:

  • []Noder: A slice of the children that satisfy the filter.
  • error: An error if iterating over the children fails.

func (*Tree) GetDirectChildren 

func (t *Tree) GetDirectChildren() ([]Noder, error)

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

Children are never nil.

Returns:

  • []Noder: A slice of the direct children of the root. Nil if the tree does not have a root.
  • error: An error if the iteration fails.

func (*Tree) GetLeaves 

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

GetLeaves returns all the leaves of the tree.

Returns:

  • []Noder: A slice of the leaves of the tree. Nil if the tree does not have a root.

Behaviors:

  • 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) HasChild 

func (t *Tree) HasChild(filter us.PredicateFilter[Noder]) (bool, error)

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

The filter must assume that the node is never nil.

Parameters:

  • filter: The filter to apply.

Returns:

  • bool: True if the tree has the child, false otherwise.
  • error: An error if the child is not of type Noder.

func (*Tree) InsertBranch added in v0.3.34 

func (t *Tree) InsertBranch(branch *Branch) (bool, error)

InsertBranch inserts the given branch into the tree.

Parameters:

  • branch: The branch to insert.

Returns:

  • bool: True if the branch was inserted, false otherwise.
  • error: An error if the insertion fails.

func (*Tree) IsSingleton 

func (t *Tree) 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) ProcessLeaves 

func (t *Tree) ProcessLeaves(f uc.EvalManyFunc[Noder, Noder]) 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 Noder.
  • 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) Prune added in v0.3.27 

func (t *Tree) Prune(filter us.PredicateFilter[Noder]) (bool, error)

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.
  • error: An error if the iteration fails.

func (*Tree) PruneBranches 

func (t *Tree) PruneBranches(filter us.PredicateFilter[Noder]) 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) PruneFunc added in v0.3.37 

func (t *Tree) PruneFunc(filter us.PredicateFilter[Noder]) bool

PruneFunc removes all the children of the node that satisfy the given filter including all of their children.

Parameters:

  • filter: The filter to apply.

Returns:

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

Behaviors:

  • The root node is not pruned.

func (*Tree) RegenerateLeaves 

func (t *Tree) RegenerateLeaves() ([]Noder, error)

RegenerateLeaves regenerates the leaves of the tree and returns them.

Returns:

  • []Noder: The newly generated leaves of the tree.
  • error: An error if the leaves could not be generated or the nodes are not of type Noder.

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) Root 

func (t *Tree) Root() Noder

Root returns the root of the tree.

Returns:

  • Noder: The root of the tree. Nil if the tree does not have a root.

func (*Tree) SearchNodes 

func (t *Tree) SearchNodes(f us.PredicateFilter[Noder]) (Noder, error)

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

Parameters:

  • f: The filter to apply.

Returns:

  • Noder: The node that satisfies the filter.
  • error: An error if the node is not found or the iteration fails.

Errors:

  • *common.ErrNotFound: If the node is not found.
  • error: The error returned by the iteration function.

func (*Tree) SetChildren 

func (t *Tree) SetChildren(children []*Tree) 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) Size 

func (t *Tree) Size() int

Size returns the number of nodes in the tree.

Returns:

  • int: The number of nodes in the tree.

func (*Tree) SkipFilter 

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

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: 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) SnakeTraversal 

func (t *Tree) SnakeTraversal() ([][]Noder, error)

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

Returns:

  • [][]Noder: A slice of slices of elements.
  • error: An error if the iterator fails.

Behaviors:

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

func (*Tree) UpdateLeaves 

func (t *Tree) UpdateLeaves() ([]Noder, error)

UpdateLeaves updates the leaves of the tree and returns them.

Returns:

  • []Noder: The newly generated leaves of the tree.
  • error: An error if the leaves could not be generated or the nodes are not of type Noder.

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 {
	// Parent, FirstChild, NextSibling, LastChild, PrevSibling are pointers to
	// the parent, first child, next sibling, last child, and previous sibling
	// of the node respectively.
	Parent, FirstChild, NextSibling, LastChild, PrevSibling *TreeNode[T]

	// Data is the value of the node.
	Data T
}

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

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 Noder)

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

Parameters:

  • child: The child to add.

Behaviors:

  • If the child is nil, it does nothing.

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]) Cleanup added in v0.3.37 

func (tn *TreeNode[T]) Cleanup()

Cleanup implements the Noder interface.

Uses DFS traversal, does not use recursion, and does not remove the node itself.

func (*TreeNode[T]) Copy 

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

Copy implements the Noder interface.

func (*TreeNode[T]) DeleteChild 

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

DeleteChild implements the Noder interface.

func (*TreeNode[T]) FString 

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

FString implements the Noder interface.

func (*TreeNode[T]) GetAncestors 

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

GetAncestors implements the Noder interface.

func (*TreeNode[T]) GetChildren 

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

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

Returns:

  • []Noder: 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]) GetFirstChild added in v0.3.37 

func (n *TreeNode[T]) GetFirstChild() Noder

GetFirstChild implements the Noder interface.

func (*TreeNode[T]) GetFirstSibling added in v0.3.37 

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

GetFirstSibling returns the first sibling of the node. If it has a parent, it returns the first child of the parent. Otherwise, it returns the first sibling of the node.

Returns:

  • *TreeNode[T]: A pointer to the first sibling. The node itself if it has no previous sibling.

func (*TreeNode[T]) GetLastSibling added in v0.3.37 

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

GetLastSibling returns the last sibling of the node. If it has a parent, it returns the last child of the parent. Otherwise, it returns the last sibling of the node.

Returns:

  • *TreeNode[T]: A pointer to the last sibling. The node itself if it has no next sibling.

func (*TreeNode[T]) GetLeaves added in v0.3.37 

func (n *TreeNode[T]) GetLeaves() []Noder

GetLeaves implements the Noder interface.

func (*TreeNode[T]) GetParent added in v0.3.37 

func (n *TreeNode[T]) GetParent() Noder

GetParent implements the Noder interface.

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

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]) IsSingleton added in v0.3.37 

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

IsSingleton implements the Noder interface.

func (*TreeNode[T]) Iterator added in v0.3.37 

func (t *TreeNode[T]) Iterator() uc.Iterater[Noder]

Iterator implements Noder.

func (*TreeNode[T]) LinkChildren added in v0.3.37 

func (tn *TreeNode[T]) LinkChildren(children []Noder)

LinkWithParent implements the Noder interface.

Children that are not *TreeNode[T] are ignored.

func (*TreeNode[T]) RemoveNode added in v0.3.37 

func (n *TreeNode[T]) RemoveNode() []Noder

RemoveNode removes the node from the tree while shifting the children up one level to maintain the tree structure.

Also, the returned children can be used to create a forest of trees if the root node is removed.

Returns:

  • []Noder: A slice of pointers to the children of the node iff the node is the root. Nil otherwise.

Example: 

// Given the tree:
1
├── 2
└── 3
	├── 4
	└── 5
└── 6

// The tree after removing node 3:

1
├── 2
└── 4
└── 5
└── 6

func (*TreeNode[T]) SetParent added in v0.3.37 

func (n *TreeNode[T]) SetParent(parent Noder) bool

SetParent implements the Noder interface.

func (*TreeNode[T]) Size 

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

Size implements the Noder interface.

This function is expensive since size is not stored.

type TreeNodeIterator added in v0.3.37 

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

TreeNodeIterator is a iterator that iterates over the children of a tree node.

func (*TreeNodeIterator[T]) Consume added in v0.3.37 

func (t *TreeNodeIterator[T]) Consume() (Noder, error)

Size implements the common.Iterater interface.

func (*TreeNodeIterator[T]) Restart added in v0.3.37 

func (t *TreeNodeIterator[T]) Restart()

Restart implements the common.Iterater interface.

type UpdateLeavesCmd added in v0.3.33 

type UpdateLeavesCmd 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() *UpdateLeavesCmd

NewUpdateLeavesCmd creates a new UpdateLeavesCmd.

Returns:

  • *UpdateLeavesCmd: A pointer to the new UpdateLeavesCmd.

func (*UpdateLeavesCmd) Copy added in v0.3.33 

func (cmd *UpdateLeavesCmd) Copy() uc.Copier

Copy implements the Debugging.Commander interface.

func (*UpdateLeavesCmd) Execute added in v0.3.33 

func (cmd *UpdateLeavesCmd) Execute(data *Tree) error

Execute implements the Debugging.Commander interface.

func (*UpdateLeavesCmd) Undo added in v0.3.33 

func (cmd *UpdateLeavesCmd) Undo(data *Tree) 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.