psqueues 0.1.1.0 → 0.2.0.0

raw patch · 10 files changed

+65/−5 lines, 10 filesdep ~basedep ~deepseq

Dependency ranges changed: base, deepseq

Files

• CHANGELOG +4/−0
• psqueues.cabal +2/−2
• src/Data/HashPSQ.hs +1/−0
• src/Data/HashPSQ/Internal.hs +12/−1
• src/Data/IntPSQ.hs +1/−0
• src/Data/IntPSQ/Internal.hs +11/−1
• src/Data/OrdPSQ.hs +1/−0
• src/Data/OrdPSQ/Internal.hs +12/−1
• tests/Data/PSQ/Class.hs +5/−0
• tests/Data/PSQ/Class/Tests.hs +16/−0

@@ -1,3 +1,7 @@+- 0.2.0.0+    * Add convenience `deleteMin` function+    * Bump `deepseq` dependency to 1.4+ - 0.1.1.0     * Remove constraints from `size` 

@@ -1,5 +1,5 @@ name: psqueues-version: 0.1.1.0+version: 0.2.0.0 license: BSD3 license-file: LICENSE maintainer: haskell@better.com@@ -63,7 +63,7 @@      build-depends:           base     >= 4.2   && < 5-        , deepseq  >= 1.2   && < 1.4+        , deepseq  >= 1.2   && < 1.5         , hashable >= 1.2.1 && < 1.3      if impl(ghc>=6.10)

@@ -24,6 +24,7 @@        -- * Delete/update     , delete+    , deleteMin     , alter     , alterMin 

@@ -23,6 +23,7 @@        -- * Delete/update     , delete+    , deleteMin     , alter     , alterMin @@ -206,6 +207,16 @@     Nothing         -> t     Just (_, _, t') -> t' +-- | /O(min(n,W))/ Delete the binding with the least priority, and return+-- rest of the queue stripped of that binding. In case the queue is empty, the+-- empty queue is returned again.+{-# INLINE deleteMin #-}+deleteMin+    :: (Hashable k, Ord k, Ord p) => HashPSQ k p v -> HashPSQ k p v+deleteMin t = case minView t of+    Nothing            -> t+    Just (_, _, _, t') -> t'+ -- | /O(min(n,W))/ The expression @alter f k map@ 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@.@@ -340,7 +351,7 @@ -- Traversals -------------------------------------------------------------------------------- --- | /O(n)/ Modify every value in the queueu.+-- | /O(n)/ Modify every value in the queue. {-# INLINABLE map #-} map :: (k -> p -> v -> w) -> HashPSQ k p v -> HashPSQ k p w map f (HashPSQ ipsq) = HashPSQ (IntPSQ.map (\_ p v -> mapBucket p v) ipsq)

@@ -27,6 +27,7 @@        -- * Delete/update     , delete+    , deleteMin     , alter     , alterMin 

@@ -24,6 +24,7 @@        -- * Delete/update     , delete+    , deleteMin     , alter     , alterMin @@ -291,6 +292,15 @@           | 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+-- rest of the queue stripped of that binding. In case the queue is empty, the+-- empty queue is returned again.+{-# INLINE deleteMin #-}+deleteMin :: Ord p => IntPSQ p v -> IntPSQ p v+deleteMin t = case minView t of+    Nothing            -> t+    Just (_, _, _, t') -> t'+ -- | /O(min(n,W))/ The expression @alter f k map@ 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@.@@ -431,7 +441,7 @@ -- Traversal ------------------------------------------------------------------------------ --- | /O(n)/ Modify every value in the queueu.+-- | /O(n)/ Modify every value in the queue. {-# INLINABLE map #-} map :: (Int -> p -> v -> w) -> IntPSQ p v -> IntPSQ p w map f =

@@ -34,6 +34,7 @@        -- * Delete/Update     , delete+    , deleteMin     , alter     , alterMin 

@@ -23,6 +23,7 @@        -- * Delete/Update     , delete+    , deleteMin     , alter     , alterMin @@ -233,6 +234,16 @@             | 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+-- rest of the queue stripped of that binding. In case the queue is empty, the+-- empty queue is returned again.+{-# INLINE deleteMin #-}+deleteMin+    :: (Ord k, Ord p) => OrdPSQ k p v -> OrdPSQ k p v+deleteMin t = case minView t of+    Nothing            -> t+    Just (_, _, _, t') -> t'+ -- | /O(log n)/ The expression @alter f k map@ 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@.@@ -352,7 +363,7 @@ -- Traversals -------------------------------------------------------------------------------- --- | /O(n)/ Modify every value in the queueu.+-- | /O(n)/ Modify every value in the queue. {-# INLINABLE map #-} map :: forall k p v w. (k -> p -> v -> w) -> OrdPSQ k p v -> OrdPSQ k p w map f =

@@ -42,6 +42,8 @@     -- Delete/update     delete         :: Ord p => Key psq -> psq p v -> psq p v+    deleteMin+        :: Ord p => psq p v -> psq p v     alter         :: Ord p         => (Maybe (p, v) -> (b, Maybe (p, v)))@@ -88,6 +90,7 @@     singleton  = IntPSQ.singleton     insert     = IntPSQ.insert     delete     = IntPSQ.delete+    deleteMin  = IntPSQ.deleteMin     alter      = IntPSQ.alter     alterMin   = IntPSQ.alterMin     fromList   = IntPSQ.fromList@@ -112,6 +115,7 @@     singleton  = OrdPSQ.singleton     insert     = OrdPSQ.insert     delete     = OrdPSQ.delete+    deleteMin  = OrdPSQ.deleteMin     alter      = OrdPSQ.alter     alterMin   = OrdPSQ.alterMin     fromList   = OrdPSQ.fromList@@ -136,6 +140,7 @@     singleton  = HashPSQ.singleton     insert     = HashPSQ.insert     delete     = HashPSQ.delete+    deleteMin  = HashPSQ.deleteMin     alter      = HashPSQ.alter     alterMin   = HashPSQ.alterMin     fromList   = HashPSQ.fromList

@@ -61,6 +61,7 @@     , testProperty "insertDelete"     (untag' prop_insertDelete)     , testProperty "insertDeleteView" (untag' prop_insertDeleteView)     , testProperty "deleteNonMember"  (untag' prop_deleteNonMember)+    , testProperty "deleteMin"        (untag' prop_deleteMin)     , testProperty "alter"            (untag' prop_alter)     , testProperty "alterMin"         (untag' prop_alterMin)     , testProperty "toList"           (untag' prop_toList)@@ -287,6 +288,21 @@ prop_deleteNonMember = Tagged $ \t ->     forAll arbitraryTestKey $ \k ->         (lookup k t == Nothing) ==> (delete k t == (t :: psq Int Char))++prop_deleteMin+    :: forall psq. (PSQ psq, TestKey (Key psq),+                    Arbitrary (psq Int Char),+                    Eq (psq Int Char),+                    Show (psq Int Char))+    => Tagged psq (psq Int Char -> Bool)+prop_deleteMin = Tagged $ \t ->+    let t' = deleteMin t+    in if null t+        then t' == t+        else case findMin t of+                Nothing        -> False+                Just (k, _, _) ->+                    size t' == size t - 1 && member k t && not (member k t')  prop_alter     :: forall psq. (PSQ psq, TestKey (Key psq),