Module type Interval_intf.Gen

module type Gen = sig .. end

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 ->
       [ `Above | `Below | `Interval_is_empty | `Within ]

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]

[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