module Biocaml_intervalTree:Interval tree (data structure)sig
..end
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
type 'a
t
exception Empty_tree
val is_empty : 'a t -> bool
val cardinal : 'a t -> int
val intersects : int -> int -> 'a t -> bool
intersects a b t
returns true
if one interval in t
intersects with the interval [a
;b
].val find_closest : int -> int -> 'a t -> int * int * 'a * int
find_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 empty : 'a t
val add : int -> int -> 'a -> 'a t -> 'a t
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) list
val enum : 'a t -> (int * int * 'a) BatEnum.t
val backwards : 'a t -> (int * int * 'a) BatEnum.t
val print : 'a t -> unit
val check_integrity : 'a t -> unit