priority-queue 0.1 → 0.1.1

raw patch · 2 files changed

+39/−7 lines, 2 files

Files

• priority-queue.cabal +1/−1
• src/Data/PriorityQueue.hs +38/−6

@@ -1,5 +1,5 @@ name:                   priority-queue-version:                0.1+version:                0.1.1 stability:              provisional license:                BSD3 license-file:           LICENSE

@@ -34,6 +34,11 @@         , PeekQueue(..)         , QueueSize(..)         +        , PQ+        , emptyPQ+        , mkPriorityQueue+        , mkDefaultPriorityQueue+                 , PriorityQueue         , newPriorityQueue         , newPriorityQueueBy@@ -53,11 +58,28 @@            , queue              :: M.Map p [a]            } +-- |A new empty 'PQ'+emptyPQ :: Ord p => (a -> p) -> PQ a+emptyPQ f = PQ f M.empty++-- |A priority queue usable in the monad 'm' with values of type 'a' data PriorityQueue m a = -    forall sr. ( DefaultStateRef sr m (PQ a)-               , ModifyRef sr m (PQ a) +    forall sr. ( ModifyRef sr m (PQ a)                 ) => PriorityQueue sr +-- |Build a priority queue from a modifiable reference containing+--  a 'PQ'+mkPriorityQueue :: ModifyRef sr m (PQ a) => sr -> PriorityQueue m a+mkPriorityQueue = PriorityQueue++-- |Build a priority queue using an instance of the default modifiable +--  reference for the requested monad and value type+mkDefaultPriorityQueue :: +        ( DefaultStateRef sr m (PQ a)+        , ModifyRef sr m (PQ a)+        ) => sr -> PriorityQueue m a+mkDefaultPriorityQueue = PriorityQueue+ -- |Construct a new priority queue using the specified indexing function newPriorityQueue ::          ( DefaultStateRef sr m1 (PQ a)@@ -66,11 +88,12 @@         , Ord p         ) => (a -> p) -> m (PriorityQueue m1 a) newPriorityQueue f = do-        pq <- newRef (PQ f M.empty)-        return (PriorityQueue pq)+        pq <- newRef (emptyPQ f)+        +        return (mkDefaultPriorityQueue pq)  -- |Construct a new priority queue using a comparator function.  It is ---  the user's respensibility to ensure that this function provides a+--  the user's responsibility to ensure that this function provides a --  sensible order. newPriorityQueueBy ::          ( DefaultStateRef sr m1 (PQ a)@@ -93,6 +116,15 @@                                         dq (PQ f pq')                                 Just ((k,[i]), pq')     -> (PQ f pq', Just i)                                 Just ((k,i:is), pq')    -> (PQ f (M.insert k is pq'), Just i)+        +        dequeueBatch q@(PriorityQueue pqRef) = atomicModifyRef pqRef dq+                where +                        dq orig@(PQ f pq) = case M.minView pq of+                                Nothing         -> (orig, [])+                                Just ([], pq')  -> +                                        -- this should never happen+                                        dq (PQ f pq')+                                Just (xs, pq')  -> (PQ f pq', xs)  -- quick hack; there's probably a more efficient (and/or less ugly) way to do this instance Monad m => DequeueWhere (PriorityQueue m a) m a where@@ -123,7 +155,7 @@  -- |local version of minViewWithKey, because some versions of Data.Map --  don't have it.-minViewWithKey :: (Monad m) => M.Map k a -> m ((k, a), M.Map k a)+minViewWithKey :: M.Map k a -> Maybe ((k, a), M.Map k a)  #ifdef NoMinViewWithKey minViewWithKey m = if M.null m