trees

Documentation

Index

• Variables
• func BFS[T interface{ ... }](tree Tree[T], visit VisitFn[T]) error
• func DFS[T interface{ ... }](tree Tree[T], visit VisitFn[T]) error
• func Equals[T interface{ ... }](tree, other Tree[T]) bool
• func Inorder[T interface{ ... }](tree Tree[T], visit VisitFn[T]) error
• func PostorderView[T interface{ ... }](tree Tree[T], visit VisitFn[T]) error
• func PreorderView[T interface{ ... }](tree Tree[T], visit VisitFn[T]) error
• type DoFunc
• type InfoTable
• type Traversor
  • func NewTraversor[T interface{ ... }, I any](do_fn DoFunc[T, I]) Traversor[T, I]
  • func (t Traversor[T, I]) BFS(node T) error
  • func (t Traversor[T, I]) DFS(node T) error
  • func (it Traversor[T, I]) Get(node T) (I, bool)
  • func (it *Traversor[T, I]) Set(node T, info I) error
• type Tree
  • func New[T interface{ ... }](root T) Tree[T]
• type TreeNoder
• type TreeWriterFn
  • func MakeWriteTree[T interface{ ... }]() TreeWriterFn[T]
• type ViewElem
  • func NewViewElem[T any](node T) *ViewElem[T]
• type VisitFn

Variables

var (
	// ErrEarlyExit occurs when the traversal should stop early without error.
	// This can be checked with the == operator.
	//
	// Format:
	//
	// 	"early exit"
	ErrEarlyExit error
)

Functions

func BFS

func BFS[T interface {
	Child() iter.Seq[T]

	TreeNoder
}](tree Tree[T], visit VisitFn[T]) error

BFS performs a breadth-first traversal of the tree without using recursion. It processes each node before its children are processed.

Parameters:

• tree: The tree to traverse. If it is nil, the function returns immediately without error.
• visit: A function to call for each node visited. If it is nil, the function returns immediately without error.

Returns:

• error: The first error encountered during the traversal, or nil if the traversal was successful.

Behaviors:

• If the tree is nil or if the visit function is nil, then the traversal won't be performed but a nil error will be returned.
• Nil children will be ignored.
• Stops traversal early if the visit function returns an error, except for ErrEarlyExit which is ignored.

func DFS

func DFS[T interface {
	BackwardChild() iter.Seq[T]
	TreeNoder
}](tree Tree[T], visit VisitFn[T]) error

DFS performs a depth-first traversal of the tree without using recursion; stopping at the first error encountered.

Parameters:

• tree: The tree to traverse.
• visit: The function to call for each node in the tree.

Returns:

• error: The first error encountered during the traversal, or nil if the traversal was successful.

Behaviors:

• If the tree is nil or if the visit function is nil, then the traversal won't be performed but a nil error will be returned.
• Nil children will be ignored.
• Stops traversal early if the visit function returns an error, except for ErrEarlyExit which is ignored.

func Equals

func Equals[T interface {
	Child() iter.Seq[T]
	Equals(other T) bool

	TreeNoder
}](tree, other Tree[T]) bool

Equals checks if two trees are equal.

The two trees are considered equal if they have the same number of nodes and the same structure. The contents of the nodes are compared with the Equals method of the node type.

Parameters:

• other: The other tree to compare with.

Returns:

• bool: True if the two trees are equal, false otherwise.

func Inorder

func Inorder[T interface {
	Child() iter.Seq[T]

	TreeNoder
}](tree Tree[T], visit VisitFn[T]) error

Inorder performs an in-order traversal of the tree by using recursion. It visits the left subtree, then the node itself, and finally the right subtree.

Parameters:

• tree: The tree to traverse. If it is nil, the function returns immediately without error.
• visit: A function to call for each node visited. If it is nil, the function returns immediately without error.

Returns:

• error: The first error encountered during the traversal, or nil if the traversal was successful.

Behaviors:

• If the tree is nil or if the visit function is nil, then the traversal won't be performed but a nil error will be returned.
• Nil children will be ignored.
• If the visit function returns an error, traversal stops immediately.
• If the visit function returns ErrEarlyExit, it is ignored and traversal continues.

func PostorderView

func PostorderView[T interface {
	BackwardChild() iter.Seq[T]

	TreeNoder
}](tree Tree[T], visit VisitFn[T]) error

PostorderView performs a post-order traversal of the tree without using recursion. It processes each node after its children have been processed.

Parameters:

• tree: The tree to traverse. If it is nil, the function returns immediately without error.
• visit: A function to call for each node visited. If it is nil, the function returns immediately without error.

Returns:

• error: The first error encountered during the traversal, or nil if the traversal was successful.

Behaviors:

• If the tree is nil or if the visit function is nil, then the traversal won't be performed but a nil error will be returned.
• Nil children will be ignored.
• Stops traversal early if the visit function returns an error, except for ErrEarlyExit which is ignored.

func PreorderView

func PreorderView[T interface {
	BackwardChild() iter.Seq[T]

	TreeNoder
}](tree Tree[T], visit VisitFn[T]) error

PreorderView performs a preorder traversal without using recursion of the tree; stopping at the first error encountered.

Parameters:

• tree: The tree to traverse.
• visit: The function to call for each node in the tree.

