Documentation ¶
Overview ¶
Package adt implements useful abstract data types.
Example ¶
package main import ( "fmt" "github.com/CloudcadeSF/etcd/pkg/adt" ) func main() { ivt := adt.NewIntervalTree() ivt.Insert(adt.NewInt64Interval(1, 3), 123) ivt.Insert(adt.NewInt64Interval(9, 13), 456) ivt.Insert(adt.NewInt64Interval(7, 20), 789) rs := ivt.Stab(adt.NewInt64Point(10)) for _, v := range rs { fmt.Printf("Overlapping range: %+v\n", v) } }
Output: Overlapping range: &{Ivl:{Begin:7 End:20} Val:789} Overlapping range: &{Ivl:{Begin:9 End:13} Val:456}
Index ¶
- type BytesAffineComparable
- type Comparable
- type Int64Comparable
- type Interval
- func NewBytesAffineInterval(begin, end []byte) Interval
- func NewBytesAffinePoint(b []byte) Interval
- func NewInt64Interval(a int64, b int64) Interval
- func NewInt64Point(a int64) Interval
- func NewStringAffineInterval(begin, end string) Interval
- func NewStringAffinePoint(s string) Interval
- func NewStringInterval(begin, end string) Interval
- func NewStringPoint(s string) Interval
- type IntervalTree
- type IntervalValue
- type IntervalVisitor
- type StringAffineComparable
- type StringComparable
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type BytesAffineComparable ¶
type BytesAffineComparable []byte
BytesAffineComparable treats empty byte arrays as > all other byte arrays
func (BytesAffineComparable) Compare ¶
func (b BytesAffineComparable) Compare(c Comparable) int
type Comparable ¶
type Comparable interface { // Compare gives the result of a 3-way comparison // a.Compare(b) = 1 => a > b // a.Compare(b) = 0 => a == b // a.Compare(b) = -1 => a < b Compare(c Comparable) int }
Comparable is an interface for trichotomic comparisons.
type Int64Comparable ¶
type Int64Comparable int64
func (Int64Comparable) Compare ¶
func (v Int64Comparable) Compare(c Comparable) int
type Interval ¶
type Interval struct { Begin Comparable End Comparable }
Interval implements a Comparable interval [begin, end) TODO: support different sorts of intervals: (a,b), [a,b], (a, b]
func NewBytesAffineInterval ¶
func NewBytesAffinePoint ¶
func NewInt64Interval ¶
func NewInt64Point ¶
func NewStringAffineInterval ¶
func NewStringAffinePoint ¶
func NewStringInterval ¶
func NewStringPoint ¶
func (*Interval) Compare ¶
func (ivl *Interval) Compare(c Comparable) int
Compare on an interval gives == if the interval overlaps.
type IntervalTree ¶
type IntervalTree interface { // Insert adds a node with the given interval into the tree. Insert(ivl Interval, val interface{}) // Delete removes the node with the given interval from the tree, returning // true if a node is in fact removed. Delete(ivl Interval) bool // Len gives the number of elements in the tree. Len() int // Height is the number of levels in the tree; one node has height 1. Height() int // MaxHeight is the expected maximum tree height given the number of nodes. MaxHeight() int // Visit calls a visitor function on every tree node intersecting the given interval. // It will visit each interval [x, y) in ascending order sorted on x. Visit(ivl Interval, ivv IntervalVisitor) // Find gets the IntervalValue for the node matching the given interval Find(ivl Interval) *IntervalValue // Intersects returns true if there is some tree node intersecting the given interval. Intersects(iv Interval) bool // Contains returns true if the interval tree's keys cover the entire given interval. Contains(ivl Interval) bool // Stab returns a slice with all elements in the tree intersecting the interval. Stab(iv Interval) []*IntervalValue // Union merges a given interval tree into the receiver. Union(inIvt IntervalTree, ivl Interval) }
IntervalTree represents a (mostly) textbook implementation of the "Introduction to Algorithms" (Cormen et al, 3rd ed.) chapter 13 red-black tree and chapter 14.3 interval tree with search supporting "stabbing queries".
func NewIntervalTree ¶
func NewIntervalTree() IntervalTree
NewIntervalTree returns a new interval tree.
type IntervalValue ¶
type IntervalValue struct { Ivl Interval Val interface{} }
IntervalValue represents a range tree node that contains a range and a value.
type IntervalVisitor ¶
type IntervalVisitor func(n *IntervalValue) bool
IntervalVisitor is used on tree searches; return false to stop searching.
type StringAffineComparable ¶
type StringAffineComparable string
StringAffineComparable treats "" as > all other strings
func (StringAffineComparable) Compare ¶
func (s StringAffineComparable) Compare(c Comparable) int
type StringComparable ¶
type StringComparable string
func (StringComparable) Compare ¶
func (s StringComparable) Compare(c Comparable) int