Documentation ¶
Index ¶
- Constants
- type BTreeG
- func (t *BTreeG[T]) Ascend(iterator ItemIteratorG[T])
- func (t *BTreeG[T]) AscendGreaterOrEqual(pivot T, iterator ItemIteratorG[T])
- func (t *BTreeG[T]) AscendLessThan(pivot T, iterator ItemIteratorG[T])
- func (t *BTreeG[T]) AscendRange(greaterOrEqual, lessThan T, iterator ItemIteratorG[T])
- func (t *BTreeG[T]) Clear(addNodesToFreelist bool)
- func (t *BTreeG[T]) Clone() (t2 *BTreeG[T])
- func (t *BTreeG[T]) Delete(item T) (T, bool)
- func (t *BTreeG[T]) DeleteMax() (T, bool)
- func (t *BTreeG[T]) DeleteMin() (T, bool)
- func (t *BTreeG[T]) Descend(iterator ItemIteratorG[T])
- func (t *BTreeG[T]) DescendGreaterThan(pivot T, iterator ItemIteratorG[T])
- func (t *BTreeG[T]) DescendLessOrEqual(pivot T, iterator ItemIteratorG[T])
- func (t *BTreeG[T]) DescendRange(lessOrEqual, greaterThan T, iterator ItemIteratorG[T])
- func (t *BTreeG[T]) Get(key T) (_ T, _ bool)
- func (t *BTreeG[T]) GetAt(k int) T
- func (t *BTreeG[T]) GetWithIndex(key T) (_ T, _ int)
- func (t *BTreeG[T]) Has(key T) bool
- func (t *BTreeG[T]) Len() int
- func (t *BTreeG[T]) Max() (_ T, _ bool)
- func (t *BTreeG[T]) Min() (_ T, _ bool)
- func (t *BTreeG[T]) ReplaceOrInsert(item T) (_ T, _ bool)
- type FreeListG
- type Int
- type Item
- type ItemIteratorG
Examples ¶
Constants ¶
const (
// DefaultFreeListSize is the default size of free list.
DefaultFreeListSize = 32
)
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type BTreeG ¶
type BTreeG[T Item[T]] struct { // contains filtered or unexported fields }
BTreeG is a generic implementation of a B-Tree.
BTreeG stores items of type T 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.
Example ¶
tr := NewG[Int](*btreeDegree) for i := Int(0); i < 10; i++ { tr.ReplaceOrInsert(i) } fmt.Println("len: ", tr.Len()) v, ok := tr.Get(3) fmt.Println("get3: ", v, ok) v, ok = tr.Get(100) fmt.Println("get100: ", v, ok) v, ok = tr.Delete(4) fmt.Println("del4: ", v, ok) v, ok = tr.Delete(100) fmt.Println("del100: ", v, ok) v, ok = tr.ReplaceOrInsert(5) fmt.Println("replace5: ", v, ok) v, ok = tr.ReplaceOrInsert(100) fmt.Println("replace100:", v, ok) v, ok = tr.Min() fmt.Println("min: ", v, ok) v, ok = tr.DeleteMin() fmt.Println("delmin: ", v, ok) v, ok = tr.Max() fmt.Println("max: ", v, ok) v, ok = tr.DeleteMax() fmt.Println("delmax: ", v, ok) fmt.Println("len: ", tr.Len())
Output: len: 10 get3: 3 true get100: 0 false del4: 4 true del100: 0 false replace5: 5 true replace100: 0 false min: 0 true delmin: 0 true max: 100 true delmax: 100 true len: 8
func NewG ¶
NewG creates a new B-Tree with the given degree.
NewG(2), for example, will create a 2-3-4 tree (each node contains 1-3 items and 2-4 children).
The passed-in LessFunc determines how objects of type T are ordered.
func NewWithFreeListG ¶
NewWithFreeListG creates a new B-Tree that uses the given node free list.
func (*BTreeG[T]) Ascend ¶
func (t *BTreeG[T]) Ascend(iterator ItemIteratorG[T])
Ascend calls the iterator for every value in the tree within the range [first, last], until iterator returns false.
func (*BTreeG[T]) AscendGreaterOrEqual ¶
func (t *BTreeG[T]) AscendGreaterOrEqual(pivot T, iterator ItemIteratorG[T])
AscendGreaterOrEqual calls the iterator for every value in the tree within the range [pivot, last], until iterator returns false.
func (*BTreeG[T]) AscendLessThan ¶
func (t *BTreeG[T]) AscendLessThan(pivot T, iterator ItemIteratorG[T])
AscendLessThan calls the iterator for every value in the tree within the range [first, pivot), until iterator returns false.
func (*BTreeG[T]) AscendRange ¶
func (t *BTreeG[T]) AscendRange(greaterOrEqual, lessThan T, iterator ItemIteratorG[T])
AscendRange calls the iterator for every value in the tree within the range [greaterOrEqual, lessThan), until iterator returns false.
func (*BTreeG[T]) Clear ¶
Clear removes all items from the btree. If addNodesToFreelist is true, t's nodes are added to its freelist as part of this call, until the freelist is full. Otherwise, the root node is simply dereferenced and the subtree left to Go's normal GC processes.
This can be much faster than calling Delete on all elements, because that requires finding/removing each element in the tree and updating the tree accordingly. It also is somewhat faster than creating a new tree to replace the old one, because nodes from the old tree are reclaimed into the freelist for use by the new one, instead of being lost to the garbage collector.
This call takes:
O(1): when addNodesToFreelist is false, this is a single operation. O(1): when the freelist is already full, it breaks out immediately O(freelist size): when the freelist is empty and the nodes are all owned by this tree, nodes are added to the freelist until full. O(tree size): when all nodes are owned by another tree, all nodes are iterated over looking for nodes to add to the freelist, and due to ownership, none are.
func (*BTreeG[T]) Clone ¶
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 (*BTreeG[T]) Delete ¶
Delete removes an item equal to the passed in item from the tree, returning it. If no such item exists, returns (zeroValue, false).
func (*BTreeG[T]) DeleteMax ¶
DeleteMax removes the largest item in the tree and returns it. If no such item exists, returns (zeroValue, false).
func (*BTreeG[T]) DeleteMin ¶
DeleteMin removes the smallest item in the tree and returns it. If no such item exists, returns (zeroValue, false).
func (*BTreeG[T]) Descend ¶
func (t *BTreeG[T]) Descend(iterator ItemIteratorG[T])
Descend calls the iterator for every value in the tree within the range [last, first], until iterator returns false.
func (*BTreeG[T]) DescendGreaterThan ¶
func (t *BTreeG[T]) DescendGreaterThan(pivot T, iterator ItemIteratorG[T])
DescendGreaterThan calls the iterator for every value in the tree within the range [last, pivot), until iterator returns false.
func (*BTreeG[T]) DescendLessOrEqual ¶
func (t *BTreeG[T]) DescendLessOrEqual(pivot T, iterator ItemIteratorG[T])
DescendLessOrEqual calls the iterator for every value in the tree within the range [pivot, first], until iterator returns false.
func (*BTreeG[T]) DescendRange ¶
func (t *BTreeG[T]) DescendRange(lessOrEqual, greaterThan T, iterator ItemIteratorG[T])
DescendRange calls the iterator for every value in the tree within the range [lessOrEqual, greaterThan), until iterator returns false.
func (*BTreeG[T]) Get ¶
Get looks for the key item in the tree, returning it. It returns (zeroValue, false) if unable to find that item.
func (*BTreeG[T]) GetAt ¶
GetAt returns the item with index k. If k < 0 or k >= t.Len(), returns nil.
func (*BTreeG[T]) GetWithIndex ¶
GetWithIndex gets the key and its index. If the key is not in the tree, the the index is the number of items < key.
func (*BTreeG[T]) Max ¶
Max returns the largest item in the tree, or (zeroValue, false) if the tree is empty.
func (*BTreeG[T]) Min ¶
Min returns the smallest item in the tree, or (zeroValue, false) if the tree is empty.
func (*BTreeG[T]) ReplaceOrInsert ¶
ReplaceOrInsert adds the given item to the tree. If an item in the tree already equals the given one, it is removed from the tree and returned, and the second return value is true. Otherwise, (zeroValue, false)
nil cannot be added to the tree (will panic).
type FreeListG ¶
type FreeListG[T Item[T]] struct { // contains filtered or unexported fields }
FreeListG represents a free list of btree nodes. By default each BTree has its own FreeList, but multiple BTrees can share the same FreeList, in particular when they're created with Clone. Two Btrees using the same freelist are safe for concurrent write access.
func NewFreeListG ¶
NewFreeListG creates a new free list. size is the maximum size of the returned free list.
type Item ¶
type Item[T any] interface { // Less tests whether the current item is less than the given argument. // // This must provide a strict weak ordering. // If !a.Less(b) && !b.Less(a), we treat this to mean a == b (i.e. we can only // hold one of either a or b in the tree). Less(than T) bool }
Item represents a single object in the tree.
type ItemIteratorG ¶
ItemIteratorG allows callers of Ascend* to iterate in-order over portions of the tree. When this function returns false, iteration will stop and the associated Ascend* function will immediately return.