rbt

Documentation

Index

• type Iterator
  • func (it *Iterator[K, V]) Get() misc.Pair[K, V]
  • func (it *Iterator[K, V]) Key() K
  • func (it *Iterator[K, V]) Move()
  • func (it *Iterator[K, V]) Node() *Node[K, V]
  • func (it *Iterator[K, V]) Remove()
  • func (it *Iterator[K, V]) SetValue(value V)
  • func (it *Iterator[K, V]) Valid() bool
  • func (it *Iterator[K, V]) Value() V
  • func (it *Iterator[K, V]) ValueRef() *V
• type Node
  • func (node *Node[K, V]) Clone() *Node[K, V]
  • func (node *Node[K, V]) Key() K
  • func (node *Node[K, V]) LeftChild() *Node[K, V]
  • func (node *Node[K, V]) Max() *Node[K, V]
  • func (node *Node[K, V]) Min() *Node[K, V]
  • func (node *Node[K, V]) Next() *Node[K, V]
  • func (node *Node[K, V]) Parent() *Node[K, V]
  • func (node *Node[K, V]) Prev() *Node[K, V]
  • func (node *Node[K, V]) RightChild() *Node[K, V]
  • func (node *Node[K, V]) Sibling() *Node[K, V]
• type Tree
  • func New[K cmp.Ordered, V any]() *Tree[K, V]
  • func NewFromIterable[K cmp.Ordered, V any](iterable iter.Iterable[misc.Pair[K, V]]) *Tree[K, V]
  • func NewWithComparator[K, V any](comparator comparison.Comparator[K]) *Tree[K, V]
  • func NewWithComparatorFromIterable[K, V any](comparator comparison.Comparator[K], iterable iter.Iterable[misc.Pair[K, V]]) *Tree[K, V]
  • func (tree *Tree[K, V]) Clear()
  • func (tree *Tree[K, V]) Clone() maps.Map[K, V]
  • func (tree *Tree[K, V]) Contains(key K) bool
  • func (tree *Tree[K, V]) Get(key K) V
  • func (tree *Tree[K, V]) GetNode(key K) *Node[K, V]
  • func (tree *Tree[K, V]) GetRef(key K) *V
  • func (tree *Tree[K, V]) Iterator() iter.Iterator[misc.Pair[K, V]]
  • func (tree *Tree[K, V]) MapIterator() maps.Iterator[K, V]
  • func (tree *Tree[K, V]) RefsStream2(yield func(K, *V) bool)
  • func (tree *Tree[K, V]) Remove(key K)
  • func (tree *Tree[K, V]) Root() *Node[K, V]
  • func (tree *Tree[K, V]) Set(key K, value V)
  • func (tree *Tree[K, V]) Size() int
  • func (tree *Tree[K, V]) Stream2(yield func(K, V) bool)
  • func (tree *Tree[K, V]) TryGet(key K) (V, bool)

Types

type Iterator

type Iterator[K, V any] struct {
	// contains filtered or unexported fields
}

Iterator is an iterator over a Tree.

func (*Iterator[K, V]) Get

func (it *Iterator[K, V]) Get() misc.Pair[K, V]

Get returns the current entry as a key-value pair.

func (*Iterator[K, V]) Key

func (it *Iterator[K, V]) Key() K

Key returns the key of the current entry.

func (*Iterator[K, V]) Move

func (it *Iterator[K, V]) Move()

Move moves the iterator to the next entry.

func (*Iterator[K, V]) Node

func (it *Iterator[K, V]) Node() *Node[K, V]

Node returns the current node.

func (*Iterator[K, V]) Remove

func (it *Iterator[K, V]) Remove()

Remove removes the current entry from the map. The iterator will point to the next entry afterward.

func (*Iterator[K, V]) SetValue

func (it *Iterator[K, V]) SetValue(value V)

SetValue sets the value of the current entry.

func (*Iterator[K, V]) Valid

func (it *Iterator[K, V]) Valid() bool

Valid returns true if it points to a valid entry.

func (*Iterator[K, V]) Value

func (it *Iterator[K, V]) Value() V

Value returns the value of the current entry.

func (*Iterator[K, V]) ValueRef

func (it *Iterator[K, V]) ValueRef() *V

ValueRef returns a reference to the value of the current entry.

type Node

type Node[K, V any] struct {
	Value V // Value is the value stored in the node.
	// contains filtered or unexported fields
}

Node is a node of a red-black tree. It should not be created directly.

func (*Node[K, V]) Clone

func (node *Node[K, V]) Clone() *Node[K, V]

Clone returns a clone of the node. The clone has the same key, value, and color as the node. The clone does not have any links to other nodes.

func (*Node[K, V]) Key

func (node *Node[K, V]) Key() K