Returns:

• error: The first error encountered during the traversal, or nil if the traversal was successful.

Behaviors:

• If tree is nil or if visit is nil, then the traversal won't be performed but a nil error will be returned.
• Nil children will be ignored.

Types

type DoFunc

type DoFunc[T interface {
	Child() iter.Seq[T]
	BackwardChild() iter.Seq[T]

	TreeNoder
}, I any] func(node T, trav *Traversor[T, I]) error

DoFunc is a function that is called for each node in the tree.

Parameters:

• node: The current node in the tree. Assumed to be non-nil.
• trav: A pointer to the traverser. Assumed to be non-nil.

Returns:

• error: An error that indicates if the traversal should stop.

type InfoTable

type InfoTable[T interface {
	Child() iter.Seq[T]
	BackwardChild() iter.Seq[T]

	TreeNoder
}, I any] struct {
	// contains filtered or unexported fields
}

InfoTable is a table that stores information about each node in the tree.

type Traversor

type Traversor[T interface {
	Child() iter.Seq[T]
	BackwardChild() iter.Seq[T]

	TreeNoder
}, I any] struct {
	// contains filtered or unexported fields
}

Traversor is a data structure that holds information necessary for the tree traversal.

func NewTraversor

func NewTraversor[T interface {
	Child() iter.Seq[T]
	BackwardChild() iter.Seq[T]

	TreeNoder
}, I any](do_fn DoFunc[T, I]) Traversor[T, I]

NewTraversor returns a new traverser. If no do function is provided, then the traverser will do nothing and return nil.

Parameters:

• do_fn: The function that is called for each node in the tree.

Returns:

• Traversor: A traverser.

func (Traversor[T, I]) BFS

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

BFS performs a breadth-first traversal of the tree without using recursion; stopping at the first error encountered.

Parameters:

• node: The node to start the traversal from.

Returns:

• error: An error if any occurred during the traversal.

Behaviors:

• If the node is nil or if the do function is nil, then the traversal won't be performed but a nil error will be returned.
• Nil children will be ignored.

func (Traversor[T, I]) DFS

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

DFS performs a depth-first traversal of the tree without using recursion; stopping at the first error encountered.

Parameters:

• node: The node to start the traversal from.

Returns:

• error: An error if any occurred during the traversal.

Behaviors:

• If the node is nil or if the do function is nil, then the traversal won't be performed but a nil error will be returned.
• Nil children will be ignored.

func (Traversor[T, I]) Get

func (it Traversor[T, I]) Get(node T) (I, bool)

Get retrieves the information for the given node.

Parameters:

• node: The node to get the information for.

Returns:

• I: The information for the given node.
• bool: True if the receiver is not nil and the node was found, false otherwise.

func (*Traversor[T, I]) Set

func (it *Traversor[T, I]) Set(node T, info I) error

Set sets the information for the given node. If the node was already setted beforehand, then it will be overwritten.

Parameters:

• node: The node to set the information for.
• info: The information to set.

Returns:

• error: An error if the receiver is nil.

type Tree

type Tree[T interface {
	TreeNoder
}] interface {
	// Size returns the number of nodes in the tree.
	//
	// Returns:
	//   - int: The number of nodes in the tree.
	Size() int

	// Root returns the root node of the tree.
	//
	// Returns:
	//   - T: The root node of the tree.
	Root() T

	fmt.Stringer
}

Tree is a data structure that represents a tree.

func New

func New[T interface {
	Child() iter.Seq[T]
	BackwardChild() iter.Seq[T]

	TreeNoder
}](root T) Tree[T]

New creates a new Tree given the root node.

Parameters:

• root: The root node of the tree.

Returns:

• Tree[T]: The tree. Nil if root is nil.

type TreeNoder

type TreeNoder interface {
	comparable

	// IsNil checks whether the node is nil.
	//
	// Returns:
	//   - bool: True if the node is nil, false otherwise.
	IsNil() bool

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

	fmt.Stringer
}

TreeNoder is an interface that must be implemented by all tree nodes.

type TreeWriterFn

type TreeWriterFn[T interface {
	Child() iter.Seq[T]
	BackwardChild() iter.Seq[T]

	TreeNoder
}] func(w io.Writer, root T) (int, error)

func MakeWriteTree

func MakeWriteTree[T interface {
	Child() iter.Seq[T]
	BackwardChild() iter.Seq[T]

	TreeNoder
}]() TreeWriterFn[T]

MakeWriteTree returns a string representation of the given token tree in a form that is easier to read and understand.

Parameters:

• root: The root of the token tree to print.

Returns:

• string: A string representation of the token tree.

If root is nil, an empty string is returned.

WARNING: This function is recursive.

type ViewElem

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

ViewElem is an element of a view.

func NewViewElem

func NewViewElem[T any](node T) *ViewElem[T]

NewViewElem returns a new view element with the given node and seen set to false.

Parameters:

• node: The node of the view.

Returns:

• *ViewElem[T]: The new view element. Never returns nil.

type VisitFn

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

VisitFn is a function that visits a node.

Parameters:

• node: The node to visit.

Returns:

• error: An error that indicates if the traversal should immediately stop.

Errors:

• ErrEarlyExit: The traversal should stop early without error.