Interval_tree.S
The Interval Tree Interface.
Interval tree is a mapping from intervals to arbitrary values. The intervals are allowed to intersect. Thus a single point may belong to more than one interval. Unlike a regular map, when an association is extract by using a key value, the interval tree uses notions of domination and intersection to extract values associated with all intervals that either dominate (i.e., are super sets) or intersects with the provided key. In that sense an interval tree is a multimap.
val sexp_of_t :
('a -> Ppx_sexp_conv_lib.Sexp.t) ->
'a t ->
Ppx_sexp_conv_lib.Sexp.t
val empty : 'a t
empty x
an empty interval tree
singleton k x
creates an interval tree that has only one mapping - from the key k
to data x
least t
returns the least bound of the tree t
.
Returns None
if t
is empty.
greatest t
returns the greatest bound of the tree t
.
Returns None
if t
is empty.
dominators t k
returns all intervals and their associated values that include k
.
intersections t k
returns all intervals and their associated values that intersects with k
intersects t k
is true
iff t
contains an interval that intersects with k
lookup t p
returns bindings of all intervals that contain the given point
filter t ~f
returns a tree where all elements for which f
returned false
are removed.
filter t ~f
returns a tree where all elements for which f
returned None
are removed and all others are mapped.
filter t ~f
returns a tree where all elements for which f
returned None
are removed and all others are mapped.
remove_intersections t k
removes all bindings that intersect with the key k
.
remove_dominators t k
removes all bindings that are included (dominated by) in the interval k
Interval Trees implement common container interface
include Core_kernel.Container.S1 with type 'a t := 'a t
val mem : 'a t -> 'a -> equal:('a -> 'a -> bool) -> bool
val length : 'a t -> int
val is_empty : 'a t -> bool
val iter : 'a t -> f:('a -> unit) -> unit
val fold : 'a t -> init:'accum -> f:('accum -> 'a -> 'accum) -> 'accum
val fold_result :
'a t ->
init:'accum ->
f:('accum -> 'a -> ('accum, 'e) Base__.Result.t) ->
('accum, 'e) Base__.Result.t
val fold_until :
'a t ->
init:'accum ->
f:('accum -> 'a -> ('accum, 'final) Base__.Container_intf.Continue_or_stop.t) ->
finish:('accum -> 'final) ->
'final
val exists : 'a t -> f:('a -> bool) -> bool
val for_all : 'a t -> f:('a -> bool) -> bool
val count : 'a t -> f:('a -> bool) -> int
val sum :
(module Base__.Container_intf.Summable with type t = 'sum) ->
'a t ->
f:('a -> 'sum) ->
'sum
val find : 'a t -> f:('a -> bool) -> 'a option
val find_map : 'a t -> f:('a -> 'b option) -> 'b option
val to_list : 'a t -> 'a list
val to_array : 'a t -> 'a array
val min_elt : 'a t -> compare:('a -> 'a -> int) -> 'a option
val max_elt : 'a t -> compare:('a -> 'a -> int) -> 'a option