Key returns the key of the node.

func (*Node[K, V]) LeftChild

func (node *Node[K, V]) LeftChild() *Node[K, V]

LeftChild returns the left child of the node.

func (*Node[K, V]) Max

func (node *Node[K, V]) Max() *Node[K, V]

Max returns the maximum node in the subtree rooted at the node.

func (*Node[K, V]) Min

func (node *Node[K, V]) Min() *Node[K, V]

Min returns the minimum node in the subtree rooted at the node.

func (*Node[K, V]) Next

func (node *Node[K, V]) Next() *Node[K, V]

Next returns the next node in the tree in the order of the keys.

func (*Node[K, V]) Parent

func (node *Node[K, V]) Parent() *Node[K, V]

Parent returns the parent of the node.

func (*Node[K, V]) Prev

func (node *Node[K, V]) Prev() *Node[K, V]

Prev returns the previous node in the tree in the order of the keys.

func (*Node[K, V]) RightChild

func (node *Node[K, V]) RightChild() *Node[K, V]

RightChild returns the right child of the node.

func (*Node[K, V]) Sibling

func (node *Node[K, V]) Sibling() *Node[K, V]

Sibling returns the sibling of the node. If the node is the root, it returns nil.

type Tree

type Tree[K, V any] struct {
	// contains filtered or unexported fields
}

Tree is a red-black tree implementation of a map. The zero value is ready to use. Do not copy a non-zero Tree.

func New

func New[K cmp.Ordered, V any]() *Tree[K, V]

New creates an empty Tree with the default comparator for ordered keys.

func NewFromIterable

func NewFromIterable[K cmp.Ordered, V any](iterable iter.Iterable[misc.Pair[K, V]]) *Tree[K, V]

NewFromIterable creates a Tree from the specified iter.Iterable.

func NewWithComparator

func NewWithComparator[K, V any](comparator comparison.Comparator[K]) *Tree[K, V]

NewWithComparator creates an empty Tree with the specified comparator.

func NewWithComparatorFromIterable

func NewWithComparatorFromIterable[K, V any](comparator comparison.Comparator[K], iterable iter.Iterable[misc.Pair[K, V]]) *Tree[K, V]

NewWithComparatorFromIterable creates a Tree with the specified comparator from the specified iter.Iterable.

func (*Tree[K, V]) Clear

func (tree *Tree[K, V]) Clear()

Clear removes all entries from the tree.

func (*Tree[K, V]) Clone

func (tree *Tree[K, V]) Clone() maps.Map[K, V]

Clone returns a shallow copy of the tree.

func (*Tree[K, V]) Contains

func (tree *Tree[K, V]) Contains(key K) bool

Contains returns true if the tree contains the specified key.

func (*Tree[K, V]) Get

func (tree *Tree[K, V]) Get(key K) V

Get returns the value associated with the specified key. Panics if the key is not present.

func (*Tree[K, V]) GetNode

func (tree *Tree[K, V]) GetNode(key K) *Node[K, V]

GetNode returns the node associated with the specified key. Returns nil if the key is not present.

func (*Tree[K, V]) GetRef

func (tree *Tree[K, V]) GetRef(key K) *V

GetRef returns a reference to the value associated with the specified key. Panics if the key is not present.

func (*Tree[K, V]) Iterator

func (tree *Tree[K, V]) Iterator() iter.Iterator[misc.Pair[K, V]]

Iterator returns an iter.Iterator over the tree.

func (*Tree[K, V]) MapIterator

func (tree *Tree[K, V]) MapIterator() maps.Iterator[K, V]

MapIterator returns an iterator over the tree.

func (*Tree[K, V]) RefsStream2

func (tree *Tree[K, V]) RefsStream2(yield func(K, *V) bool)

RefsStream2 streams over the keys and references to the values in the Map.

func (*Tree[K, V]) Remove

func (tree *Tree[K, V]) Remove(key K)

Remove removes the entry with the specified key. Does nothing if the key is not present.

func (*Tree[K, V]) Root

func (tree *Tree[K, V]) Root() *Node[K, V]

Root returns the root node of the tree.

func (*Tree[K, V]) Set

func (tree *Tree[K, V]) Set(key K, value V)

Set sets the value associated with the specified key.

func (*Tree[K, V]) Size

func (tree *Tree[K, V]) Size() int

Size returns the number of entries in the tree.

func (*Tree[K, V]) Stream2

func (tree *Tree[K, V]) Stream2(yield func(K, V) bool)

Stream2 streams over the entries in the Tree.

func (*Tree[K, V]) TryGet

func (tree *Tree[K, V]) TryGet(key K) (V, bool)

TryGet returns the value associated with the specified key, or zero value and false if the key is not present.