-- Uses list to implement a priority queue.  (Not very efficient!)
-- by Scot Drysdale on 10/16/07

module ListPriorityQueue (PriorityQueue, 
                          empty, insert, getMin, deleteMin, isEmpty)
where

type PriorityQueue a b = [(a, b)] 

-- Return an empty PQ
empty :: PriorityQueue a b
empty = []

-- Inserts new item into PQ
insert      :: (Ord a) => (a, b) -> PriorityQueue a b -> PriorityQueue a b
insert x []                   = [x]
insert new@(k,v) (p@(k1,v1) : rest) | k <= k1   = new : p : rest
                                    | otherwise = p : insert new rest

-- Returns the minimum item in PQ                                  
getMin   :: PriorityQueue a b -> (a, b)
getMin [] = error "getMin of empty priority queue"
getMin pq = head pq

-- Deletes the minimum item from PQ
deleteMin :: PriorityQueue a b -> PriorityQueue a b
deleteMin [] = error "deleteMin of empty priority queue"
deleteMin pq = tail pq

-- Returns true if empty
isEmpty   :: PriorityQueue a b -> Bool
isEmpty [] = True
isEmpty _  = False