Legend:
Library
Module
Module type
Parameter
Class
Class type
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.
fold_result t ~init ~f is a short-circuiting version of fold that runs in the Result monad. If f returns an Error _, that value is returned without any additional invocations of f.
fold_until t ~init ~f ~finish is a short-circuiting version of fold. If f returns Stop _ the computation ceases and results in that value. If f returns Continue _, the fold will proceed. If f never returns Stop _, the final result is computed by finish.
Example:
type maybe_negative =
| Found_negative of int
| All_nonnegative of { sum : int }
(** [first_neg_or_sum list] returns the first negative number in [list], if any,
otherwise returns the sum of the list. *)
let first_neg_or_sum =
List.fold_until ~init:0
~f:(fun sum x ->
if x < 0
then Stop (Found_negative x)
else Continue (sum + x))
~finish:(fun sum -> All_nonnegative { sum })
;;
let x = first_neg_or_sum [1; 2; 3; 4; 5]
val x : maybe_negative = All_nonnegative {sum = 15}
let y = first_neg_or_sum [1; 2; -3; 4; 5]
val y : maybe_negative = Found_negative -3
val min_elt : 'at->compare:('a->'a-> int)->'a option
Returns a minimum (resp maximum) element from the collection using the provided compare function, or None if the collection is empty. In case of a tie, the first element encountered while traversing the collection is returned. The implementation uses fold so it has the same complexity as fold.
val max_elt : 'at->compare:('a->'a-> int)->'a option