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 (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) (added bool)
- func (root *Tree) InsertGetIt(item Item) (added bool, it Iterator)
- 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)
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type CompareFunc ¶
CompareFunc returns 0 if a==b, <0 if a<b, >0 if a>b.
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) Item ¶
func (iter Iterator) Item() interface{}
Return the current element.
REQUIRES: !iter.Limit() && !iter.NegativeLimit()
func (Iterator) NegativeLimit ¶
Check if the iterator points before the minumum element in the tree
func (Iterator) Next ¶
Create a new iterator that points to the successor of the current element.
REQUIRES: !iter.Limit()
type Tree ¶
type Tree struct {
// contains filtered or unexported fields
}
func (*Tree) DeleteWithIterator ¶
Delete the current item.
REQUIRES: !iter.Limit() && !iter.NegativeLimit()
func (*Tree) DeleteWithKey ¶
Delete an item with the given key. Return true iff the item was found.
func (*Tree) DumpAsString ¶
func (*Tree) FindGE ¶
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 ¶
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 ¶
A convenience function for finding an element equal to key. Return nil if not found.
func (*Tree) Insert ¶
Insert an item. If the item is already in the tree, do nothing and return false.
func (*Tree) InsertGetIt ¶
InsertGetIt tries to add an item to the tree and return an Iterator pointing to it. If the item is already in the tree, do nothing and return false (it.root and it.node will be nil). Else return true, and Iterator 'it' refers to the just inserted element.
func (*Tree) Max ¶
Create an iterator that points at the maximum item in the tree
If the tree is empty, return NegativeLimit()
func (*Tree) Min ¶
Create an iterator that points to the minimum item in the tree If the tree is empty, return Limit()
func (*Tree) NegativeLimit ¶
Create an iterator that points before the minimum item in the tree