PriorityQueue.hs

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" ++ table
        where (table, _)  = Map.mapAccumWithKey acc "" m
              acc str (k, U) v = (str ++ "\t" ++ show v ++ " -> " ++ show k ++ "\n", v)

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