ordered.ml

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

module type HEAP =
sig
  module Elem : ORDERED

  type heap

  val empty : heap
  val insert : Elem.t -> heap -> heap
  val find_min : heap -> Elem.t
  val delete_min : heap -> heap
end

module SomeHeap (Element : ORDERED) : (HEAP with module Elem = Element) =
struct
  module Elem = Element

  type heap

  let empty = failwith "skipped"
  let insert = failwith "skipped"
  let find_min = failwith "skipped"
  let delete_min = failwith "skipped"
end

module BootstrappedHeap
  (MakeH : functor (Element : ORDERED) -> HEAP with module Elem = Element)
  (Element : ORDERED) : (HEAP with module Elem = Element) =
struct
  module Elem = Element

  module rec BootstrappedElem :
  sig
    type t =
      | E
      | H of Elem.t * PrimH.heap
    val compare : t -> t -> int
  end =
  struct
    type t =
      | E
      | H of Elem.t * PrimH.heap
    let compare t1 t2 = match t1, t2 with
      | H (x, _), H (y, _) -> Elem.compare x y
      | _ -> failwith "unreachable"
  end
  and PrimH : (HEAP with module Elem = BootstrappedElem) =
    MakeH(BootstrappedElem)

  type heap

  let empty = failwith "not implemented"
  let insert = failwith "not implemented"
  let find_min = failwith "not implemented"
  let delete_min = failwith "not implemented"
end