pqueue 1.6.0.0 → 1.7.0.0

raw patch · 9 files changed

+56/−80 lines, 9 filesdep ~base

Dependency ranges changed: base

Files

• CHANGELOG.md +7/−0
• pqueue.cabal +19/−22
• src/BinomialQueue/Internals.hs +6/−6
• src/Data/PQueue/Internals.hs +6/−6
• src/Data/PQueue/Max.hs +6/−6
• src/Data/PQueue/Prio/Internals.hs +6/−23
• src/Data/PQueue/Prio/Max.hs +0/−1
• src/Data/PQueue/Prio/Max/Internals.hs +6/−15
• src/Data/PQueue/Prio/Min.hs +0/−1

@@ -1,5 +1,12 @@ # Revision history for pqueue +## 1.7.0.0 -- 2026-04-16++* Remove `insertBehind` ([#145](https://github.com/lspitzner/pqueue/pull/145))++* Change `Read` and `Show` instances to use `fromList`+  ([#144](https://github.com/lspitzner/pqueue/issues/144))+ ## 1.6.0.0 -- 2025-10-11  * Deprecate `mapU` and replace it by `mapMonotonic` in `Data.PQeueu.Min` and `Data.PQueue.Max`

@@ -1,8 +1,9 @@+cabal-version:      2.2 name:               pqueue-version:            1.6.0.0+version:            1.7.0.0 category:           Data Structures author:             Louis Wasserman-license:            BSD3+license:            BSD-3-Clause license-file:       LICENSE stability:          experimental synopsis:           Reliable, persistent, fast priority queues.@@ -14,8 +15,8 @@ homepage:           https://github.com/lspitzner/pqueue bug-reports:        https://github.com/lspitzner/pqueue/issues build-type:         Simple-cabal-version:      >= 1.10 tested-with:+  GHC == 9.14.1   GHC == 9.12.2   GHC == 9.10.3   GHC == 9.8.4@@ -30,7 +31,7 @@   GHC == 8.2.2   GHC == 8.0.2 -extra-source-files:+extra-doc-files:   CHANGELOG.md   README.md @@ -43,10 +44,9 @@   default-language:     Haskell2010   build-depends:-  { base >= 4.9 && < 4.22-  , deepseq >= 1.3 && < 1.6-  , indexed-traversable >= 0.1 && < 0.2-  }+    , base >= 4.9 && < 4.23+    , deepseq >= 1.3 && < 1.6+    , indexed-traversable >= 0.1 && < 0.2   exposed-modules:     Data.PQueue.Prio.Min     Data.PQueue.Prio.Max@@ -62,9 +62,8 @@     Data.PQueue.Internals.Down     Data.PQueue.Prio.Max.Internals     Nattish-  if impl(ghc) {+  if impl(ghc)     default-extensions: DeriveDataTypeable-  }   other-extensions:       BangPatterns     , CPP@@ -82,12 +81,11 @@   type: exitcode-stdio-1.0   main-is: PQueueTests.hs   build-depends:-  { base >= 4.9 && < 4.22-  , deepseq >= 1.3 && < 1.6-  , indexed-traversable >= 0.1 && < 0.2-  , tasty-  , tasty-quickcheck-  }+    , base >= 4.9 && < 4.23+    , deepseq >= 1.3 && < 1.6+    , indexed-traversable >= 0.1 && < 0.2+    , tasty+    , tasty-quickcheck   other-modules:     Data.PQueue.Prio.Min     Data.PQueue.Prio.Max@@ -108,9 +106,8 @@     Validity.PQueue.Prio.BinomialQueue     Validity.PQueue.Prio.Min     Validity.PQueue.Prio.Max-  if impl(ghc) {+  if impl(ghc)     default-extensions: DeriveDataTypeable-  }   ghc-options:     -Wall     -fno-warn-type-defaults@@ -126,11 +123,11 @@     KWay.RandomIncreasing   ghc-options:      -O2   build-depends:-      base          >= 4.9 && < 5+    , base          >= 4.9 && < 5     , pqueue     , deepseq       >= 1.3 && < 1.6     , random        >= 1.2 && < 1.4-    , tasty-bench   >= 0.3 && < 0.5+    , tasty-bench   >= 0.3 && < 0.6  benchmark minpqueue-benchmarks   default-language: Haskell2010@@ -143,8 +140,8 @@     KWay.RandomIncreasing   ghc-options:      -O2   build-depends:-      base          >= 4.9 && < 5+    , base          >= 4.9 && < 5     , pqueue     , deepseq       >= 1.3 && < 1.6     , random        >= 1.2 && < 1.4-    , tasty-bench   >= 0.3 && < 0.5+    , tasty-bench   >= 0.3 && < 0.6

@@ -726,21 +726,21 @@  instance (Ord a, Show a) => Show (MinQueue a) where   showsPrec p xs = showParen (p > 10) $-    showString "fromAscList " . shows (toAscList xs)+    showString "fromList " . shows (toAscList xs) -instance Read a => Read (MinQueue a) where+instance (Ord a, Read a) => Read (MinQueue a) where #ifdef __GLASGOW_HASKELL__   readPrec = parens $ prec 10 $ do-    Ident "fromAscList" <- lexP+    Ident "fromList" <- lexP     xs <- readPrec-    return (fromAscList xs)+    return (fromList xs)    readListPrec = readListPrecDefault #else   readsPrec p = readParen (p > 10) $ \r -> do-    ("fromAscList",s) <- lex r+    ("fromList",s) <- lex r     (xs,t) <- reads s-    return (fromAscList xs,t)+    return (fromList xs,t) #endif  instance Ord a => Semigroup (MinQueue a) where

