Documentation ¶
Overview ¶
Package adt implements useful abstract data types.
Example ¶
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
- func (ivt *IntervalTree) Contains(ivl Interval) bool
- func (ivt *IntervalTree) Delete(ivl Interval) bool
- func (ivt *IntervalTree) Find(ivl Interval) (ret *IntervalValue)
- func (ivt *IntervalTree) Height() int
- func (ivt *IntervalTree) Insert(ivl Interval, val interface{})
- func (ivt *IntervalTree) Intersects(iv Interval) bool
- func (ivt *IntervalTree) Len() int
- func (ivt *IntervalTree) MaxHeight() int
- func (ivt *IntervalTree) Stab(iv Interval) (ivs []*IntervalValue)
- func (ivt *IntervalTree) Visit(ivl Interval, ivv IntervalVisitor)
- 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 struct {
// contains filtered or unexported fields
}
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".
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 ¶
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