README
¶
// rbts: serialized red-black tree
// Greenpack serialization code has been
// added to this tree, and Item must
// implement msgp.Serz now.
// original docs:
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() 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
- func (iter Iterator) Tree() *Tree
- type Tree
- func (r *Tree) AddCtor(typename string, ctor func() interface{})
- func (z *Tree) DecodeMsg(dc *msgp.Reader) (err error)
- func (root *Tree) DeleteWithIterator(iter Iterator)
- func (root *Tree) DeleteWithKey(key Item) bool
- func (root *Tree) Dump()
- func (root *Tree) DumpAsString() string
- func (z *Tree) EncodeMsg(en *msgp.Writer) (err error)
- 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 (r *Tree) KnownTypes() string
- func (root *Tree) Len() int
- func (root *Tree) Limit() Iterator
- func (z *Tree) MarshalMsg(b []byte) (o []byte, err error)
- func (root *Tree) Max() Iterator
- func (root *Tree) Min() Iterator
- func (z *Tree) Msgsize() (s int)
- func (root *Tree) NegativeLimit() Iterator
- func (r *Tree) NewValueAsInterface(zid int64, typename string) interface{}
- func (s *Tree) PostLoadHook()
- func (s *Tree) PreSaveHook()
- func (s *Tree) Reset()
- func (z *Tree) UnmarshalMsg(bts []byte) (o []byte, err error)
- func (z *Tree) UnmarshalMsgWithCfg(bts []byte, cfg *msgp.RuntimeConfig) (o []byte, err error)
- func (tr *Tree) Walk(n *node, indent int, lab string)
- type TreeSerz
- func (z *TreeSerz) DecodeMsg(dc *msgp.Reader) (err error)
- func (z *TreeSerz) EncodeMsg(en *msgp.Writer) (err error)
- func (z *TreeSerz) MarshalMsg(b []byte) (o []byte, err error)
- func (z *TreeSerz) Msgsize() (s int)
- func (z *TreeSerz) UnmarshalMsg(bts []byte) (o []byte, err error)
- func (z *TreeSerz) UnmarshalMsgWithCfg(bts []byte, cfg *msgp.RuntimeConfig) (o []byte, err error)
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) 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 {
Serz *TreeSerz `zid:"0"`
// contains filtered or unexported fields
}
func (*Tree) DecodeMsg ¶
DecodeMsg implements msgp.Decodable We treat empty fields as if we read a Nil from the wire.
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. Else return true.
func (*Tree) KnownTypes ¶
func (*Tree) MarshalMsg ¶
MarshalMsg implements msgp.Marshaler
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) Msgsize ¶
Msgsize returns an upper bound estimate of the number of bytes occupied by the serialized message
func (*Tree) NegativeLimit ¶
Create an iterator that points before the minimum item in the tree
func (*Tree) NewValueAsInterface ¶
func (*Tree) PostLoadHook ¶
func (s *Tree) PostLoadHook()
func (*Tree) PreSaveHook ¶
func (s *Tree) PreSaveHook()
func (*Tree) UnmarshalMsg ¶
UnmarshalMsg implements msgp.Unmarshaler
func (*Tree) UnmarshalMsgWithCfg ¶
type TreeSerz ¶
type TreeSerz struct {
Elslice []Item `msg:",iface" zid:"0"`
}
func (*TreeSerz) DecodeMsg ¶
DecodeMsg implements msgp.Decodable We treat empty fields as if we read a Nil from the wire.
func (*TreeSerz) MarshalMsg ¶
MarshalMsg implements msgp.Marshaler
func (*TreeSerz) Msgsize ¶
Msgsize returns an upper bound estimate of the number of bytes occupied by the serialized message
func (*TreeSerz) UnmarshalMsg ¶
UnmarshalMsg implements msgp.Unmarshaler
Source Files