packages feed

pqueue 1.3.1.1 → 1.3.2

raw patch · 8 files changed

+68/−16 lines, 8 files

Files

+ CHANGELOG.md view
@@ -0,0 +1,21 @@+# Revision history for pqueue++## 1.3.2    -- 2016-09-28++  * Add function `insertBehind` as a slight variation of `insert` which differs+    in behaviour for elements the compare equal.++## 1.3.1.1  -- 2016-05-21++  * Ensure compatibility with ghc-8+  * Minor internal refactors++## 1.3.1    -- 2015-10-03++  * Add Monoid instance for MaxPQueue++## 1.3.0    -- 2015-06-23++  * Lennart Spitzner starts co-maintaining+  * new git repository at github.com:lspitzner/pqueue+  * Ensure compatibility with ghc-7.10
Data/PQueue/Internals.hs view
@@ -15,6 +15,7 @@   minView,   singleton,   insert,+  insertBehind,   union,   mapMaybe,   mapEither,@@ -189,6 +190,11 @@ -- | Amortized /O(1)/, worst-case /O(log n)/.  Insert an element into the priority queue.   insert :: Ord a => a -> MinQueue a -> MinQueue a insert = insert' (<=)++-- | Amortized /O(1)/, worst-case /O(log n)/.  Insert an element into the priority queue,+--   putting it behind elements that compare equal to the inserted one.+insertBehind :: Ord a => a -> MinQueue a -> MinQueue a+insertBehind = insert' (<)  -- | Amortized /O(log (min(n,m)))/, worst-case /O(log (max (n,m)))/.  Take the union of two priority queues. union :: Ord a => MinQueue a -> MinQueue a -> MinQueue a
Data/PQueue/Max.hs view
@@ -41,6 +41,7 @@   -- * Construction operations   singleton,   insert,+  insertBehind,   union,   unions,   -- * Subsets@@ -187,6 +188,11 @@ -- | /O(1)/.  Insert an element into the priority queue.   insert :: Ord a => a -> MaxQueue a -> MaxQueue a x `insert` MaxQ q = MaxQ (Down x `Min.insert` q)++-- | Amortized /O(1)/, worst-case /O(log n)/.  Insert an element into the priority queue,+--   putting it behind elements that compare equal to the inserted one.+insertBehind :: Ord a => a -> MaxQueue a -> MaxQueue a+x `insertBehind` MaxQ q = MaxQ (Down x `Min.insertBehind` q)  -- | /O(log (min(n1,n2)))/.  Take the union of two priority queues. union :: Ord a => MaxQueue a -> MaxQueue a -> MaxQueue a
Data/PQueue/Min.hs view
@@ -41,6 +41,7 @@   -- * Construction operations   singleton,   insert,+  insertBehind,   union,   unions,   -- * Subsets
Data/PQueue/Prio/Internals.hs view
@@ -6,12 +6,13 @@   BinomTree(..),   Zero(..),   Succ(..),-  LEq,+  CompF,   empty,   null,   size,   singleton,   insert,+  insertBehind,   union,   getMin,   adjustMinWithKey,@@ -82,7 +83,7 @@ data Zero k a = Zero data Succ rk k a = Succ {-# UNPACK #-} !(BinomTree rk k a) (rk k a) -type LEq a = a -> a -> Bool+type CompF a = a -> a -> Bool  instance (Ord k, Eq a) => Eq (MinPQueue k a) where   MinPQ n1 k1 a1 ts1 == MinPQ n2 k2 a2 ts2 =@@ -139,8 +140,15 @@ insert :: Ord k => k -> a -> MinPQueue k a -> MinPQueue k a insert = insert' (<=) +-- | Amortized /O(1)/, worst-case /O(log n)/.  Insert an element +--   with the specified key into the priority queue,+--   putting it behind elements whos key compares equal to the+--   inserted one.+insertBehind :: Ord k => k -> a -> MinPQueue k a -> MinPQueue k a+insertBehind = insert' (<)+ -- | Internal helper method, using a specific comparator function.-insert' :: LEq k -> k -> a -> MinPQueue k a -> MinPQueue k a+insert' :: CompF k -> k -> a -> MinPQueue k a -> MinPQueue k a insert' _ k a Empty = singleton k a insert' (<=) k a (MinPQ n k' a' ts)   | k <= k'    = MinPQ (n+1) k  a  (incr (<=) (tip k' a') ts)@@ -152,7 +160,7 @@ union = union' (<=)  -- | Takes the union of the two specified queues, using the given comparison function.-union' :: LEq k -> MinPQueue k a -> MinPQueue k a -> MinPQueue k a+union' :: CompF k -> MinPQueue k a -> MinPQueue k a -> MinPQueue k a union' (<=) (MinPQ n1 k1 a1 ts1) (MinPQ n2 k2 a2 ts2)   | k1 <= k2   = MinPQ (n1 + n2) k1 a1 (insMerge k2 a2)   | otherwise  = MinPQ (n1 + n2) k2 a2 (insMerge k1 a1)@@ -242,13 +250,13 @@ tip k a = BinomTree k a Zero  -- | /O(1)/.  Takes the union of two binomial trees of the same rank.-meld :: LEq k -> BinomTree rk k a -> BinomTree rk k a -> BinomTree (Succ rk) k a+meld :: CompF k -> BinomTree rk k a -> BinomTree rk k a -> BinomTree (Succ rk) k a meld (<=) t1@(BinomTree k1 v1 ts1) t2@(BinomTree k2 v2 ts2)   | k1 <= k2   = BinomTree k1 v1 (Succ t2 ts1)   | otherwise  = BinomTree k2 v2 (Succ t1 ts2)  -- | Takes the union of two binomial forests, starting at the same rank.  Analogous to binary addition.-mergeForest :: LEq k -> BinomForest rk k a -> BinomForest rk k a -> BinomForest rk k a+mergeForest :: CompF k -> BinomForest rk k a -> BinomForest rk k a -> BinomForest rk k a mergeForest (<=) f1 f2 = case (f1, f2) of   (Skip ts1, Skip ts2)       -> Skip (mergeForest (<=) ts1 ts2)   (Skip ts1, Cons t2 ts2)    -> Cons t2 (mergeForest (<=) ts1 ts2)@@ -259,7 +267,7 @@  -- | Takes the union of two binomial forests, starting at the same rank, with an additional tree.   -- Analogous to binary addition when a digit has been carried.-carryForest :: LEq k -> BinomTree rk k a -> BinomForest rk k a -> BinomForest rk k a -> BinomForest rk k a+carryForest :: CompF k -> BinomTree rk k a -> BinomForest rk k a -> BinomForest rk k a -> BinomForest rk k a carryForest (<=) t0 f1 f2 = t0 `seq` case (f1, f2) of   (Cons t1 ts1, Cons t2 ts2) -> Cons t0 (carryMeld t1 t2 ts1 ts2)   (Cons t1 ts1, Skip ts2)    -> Skip (carryMeld t0 t1 ts1 ts2)@@ -270,7 +278,7 @@   where  carryMeld = carryForest (<=) .: meld (<=)  -- | Inserts a binomial tree into a binomial forest.  Analogous to binary incrementation.-incr :: LEq k -> BinomTree rk k a -> BinomForest rk k a -> BinomForest rk k a+incr :: CompF k -> BinomTree rk k a -> BinomForest rk k a -> BinomForest rk k a incr (<=) t ts = t `seq` case ts of   Nil         -> Cons t Nil   Skip ts'    -> Cons t ts'@@ -285,7 +293,7 @@   Skip tss'    -> Cons t tss'   Cons t' tss' -> Skip (incrMin (BinomTree k a (Succ t' ts)) tss') -extractHeap :: LEq k -> Int -> BinomHeap k a -> MinPQueue k a+extractHeap :: CompF k -> Int -> BinomHeap k a -> MinPQueue k a extractHeap (<=) n ts = n `seq` case extractForest (<=) ts of   No                      -> Empty   Yes (Extract k a _ ts') -> MinPQ (n-1) k a ts'@@ -318,8 +326,8 @@ data Extract rk k a = Extract k a (rk k a) (BinomForest rk k a) data MExtract rk k a = No | Yes {-# UNPACK #-} !(Extract rk k a) -incrExtract :: LEq k -> Maybe (BinomTree rk k a) -> Extract (Succ rk) k a -> Extract rk k a-incrExtract _    Nothing (Extract k a (Succ t ts) tss)+incrExtract :: CompF k -> Maybe (BinomTree rk k a) -> Extract (Succ rk) k a -> Extract rk k a+incrExtract _ Nothing (Extract k a (Succ t ts) tss)   = Extract k a ts (Cons t tss) incrExtract (<=) (Just t) (Extract k a (Succ t' ts) tss)   = Extract k a ts (Skip (incr (<=) (meld (<=) t t') tss))@@ -327,7 +335,7 @@ -- | Walks backward from the biggest key in the forest, as far as rank @rk@. -- Returns its progress.  Each successive application of @extractBin@ takes -- amortized /O(1)/ time, so applying it from the beginning takes /O(log n)/ time.-extractForest :: LEq k -> BinomForest rk k a -> MExtract rk k a+extractForest :: CompF k -> BinomForest rk k a -> MExtract rk k a extractForest _ Nil = No extractForest (<=) (Skip tss) = case extractForest (<=) tss of   No     -> No@@ -350,7 +358,7 @@            = Succ (BinomTree k (f k a) (fCh ts)) (fCh tss)  -- | Utility function for mapping a 'Maybe' function over a forest.-mapMaybeF :: LEq k -> (k -> a -> Maybe b) -> (rk k a -> MinPQueue k b) ->+mapMaybeF :: CompF k -> (k -> a -> Maybe b) -> (rk k a -> MinPQueue k b) ->   BinomForest rk k a -> MinPQueue k b mapMaybeF (<=) f fCh ts = case ts of   Nil    -> Empty@@ -362,7 +370,7 @@            insF k a (fCh ts) (fCh tss)  -- | Utility function for mapping an 'Either' function over a forest.-mapEitherF :: LEq k -> (k -> a -> Either b c) -> (rk k a -> (MinPQueue k b, MinPQueue k c)) ->+mapEitherF :: CompF k -> (k -> a -> Either b c) -> (rk k a -> (MinPQueue k b, MinPQueue k c)) ->   BinomForest rk k a -> (MinPQueue k b, MinPQueue k c) mapEitherF (<=) f fCh ts = case ts of   Nil    -> (Empty, Empty)
Data/PQueue/Prio/Max.hs view
@@ -37,6 +37,7 @@   empty,   singleton,   insert,+  insertBehind,   union,   unions,    -- * Query@@ -187,6 +188,11 @@ -- an element with the specified key into the queue. insert :: Ord k => k -> a -> MaxPQueue k a -> MaxPQueue k a insert k a (MaxPQ q) = MaxPQ (Q.insert (Down k) a q)++-- | Amortized /O(1)/, worst-case /O(log n)/.  Insert an element into the priority queue,+--   putting it behind elements that compare equal to the inserted one.+insertBehind :: Ord k => k -> a -> MaxPQueue k a -> MaxPQueue k a+insertBehind k a (MaxPQ q) = MaxPQ (Q.insertBehind (Down k) a q)  -- | Amortized /O(log(min(n1, n2)))/, worst-case /O(log(max(n1, n2)))/.  Returns the union -- of the two specified queues.
Data/PQueue/Prio/Min.hs view
@@ -37,6 +37,7 @@   empty,   singleton,   insert,+  insertBehind,   union,   unions,    -- * Query
pqueue.cabal view
@@ -1,5 +1,5 @@ Name:               pqueue-Version:            1.3.1.1+Version:            1.3.2 Category:           Data Structures Author:             Louis Wasserman License:            BSD3@@ -12,8 +12,11 @@ Bug-reports:        https://github.com/lspitzner/pqueue/issues Build-type:         Simple cabal-version:      >= 1.6-extra-source-files: include/Typeable.h tested-with:        GHC == 7.0.4, GHC == 7.2.2, GHC == 7.6.3, GHC == 7.8.4, GHC == 7.10.1, GHC == 8.0.1+extra-source-files: {+  include/Typeable.h+  CHANGELOG.md+}  source-repository head   type: git