README
¶
interval
import "github.com/zendesk/generic/interval"
Package interval provides an implementation of an interval tree built using an augmented AVL tree. An interval tree stores values associated with intervals, and can efficiently determine which intervals overlap with others. All intervals must have a unique starting position. It supports the following operations, where 'n' is the number of intervals in the tree:
* Put: add an interval to the tree. Complexity: O(lg n).
* Get: find an interval with a given starting position. Complexity O(lg n).
* Overlaps: find all intervals that overlap with a given interval. Complexity: O(lg n + m), where 'm' is the size of the result (number of overlapping intervals found).
* Remove: remove the interval at a given position. Complexity: O(lg n).
Example
{
tree := New[string]()
tree.Put(0, 10, "foo")
tree.Put(5, 9, "bar")
tree.Put(10, 11, "baz")
tree.Put(-10, 4, "quux")
vals := tree.Overlaps(4, 10)
for _, v := range vals {
fmt.Println(v)
}
}
Output
foo
bar
Index
- type KV
- type Tree
- [func NewV any *Tree[V]](<#func-new>)
- func (t *Tree[V]) Each(fn func(low, high int, val V))
- func (t *Tree[V]) Get(pos int) (V, bool)
- func (t *Tree[V]) Height() int
- func (t *Tree[V]) Overlaps(low, high int) []V
- func (t *Tree[V]) Put(low, high int, value V)
- func (t *Tree[V]) Remove(pos int)
- func (t *Tree[V]) Size() int
type KV
type KV[V any] struct {
Low, High int
Val V
}
type Tree
Tree implements an interval tree. All intervals must have unique starting positions.
type Tree[V any] struct {
// contains filtered or unexported fields
}
func New
func New[V any]() *Tree[V]
New returns an empty interval tree.
func (*Tree[V]) Each
func (t *Tree[V]) Each(fn func(low, high int, val V))
Each calls 'fn' on every element in the tree, and its corresponding interval, in order sorted by starting position.
func (*Tree[V]) Get
func (t *Tree[V]) Get(pos int) (V, bool)
Get returns the value associated with the interval starting at 'pos', or 'false' if no such value exists.
func (*Tree[V]) Height
func (t *Tree[V]) Height() int
Height returns the height of the tree.
func (*Tree[V]) Overlaps
func (t *Tree[V]) Overlaps(low, high int) []V
Overlaps returns all values that overlap with the given range.
func (*Tree[V]) Put
func (t *Tree[V]) Put(low, high int, value V)
Put associates the interval 'key' with 'value'.
func (*Tree[V]) Remove
func (t *Tree[V]) Remove(pos int)
Remove deletes the interval starting at 'pos'.
func (*Tree[V]) Size
func (t *Tree[V]) Size() int
Size returns the number of elements in the tree.
Generated by gomarkdoc
Documentation
¶
Overview ¶
Package interval provides an implementation of an interval tree built using an augmented AVL tree. An interval tree stores values associated with intervals, and can efficiently determine which intervals overlap with others. All intervals must have a unique starting position. It supports the following operations, where 'n' is the number of intervals in the tree:
* Put: add an interval to the tree. Complexity: O(lg n).
* Get: find an interval with a given starting position. Complexity O(lg n).
- Overlaps: find all intervals that overlap with a given interval. Complexity: O(lg n + m), where 'm' is the size of the result (number of overlapping intervals found).
* Remove: remove the interval at a given position. Complexity: O(lg n).
Example ¶
tree := New[string]()
tree.Put(0, 10, "foo")
tree.Put(5, 9, "bar")
tree.Put(10, 11, "baz")
tree.Put(-10, 4, "quux")
vals := tree.Overlaps(4, 10)
for _, v := range vals {
fmt.Println(v)
}
Output: foo bar
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Tree ¶
type Tree[V any] struct { // contains filtered or unexported fields }
Tree implements an interval tree. All intervals must have unique starting positions.
func (*Tree[V]) Each ¶
Each calls 'fn' on every element in the tree, and its corresponding interval, in order sorted by starting position.
func (*Tree[V]) Get ¶
Get returns the value associated with the interval starting at 'pos', or 'false' if no such value exists.
Source Files