Interval tree (data structure)
An interval tree is a collection of integer-bounded intervals labeled by a value.
For a brief description of the implementation, see the matching Wikipedia article
val is_empty : 'a t -> boolval cardinal : 'a t -> intval intersects : 'a t -> low:int -> high:int -> boolintersects a b t returns true if one interval in t intersects with the interval [a;b].
val empty : 'a tthe empty tree
add lo hi v t adds the interval (lo, hi) labeled with value v to the contents of t. Note that in contrast to sets, identical intervals (even with identical labels) may be *repeated* in an interval tree. E.g., add 1 2 () (add 1 2 ()) contains 2 intervals.
val elements : 'a t -> (int * int * 'a) listval to_seq : 'a t -> (int * int * 'a) Stdlib.Seq.tval to_backwards_seq : 'a t -> (int * int * 'a) Stdlib.Seq.tval find_closest : 'a t -> int -> int -> int * int * 'a * intfind_closest lo hi t returns the interval in t which is at minimal distance of the interval [lo;hi]. The resulting tuple contains from left to right, left-end of the interval, right-end of the interval, value associated to the interval and distance to the interval given in argument. Overlapping intervals are at distance 0 of each other.
Raises Empty_tree if t is empty
val find_intersecting_elem :
'a t ->
int ->
int ->
(int * int * 'a) Stdlib.Seq.tfind_intersecting_elem a b t is equivalent to Seq.filter (fun
(x,y,_) -> intersects x y t) (to_seq t) but is more efficient.
Create an interval tree with the elements which overlap with [low, high].
val print : 'a t -> unitUsed for debugging purpose, should be removed in the long run
val check_integrity : 'a t -> unitUsed for debugging purpose, should be removed in the long run