ActiveGo 1.8Package adt
Overview ▹
▹ Example
Index ▹
type BytesAffineComparable ¶
BytesAffineComparable treats empty byte arrays as > all other byte arrays
type BytesAffineComparable []byte
func (BytesAffineComparable) Compare ¶
func (b BytesAffineComparable) Compare(c Comparable) int
type Comparable ¶
Comparable is an interface for trichotomic comparisons.
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
}
type Int64Comparable ¶
type Int64Comparable int64
func (Int64Comparable) Compare ¶
func (v Int64Comparable) Compare(c Comparable) int
type Interval ¶
Interval implements a Comparable interval [begin, end) TODO: support different sorts of intervals: (a,b), [a,b], (a, b]
type Interval struct {
Begin Comparable
End Comparable
}
func NewBytesAffineInterval ¶
func NewBytesAffineInterval(begin, end []byte) Interval
func NewBytesAffinePoint ¶
func NewBytesAffinePoint(b []byte) Interval
func NewInt64Interval ¶
func NewInt64Interval(a int64, b int64) Interval
func NewInt64Point ¶
func NewInt64Point(a int64) Interval
func NewStringAffineInterval ¶
func NewStringAffineInterval(begin, end string) Interval
func NewStringAffinePoint ¶
func NewStringAffinePoint(s string) Interval
func NewStringInterval ¶
func NewStringInterval(begin, end string) Interval
func NewStringPoint ¶
func NewStringPoint(s string) Interval
func (*Interval) Compare ¶
func (ivl *Interval) Compare(c Comparable) int
Compare on an interval gives == if the interval overlaps.
type IntervalTree ¶
IntervalTree represents a (mostly) textbook implementation of the "Introduction to Algorithms" (Cormen et al, 2nd ed.) chapter 13 red-black tree and chapter 14.3 interval tree with search supporting "stabbing queries".
type IntervalTree struct {
// contains filtered or unexported fields
}
func (*IntervalTree) Contains ¶
func (ivt *IntervalTree) Contains(ivl Interval) bool
Contains returns true if the interval tree's keys cover the entire given interval.
func (*IntervalTree) Delete ¶
func (ivt *IntervalTree) Delete(ivl Interval) bool
Delete removes the node with the given interval from the tree, returning true if a node is in fact removed.
func (*IntervalTree) Find ¶
func (ivt *IntervalTree) Find(ivl Interval) (ret *IntervalValue)
Find gets the IntervalValue for the node matching the given interval
func (*IntervalTree) Height ¶
func (ivt *IntervalTree) Height() int
Height is the number of levels in the tree; one node has height 1.
func (*IntervalTree) Insert ¶
func (ivt *IntervalTree) Insert(ivl Interval, val interface{})
Insert adds a node with the given interval into the tree.
func (*IntervalTree) Intersects ¶
func (ivt *IntervalTree) Intersects(iv Interval) bool
Intersects returns true if there is some tree node intersecting the given interval.
func (*IntervalTree) Len ¶
func (ivt *IntervalTree) Len() int
Len gives the number of elements in the tree
func (*IntervalTree) MaxHeight ¶
func (ivt *IntervalTree) MaxHeight() int
MaxHeight is the expected maximum tree height given the number of nodes
func (*IntervalTree) Stab ¶
func (ivt *IntervalTree) Stab(iv Interval) (ivs []*IntervalValue)
Stab returns a slice with all elements in the tree intersecting the interval.
func (*IntervalTree) Visit ¶
func (ivt *IntervalTree) Visit(ivl Interval, ivv IntervalVisitor)
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.
type IntervalValue ¶
type IntervalValue struct {
Ivl Interval
Val interface{}
}
type IntervalVisitor ¶
IntervalVisitor is used on tree searches; return false to stop searching.
type IntervalVisitor func(n *IntervalValue) bool
type StringAffineComparable ¶
StringAffineComparable treats "" as > all other strings
type StringAffineComparable string
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