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

functor AddRoot (Q:PRIORITY_QUEUE) : PRIORITY_QUEUE =
struct
    structure Elem = Q.Elem

    datatype T = Empty | Root of Elem.T * Q.T

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

    fun insert (y, Empty) = Root (y, Q.empty)
      | insert (y, Root (x, q)) =
          if Elem.leq (y,x) then Root (y, Q.insert (x,q))
                            else Root (x, Q.insert (y,q))
    fun meld (Empty, rq) = rq
      | meld (rq, Empty) = rq
      | meld (Root (x1,q1), Root (x2,q2)) =
          if Elem.leq (x1,x2) then Root (x1, Q.insert (x2, Q.meld (q1,q2)))
                              else Root (x2, Q.insert (x1, Q.meld (q1,q2)))

    exception EMPTY

    fun findMin Empty = raise EMPTY
      | findMin (Root (x, q)) = x
    fun deleteMin Empty = raise EMPTY
      | deleteMin (Root (x,q)) =
          if Q.isEmpty q then Empty else Root (Q.findMin q,Q.deleteMin q)
end