packages feed

pqueue 1.3.2.3 → 1.4.1.1

raw patch · 8 files changed

+68/−28 lines, 8 filesdep ~base

Dependency ranges changed: base

Files

CHANGELOG.md view
@@ -1,5 +1,16 @@ # Revision history for pqueue +## 1.4.1.1  -- 2018-02-11++  * Remove/Replace buggy insertBehind implementation.++    The existing implementation did not always insert behind. As a fix,+    the function was removed from Data.PQueue.Max/Min and was rewritten+    with a O(n) complexity (!) for Data.PQueue.Prio.Max/Min.++  * Adapt for ghc-8.4, based on the ghc-8.4.1-alpha1 release+  * Drop support for ghc<7.4+ ## 1.3.2.3  -- 2017-08-01    * Maintenance release for ghc-8.2
Data/PQueue/Internals.hs view
@@ -15,7 +15,6 @@   minView,   singleton,   insert,-  insertBehind,   union,   mapMaybe,   mapEither,@@ -193,11 +192,6 @@ -- | 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,7 +41,6 @@   -- * Construction operations   singleton,   insert,-  insertBehind,   union,   unions,   -- * Subsets@@ -90,6 +89,10 @@ import Data.Maybe (fromMaybe) import Data.Foldable (foldl, foldr) +#if MIN_VERSION_base(4,9,0)+import Data.Semigroup (Semigroup((<>)))+#endif+ import qualified Data.PQueue.Min as Min import qualified Data.PQueue.Prio.Max.Internals as Prio import Data.PQueue.Prio.Max.Internals (Down(..))@@ -137,6 +140,11 @@     return (fromDescList xs,t) #endif +#if MIN_VERSION_base(4,9,0)+instance Ord a => Semigroup (MaxQueue a) where+  (<>) = union+#endif+ instance Ord a => Monoid (MaxQueue a) where   mempty = empty   mappend = union@@ -187,11 +195,6 @@ -- | /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,7 +41,6 @@   -- * Construction operations   singleton,   insert,-  insertBehind,   union,   unions,   -- * Subsets@@ -89,6 +88,10 @@ import Data.Foldable (foldl, foldr, foldl') import Data.Maybe (fromMaybe) +#if MIN_VERSION_base(4,9,0)+import Data.Semigroup (Semigroup((<>)))+#endif+ import qualified Data.List as List  import Data.PQueue.Internals@@ -121,6 +124,11 @@     ("fromAscList",s) <- lex r     (xs,t) <- reads s     return (fromAscList xs,t)+#endif++#if MIN_VERSION_base(4,9,0)+instance Ord a => Semigroup (MinQueue a) where+  (<>) = union #endif  instance Ord a => Monoid (MinQueue a) where
Data/PQueue/Prio/Internals.hs view
@@ -36,7 +36,7 @@ import Control.Applicative.Identity (Identity(Identity, runIdentity)) import Control.DeepSeq (NFData(rnf), deepseq) -import Data.Monoid (Monoid (..))+import Data.Monoid ((<>))  import Prelude hiding (null) @@ -105,10 +105,6 @@     (No, No) -> True     _        -> False -(<>) :: Monoid m => m -> m -> m-(<>) = mappend-infixr 6 <>- instance (Ord k, Ord a) => Ord (MinPQueue k a) where   MinPQ _n1 k10 a10 ts10 `compare` MinPQ _n2 k20 a20 ts20 =     cmpExtract k10 a10 ts10 k20 a20 ts20@@ -153,12 +149,20 @@ 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,+-- | /O(n)/ (an earlier implementation had /O(1)/ but was buggy).+--   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' (<)+insertBehind k v q =+  let (smaller, larger) = spanKey (<= k) q+  in  foldr (uncurry insert) (insert k v larger) smaller++spanKey :: Ord k => (k -> Bool) -> MinPQueue k a -> ([(k, a)], MinPQueue k a)+spanKey p q = case minViewWithKey q of+  Just (t@(k, _), q') | p k ->+    let (kas, q'') = spanKey p q' in (t : kas, q'')+  _ -> ([], q)  -- | Internal helper method, using a specific comparator function. insert' :: CompF k -> k -> a -> MinPQueue k a -> MinPQueue k a
Data/PQueue/Prio/Max.hs view
@@ -123,6 +123,10 @@ import Data.Maybe (fromMaybe) import Data.PQueue.Prio.Max.Internals +#if MIN_VERSION_base(4,9,0)+import Data.Semigroup (Semigroup((<>)))+#endif+ import Prelude hiding (map, filter, break, span, takeWhile, dropWhile, splitAt, take, drop, (!!), null, foldr, foldl)  import qualified Data.PQueue.Prio.Min as Q@@ -138,6 +142,11 @@ first' :: (a -> b) -> (a, c) -> (b, c) first' f (a, c) = (f a, c) +#if MIN_VERSION_base(4,9,0)+instance Ord k => Semigroup (MaxPQueue k a) where+  (<>) = union+#endif+ instance Ord k => Monoid (MaxPQueue k a) where   mempty = empty   mappend = union@@ -185,8 +194,10 @@ 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.+-- | /O(n)/ (an earlier implementation had /O(1)/ but was buggy).+--   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 -> MaxPQueue k a -> MaxPQueue k a insertBehind k a (MaxPQ q) = MaxPQ (Q.insertBehind (Down k) a q)
Data/PQueue/Prio/Min.hs view
@@ -125,6 +125,10 @@ import Data.Foldable (Foldable) import Data.Maybe (fromMaybe) +#if MIN_VERSION_base(4,9,0)+import Data.Semigroup (Semigroup((<>)))+#endif+ import Data.PQueue.Prio.Internals  import Prelude hiding (map, filter, break, span, takeWhile, dropWhile, splitAt, take, drop, (!!), null)@@ -146,6 +150,11 @@  infixr 8 .: +#if MIN_VERSION_base(4,9,0)+instance Ord k => Semigroup (MinPQueue k a) where+  (<>) = union+#endif+ instance Ord k => Monoid (MinPQueue k a) where   mempty = empty   mappend = union@@ -307,8 +316,8 @@ -- | Equivalent to @'spanWithKey' (\ k a -> 'not' (p k a)) q@. breakWithKey :: Ord k => (k -> a -> Bool) -> MinPQueue k a -> ([(k, a)], MinPQueue k a) spanWithKey p q = case minViewWithKey q of-  Just ((k, a), q')-    | p k a -> let (kas, q'') = spanWithKey p q' in ((k, a):kas, q'')+  Just (t@(k, a), q')+    | p k a -> let (kas, q'') = spanWithKey p q' in (t:kas, q'')   _         -> ([], q) breakWithKey p = spanWithKey (not .: p)
pqueue.cabal view
@@ -1,5 +1,5 @@ Name:               pqueue-Version:            1.3.2.3+Version:            1.4.1.1 Category:           Data Structures Author:             Louis Wasserman License:            BSD3@@ -26,7 +26,7 @@   default-language:     Haskell2010   build-depends:-  { base >= 4 && < 4.11+  { base >= 4.5 && < 4.12   , deepseq >= 1.3 && < 1.5   }   exposed-modules:@@ -64,7 +64,7 @@   Type: exitcode-stdio-1.0   Main-Is: PQueueTests.hs   Build-Depends:-  { base >= 4 && < 4.11+  { base >= 4.5 && < 4.12   , deepseq >= 1.3 && < 1.5   , QuickCheck >=2.5 && <3   }