Module `Interval.Make`

Interval.Make is a functor that takes a type that you'd like to create intervals for and returns a module with functions over intervals of that type.

For example, suppose you had a Percent.t type and wanted to work with intervals over it, i.e., inclusive ranges like 40-50% or 0-100%. You would create your Percent_interval module by calling:

module Percent_interval = Interval.Make(Percent)

You now have a module with lots of functionality ready to use. For instance you could call Percent_interval.empty to create an empty interval, or:

Percent_interval.create (Percent.of_percentage 3) (Percent.of_percentage 30)

to get an actual interval that ranges from 3% to 30%. You can then ask questions of this interval, like whether it's a subset of another interval or whether it contains a particular value.

NB. In order to use the Interval.Make functor, your type must satisfy Comparable and support bin-io and s-expression conversion. At a minimum, then, Percent must look like this:

module Percent = struct
  module T = struct
    type t = float [@@deriving bin_io, compare, sexp]
  end
  include T
  include Comparable.Make_binable(T)
end

Parameters

Bound : sig ... end

Signature

type t

include Bin_prot.Binable.S with type t := t

type t

include Bin_prot.Binable.S_only_functions with type t := t

type t

val bin_size_t : t Bin_prot.Size.sizer
val bin_write_t : t Bin_prot.Write.writer
val bin_read_t : t Bin_prot.Read.reader
val __bin_read_t__ : (int -> t) Bin_prot.Read.reader: This function only needs implementation if t exposed to be a polymorphic variant. Despite what the type reads, this does *not* produce a function after reading; instead it takes the constructor tag (int) before reading and reads the rest of the variant t afterwards.

val bin_shape_t : Bin_prot.Shape.t
val bin_writer_t : t Bin_prot.Type_class.writer
val bin_reader_t : t Bin_prot.Type_class.reader
val bin_t : t Bin_prot.Type_class.t

include Ppx_sexp_conv_lib.Sexpable.S with type t := t

type t

val t_of_sexp : Sexplib0.Sexp.t -> t
val sexp_of_t : t -> Sexplib0.Sexp.t

val compare : t -> t -> int
val hash_fold_t : Base.Hash.state -> t -> Base.Hash.state
val hash : t -> Base.Hash.hash_value

type bound = Bound.t

type 'a t
type 'a bound: bound is the type of points in the interval (and therefore of the bounds). bound is instantiated in two different ways below: in module type S as a monotype and in module type S1 as 'a.

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 it 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 upper bound is the greatest upper bound of the intervals in the list, and whose lower bound is the least lower bound of the list.

Suppose you had three intervals a, b, and c:

             a:  (   )
             b:    (     )
             c:            ( )

          hull:  (           )

In this case the hull goes from lbound_exn a to ubound_exn c.

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 you think 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, map ~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, e.g., (3,4) and (4,5) would count as disjoint according to this function.

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 considers the intersection (intersect i1 i2) of every pair of intervals (i1, i2), with i1 drawn from ilist1 and i2 from ilist2, returning just the non-empty intersections. By construction these intervals will be disjoint, too. For example:

let i = Interval.create;;
list_intersect [i 4 7; i 9 15] [i 2 4; i 5 10; i 14 20];;
[(4, 4), (5, 7), (9, 10), (14, 15)]

Raises an exception if either input list is non-disjoint.

val half_open_intervals_are_a_partition : 'a t list -> bool: Returns true if the intervals, when considered as half-open intervals, nestle up cleanly one to the next. I.e., if you sort the intervals by the lower bound, then the upper bound of the nth interval is equal to the lower bound of the n+1th interval. The intervals do not need to partition the entire space, they just need to partition their union.

val create : bound -> bound -> t: create has the same type as in Gen, but adding it here prevents a type-checker issue with nongeneralizable type variables.

type 'a poly_t

val to_poly : t -> bound poly_t

type 'a poly_set

module Set : sig ... end with type 'a interval := t