tree

Documentation

Index

• func BstCmpFind[T data.CmpOrdered[T]](root *BinaryTreeNodeWrapper[T], target T) bool
• func BstCmpInsert[T data.CmpOrdered[T]](root, node *BinaryTreeNodeWrapper[T]) bool
• func BstFind[T constraints.Ordered](root *BinaryTreeNodeWrapper[T], target T) bool
• func BstInsert[T constraints.Ordered](root *BinaryTreeNodeWrapper[T], node *BinaryTreeNodeWrapper[T]) bool
• func BstInsertRecurse[T constraints.Ordered](root *BinaryTreeNodeWrapper[T], node *BinaryTreeNodeWrapper[T]) bool
• func Inorder[POS any, NODE any](tree BinaryTree[POS, NODE], node POS, f func(NODE) error) error
• func InorderNode[NODE BinaryTreeNode[any]](node NODE, f func(NODE) error) error
• func InorderNodeRecurse[T any, NODE BinaryTreeNode[T]](node NODE, f func(NODE) error) error
• func InorderRecurse[POS any, NODE any](tree BinaryTree[POS, NODE], node POS, f func(NODE) error) error
• func LeftChildIdx(parent int) int
• func ParentIdx(child int) int
• func RightChildIdx(parent int) int
• type BinaryTree
• type BinaryTreeBasic
• type BinaryTreeNode
  • func DigLeft[T any](root BinaryTreeNode[T]) (BinaryTreeNode[T], uint)
  • func DigRight[T any](node BinaryTreeNode[T]) (BinaryTreeNode[T], uint)
• type BinaryTreeNodeWrapper
  • func BstCmpRemove[T data.CmpOrdered[T]](root *BinaryTreeNodeWrapper[T], target T) *BinaryTreeNodeWrapper[T]
  • func BstRemove[T constraints.Ordered](root *BinaryTreeNodeWrapper[T], target T) *BinaryTreeNodeWrapper[T]
  • func (n *BinaryTreeNodeWrapper[T]) IsLeaf() bool
  • func (n *BinaryTreeNodeWrapper[T]) IsNull() bool
  • func (n *BinaryTreeNodeWrapper[T]) Left() BinaryTreeNode[T]
  • func (n *BinaryTreeNodeWrapper[T]) Right() BinaryTreeNode[T]
  • func (n *BinaryTreeNodeWrapper[T]) Value() T
• type Bst
  • func NewBst[T constraints.Ordered]() *Bst[T]
  • func (b *Bst[T]) Find(target T) bool
  • func (b *Bst[T]) Insert(item T) bool
  • func (b *Bst[T]) Remove(target T) bool
• type BstCmp
  • func NewBstCmp[T data.CmpOrdered[T]]() *BstCmp[T]
  • func (b *BstCmp[T]) Find(target T) bool
  • func (b *BstCmp[T]) Insert(item T) bool
  • func (b *BstCmp[T]) Remove(target T) bool
• type BstCount
  • func NewBstCount[T any](bst BinaryTreeBasic[T]) *BstCount[T]
  • func (b *BstCount[T]) Find(item T) bool
  • func (b *BstCount[T]) Insert(item T) bool
  • func (b *BstCount[T]) Remove(item T) bool
• type Heap
  • func NewHeap[T constraints.Ordered](order data.SortOrder) *Heap[T]
  • func NewHeapCmp[T data.CmpOrdered[T]](order data.SortOrder) *Heap[T]
  • func (h *Heap[T]) IsEmpty() bool
  • func (h *Heap[T]) Len() int
  • func (h *Heap[T]) PeekGetter() data.Getter[T]
  • func (h *Heap[T]) PeekValue() T
  • func (h *Heap[T]) Pop() *T
  • func (h *Heap[T]) PopGetter() data.Getter[T]
  • func (h *Heap[T]) PopValue() T
  • func (h *Heap[T]) Push(item T)
  • func (h *Heap[T]) PushGetter(getter data.Getter[T])

Functions

func BstCmpFind

func BstCmpFind[T data.CmpOrdered[T]](root *BinaryTreeNodeWrapper[T], target T) bool

func BstCmpInsert

func BstCmpInsert[T data.CmpOrdered[T]](root, node *BinaryTreeNodeWrapper[T]) bool

func BstFind

func BstFind[T constraints.Ordered](root *BinaryTreeNodeWrapper[T], target T) bool

func BstInsert

func BstInsert[T constraints.Ordered](root *BinaryTreeNodeWrapper[T], node *BinaryTreeNodeWrapper[T]) bool

func BstInsertRecurse

func BstInsertRecurse[T constraints.Ordered](root *BinaryTreeNodeWrapper[T], node *BinaryTreeNodeWrapper[T]) bool

func Inorder

func Inorder[POS any, NODE any](
	tree BinaryTree[POS, NODE],
	node POS,
	f func(NODE) error,
) error

func InorderNode

func InorderNode[NODE BinaryTreeNode[any]](
	node NODE,
	f func(NODE) error,
) error

func InorderNodeRecurse

func InorderNodeRecurse[T any, NODE BinaryTreeNode[T]](
	node NODE,
	f func(NODE) error,
) error

func InorderRecurse

func InorderRecurse[POS any, NODE any](
	tree BinaryTree[POS, NODE],
	node POS,
	f func(NODE) error,
) error

func LeftChildIdx

func LeftChildIdx(parent int) int

func ParentIdx

func ParentIdx(child int) int

func RightChildIdx

func RightChildIdx(parent int) int

Types

type BinaryTree

