rbtree

README

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

INSTALLATION
    go get github.com/yasushi-saito/rbtree

EXAMPLE

        More examples can be found in rbtree_test.go

        import "github.com/yasushi-saito/rbtree"

	type MyItem struct {
		key   int
		value string
	}

	tree := rbtree.NewTree(func(a, b Item) int { return a.(MyItem).key - b.(MyItem).key })
	tree.Insert(MyItem{10, "value10"})
	tree.Insert(MyItem{12, "value12"})

	fmt.Println("Get(10) ->", tree.Get(MyItem{10, ""}))
	fmt.Println("Get(11) ->", tree.Get(MyItem{11, ""}))

	// Find an element >= 11
	iter := tree.FindGE(MyItem{11, ""})
	fmt.Println("FindGE(11) ->", iter.Item())

	// Find an element >= 13
	iter = tree.FindGE(MyItem{13, ""})
	if !iter.End() { panic("There should be no element >= 13") }

	// Output:
	// Get(10) -> {10 value10}
	// Get(11) -> <nil>
	// FindGE(11) -> {12 value12}

TYPES

type CompareFunc func(a, b Item) int
    CompareFunc returns 0 if a==b, <0 if a<b, >0 if a>b.

type Item interface{}
    Item is the object stored in each tree node.

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 (iter Iterator) Equal(iter2 Iterator) bool

func (iter Iterator) Item() interface{}
    Return the current element.

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

func (iter Iterator) Limit() bool
    Check if the iterator points beyond the max element in the tree

func (iter Iterator) Max() bool
    Check if the iterator points to the maximum element in the tree

func (iter Iterator) Min() bool
    Check if the iterator points to the minimum element in the tree

func (iter Iterator) NegativeLimit() bool
    Check if the iterator points before the minumum element in the tree

func (iter Iterator) Next() Iterator
    Create a new iterator that points to the successor of the current
    element.

    REQUIRES: !iter.Limit()

func (iter Iterator) Prev() Iterator
    Create a new iterator that points to the predecessor of the current
    node.

    REQUIRES: !iter.NegativeLimit()

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

func NewTree(compare CompareFunc) *Tree
    Create a new empty tree.

func (root *Tree) DeleteWithIterator(iter Iterator)
    Delete the current item.

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

func (root *Tree) DeleteWithKey(key Item) bool
    Delete an item with the given key. Return true iff the item was found.

func (root *Tree) FindGE(key Item) Iterator
    Find the smallest element N such that N >= key, and return the iterator
    pointing to the element. If no such element is found, return
    root.Limit().

func (root *Tree) FindLE(key Item) Iterator
    Find the largest element N such that N <= key, and return the iterator
    pointing to the element. If no such element is found, return
    iter.NegativeLimit().

func (root *Tree) Get(key Item) Item
    A convenience function for finding an element equal to key. Return nil
    if not found.

func (root *Tree) Insert(item Item) bool
    Insert an item. If the item is already in the tree, do nothing and
    return false. Else return true.

func (root *Tree) Len() int
    Return the number of elements in the tree.

func (root *Tree) Limit() Iterator
    Create an iterator that points beyond the maximum item in the tree

func (root *Tree) Max() Iterator
    Create an iterator that points at the maximum item in the tree

    If the tree is empty, return NegativeLimit()

func (root *Tree) Min() Iterator
    Create an iterator that points to the minimum item in the tree If the
    tree is empty, return Limit()

func (root *Tree) NegativeLimit() Iterator
    Create an iterator that points before the minimum item in the tree

Documentation

Overview

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.

Index

• type CompareFunc
• type Item
• type Iterator
  • func (iter Iterator) Equal(iter2 Iterator) bool
  • func (iter Iterator) Item() interface{}
  • 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
  • func (iter Iterator) Tree() *Tree
• type Tree
  • func NewTree(compare CompareFunc) *Tree
  • func (root *Tree) DeleteWithIterator(iter Iterator)
  • func (root *Tree) DeleteWithKey(key Item) bool
  • func (root *Tree) Dump()
  • func (root *Tree) DumpAsString() string
  • func (root *Tree) FindGE(key Item) Iterator
  • func (root *Tree) FindLE(key Item) Iterator
  • func (root *Tree) Get(key Item) Item
  • func (root *Tree) Insert(item Item) bool
  • func (root *Tree) Len() int
  • func (root *Tree) Limit() Iterator
  • func (root *Tree) Max() Iterator
  • func (root *Tree) Min() Iterator
  • func (root *Tree) NegativeLimit() Iterator
  • func (tr *Tree) Walk(n *node, indent int, lab string)

Types

type CompareFunc

type CompareFunc func(a, b Item) int

CompareFunc returns 0 if a==b, <0 if a<b, >0 if a>b.

type Item

type Item interface{}

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(iter2 Iterator) bool

func (Iterator) Item

func (iter Iterator) Item() interface{}

Return the current element.

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

func (Iterator) Limit

func (iter Iterator) Limit() bool

Check if the iterator points beyond the max element in the tree

func (Iterator) Max

func (iter Iterator) Max() bool

Check if the iterator points to the maximum element in the tree

func (Iterator) Min

func (iter Iterator) Min() bool

Check if the iterator points to the minimum element in the tree

func (Iterator) NegativeLimit

func (iter Iterator) NegativeLimit() bool

Check if the iterator points before the minumum element in the tree

func (Iterator) Next

func (iter Iterator) Next() Iterator

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

REQUIRES: !iter.Limit()

func (Iterator) Prev

func (iter Iterator) Prev() Iterator

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

REQUIRES: !iter.NegativeLimit()

func (Iterator) Tree

func (iter Iterator) Tree() *Tree

allow clients to verify iterator is from the right tree.

type Tree

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

func NewTree

func NewTree(compare CompareFunc) *Tree

Create a new empty tree.

func (*Tree) DeleteWithIterator

func (root *Tree) DeleteWithIterator(iter Iterator)

Delete the current item.

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

func (*Tree) DeleteWithKey

func (root *Tree) DeleteWithKey(key Item) bool

Delete an item with the given key. Return true iff the item was found.

func (*Tree) Dump

func (root *Tree) Dump()

func (*Tree) DumpAsString

func (root *Tree) DumpAsString() string

func (*Tree) FindGE

func (root *Tree) FindGE(key Item) Iterator

Find the smallest element N such that N >= key, and return the iterator pointing to the element. If no such element is found, return root.Limit().

func (*Tree) FindLE

func (root *Tree) FindLE(key Item) Iterator

Find the largest element N such that N <= key, and return the iterator pointing to the element. If no such element is found, return iter.NegativeLimit().

func (*Tree) Get

func (root *Tree) Get(key Item) Item

A convenience function for finding an element equal to key. Return nil if not found.

func (*Tree) Insert

func (root *Tree) Insert(item Item) bool

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

func (*Tree) Len

func (root *Tree) Len() int

Return the number of elements in the tree.

func (*Tree) Limit

func (root *Tree) Limit() Iterator

Create an iterator that points beyond the maximum item in the tree

func (*Tree) Max

func (root *Tree) Max() Iterator

Create an iterator that points at the maximum item in the tree

If the tree is empty, return NegativeLimit()

func (*Tree) Min

func (root *Tree) Min() Iterator

Create an iterator that points to the minimum item in the tree If the tree is empty, return Limit()

func (*Tree) NegativeLimit

func (root *Tree) NegativeLimit() Iterator

Create an iterator that points before the minimum item in the tree

func (*Tree) Walk

func (tr *Tree) Walk(n *node, indent int, lab string)