PriorityQueue.hs

module PriorityQueue where

import Data.Map (Map)
import qualified Data.Map as Map

data Unique = U

instance Eq Unique where
    U == U = False

instance Ord Unique where
    compare U U = LT

data PriorityQueue k v = PriorityQueue (v -> k) (Map (k, Unique) v)

-- instance (Ord k, Show k, Show v) => Show (PriorityQueue k v) where
--     show (PriorityQueue _ m) = "PriorityQueue\n" ++
--         unlines (map (\(k, U) -> "\t" ++ show (m Map.! k) ++ " -> " ++ show k) keys)
--         where keys = Map.keys m

empty :: Ord k => (v -> k) -> PriorityQueue k v
empty k = PriorityQueue k Map.empty

insert :: Ord k => v -> PriorityQueue k v -> PriorityQueue k v
insert v (PriorityQueue k m) = PriorityQueue k (Map.insert (k v, U) v m)

findMin :: Ord k => PriorityQueue k v -> (k, v)
findMin (PriorityQueue _ m) = let ((k, _), v) = Map.findMin m in (k, v)

deleteMin :: Ord k => PriorityQueue k v -> PriorityQueue k v
deleteMin (PriorityQueue k m) = PriorityQueue k (Map.deleteMin m)

minView :: Ord k => PriorityQueue k v -> ((k, v), PriorityQueue k v)
minView p = (findMin p, deleteMin p)

size :: Ord k => PriorityQueue k v -> Int
size (PriorityQueue _ m) = Map.size m

null :: Ord k => PriorityQueue k v -> Bool
null (PriorityQueue _ m) = Map.null m