rbtree

Documentation

Index

• type Item
• type Iterator
  • func (iter Iterator) Equal(other Iterator) bool
  • func (iter Iterator) Item() *Item
  • func (iter Iterator) Limit() bool
  • func (iter Iterator) Max() bool
  • func (iter Iterator) Min() bool
  • func (iter Iterator) NegativeLimit() bool
  • func (iter Iterator) Next() Iterator
  • func (iter Iterator) Prev() Iterator
• type RBTree
  • func (tree *RBTree) Clone() *RBTree
  • func (tree *RBTree) DeleteWithIterator(iter Iterator)
  • func (tree *RBTree) DeleteWithKey(key int) bool
  • func (tree *RBTree) FindGE(key int) Iterator
  • func (tree *RBTree) FindLE(key int) Iterator
  • func (tree *RBTree) Get(key int) *int
  • func (tree *RBTree) Insert(item Item) (bool, Iterator)
  • func (tree *RBTree) Len() int
  • func (tree *RBTree) Limit() Iterator
  • func (tree *RBTree) Max() Iterator
  • func (tree *RBTree) Min() Iterator
  • func (tree *RBTree) NegativeLimit() Iterator

Types

type Item

type Item struct {
	Key   int
	Value int
}

Item is the object stored in each tree node.

type Iterator

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

Iterator allows scanning tree elements in sort order.

Iterator invalidation rule is the same as C++ std::map<>'s. That is, if you delete the element that an iterator points to, the iterator becomes invalid. For other operation types, the iterator remains valid.

func (Iterator) Equal

func (iter Iterator) Equal(other Iterator) bool

Equal checks for the underlying nodes equality.

func (Iterator) Item

func (iter Iterator) Item() *Item

Item returns the current element. Allows mutating the node (key to be changed with care!).

REQUIRES: !iter.Limit() && !iter.NegativeLimit()

func (Iterator) Limit

func (iter Iterator) Limit() bool

Limit checks if the iterator points beyond the max element in the tree.

func (Iterator) Max

func (iter Iterator) Max() bool

Max checks if the iterator points to the maximum element in the tree.

func (Iterator) Min

func (iter Iterator) Min() bool

Min checks if the iterator points to the minimum element in the tree.

func (Iterator) NegativeLimit

func (iter Iterator) NegativeLimit() bool

NegativeLimit checks if the iterator points before the minimum element in the tree.

func (Iterator) Next

func (iter Iterator) Next() Iterator

Next creates a new iterator that points to the successor of the current element.

REQUIRES: !iter.Limit()

func (Iterator) Prev

func (iter Iterator) Prev() Iterator

Prev creates a new iterator that points to the predecessor of the current node.

REQUIRES: !iter.NegativeLimit()

type RBTree

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

RBTree created by Yaz Saito on 06/10/12.

A red-black tree with an API similar to C++ STL's.

The implementation is inspired (read: stolen) from: http://en.literateprograms.org/Red-black_tree_(C)#chunk use:private function prototypes.

The code was optimized for the simple integer types of Key and Value.

func (*RBTree) Clone

func (tree *RBTree) Clone() *RBTree

Clone performs a deep copy of the tree.

func (*RBTree) DeleteWithIterator

func (tree *RBTree) DeleteWithIterator(iter Iterator)

DeleteWithIterator deletes the current item.

REQUIRES: !iter.Limit() && !iter.NegativeLimit()

func (*RBTree) DeleteWithKey

func (tree *RBTree) DeleteWithKey(key int) bool

DeleteWithKey deletes an item with the given Key. Returns true iff the item was found.

func (*RBTree) FindGE

func (tree *RBTree) FindGE(key int) Iterator

FindGE finds the smallest element N such that N >= Key, and returns the iterator pointing to the element. If no such element is found, returns tree.Limit().

func (*RBTree) FindLE

func (tree *RBTree) FindLE(key int) Iterator

FindLE finds the largest element N such that N <= Key, and returns the iterator pointing to the element. If no such element is found, returns iter.NegativeLimit().

func (*RBTree) Get

func (tree *RBTree) Get(key int) *int

Get is a convenience function for finding an element equal to Key. Returns nil if not found.

func (*RBTree) Insert

func (tree *RBTree) Insert(item Item) (bool, Iterator)

Insert an item. If the item is already in the tree, do nothing and return false. Else return true.

func (*RBTree) Len

func (tree *RBTree) Len() int

Len returns the number of elements in the tree.

func (*RBTree) Limit

func (tree *RBTree) Limit() Iterator

Limit creates an iterator that points beyond the maximum item in the tree.

func (*RBTree) Max

func (tree *RBTree) Max() Iterator

Max creates an iterator that points at the maximum item in the tree.

If the tree is empty, returns NegativeLimit().

func (*RBTree) Min

func (tree *RBTree) Min() Iterator

Min creates an iterator that points to the minimum item in the tree. If the tree is empty, returns Limit()

func (*RBTree) NegativeLimit

func (tree *RBTree) NegativeLimit() Iterator

NegativeLimit creates an iterator that points before the minimum item in the tree.