module List : sig
    type 'a t
end

module type Comparable = sig
    type t
    val compare : t -> t -> int
end

module Make_interval(Endpoint : Comparable) = struct
    type t =
        | Interval of Endpoint.t * Endpoint.t
        | Empty

    let create low high =
        if Endpoint.compare low high > 0 then Empty else Interval (low,high)

    let is_empty = function
        | Empty -> true
        | Interval _ -> false

    let contains t x =
        let compare = Endpoint.compare in
        match t with
        | Empty -> false
        | Interval (l,h) ->
                compare x l >= 0 && compare x h <= 0

    let intersect t1 t2 =
        let min x y = if Endpoint.compare x y <= 0 then x else y in
        let max x y = if Endpoint.compare x y >= 0 then x else y in
        match t1, t2 with
        | Empty, _ | _, Empty -> Empty
        | Interval (l1,h1), Interval (l2,h2) ->
                create (max l1 l2) (min h1 h2)
end

module Int = struct
    let compare x y =
        if x = y then 0
        else if x > y then 1
        else -1
end

module Int_interval = Make_interval(struct
    type t = int
    let compare = Int.compare
end);;