Up

Module Int

Signature

include S with type bound = Core_kernel.Std.Int.t
type t
val t_of_sexp : Sexplib.Sexp.t -> t
val sexp_of_t : t -> Sexplib.Sexp.t
val bin_t : t Bin_prot.Type_class.t
val bin_read_t : t Bin_prot.Read.reader
val __bin_read_t__ : (int -> t) Bin_prot.Read.reader
val bin_reader_t : t Bin_prot.Type_class.reader
val bin_size_t : t Bin_prot.Size.sizer
val bin_write_t : t Bin_prot.Write.writer
val bin_writer_t : t Bin_prot.Type_class.writer
type bound = Core_kernel.Std.Int.t
type 'a t_ = t
type 'a bound_ = bound
include Interval_intf.Gen with type 'a t := 'a t_ with type 'a bound := 'a bound_
type 'a t
type 'a bound

Module for simple closed intervals over arbitrary types that are ordered correctly using polymorphic compare.

val create : 'a bound -> 'a bound -> 'a t

create l u returns the interval with lower bound l and upper bound u, unless l > u, in which case create returns the empty interval.

val empty : 'a t
val intersect : 'a t -> 'a t -> 'a t
val is_empty : 'a t -> bool
val is_empty_or_singleton : 'a t -> bool
val bounds : 'a t -> ('a bound * 'a bound) option
val lbound : 'a t -> 'a bound option
val ubound : 'a t -> 'a bound option
val bounds_exn : 'a t -> 'a bound * 'a bound
val lbound_exn : 'a t -> 'a bound
val ubound_exn : 'a t -> 'a bound
val convex_hull : 'a t list -> 'a t

convex_hull ts returns an interval whose upperbound is the greatest upperbound of the intervals in the list, and whose lowerbound is the least lowerbound of the list.

val contains : 'a t -> 'a bound -> bool
val compare_value : 'a t -> 'a bound -> [
| `Below
| `Within
| `Above
| `Interval_is_empty
]
val bound : 'a t -> 'a bound -> 'a bound option

bound t x returns None iff is_empty t. If bounds t = Some (a, b), then bound returns Some y where y is the element of t closest to x. I.e.:

| y = a if x < a | y = x if a <= x <= b | y = b if x > b

val is_superset : 'a t -> of_:'a t -> bool

is_superset i1 of_:i2 is whether i1 contains i2. The empty interval is contained in every interval.

val is_subset : 'a t -> of_:'a t -> bool
val map : 'a t -> f:('a bound -> 'b bound) -> 'b t

map t ~f returns create (f l) (f u) if bounds t = Some (l, u), and empty if t is empty. Note that if f l > f u, the result of map is empty, by the definition of create.

If one thinks of an interval as a set of points, rather than a pair of its bounds, then map is not the same as the usual mathematical notion of mapping f over that set. For example, ~f:(fun x -> x * x) maps the interval 

 [-1,1]

to 

 [1,1]

, not to 

 [0,1]

.

val are_disjoint : 'a t list -> bool

are_disjoint ts returns true iff the intervals in ts are pairwise disjoint.

val are_disjoint_as_open_intervals : 'a t list -> bool

Returns true iff a given set of intervals would be disjoint if considered as open intervals. i.e., (3,4) and (4,5) would count as disjoint.

val list_intersect : 'a t list -> 'a t list -> 'a t list

Assuming that ilist1 and ilist2 are lists of (disjoint) intervals, list_intersect ilist1 ilist2 returns the list of disjoint intervals that correspond to the intersection of ilist1 with ilist2.

val half_open_intervals_are_a_partition : 'a t list -> bool
val create : bound -> bound -> t
type 'a poly_t
val to_poly : t -> bound poly_t
type 'a poly_set
module Set : sig .. end
include Core_kernel.Std.Container.S0 with type t := t with type elt := bound
type t
type elt
val mem : ?equal:(elt -> elt -> bool) -> t -> elt -> bool

Checks whether the provided element is there using the default equality test, using the provided equal function if it is not

val length : t -> int
val is_empty : t -> bool
val iter : t -> f:(elt -> unit) -> unit

iter must allow exceptions raised in f to escape, terminating the iteration cleanly. The same holds for all functions below taking an f.

val fold : t -> init:'accum -> f:('accum -> elt -> 'accum) -> 'accum

fold t ~init ~f returns f (... f (f (f init e1) e2) e3 ...) en, where e1..en are the elements of t

val exists : t -> f:(elt -> bool) -> bool

Returns true if and only if there exists an element for which the provided function evaluates to true. This is a short-circuiting operation.

val for_all : t -> f:(elt -> bool) -> bool

Returns true if and only if the provided function evaluates to true for all elements. This is a short-circuiting operation.

val count : t -> f:(elt -> bool) -> int

Returns the number of elements for which the provided function evaluates to true.

val sum : (module Commutative_group.S with type t = 'sum) -> t -> f:(elt -> 'sum) -> 'sum

Returns the sum of f i for i in the container

val find : t -> f:(elt -> bool) -> elt option

Returns as an option the first element for which f evaluates to true.

val find_map : t -> f:(elt -> 'a option) -> 'a option

Returns the first evaluation of f that returns Some, and returns None if there is no such element.

val to_list : t -> elt list
val to_array : t -> elt array
val min_elt : t -> cmp:(elt -> elt -> int) -> elt option

Returns a min (resp max) element from the collection using the provided cmp function. 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. Returns None iff the collection is empty.

val max_elt : t -> cmp:(elt -> elt -> int) -> elt option
include Core_kernel.Std.Binary_searchable.S with type t := t with type elt := bound
type elt
type t

The functions produced by this functor are very powerful, but also somewhat complex to read. Here are some simple examples to clarify the use cases. Below we assume that the function compare is in scope:


      (* find the index of an element [e] in [t] *)
      binary_search t ~compare `First_equal_to e;

      (* find the index where an element [e] should be inserted *)
      binary_search t ~compare `First_greater_than_or_equal_to e;

      (* find the index in [t] where all elements to the left are less than [e] *)
      binary_search_segmented t ~segment_of:(fun e' ->
        if compare e' e <= 0 then `Left else `Right) `First_on_right
val binary_search : (t, elt) Binary_searchable_intf.binary_search

binary_search ?pos ?len t ~compare which elt takes t that is sorted in nondecreasing order according to compare, where compare and elt divide t into three (possibly empty) segments:

        |  < elt  |  = elt  |  > elt  |

binary_search returns the index in t of an element on the boundary of segments as specified by which. See the diagram below next to the which variants.

By default, binary_search searches the entire t. One can supply ?pos or ?len to search a slice of t.

binary_search does not check that compare orders t, and behavior is unspecified if compare doesn't order t. Behavior is also unspecified if compare mutates t.

val binary_search_segmented : (t, elt) Binary_searchable_intf.binary_search_segmented

binary_search_segmented ?pos ?len t ~segment_of which takes an segment_of function that divides t into two (possibly empty) segments:

        | segment_of elt = `Left | segment_of elt = `Right |

binary_search_segmented returns the index of the element on the boundary of the segments as specified by which: `Last_on_left yields the index of the last element of the left segment, while `First_on_right yields the index of the first element of the right segment. It returns None if the segment is empty.

By default, binary_search searches the entire t. One can supply ?pos or ?len to search a slice of t.

binary_search_segmented does not check that segment_of segments t as in the diagram, and behavior is unspecified if segment_of doesn't segment t. Behavior is also unspecified if segment_of mutates t.