rbtree

Documentation

Index

• func Greater[T constraints.Ordered](x, y T) bool
• func Less[T constraints.Ordered](x, y T) bool
• type CompareFunc
• type Iterator
• type RBTree
  • func New[K comparable, V any](cmp CompareFunc[K]) *RBTree[K, V]
  • func (tree *RBTree[K, V]) Clear()
  • func (tree *RBTree[K, V]) Erase(iter Iterator[K, V]) bool
  • func (tree *RBTree[K, V]) Find(key K) Iterator[K, V]
  • func (tree *RBTree[K, V]) First() Iterator[K, V]
  • func (tree *RBTree[K, V]) Format(formatter container.TreeFormatter) string
  • func (tree *RBTree[K, V]) Insert(key K, value V) (Iterator[K, V], bool)
  • func (tree *RBTree[K, V]) Last() Iterator[K, V]
  • func (tree RBTree[K, V]) Len() int
  • func (tree *RBTree[K, V]) MarshalTree(prefix string) string
  • func (tree *RBTree[K, V]) Remove(key K) bool
  • func (tree *RBTree[K, V]) String() string

Examples

• RBTree

Functions

func Greater

func Greater[T constraints.Ordered](x, y T) bool

func Less

func Less[T constraints.Ordered](x, y T) bool

Types

type CompareFunc

type CompareFunc[T comparable] func(k1, k2 T) bool

CompareFunc represents comparation between key

type Iterator

type Iterator[K comparable, V any] interface {
	// Prev returns previous iterator
	Prev() Iterator[K, V]
	// Next returns next node iterator
	Next() Iterator[K, V]
	// Key returns key of the node
	Key() K
	// Value returns value of the node
	Value() V
	// SetValue sets value of the node
	SetValue(V)
	// contains filtered or unexported methods
}

Iterator represents an iterator of RBTree to iterate nodes

type RBTree

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

RBTree RBComment

Example

tree := New[int, int](Greater[int])
fmt.Print("empty:\n" + tree.Format(container.TreeFormatter{}))

tree.Insert(1, 2)
tree.Insert(2, 4)
tree.Insert(4, 8)
tree.Insert(8, 16)

fmt.Print("default:\n" + tree.Format(container.TreeFormatter{}))
fmt.Print("custom:\n" + tree.Format(container.TreeFormatter{
	Prefix:         "... ",
	IconParent:     "|  ",
	IconBranch:     "|--",
	IconLastBranch: "+--",
}))
fmt.Println("plain:\n" + tree.String())

Output:

empty:
<nil>
default:
2:4
├── 4:8
│   └── 8:16
└── 1:2
custom:
... 2:4
... |-- 4:8
... |   +-- 8:16
... +-- 1:2
plain:
[8:16 4:8 2:4 1:2]

func New

func New[K comparable, V any](cmp CompareFunc[K]) *RBTree[K, V]

New creates a RBTree with compare function

func (*RBTree[K, V]) Clear

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

Clear clears the container

func (*RBTree[K, V]) Erase

func (tree *RBTree[K, V]) Erase(iter Iterator[K, V]) bool

Erase deletes the node, false returned if the node not found.

func (*RBTree[K, V]) Find

func (tree *RBTree[K, V]) Find(key K) Iterator[K, V]

Find finds node by the key, nil returned if the key not found.

func (*RBTree[K, V]) First

func (tree *RBTree[K, V]) First() Iterator[K, V]

First returns the first node.

usage:

iter := tree.First()
for iter != nil {
	// hint: do something here using iter
	// hint: iter.Key(), iter.Value(), iter.SetValue(newValue)
	iter = iter.Next()
}

func (*RBTree[K, V]) Format

func (tree *RBTree[K, V]) Format(formatter container.TreeFormatter) string

Format formats the tree

func (*RBTree[K, V]) Insert

func (tree *RBTree[K, V]) Insert(key K, value V) (Iterator[K, V], bool)

Insert inserts a key-value pair, inserted node and true returned if the key not found, otherwise, existed node and false returned.

func (*RBTree[K, V]) Last

func (tree *RBTree[K, V]) Last() Iterator[K, V]

Last returns the first node.

usage:

iter := tree.Last()
for iter != nil {
	// hint: do something here using iter
	// hint: iter.Key(), iter.Value(), iter.SetValue(newValue)
	iter = iter.Prev()
}

func (RBTree[K, V]) Len

func (tree RBTree[K, V]) Len() int

Len returns the number of elements

func (*RBTree[K, V]) MarshalTree

func (tree *RBTree[K, V]) MarshalTree(prefix string) string

MarshalTree returns a pretty output as a tree

func (*RBTree[K, V]) Remove

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

Remove removes the key, false returned if the key not found.

func (*RBTree[K, V]) String

func (tree *RBTree[K, V]) String() string

String returns content of the tree as a plain string