(* Chris Okasaki
   School of Computer Science
   Carnegie Mellon University
   Pittsburgh, PA 15213
   cokasaki@cs.cmu.edu *)

functor Bootstrap (functor MakeQ (E:ORDERED) : sig
                                                 include PRIORITY_QUEUE
                                                 sharing Elem = E
                                               end)
                  (E:ORDERED) : PRIORITY_QUEUE =
struct
  structure Elem = E

  (* recursive structures not supported in SML! *)
  structure rec RootedQ =
      struct
        datatype T = Root of Elem.T * Q.T
        fun leq (Root (x1,q1), Root (x2,q2)) = Elem.leq (x1,x2)
      end
  and Q = MakeQ (RootedQ) 

  open RootedQ  (* expose Root constructor *)

  datatype T = Empty | NonEmpty of RootedQ.T

  val empty = Empty
  fun isEmpty Empty = true
    | isEmpty (NonEmpty _) = false

  fun insert (x, xs) = meld (NonEmpty (Root (x, Q.empty)), xs)
  and meld (Empty, xs) = xs
    | meld (xs, Empty) = xs
    | meld (NonEmpty (r1 as Root (x1,q1)), NonEmpty (r2 as Root (x2,q2))) =
        if Elem.leq (x1,x2) then NonEmpty (Root (x1,Q.insert (r2,q1)))
                            else NonEmpty (Root (x2,Q.insert (r1,q2)))

  exception EMPTY

  fun findMin Empty = raise EMPTY
    | findMin (NonEmpty (Root (x,q))) = x
  fun deleteMin Empty = raise EMPTY
    | deleteMin (NonEmpty (Root (x,q))) =
        if Q.isEmpty q then Empty
        else let val (Root (y,q1)) = Q.findMin q
                 val q2 = Q.deleteMin q
             in NonEmpty (Root (y,Q.meld (q1,q2))) end
end