psqueues 0.2.0.0 → 0.2.0.1
raw patch · 5 files changed
+57/−52 lines, 5 files
Files
- CHANGELOG +3/−0
- psqueues.cabal +36/−34
- src/Data/HashPSQ/Internal.hs +6/−6
- src/Data/IntPSQ/Internal.hs +7/−7
- src/Data/OrdPSQ/Internal.hs +5/−5
CHANGELOG view
@@ -1,3 +1,6 @@+- 0.2.0.1+ * Minor documentation fixes+ - 0.2.0.0 * Add convenience `deleteMin` function * Bump `deepseq` dependency to 1.4
psqueues.cabal view
@@ -1,12 +1,15 @@-name: psqueues-version: 0.2.0.0-license: BSD3-license-file: LICENSE-maintainer: haskell@better.com-bug-reports: https://github.com/bttr/psqueues/issues-synopsis: Pure priority search queues-category: Data Structures-description:+Name: psqueues+Version: 0.2.0.1+License: BSD3+License-file: LICENSE+Maintainer: Jasper Van der Jeugt <jaspervdj@gmail.com>+Bug-reports: https://github.com/bttr/psqueues/issues+Synopsis: Pure priority search queues+Category: Data Structures+Build-type: Simple+Cabal-version: >=1.8++Description: The psqueues package provides <http://en.wikipedia.org/wiki/Priority_queue Priority Search Queues> in three different flavors.@@ -19,8 +22,8 @@ considerably faster and provides a slightly different API. . * @IntPSQ p v@ is a far more efficient implementation. It fixes the key type- to @Int@ and uses a <http://en.wikipedia.org/wiki/Radix_tree radix tree>- (like @IntMap@) with an additional min-heap property.+ to @Int@ and uses a <http://en.wikipedia.org/wiki/Radix_tree radix tree>+ (like @IntMap@) with an additional min-heap property. . * @HashPSQ k p v@ is a fairly straightforward extension of @IntPSQ@: it simply uses the keys' hashes as indices in the @IntPSQ@. If there are any@@ -48,44 +51,43 @@ * Schedulers; . * Pathfinding algorithms, such as Dijkstra's and A*.-build-type: Simple-cabal-version: >=1.8-extra-source-files:++Extra-source-files: CHANGELOG -source-repository head+Source-repository head type: git location: http://github.com/bttr/psqueues.git Library- ghc-options: -O2 -Wall- hs-source-dirs: src+ Ghc-options: -O2 -Wall+ Hs-source-dirs: src - build-depends:+ Build-depends: base >= 4.2 && < 5 , deepseq >= 1.2 && < 1.5 , hashable >= 1.2.1 && < 1.3 if impl(ghc>=6.10)- build-depends: ghc-prim+ Build-depends: ghc-prim - exposed-modules:+ Exposed-modules: Data.HashPSQ Data.IntPSQ Data.OrdPSQ- other-modules:+ Other-modules: Data.BitUtil Data.HashPSQ.Internal Data.IntPSQ.Internal Data.OrdPSQ.Internal -benchmark psqueues-benchmarks- type: exitcode-stdio-1.0- hs-source-dirs: src benchmarks- main-is: Main.hs- ghc-options: -Wall+Benchmark psqueues-benchmarks+ Type: exitcode-stdio-1.0+ Hs-source-dirs: src benchmarks+ Main-is: Main.hs+ Ghc-options: -Wall - build-depends:+ Build-depends: containers >= 0.5 , unordered-containers >= 0.2.4 , criterion >= 0.8@@ -101,13 +103,13 @@ , psqueues Test-suite psqueues-tests- cpp-options: -DTESTING -DSTRICT- ghc-options: -Wall- hs-source-dirs: src tests- main-is: Main.hs- type: exitcode-stdio-1.0+ Cpp-options: -DTESTING -DSTRICT+ Ghc-options: -Wall+ Hs-source-dirs: src tests+ Main-is: Main.hs+ Type: exitcode-stdio-1.0 - other-modules:+ Other-modules: Data.PSQ.Class Data.PSQ.Class.Gen Data.PSQ.Class.Tests@@ -116,7 +118,7 @@ Data.IntPSQ.Tests Data.OrdPSQ.Tests - build-depends:+ Build-depends: HUnit >= 1.2 && < 1.3 , QuickCheck >= 2.7 && < 2.8 , test-framework >= 0.8 && < 0.9
src/Data/HashPSQ/Internal.hs view
@@ -168,7 +168,7 @@ -- Insertion -------------------------------------------------------------------------------- --- | /O(min(n,W))/ Insert a new key, priority and value in the queue. If the key+-- | /O(min(n,W))/ Insert a new key, priority and value into the queue. If the key -- is already present in the queue, the associated priority and value are -- replaced with the supplied priority and value. {-# INLINABLE insert #-}@@ -207,7 +207,7 @@ Nothing -> t Just (_, _, t') -> t' --- | /O(min(n,W))/ Delete the binding with the least priority, and return+-- | /O(min(n,W))/ Delete the binding with the least priority, and return the -- rest of the queue stripped of that binding. In case the queue is empty, the -- empty queue is returned again. {-# INLINE deleteMin #-}@@ -217,7 +217,7 @@ Nothing -> t Just (_, _, _, t') -> t' --- | /O(min(n,W))/ The expression @alter f k map@ alters the value @x@ at @k@,+-- | /O(min(n,W))/ The expression @alter f k queue@ alters the value @x@ at @k@, -- or absence thereof. 'alter' can be used to insert, delete, or update a value -- in a queue. It also allows you to calculate an additional value @b@. {-# INLINABLE alter #-}@@ -294,7 +294,7 @@ -- Views -------------------------------------------------------------------------------- --- | /O(min(n,W))/ Insert a new key, priority and value in the queue. If the key+-- | /O(min(n,W))/ Insert a new key, priority and value into the queue. If the key -- is already present in the queue, then the evicted priority and value can be -- found the first element of the returned tuple. {-# INLINABLE insertView #-}@@ -358,7 +358,7 @@ where mapBucket p (B k v opsq) = B k (f k p v) (OrdPSQ.map f opsq) --- | /O(n)/ Strict fold over every key, priority and value in the map. The order+-- | /O(n)/ Strict fold over every key, priority and value in the queue. The order -- in which the fold is performed is not specified. {-# INLINABLE fold' #-} fold' :: (k -> p -> v -> a -> a) -> a -> HashPSQ k p v -> a@@ -438,7 +438,7 @@ -- Validity check -------------------------------------------------------------------------------- --- | /O(n^2)/ Internal function to check if the 'OrdPSQ' is valid, i.e. if all+-- | /O(n^2)/ Internal function to check if the 'HashPSQ' is valid, i.e. if all -- invariants hold. This should always be the case. valid :: (Hashable k, Ord k, Ord p) => HashPSQ k p v -> Bool valid t@(HashPSQ ipsq) =
src/Data/IntPSQ/Internal.hs view
@@ -170,7 +170,7 @@ null Nil = True null _ = False --- | /O(n)/ The number of elements stored in the PSQ.+-- | /O(n)/ The number of elements stored in the queue. size :: IntPSQ p v -> Int size Nil = 0 size (Tip _ _ _) = 1@@ -224,7 +224,7 @@ -- Insertion ------------------------------------------------------------------------------ --- | /O(min(n,W))/ Insert a new key, priority and value in the queue. If the key+-- | /O(min(n,W))/ Insert a new key, priority and value into the queue. If the key -- is already present in the queue, the associated priority and value are -- replaced with the supplied priority and value. insert :: Ord p => Int -> p -> v -> IntPSQ p v -> IntPSQ p v@@ -292,7 +292,7 @@ | zero k m -> binShrinkL k' p' x' m (go l) r | otherwise -> binShrinkR k' p' x' m l (go r) --- | /O(min(n,W))/ Delete the binding with the least priority, and return+-- | /O(min(n,W))/ Delete the binding with the least priority, and return the -- rest of the queue stripped of that binding. In case the queue is empty, the -- empty queue is returned again. {-# INLINE deleteMin #-}@@ -301,7 +301,7 @@ Nothing -> t Just (_, _, _, t') -> t' --- | /O(min(n,W))/ The expression @alter f k map@ alters the value @x@ at @k@,+-- | /O(min(n,W))/ The expression @alter f k queue@ alters the value @x@ at @k@, -- or absence thereof. 'alter' can be used to insert, delete, or update a value -- in a queue. It also allows you to calculate an additional value @b@. {-# INLINE alter #-}@@ -389,7 +389,7 @@ -- Views ------------------------------------------------------------------------------ --- | /O(min(n,W))/ Insert a new key, priority and value in the queue. If the key+-- | /O(min(n,W))/ Insert a new key, priority and value into the queue. If the key -- is already present in the queue, then the evicted priority and value can be -- found the first element of the returned tuple. insertView :: Ord p => Int -> p -> v -> IntPSQ p v -> (Maybe (p, v), IntPSQ p v)@@ -452,7 +452,7 @@ Tip k p x -> Tip k p (f k p x) Bin k p x m l r -> Bin k p (f k p x) m (go l) (go r) --- | /O(n)/ Strict fold over every key, priority and value in the map. The order+-- | /O(n)/ Strict fold over every key, priority and value in the queue. The order -- in which the fold is performed is not specified. {-# INLINABLE fold' #-} fold' :: (Int -> p -> v -> a -> a) -> a -> IntPSQ p v -> a@@ -633,7 +633,7 @@ -- Validity checks for the datastructure invariants ------------------------------------------------------------------------------ --- | /O(n^2)/ Internal function to check if the 'OrdPSQ' is valid, i.e. if all+-- | /O(n^2)/ Internal function to check if the 'IntPSQ' is valid, i.e. if all -- invariants hold. This should always be the case. valid :: Ord p => IntPSQ p v -> Bool valid psq =
src/Data/OrdPSQ/Internal.hs view
@@ -191,7 +191,7 @@ -- Insertion -------------------------------------------------------------------------------- --- | /O(log n)/ Insert a new key, priority and value in the queue. If the key is+-- | /O(log n)/ Insert a new key, priority and value into the queue. If the key is -- already present in the queue, the associated priority and value are replaced -- with the supplied priority and value. {-# INLINABLE insert #-}@@ -234,7 +234,7 @@ | k <= m -> go (Winner e' tl m) `play` (Winner e tr m') | otherwise -> (Winner e' tl m) `play` go (Winner e tr m') --- | /O(log n)/ Delete the binding with the least priority, and return+-- | /O(log n)/ Delete the binding with the least priority, and return the -- rest of the queue stripped of that binding. In case the queue is empty, the -- empty queue is returned again. {-# INLINE deleteMin #-}@@ -244,7 +244,7 @@ Nothing -> t Just (_, _, _, t') -> t' --- | /O(log n)/ The expression @alter f k map@ alters the value @x@ at @k@, or+-- | /O(log n)/ The expression @alter f k queue@ alters the value @x@ at @k@, or -- absence thereof. 'alter' can be used to insert, delete, or update a value -- in a queue. It also allows you to calculate an additional value @b@. {-# INLINE alter #-}@@ -318,7 +318,7 @@ -- Views -------------------------------------------------------------------------------- --- | /O(log n)/ Insert a new key, priority and value in the queue. If the key is+-- | /O(log n)/ Insert a new key, priority and value into the queue. If the key is -- already present in the queue, then the evicted priority and value can be -- found the first element of the returned tuple. {-# INLINABLE insertView #-}@@ -382,7 +382,7 @@ goLTree (RLoser s e l k r) = RLoser s (goElem e) (goLTree l) k (goLTree r) --- | /O(n)/ Strict fold over every key, priority and value in the map. The order+-- | /O(n)/ Strict fold over every key, priority and value in the queue. The order -- in which the fold is performed is not specified. {-# INLINE fold' #-} fold' :: (k -> p -> v -> a -> a) -> a -> OrdPSQ k p v -> a