Documentation ¶
Overview ¶
Package interval implements an interval tree based on an augmented Left-Leaning Red Black tree.
Index ¶
- Constants
- Variables
- type Comparable
- type IntInterface
- type IntNode
- type IntOperation
- type IntOverlapper
- type IntRange
- type IntTree
- func (t *IntTree) AdjustRanges()
- func (t *IntTree) Ceil(q IntInterface) (o IntInterface, err error)
- func (t *IntTree) Delete(e IntInterface, fast bool) (err error)
- func (t *IntTree) DeleteMax(fast bool)
- func (t *IntTree) DeleteMin(fast bool)
- func (t *IntTree) Do(fn IntOperation) bool
- func (t *IntTree) DoMatching(fn IntOperation, q IntOverlapper) bool
- func (t *IntTree) DoMatchingReverse(fn IntOperation, q IntOverlapper) bool
- func (t *IntTree) DoReverse(fn IntOperation) bool
- func (t *IntTree) Floor(q IntInterface) (o IntInterface, err error)
- func (t *IntTree) Get(q IntOverlapper) (o []IntInterface)
- func (t *IntTree) Insert(e IntInterface, fast bool) (err error)
- func (t *IntTree) Len() int
- func (t *IntTree) Max() IntInterface
- func (t *IntTree) Min() IntInterface
- type Interface
- type Mutable
- 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
Examples ¶
Constants ¶
const ( TD234 = iota BU23 )
Operation mode of the underlying LLRB tree.
const Mode = BU23
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 interface { // 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. // Compare(Comparable) int }
A Comparable is a type that describes the ends of an Overlapper.
type IntInterface ¶
type IntInterface interface { IntOverlapper Range() IntRange ID() uintptr // Returns a unique ID for the element. }
An IntInterface is a type that can be inserted into a IntTree.
type IntNode ¶
type IntNode struct { Elem IntInterface Interval IntRange Range IntRange Left, Right *IntNode Color llrb.Color }
A IntNode represents a node in an IntTree.
type IntOperation ¶
type IntOperation func(IntInterface) (done bool)
An IntOperation is a function that operates on an IntInterface. If done is returned true, the IntOperation is indicating that no further work needs to be done and so the Do function should traverse no further.
type IntOverlapper ¶
type IntOverlapper interface { // Overlap returns a boolean indicating whether the receiver overlaps a range. Overlap(IntRange) bool }
An IntOverlapper can determine whether it overlaps an integer range.
type IntRange ¶
type IntRange struct {
Start, End int
}
An IntRange is a type that describes the basic characteristics of an interval over the integer number line.
type IntTree ¶
type IntTree struct { Root *IntNode // Root node of the tree. Count int // Number of elements stored. }
A IntTree manages the root node of an integer line interval tree. Public methods are exposed through this type.
func (*IntTree) AdjustRanges ¶
func (t *IntTree) AdjustRanges()
AdjustRanges fixes range fields for all IntNodes in the IntTree. This must be called before Get or DoMatching* is used if fast insertion or deletion has been performed.
func (*IntTree) Ceil ¶
func (t *IntTree) Ceil(q IntInterface) (o IntInterface, err error)
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 (*IntTree) Delete ¶
func (t *IntTree) Delete(e IntInterface, fast bool) (err error)
Delete deletes the element e if it exists in the IntTree.
func (*IntTree) Do ¶
func (t *IntTree) Do(fn IntOperation) bool
Do performs fn on all intervals stored in the tree. A boolean is returned indicating whether the Do traversal was interrupted by an IntOperation returning true. If fn alters stored intervals' end points, future tree operation behaviors are undefined.
func (*IntTree) DoMatching ¶
func (t *IntTree) DoMatching(fn IntOperation, q IntOverlapper) bool
DoMatch 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 IntOperation returning true. If fn alters stored intervals' end points, future tree operation behaviors are undefined.
func (*IntTree) DoMatchingReverse ¶
func (t *IntTree) DoMatchingReverse(fn IntOperation, q IntOverlapper) bool
DoMatchReverse 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 IntOperation returning true. If fn alters stored intervals' end points, future tree operation behaviors are undefined.
func (*IntTree) DoReverse ¶
func (t *IntTree) DoReverse(fn IntOperation) bool
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 IntOperation returning true. If fn alters stored intervals' end points, future tree operation behaviors are undefined.
func (*IntTree) Floor ¶
func (t *IntTree) Floor(q IntInterface) (o IntInterface, err error)
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 (*IntTree) Get ¶
func (t *IntTree) Get(q IntOverlapper) (o []IntInterface)
Get returns a slice of IntInterfaces that overlap q in the IntTree according to q.Overlap().
func (*IntTree) Insert ¶
func (t *IntTree) Insert(e IntInterface, fast bool) (err error)
Insert inserts the IntInterface e into the IntTree. Insertions may replace existing stored intervals.
func (*IntTree) Max ¶
func (t *IntTree) Max() IntInterface
Return the right-most interval stored in the tree.
func (*IntTree) Min ¶
func (t *IntTree) Min() IntInterface
Return the left-most interval stored in the tree.
type Interface ¶
type Interface interface { Overlapper Range ID() uintptr // Returns a unique ID for the element. NewMutable() Mutable // Returns an mutable copy of the Interface's range. }
An Interface is a type that can be inserted into a Tree.
type Mutable ¶
type Mutable interface { Range SetStart(Comparable) // Set the start value. SetEnd(Comparable) // Set the end value. }
A Mutable is a Range that can have its range altered.
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 interface { // Return a Comparable equal to the start value of the Overlapper. Start() Comparable // Return a Comparable equal to the end value of the Overlapper. 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.
Example ¶
package main import ( "fmt" "github.com/biogo/store/interval" ) func min(a, b Int) Int { if a < b { return a } return b } func max(a, b Int) Int { if a > b { return a } return b } // Flatten all overlapping intervals, storing originals as sub-intervals. func Flatten(t *interval.Tree) { var ( fi = true ti []Interval mid uintptr ) t.Do( func(e interval.Interface) (done bool) { iv := e.(Interval) if fi || iv.start >= ti[len(ti)-1].end { ti = append(ti, Interval{ start: iv.start, end: iv.end, }) fi = false } else { ti[len(ti)-1].end = max(ti[len(ti)-1].end, iv.end) } ti[len(ti)-1].Sub = append(ti[len(ti)-1].Sub, iv) if iv.id > mid { mid = iv.id } return }, ) mid++ t.Root, t.Count = nil, 0 for i, iv := range ti { iv.id = uintptr(i) + mid t.Insert(iv, true) } t.AdjustRanges() } func main() { t := &interval.Tree{} for i, iv := range ivs { iv.id = uintptr(i) err := t.Insert(iv, false) if err != nil { fmt.Println(err) } } Flatten(t) t.Do(func(e interval.Interface) (done bool) { fmt.Printf("%s: %v\n", e, e.(Interval).Sub); return }) }
Output: [0,8)#10: [[0,2)#0 [1,6)#2 [1,3)#4 [2,4)#1 [3,4)#3 [4,6)#5 [5,8)#6 [5,7)#8 [6,8)#7] [8,9)#11: [[8,9)#9]
func (*Tree) DoMatching ¶
func (t *Tree) DoMatching(fn Operation, q Overlapper) bool
DoMatch 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.
Example ¶
package main import ( "fmt" "github.com/biogo/store/interval" ) // Merge an interval into the tree, replacing overlapping intervals, but retaining them as sub intervals. func Merge(t *interval.Tree, ni Interval) { var ( fi = true qi = &Interval{start: ni.start, end: ni.end} r []interval.Interface ) t.DoMatching( func(e interval.Interface) (done bool) { iv := e.(Interval) r = append(r, e) ni.Sub = append(ni.Sub, iv) // Flatten merge history. ni.Sub = append(ni.Sub, iv.Sub...) iv.Sub = nil if fi { ni.start = min(iv.start, ni.start) fi = false } ni.end = max(iv.end, ni.end) return }, qi, ) for _, d := range r { t.Delete(d, false) } t.Insert(ni, false) } func main() { t := &interval.Tree{} var ( i int iv Interval ) for i, iv = range ivs { iv.id = uintptr(i) err := t.Insert(iv, false) if err != nil { fmt.Println(err) } } i++ Merge(t, Interval{start: -1, end: 4, id: uintptr(i)}) t.Do(func(e interval.Interface) (done bool) { fmt.Printf("%s: %v\n", e, e.(Interval).Sub) return }) }
Output: [-1,6)#10: [[0,2)#0 [1,6)#2 [1,3)#4 [2,4)#1 [3,4)#3] [4,6)#5: [] [5,8)#6: [] [5,7)#8: [] [6,8)#7: [] [8,9)#9: []
func (*Tree) DoMatchingReverse ¶
func (t *Tree) DoMatchingReverse(fn Operation, q Overlapper) bool
DoMatchReverse 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.