Documentation
¶
Overview ¶
Implements Left-Leaning Red Black trees. Structure is not thread safe.
Index ¶
- Constants
- type LLRBMode
- type Operation
- type Tree
- func (t *Tree) Ceil(key compare.Comparable) (compare.Comparable, interface{})
- func (t *Tree) Clear()
- func (t *Tree) Delete(key compare.Comparable)
- func (t *Tree) DeleteMax()
- func (t *Tree) DeleteMin()
- func (t *Tree) Do(fn Operation) bool
- func (t *Tree) DoMatching(fn Operation, q compare.Comparable) bool
- func (t *Tree) DoRange(fn Operation, from, to compare.Comparable) bool
- func (t *Tree) DoRangeReverse(fn Operation, from, to compare.Comparable) bool
- func (t *Tree) DoReverse(fn Operation) bool
- func (t *Tree) Empty() bool
- func (t *Tree) Floor(key compare.Comparable) (compare.Comparable, interface{})
- func (t *Tree) Get(key compare.Comparable) (compare.Comparable, interface{})
- func (t *Tree) Insert(key compare.Comparable, value interface{})
- func (t *Tree) Keys() []compare.Comparable
- func (t *Tree) Len() int
- func (t *Tree) Max() (compare.Comparable, interface{})
- func (t *Tree) Min() (compare.Comparable, interface{})
- func (t *Tree) Values() []interface{}
Constants ¶
const ( LLRB234 = LLRBMode(0) LLRB23 = LLRBMode(1) )
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Operation ¶
type Operation func(key compare.Comparable, value interface{}) (done bool)
An Operation is a function that operates on a Comparable. If done is returned true, the Operation is indicating that no further work needs to be done and so the Do function should traverse no further.
type Tree ¶
type Tree struct {
// contains filtered or unexported fields
}
A Tree manages the root node of an LLRB tree. Public methods are exposed through this type.
func (*Tree) Ceil ¶
func (t *Tree) Ceil(key compare.Comparable) (compare.Comparable, interface{})
Ceil returns the smallest value equal to or greater than the query q according to q.Compare().
func (*Tree) Delete ¶
func (t *Tree) Delete(key compare.Comparable)
func (*Tree) Do ¶
Do performs fn on all values stored in the tree. A boolean is returned indicating whether the Do traversal was interrupted by an Operation returning true. If fn alters stored values' sort relationships, future tree operation behaviors are undefined.
func (*Tree) DoMatching ¶
func (t *Tree) DoMatching(fn Operation, q compare.Comparable) bool
DoMatch performs fn on all values stored in the tree that match q according to Compare, with q.Compare() used to guide tree traversal, so DoMatching() will out perform Do() with a called conditional function if the condition is based on sort order, but can not be reliably used if the condition is independent of sort order. A boolean is returned indicating whether the Do traversal was interrupted by an Operation returning true. If fn alters stored values' sort relationships, future tree operation behaviors are undefined.
func (*Tree) DoRange ¶
func (t *Tree) DoRange(fn Operation, from, to compare.Comparable) bool
DoRange performs fn on all values stored in the tree over the interval [from, to) from left to right. If to is less than from DoRange will panic. A boolean is returned indicating whether the Do traversal was interrupted by an Operation returning true. If fn alters stored values' sort relationships future tree operation behaviors are undefined.
func (*Tree) DoRangeReverse ¶
func (t *Tree) DoRangeReverse(fn Operation, from, to compare.Comparable) bool
DoRangeReverse performs fn on all values stored in the tree over the interval (to, from] from right to left. If from is less than to DoRange will panic. A boolean is returned indicating whether the Do traversal was interrupted by an Operation returning true. If fn alters stored values' sort relationships future tree operation behaviors are undefined.
func (*Tree) DoReverse ¶
DoReverse performs fn on all values stored in the tree, but in reverse of sort order. A boolean is returned indicating whether the Do traversal was interrupted by an Operation returning true. If fn alters stored values' sort relationships, future tree operation behaviors are undefined.
func (*Tree) Floor ¶
func (t *Tree) Floor(key compare.Comparable) (compare.Comparable, interface{})
Floor returns the greatest value equal to or less than the query key according to key.Compare().
func (*Tree) Get ¶
func (t *Tree) Get(key compare.Comparable) (compare.Comparable, interface{})
Get returns the first match of q in the Tree. If insertion without replacement is used, this is probably not what you want.
func (*Tree) Insert ¶
func (t *Tree) Insert(key compare.Comparable, value interface{})
func (*Tree) Keys ¶
func (t *Tree) Keys() []compare.Comparable
func (*Tree) Max ¶
func (t *Tree) Max() (compare.Comparable, interface{})
func (*Tree) Min ¶
func (t *Tree) Min() (compare.Comparable, interface{})
Source Files