type BinaryTree[POS any, NODE any] interface {
	BinaryTreeBasic[NODE]

	Parent(node POS) POS
	LeftChild(node POS) POS
	RightChild(node POS) POS
	Node(pos POS) NODE

	NodeIsRoot(node POS) bool
	NodeIsNull(node POS) bool
}

BinaryTree have extra methods to work with nodes. POS is any type used for indexing a node, e.g. a bintree with backing arrays may use int as POS.

type BinaryTreeBasic

type BinaryTreeBasic[NODE any] interface {
	// Insert inserts a node to the tree,
	// returning bool indicating if a node was added.
	// False is returned if an existing node was replaced
	// with new node, leaving tree size unchanged.
	Insert(node NODE) bool

	// Remove removes node, returning whether the removal
	// was successful.
	Remove(node NODE) bool

	Find(node NODE) bool
}

BinaryTreeBasic is basic, minimal binary tree with node type NODE

type BinaryTreeNode

type BinaryTreeNode[T any] interface {
	Value() T
	Left() BinaryTreeNode[T]
	Right() BinaryTreeNode[T]
	IsNull() bool
}

func DigLeft

func DigLeft[T any](root BinaryTreeNode[T]) (BinaryTreeNode[T], uint)

DigLeft digs for smallest values in the subtree, returning the node as well as the height to that node.

func DigRight

func DigRight[T any](node BinaryTreeNode[T]) (BinaryTreeNode[T], uint)

DigRight digs for smallest values in the subtree, returning the node as well as the height to that node.

type BinaryTreeNodeWrapper

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

func BstCmpRemove

func BstCmpRemove[T data.CmpOrdered[T]](root *BinaryTreeNodeWrapper[T], target T) *BinaryTreeNodeWrapper[T]

BstRemove removes target from subtree tree, returning the new root of the subtree

func BstRemove

func BstRemove[T constraints.Ordered](root *BinaryTreeNodeWrapper[T], target T) *BinaryTreeNodeWrapper[T]

BstRemove removes target from subtree tree, returning the new root of the subtree

func (*BinaryTreeNodeWrapper[T]) IsLeaf

func (n *BinaryTreeNodeWrapper[T]) IsLeaf() bool

func (*BinaryTreeNodeWrapper[T]) IsNull

func (n *BinaryTreeNodeWrapper[T]) IsNull() bool

func (*BinaryTreeNodeWrapper[T]) Left

func (n *BinaryTreeNodeWrapper[T]) Left() BinaryTreeNode[T]

func (*BinaryTreeNodeWrapper[T]) Right

func (n *BinaryTreeNodeWrapper[T]) Right() BinaryTreeNode[T]

func (*BinaryTreeNodeWrapper[T]) Value

func (n *BinaryTreeNodeWrapper[T]) Value() T

type Bst

type Bst[T constraints.Ordered] struct {
	Root BinaryTreeNodeWrapper[T]
}

Bst is BST implementation with nodeWrapper as node.

func NewBst

func NewBst[T constraints.Ordered]() *Bst[T]

func (*Bst[T]) Find

func (b *Bst[T]) Find(target T) bool

func (*Bst[T]) Insert

func (b *Bst[T]) Insert(item T) bool

func (*Bst[T]) Remove

func (b *Bst[T]) Remove(target T) bool

type BstCmp

type BstCmp[T data.CmpOrdered[T]] struct {
	Root BinaryTreeNodeWrapper[T]
}

BstCmp is for types with Cmp(T) int methods, e.g. *big.Int

func NewBstCmp

func NewBstCmp[T data.CmpOrdered[T]]() *BstCmp[T]

func (*BstCmp[T]) Find

func (b *BstCmp[T]) Find(target T) bool

func (*BstCmp[T]) Insert

func (b *BstCmp[T]) Insert(item T) bool

func (*BstCmp[T]) Remove

func (b *BstCmp[T]) Remove(target T) bool

type BstCount

type BstCount[T any] struct {
	Count uint64

	BinaryTreeBasic[T]
}

func NewBstCount

func NewBstCount[T any](bst BinaryTreeBasic[T]) *BstCount[T]

func (*BstCount[T]) Find

func (b *BstCount[T]) Find(item T) bool

func (*BstCount[T]) Insert

func (b *BstCount[T]) Insert(item T) bool

func (*BstCount[T]) Remove

func (b *BstCount[T]) Remove(item T) bool

type Heap

type Heap[T any] struct {
	Items    []data.Getter[T]
	LessFunc data.LessFunc[data.Getter[T]]
}

Heap is a binary heap implementation backed by Go slice.

func NewHeap

func NewHeap[T constraints.Ordered](
	order data.SortOrder,
) *Heap[T]

func NewHeapCmp

func NewHeapCmp[T data.CmpOrdered[T]](
	order data.SortOrder,
) *Heap[T]

func (*Heap[T]) IsEmpty

func (h *Heap[T]) IsEmpty() bool

func (*Heap[T]) Len

func (h *Heap[T]) Len() int

func (*Heap[T]) PeekGetter

func (h *Heap[T]) PeekGetter() data.Getter[T]

func (*Heap[T]) PeekValue

func (h *Heap[T]) PeekValue() T

func (*Heap[T]) Pop

func (h *Heap[T]) Pop() *T

func (*Heap[T]) PopGetter

func (h *Heap[T]) PopGetter() data.Getter[T]

func (*Heap[T]) PopValue

func (h *Heap[T]) PopValue() T

func (*Heap[T]) Push

func (h *Heap[T]) Push(item T)

func (*Heap[T]) PushGetter

func (h *Heap[T]) PushGetter(getter data.Getter[T])