Documentation ¶
Overview ¶
Example (Simple_usage) ¶
// build a new SimpleTree and insert 3 integers in it st := NewSimpleTree().Insert(Int(17), Int(66), Int(42)) // print 42 fmt.Println(st.Ascend(Int(42))) // print <nil> fmt.Println(st.Ascend(Int(43))) // print [42 17 66] fmt.Println(st.Flatten()) // rebalance the tree st.Rebalance() // print [17 66 42] fmt.Println(st.Flatten()) // build a new FreeTree using the data from the SimpleTree ft, err := NewFreeTree(st) if err != nil { log.Fatal(err) } // delete the SimpleTree and clear the garbage st = st.DeleteGC() // print 42 fmt.Println(ft.Ascend(Int(42))) // print <nil> fmt.Println(ft.Ascend(Int(43))) // print [17 66 42] fmt.Println(ft.Flatten()) // delete the FreeTree ft.Delete()
Output: 42 <nil> [42 17 66] [17 66 42] 42 <nil> [17 66 42]
Index ¶
- type Comparable
- type ComparableArray
- type FreeTree
- type SimpleTree
- func (st SimpleTree) Ascend(pivot Comparable) Comparable
- func (st *SimpleTree) Delete() *SimpleTree
- func (st *SimpleTree) DeleteGC() *SimpleTree
- func (st SimpleTree) Flatten() ComparableArray
- func (st *SimpleTree) Insert(cs ...Comparable) *SimpleTree
- func (st *SimpleTree) InsertArray(ca ComparableArray) *SimpleTree
- func (st *SimpleTree) Rebalance() *SimpleTree
- func (st *SimpleTree) RebalanceGC() *SimpleTree
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Comparable ¶
type Comparable interface { // Less returns true if `c1` < `c2` Less(c2 Comparable) bool }
Comparable exposes a single Less method.
type ComparableArray ¶
type ComparableArray []Comparable
ComparableArray represents a sortable array of Comparables.
func (ComparableArray) Len ¶
func (ca ComparableArray) Len() int
Len returns the length of the array.
func (ComparableArray) Less ¶
func (ca ComparableArray) Less(i, j int) bool
Less returns true if `ca[i]` < `ca[j]`.
func (ComparableArray) Swap ¶
func (ca ComparableArray) Swap(i, j int)
Swap swaps the values of `ca[i]` and `ca[j]`.
type FreeTree ¶
type FreeTree struct {
// contains filtered or unexported fields
}
FreeTree implements a binary search tree with zero GC overhead.
func NewFreeTree ¶
func NewFreeTree(st *SimpleTree) (*FreeTree, error)
NewFreeTree returns a new FreeTree using the data from a supplied SimpleTree.
func (FreeTree) Ascend ¶
func (ft FreeTree) Ascend(pivot Comparable) Comparable
Ascend returns the first element in the tree that is == `pivot`.
func (FreeTree) Flatten ¶
func (ft FreeTree) Flatten() ComparableArray
Flatten returns the content of the tree as a ComparableArray.
type SimpleTree ¶
type SimpleTree struct {
// contains filtered or unexported fields
}
SimpleTree implements a simple binary search tree.
func (SimpleTree) Ascend ¶
func (st SimpleTree) Ascend(pivot Comparable) Comparable
Ascend returns the first element in the tree that is == `pivot`.
func (*SimpleTree) Delete ¶
func (st *SimpleTree) Delete() *SimpleTree
Delete sets all the pointers in the tree to nil.
I strongly suggest running the garbage collector and scavenger once it's done.
runtime.GC() debug.FreeOSMemory()
Alternatively, you can use DeleteGC().
func (*SimpleTree) DeleteGC ¶
func (st *SimpleTree) DeleteGC() *SimpleTree
DeleteGC sets all the pointers of the tree to nil and runs the garbage collector.
func (SimpleTree) Flatten ¶
func (st SimpleTree) Flatten() ComparableArray
Flatten returns the content of the tree as a ComparableArray.
func (*SimpleTree) Insert ¶
func (st *SimpleTree) Insert(cs ...Comparable) *SimpleTree
Insert inserts the given Comparables in the tree. It does not rebalance the tree, use Rebalance() for that.
If the tree is currently empty and the passed-in Comparable are already sorted in increasing order, the tree will be perfectly balanced. This means you don't have to Rebalance() the tree if you've inserted all your pre-sorted data in one Insert() call.
func (*SimpleTree) InsertArray ¶
func (st *SimpleTree) InsertArray(ca ComparableArray) *SimpleTree
InsertArray is a helper to use Insert() with a ComparableArray.
func (*SimpleTree) Rebalance ¶
func (st *SimpleTree) Rebalance() *SimpleTree
Rebalance rebalances the tree to guarantee O(log(n)) search complexity.
Rebalancing is implemented as straightforwardly as possible: it's dumb. I strongly suggest running the garbage collector and scavenger once it's done.
runtime.GC() debug.FreeOSMemory()
Alternatively, you can use RebalanceGC().
func (*SimpleTree) RebalanceGC ¶
func (st *SimpleTree) RebalanceGC() *SimpleTree
RebalanceGC rebalances the tree and runs the garbage collector.