BTree is an implementation of a B-Tree.
BTree stores item instances in an ordered structure, allowing easy insertion, removal, and iteration.
Write operations are not safe for concurrent mutation by multiple goroutines, but Read operations are.
type BTree struct {
// contains filtered or unexported fields
}
func New(degree int, less func(interface{}, interface{}) bool) *BTree
New creates a new B-Tree with the given degree and comparison function.
New(2, less), for example, will create a 2-3-4 tree (each node contains 1-3 items and 2-4 children).
The less function tests whether the current item is less than the given argument. It must provide a strict weak ordering. If !less(a, b) && !less(b, a), we treat this to mean a == b (i.e. the tree can hold only one of a or b).
func (t *BTree) After(k Key) *Iterator
After returns an iterator positioned just after k. After the first call to Next, the Iterator will be at k, or at the key just less than k if k is not in the tree. Subsequent calls to Next will traverse the tree's items in descending order.
func (t *BTree) AfterIndex(i int) *Iterator
AfterIndex returns an iterator positioned just after the item with the given index. The iterator will traverse the tree's items in descending order. If i is not in the range [0, tr.Len()], AfterIndex panics. Note that it is not an error to provide an index of tr.Len().
func (t *BTree) At(i int) (Key, Value)
At returns the key and value at index i. The minimum item has index 0. If i is outside the range [0, t.Len()), At panics.
func (t *BTree) Before(k Key) *Iterator
Before returns an iterator positioned just before k. After the first call to Next, the Iterator will be at k, or at the key just greater than k if k is not in the tree. Subsequent calls to Next will traverse the tree's items in ascending order.
func (t *BTree) BeforeIndex(i int) *Iterator
BeforeIndex returns an iterator positioned just before the item with the given index. The iterator will traverse the tree's items in ascending order. If i is not in the range [0, tr.Len()], BeforeIndex panics. Note that it is not an error to provide an index of tr.Len().
func (t *BTree) Clone() *BTree
Clone clones the btree, lazily. Clone should not be called concurrently, but the original tree (t) and the new tree (t2) can be used concurrently once the Clone call completes.
The internal tree structure of b is marked read-only and shared between t and t2. Writes to both t and t2 use copy-on-write logic, creating new nodes whenever one of b's original nodes would have been modified. Read operations should have no performance degredation. Write operations for both t and t2 will initially experience minor slow-downs caused by additional allocs and copies due to the aforementioned copy-on-write logic, but should converge to the original performance characteristics of the original tree.
func (t *BTree) Delete(k Key) (Value, bool)
Delete removes the item with the given key, returning its value. The second return value reports whether the key was found.
func (t *BTree) DeleteMax() (Key, Value)
DeleteMax removes the largest item in the tree and returns its key and value. If the tree is empty, it returns zero values.
func (t *BTree) DeleteMin() (Key, Value)
DeleteMin removes the smallest item in the tree and returns its key and value. If the tree is empty, it returns zero values.
func (t *BTree) Get(k Key) Value
Get returns the value for the given key in the tree, or the zero value if the key is not in the tree.
To distinguish a zero value from a key that is not present, use GetWithIndex.
func (t *BTree) GetWithIndex(k Key) (Value, int)
GetWithIndex returns the value and index for the given key in the tree, or the zero value and -1 if the key is not in the tree.
func (t *BTree) Has(k Key) bool
Has reports whether the given key is in the tree.
func (t *BTree) Len() int
Len returns the number of items currently in the tree.
func (t *BTree) Max() (Key, Value)
Max returns the largest key in the tree and its value. If the tree is empty, both return values are zero values.
func (t *BTree) Min() (Key, Value)
Min returns the smallest key in the tree and its value. If the tree is empty, it returns zero values.
func (t *BTree) Set(k Key, v Value) (old Value, present bool)
Set sets the given key to the given value in the tree. If the key is present in the tree, its value is changed and the old value is returned along with a second return value of true. If the key is not in the tree, it is added, and the second return value is false.
func (t *BTree) SetWithIndex(k Key, v Value) (old Value, present bool, index int)
SetWithIndex sets the given key to the given value in the tree, and returns the index at which it was inserted.
An Iterator supports traversing the items in the tree.
type Iterator struct {
Key Key
Value Value
// Index is the position of the item in the tree viewed as a sequence.
// The minimum item has index zero.
Index int
// contains filtered or unexported fields
}
func (it *Iterator) Next() bool
Next advances the Iterator to the next item in the tree. If Next returns true, the Iterator's Key, Value and Index fields refer to the next item. If Next returns false, there are no more items and the values of Key, Value and Index are undefined.
If the tree is modified during iteration, the behavior is undefined.
Key represents a key into the tree.
type Key interface{}
Value represents a value in the tree.
type Value interface{}