StaticIntervalTree
Defined in: packages/data/src/interval/static-interval-tree.ts:51
A centered interval tree: which intervals contain a point, or overlap a range.
Intervals are half-open, [from, to), so touching intervals do not count as
overlapping — the convention that makes adjacent ranges tile without
ambiguity.
Each node picks a center point and holds every interval spanning it, kept in two orders so a query can stop as soon as an interval is out of range rather than scanning the whole node. Intervals entirely left or right of the center recurse into subtrees.
Static: the whole interval set is given at construction, which is what allows the balanced centers. Building is O(n log n).
Time complexity: O(log n + k) per query for k results.
Type Parameters
Section titled “Type Parameters”P
The endpoint type.
V
The value carried by an interval.
Implements
Section titled “Implements”IIntervalIndex<P,V>
Constructors
Section titled “Constructors”Constructor
Section titled “Constructor”new StaticIntervalTree<
P,V>(intervals,options?):StaticIntervalTree<P,V>
Defined in: packages/data/src/interval/static-interval-tree.ts:57
Parameters
Section titled “Parameters”intervals
Section titled “intervals”Iterable<Interval<P, V>>
options?
Section titled “options?”Returns
Section titled “Returns”StaticIntervalTree<P, V>
Properties
Section titled “Properties”comparator
Section titled “comparator”
readonlycomparator:Comparator<P>
Defined in: packages/data/src/interval/static-interval-tree.ts:55
Methods
Section titled “Methods”count()
Section titled “count()”count():
number
Defined in: packages/data/src/interval/static-interval-tree.ts:90
The number of intervals indexed.
Empty (from === to) intervals are discarded at construction, so this can
be lower than the number handed in.
Returns
Section titled “Returns”number
overlapping()
Section titled “overlapping()”overlapping(
from,to):IterableIterator<V>
Defined in: packages/data/src/interval/static-interval-tree.ts:108
The values of every interval overlapping [from, to).
An empty or inverted query range yields nothing: no interval overlaps a range of zero width.
Parameters
Section titled “Parameters”P
P
Returns
Section titled “Returns”IterableIterator<V>
Implementation of
Section titled “Implementation of”stab()
Section titled “stab()”stab(
point):IterableIterator<V>
Defined in: packages/data/src/interval/static-interval-tree.ts:98
The values of every interval containing point, i.e. where from <= point < to.
Parameters
Section titled “Parameters”P
Returns
Section titled “Returns”IterableIterator<V>