@@ -357,21 +357,21 @@  instance (Ord a, Show a) => Show (MinQueue a) where   showsPrec p xs = showParen (p > 10) $-    showString "fromAscList " . shows (toAscList xs)+    showString "fromList " . shows (toAscList xs) -instance Read a => Read (MinQueue a) where+instance (Ord a, Read a) => Read (MinQueue a) where #ifdef __GLASGOW_HASKELL__   readPrec = parens $ prec 10 $ do-    Ident "fromAscList" <- lexP+    Ident "fromList" <- lexP     xs <- readPrec-    return (fromAscList xs)+    return (fromList xs)    readListPrec = readListPrecDefault #else   readsPrec p = readParen (p > 10) $ \r -> do-    ("fromAscList",s) <- lex r+    ("fromList",s) <- lex r     (xs,t) <- reads s-    return (fromAscList xs,t)+    return (fromList xs,t) #endif  instance Ord a => Semigroup (MinQueue a) where

@@ -124,21 +124,21 @@  instance (Ord a, Show a) => Show (MaxQueue a) where   showsPrec p xs = showParen (p > 10) $-    showString "fromDescList " . shows (toDescList xs)+    showString "fromList " . shows (toDescList xs) -instance Read a => Read (MaxQueue a) where+instance (Ord a, Read a) => Read (MaxQueue a) where #ifdef __GLASGOW_HASKELL__   readPrec = parens $ prec 10 $ do-    Ident "fromDescList" <- lexP+    Ident "fromList" <- lexP     xs <- readPrec-    return (fromDescList xs)+    return (fromList xs)    readListPrec = readListPrecDefault #else   readsPrec p = readParen (p > 10) $ \r -> do-    ("fromDescList",s) <- lex r+    ("fromList",s) <- lex r     (xs,t) <- reads s-    return (fromDescList xs,t)+    return (fromList xs,t) #endif  instance Ord a => Semigroup (MaxQueue a) where

@@ -17,7 +17,6 @@   size,   singleton,   insert,-  insertBehind,   insertEager,   union,   getMin,@@ -130,21 +129,21 @@  instance (Ord k, Show k, Show a) => Show (MinPQueue k a) where   showsPrec p xs = showParen (p > 10) $-    showString "fromAscList " . shows (toAscList xs)+    showString "fromList " . shows (toAscList xs) -instance (Read k, Read a) => Read (MinPQueue k a) where+instance (Ord k, Read k, Read a) => Read (MinPQueue k a) where #ifdef __GLASGOW_HASKELL__   readPrec = parens $ prec 10 $ do-    Ident "fromAscList" <- lexP+    Ident "fromList" <- lexP     xs <- readPrec-    return (fromAscList xs)+    return (fromList xs)    readListPrec = readListPrecDefault #else   readsPrec p = readParen (p > 10) $ \r -> do-    ("fromAscList",s) <- lex r+    ("fromList",s) <- lex r     (xs,t) <- reads s-    return (fromAscList xs,t)+    return (fromList xs,t) #endif  -- | The union of a list of queues: (@'unions' == 'List.foldl' 'union' 'empty'@).@@ -234,22 +233,6 @@ insertEager k a (MinPQ n k' a' ts)   | k <= k' = MinPQ (n + 1) k a  (insertEagerHeap k' a' ts)   | otherwise = MinPQ (n + 1) k' a' (insertEagerHeap k a ts)---- | \(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 whose key compares equal to the--- inserted one.-{-# DEPRECATED insertBehind "This function is not reliable." #-}-insertBehind :: Ord k => k -> a -> MinPQueue k a -> MinPQueue k a-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)  -- | Amortized \(O(\log \min(n_1,n_2))\), worst-case \(O(\log \max(n_1,n_2))\). Returns the union -- of the two specified queues.

@@ -32,7 +32,6 @@   empty,   singleton,   insert,-  insertBehind,   union,   unions,   -- * Query

@@ -20,7 +20,6 @@   empty,   singleton,   insert,-  insertBehind,   union,   unions,   -- * Query@@ -162,21 +161,21 @@  instance (Ord k, Show k, Show a) => Show (MaxPQueue k a) where   showsPrec p xs = showParen (p > 10) $-    showString "fromDescList " . shows (toDescList xs)+    showString "fromList " . shows (toDescList xs) -instance (Read k, Read a) => Read (MaxPQueue k a) where+instance (Ord k, Read k, Read a) => Read (MaxPQueue k a) where #ifdef __GLASGOW_HASKELL__   readPrec = parens $ prec 10 $ do-    Ident "fromDescList" <- lexP+    Ident "fromList" <- lexP     xs <- readPrec-    return (fromDescList xs)+    return (fromList xs)    readListPrec = readListPrecDefault #else   readsPrec p = readParen (p > 10) $ \r -> do-    ("fromDescList",s) <- lex r+    ("fromList",s) <- lex r     (xs,t) <- reads s-    return (fromDescList xs,t)+    return (fromList xs,t) #endif  instance Functor (MaxPQueue k) where@@ -217,14 +216,6 @@ -- an element with the specified key into the queue. insert :: Ord k => k -> a -> MaxPQueue k a -> MaxPQueue k a insert = coerce Q.insert---- | \(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 whose key compares equal to the--- inserted one.-{-# DEPRECATED insertBehind "This function is not reliable." #-}-insertBehind :: Ord k => k -> a -> MaxPQueue k a -> MaxPQueue k a-insertBehind = coerce Q.insertBehind  -- | Amortized \(O(\log \min(n_1,n_2))\), worst-case \(O(\log \max(n_1,n_2))\). Returns the union -- of the two specified queues.

@@ -42,7 +42,6 @@   empty,   singleton,   insert,-  insertBehind,   union,   unions,   -- * Query