Documentation
¶
Overview ¶
Package interval implements an interval tree based on an augmented Left-Leaning Red Black tree.
Index ¶
- Constants
- Variables
- type Comparable
- type Interface
- type Node
- type Operation
- type Overlapper
- type Range
- type Tree
- func (t *Tree) AdjustRanges()
- func (t *Tree) Ceil(q Interface) (o Interface, err error)
- func (t *Tree) Delete(e Interface, fast bool) (err error)
- func (t *Tree) DeleteMax(fast bool)
- func (t *Tree) DeleteMin(fast bool)
- func (t *Tree) Do(fn Operation) bool
- func (t *Tree) DoMatching(fn Operation, q Overlapper) bool
- func (t *Tree) DoMatchingReverse(fn Operation, q Overlapper) bool
- func (t *Tree) DoReverse(fn Operation) bool
- func (t *Tree) Floor(q Interface) (o Interface, err error)
- func (t *Tree) Get(q Overlapper) (o []Interface)
- func (t *Tree) Insert(e Interface, fast bool) (err error)
- func (t *Tree) Len() int
- func (t *Tree) Max() Interface
- func (t *Tree) Min() Interface
Constants ¶
const ( TD234 = iota BU23 )
Operation mode of the underlying LLRB tree.
const Mode = BU23
Mode .
Variables ¶
var ErrInvertedRange = errors.New("interval: inverted range")
ErrInvertedRange is returned if an interval is used where the start value is greater than the end value.
Functions ¶
This section is empty.
Types ¶
type Comparable ¶
type Comparable []byte
A Comparable is a type that describes the ends of an Overlapper.
func (Comparable) Compare ¶
func (c Comparable) Compare(o Comparable) int
Compare returns a value indicating the sort order relationship between the receiver and the parameter.
Given c = a.Compare(b):
c < 0 if a < b; c == 0 if a == b; and c > 0 if a > b.
type Interface ¶
type Interface interface {
Overlapper
Range() Range
ID() uintptr // Returns a unique ID for the element.
}
An Interface is a type that can be inserted into a Tree.
type Operation ¶
An Operation is a function that operates on an Interface. If done is returned true, the Operation is indicating that no further work needs to be done and so the Do function should traverse no further.
type Overlapper ¶
type Overlapper interface {
// Overlap returns a boolean indicating whether the receiver overlaps the parameter.
Overlap(Range) bool
}
An Overlapper can determine whether it overlaps a range.
type Range ¶
type Range struct {
Start, End Comparable
}
A Range is a type that describes the basic characteristics of an interval.
type Tree ¶
A Tree manages the root node of an interval tree. Public methods are exposed through this type.
func (*Tree) AdjustRanges ¶
func (t *Tree) AdjustRanges()
AdjustRanges fixes range fields for all Nodes in the Tree. This must be called before Get or DoMatching* is used if fast insertion or deletion has been performed.
func (*Tree) Ceil ¶
Ceil returns the smallest value equal to or greater than the query q according to q.Start.Compare(), with ties broken by comparison of ID() values.
func (*Tree) Do ¶
Do performs fn on all intervals stored in the tree. A boolean is returned indicating whether the Do traversal was interrupted by an Operation returning true. If fn alters stored intervals' sort relationships, future tree operation behaviors are undefined.
func (*Tree) DoMatching ¶
func (t *Tree) DoMatching(fn Operation, q Overlapper) bool
DoMatching performs fn on all intervals stored in the tree that match q according to Overlap, with q.Overlap() used to guide tree traversal, so DoMatching() will out perform Do() with a called conditional function if the condition is based on sort order, but can not be reliably used if the condition is independent of sort order. A boolean is returned indicating whether the Do traversal was interrupted by an Operation returning true. If fn alters stored intervals' sort relationships, future tree operation behaviors are undefined.
func (*Tree) DoMatchingReverse ¶
func (t *Tree) DoMatchingReverse(fn Operation, q Overlapper) bool
DoMatchingReverse performs fn on all intervals stored in the tree that match q according to Overlap, with q.Overlap() used to guide tree traversal, so DoMatching() will out perform Do() with a called conditional function if the condition is based on sort order, but can not be reliably used if the condition is independent of sort order. A boolean is returned indicating whether the Do traversal was interrupted by an Operation returning true. If fn alters stored intervals' sort relationships, future tree operation behaviors are undefined.
func (*Tree) DoReverse ¶
DoReverse performs fn on all intervals stored in the tree, but in reverse of sort order. A boolean is returned indicating whether the Do traversal was interrupted by an Operation returning true. If fn alters stored intervals' sort relationships, future tree operation behaviors are undefined.
func (*Tree) Floor ¶
Floor returns the largest value equal to or less than the query q according to q.Start.Compare(), with ties broken by comparison of ID() values.
func (*Tree) Get ¶
func (t *Tree) Get(q Overlapper) (o []Interface)
Get returns a slice of Interfaces that overlap q in the Tree according to q.Overlap().
func (*Tree) Insert ¶
Insert inserts the Interface e into the Tree. Insertions may replace existing stored intervals.
Source Files