-------------------------------------------------
-- PQueue.hs                                   --
-------------------------------------------------
-- Implementation des ADT Prioritätsschlange   --
-- Priorität wird durch Typ Int repräsentiert, --
-- wobei niedere Werte eine hörere Priorität   --
-- besitzen.                                   --
-------------------------------------------------

module PQueue (frontp, front, dequeue, PQueue(CreatePQueue, Enqueue)) where


-- Datentyp
data PQueue a = CreatePQueue | Enqueue (PQueue a) (a, Int) deriving ( Eq, Show )

-- Signatur:
front    :: (PQueue a) -> a
frontp   :: (PQueue a) -> Int
dequeue  :: (PQueue a) -> (PQueue a)
priority :: (PQueue a) -> Int

--Axiome:
front (Enqueue CreatePQueue (x, p))    = x
front (Enqueue s (x, p))
  | priority s > p                     = x
  | otherwise                          = front s
  
frontp (Enqueue CreatePQueue (x, p))   = p
frontp (Enqueue s (x, p))
  | priority s > p                     = p
  | otherwise                          = frontp s
                         
dequeue (Enqueue CreatePQueue (x, p))  = CreatePQueue
dequeue (Enqueue s (x, p))
  | priority s > p                     = s
  | otherwise                          = Enqueue (dequeue s) (x, p)
                           
priority (Enqueue CreatePQueue (x, p)) = p
priority (Enqueue s (x, p))            = min p (priority s)