rbtree

Documentation

Index

• type CompareFunc
• type Iterator
• type K
• type RBTree
  • func New(cmp CompareFunc) *RBTree
  • func (tree *RBTree) Clear()
  • func (tree *RBTree) Erase(iter Iterator) bool
  • func (tree *RBTree) Find(key K) Iterator
  • func (tree *RBTree) First() Iterator
  • func (tree *RBTree) Format(formatter container.TreeFormatter) string
  • func (tree *RBTree) Insert(key K, value V) (Iterator, bool)
  • func (tree *RBTree) Last() Iterator
  • func (tree RBTree) Len() int
  • func (tree *RBTree) MarshalTree(prefix string) string
  • func (tree *RBTree) Remove(key K) bool
  • func (tree *RBTree) String() string
• type V

Examples

• RBTree

Types

type CompareFunc

type CompareFunc func(k1, k2 K) bool

CompareFunc represents comparation between key

type Iterator

type Iterator interface {
	// Prev returns previous iterator
	Prev() Iterator
	// Next returns next node iterator
	Next() Iterator
	// 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 K

type K = int

K represents type of the key

type RBTree

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

RBTree RBComment

Example

tree := New(func(k1, k2 K) bool { return k1 > k2 })
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())

func New

func New(cmp CompareFunc) *RBTree

New creates a RBTree with compare function

func (*RBTree) Clear

func (tree *RBTree) Clear()

Clear clears the container

func (*RBTree) Erase

func (tree *RBTree) Erase(iter Iterator) bool

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

func (*RBTree) Find

func (tree *RBTree) Find(key K) Iterator

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

func (*RBTree) First

func (tree *RBTree) First() Iterator

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

func (tree *RBTree) Format(formatter container.TreeFormatter) string

Format formats the tree

func (*RBTree) Insert

func (tree *RBTree) Insert(key K, value V) (Iterator, 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) Last

func (tree *RBTree) Last() Iterator

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

func (tree RBTree) Len() int

Len returns the number of elements

func (*RBTree) MarshalTree

func (tree *RBTree) MarshalTree(prefix string) string

MarshalTree returns a pretty output as a tree

func (*RBTree) Remove

func (tree *RBTree) Remove(key K) bool

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

func (*RBTree) String

func (tree *RBTree) String() string

String returns content of the tree as a plain string

type V

type V = int

V represents type of the value