Documentation ¶
Index ¶
- func BytesComparator(a, b interface{}) int
- func Float32Comparator(a, b interface{}) int
- func Float64Comparator(a, b interface{}) int
- func Int16Comparator(a, b interface{}) int
- func Int32Comparator(a, b interface{}) int
- func Int64Comparator(a, b interface{}) int
- func Int8Comparator(a, b interface{}) int
- func IntComparator(a, b interface{}) int
- func StringComparator(a, b interface{}) int
- func TimeComparator(a, b interface{}) int
- func UInt16Comparator(a, b interface{}) int
- func UInt32Comparator(a, b interface{}) int
- func UInt64Comparator(a, b interface{}) int
- func UInt8Comparator(a, b interface{}) int
- func UIntComparator(a, b interface{}) int
- type Comparator
- type Handle
- func (h Handle) Delete(n *Node, key interface{}) *Node
- func (h Handle) Get(n *Node, key interface{}) (v interface{}, found bool)
- func (h Handle) GetNode(n *Node, key interface{}) (*Node, bool)
- func (h Handle) Insert(n *Node, key, val, weight interface{}) (new *Node, ok bool)
- func (h Handle) Iter(n *Node) *Iterator
- func (h Handle) Merge(left, right *Node) *Node
- func (h Handle) Pop(n *Node) (interface{}, *Node)
- func (h Handle) SetWeight(n *Node, key, weight interface{}) (new *Node, ok bool)
- func (h Handle) Split(n *Node, key interface{}) (*Node, *Node)
- func (h Handle) Upsert(n *Node, key, val, weight interface{}) (new *Node, created bool)
- func (h Handle) UpsertIf(n *Node, key, val, weight interface{}, f func(*Node) bool) (*Node, bool)
- type Iterator
- type Node
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func BytesComparator ¶
func BytesComparator(a, b interface{}) int
BytesComparator provides a basic comparison on []byte. Nil values are treated as infinite.
func Float32Comparator ¶
func Float32Comparator(a, b interface{}) int
Float32Comparator provides a basic comparison on float32. Nil values are treated as infinite.
func Float64Comparator ¶
func Float64Comparator(a, b interface{}) int
Float64Comparator provides a basic comparison on float64. Nil values are treated as infinite.
func Int16Comparator ¶
func Int16Comparator(a, b interface{}) int
Int16Comparator provides a basic comparison on int16. Nil values are treated as infinite.
func Int32Comparator ¶
func Int32Comparator(a, b interface{}) int
Int32Comparator provides a basic comparison on int32. Nil values are treated as infinite.
func Int64Comparator ¶
func Int64Comparator(a, b interface{}) int
Int64Comparator provides a basic comparison on int64. Nil values are treated as infinite.
func Int8Comparator ¶
func Int8Comparator(a, b interface{}) int
Int8Comparator provides a basic comparison on int8. Nil values are treated as infinite.
func IntComparator ¶
func IntComparator(a, b interface{}) int
IntComparator compares integers. Nil values are considered infinite.
func StringComparator ¶
func StringComparator(a, b interface{}) int
StringComparator provides a fast comparison on strings. Nil values are treated as infinite.
func TimeComparator ¶
func TimeComparator(a, b interface{}) int
TimeComparator provides a basic comparison on time.Time. Nil values are treated as infinite.
func UInt16Comparator ¶
func UInt16Comparator(a, b interface{}) int
UInt16Comparator provides a basic comparison on uint16. Nil values are treated as infinite.
func UInt32Comparator ¶
func UInt32Comparator(a, b interface{}) int
UInt32Comparator provides a basic comparison on uint32. Nil values are treated as infinite.
func UInt64Comparator ¶
func UInt64Comparator(a, b interface{}) int
UInt64Comparator provides a basic comparison on uint64. Nil values are treated as infinite.
func UInt8Comparator ¶
func UInt8Comparator(a, b interface{}) int
UInt8Comparator provides a basic comparison on uint8. Nil values are treated as infinite.
func UIntComparator ¶
func UIntComparator(a, b interface{}) int
UIntComparator provides a basic comparison on uint. Nil values are treated as infinite.
Types ¶
type Comparator ¶
type Comparator func(a, b interface{}) int
Comparator establishes ordering between two elements. It returns -1 if a < b, 0 if a == b, and 1 if a > b. Nil values are treated as -Inf.
func MaxTreap ¶
func MaxTreap(f Comparator) Comparator
MaxTreap wraps a comparator, resulting in a treap with max-heap ordering.
type Handle ¶
type Handle struct {
CompareWeights, CompareKeys Comparator
}
Handle performs purely functional transformations on a treap.
Example ¶
package main import ( "fmt" "github.com/lthibault/treap" ) func main() { // Treap operations are performed by a lightweight handle. Usually, you'll create a // single global handle and share it between goroutines. Handle's methods are thread- // safe. // // A handle is defined by it's comparison functions (type `treap.Comparator`). var handle = treap.Handle{ // CompareKeys is used to store and receive mapped entries. The comparator must be // compatible with the Go type used for keys. In this example, we'll use strings as // keys. CompareKeys: treap.StringComparator, // CompareWeights is used to maintain priority-ordering of mapped entries, providing // us with fast `Pop`, `Insert` and `SetWeight` operations. You'll usually want // to use a `treap.IntComparator` for weights, but you can use any comparison // function you require. Try it with `treap.TimeComparator`! // // Note that treaps are min-heaps by default, so `Pop` will always return the item // with the _smallest_ weight. You can easily switch to a max-heap by using // `treap.MaxTreap`, if required. CompareWeights: treap.IntComparator, } // We define an empty root node. Don't worry -- there's no initialization required! var root *treap.Node // We're going to insert each of these boxers into the treap, and observe how the // treap treap provides us with a combination of map and heap semantics. for _, boxer := range []struct { FirstName, LastName string Weight int }{{ FirstName: "Cassius", LastName: "Clay", Weight: 210, }, { FirstName: "Joe", LastName: "Frazier", Weight: 215, }, { FirstName: "Marcel", LastName: "Cerdan", Weight: 154, }, { FirstName: "Jake", LastName: "LaMotta", Weight: 160, }} { // Again, the treap is a purely-functional, persistent data structure. `Insert` // returns a _new_ heap, which replaces `root` on each iteration. // // When used in conjunction with `atomic.CompareAndSwapPointer`, it is possible // to read from a treap without ever blocking -- even in the presence of // concurrent writers! root, _ = handle.Insert(root, boxer.FirstName, boxer.LastName, boxer.Weight) } // Now that we've populated the treap, we can query it like an ordinary map. lastn, _ := handle.Get(root, "Cassius") fmt.Printf("Cassius => %s\n", lastn) // Treaps also behave like binary heaps. Let's start by peeking at the first value // in the resulting priority queue. Remember: this is a min-heap by default. fmt.Printf("Head node is:\t\t%s %s, %d lbs\n", root.Key, root.Value, root.Weight) // Woah, that was easy! Now let's Pop that first value off of the heap. // Remember: this is an immutable data-structure, so `Pop` doesn't actually mutate // any state! lastn, _ = handle.Pop(root) fmt.Printf("Popped head node:\tMarcel %s\n", lastn) // Jake LaMotta moved up to the heavyweight class late in his career. Let's made an // adjustment to his weight. root, _ = handle.SetWeight(root, "Jake", 205) // Let's list our boxers in ascending order of weight. You may have noticed // there's no `PopNode` method on `treap.Handler`. This is not a mistake! A `Pop` // is just a merge on the root node's subtrees. Check it out: fmt.Println("\n[ heap traversal... ]") for n := root; n != nil; { fmt.Printf("%s %s: %d\n", n.Key, n.Value, n.Weight) n = handle.Merge(n.Left, n.Right) } // Lastly, we can iterate through the treap in key-order (smallest to largest). // To do this, we use an iterator. Contrary to treaps, iterators are stateful and // mutable! As such, they are NOT thread-safe. However, multiple concurrent // iterators can traverse the same treap safely. var i int fmt.Println("\n[ binary search-tree traversal (notice keys are sorted alphabetically)... ]") for iterator := handle.Iter(root); iterator.Node != nil; iterator.Next() { fmt.Printf("[%d] %s %s: %d\n", i, iterator.Key, iterator.Value, iterator.Weight) i++ } }
Output: Cassius => Clay Head node is: Marcel Cerdan, 154 lbs Popped head node: Marcel Cerdan [ heap traversal... ] Marcel Cerdan: 154 Jake LaMotta: 205 Cassius Clay: 210 Joe Frazier: 215 [ binary search-tree traversal (notice keys are sorted alphabetically)... ] [0] Cassius Clay: 210 [1] Jake LaMotta: 205 [2] Joe Frazier: 215 [3] Marcel Cerdan: 154
func (Handle) Get ¶
Get an element by key. Returns nil if the key is not in the treap. O(log n) if the treap is balanced (i.e. has uniformly distributed weights).
func (Handle) GetNode ¶ added in v0.0.4
GetNode returns the subtree whose root has the specified key. This is equivalent to Get, but returns a full node.
func (Handle) Insert ¶
Insert an element into the treap, returning false if the element is already present.
O(log n) if the treap is balanced (see Get).
func (Handle) Merge ¶
Merge two treaps. The root will be the root of the input treap with the lowest weight.
O(log n) if the treap is balanced (see Get).
func (Handle) Pop ¶ added in v0.0.2
Pop the next value off the heap. By default, this is the item with the lowest weight.
Pop is equivalent to calling Delete on a root node's key, but avoids an O(n) insert operation.
O(log n)
func (Handle) SetWeight ¶ added in v0.0.2
SetWeight adjusts the weight of the specified item. It is a nop if the key is not in the treap, in which case the returned bool is `false`.
O(log n) if the treap is balanced (see Get).
func (Handle) Split ¶
Split a treap into its left and right branches at point `key`. Key need not be present in the treap. If it is, it WILL NOT be present in either of the resulting subtreaps.
O(log n) if the treap is balanced (see Get).
type Iterator ¶ added in v0.0.3
type Iterator struct { *Node // contains filtered or unexported fields }
Iterator contains treap iteration state. Its methods are NOT thread-safe, but multiple concurrent iterators are supported.