-
Notifications
You must be signed in to change notification settings - Fork 8
An yet-another red-black tree implementation, with a C++ STL-like API.
License
yasushi-saito/rbtree
Folders and files
Name | Name | Last commit message | Last commit date | |
---|---|---|---|---|
Repository files navigation
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
About
An yet-another red-black tree implementation, with a C++ STL-like API.
Resources
License
Stars
Watchers
Forks
Releases
No releases published
Packages 0
No packages published