Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement