psqueues 0.2.0.3 → 0.2.1.0
raw patch · 5 files changed
+40/−59 lines, 5 filesdep ~basePVP: major bump suggested
API removals or changes: PVP suggests a major version bump
Dependency ranges changed: base
API changes (from Hackage documentation)
- Data.OrdPSQ: lookup :: Ord k => k -> OrdPSQ k p v -> Maybe (p, v)
+ Data.OrdPSQ: lookup :: (Ord k) => k -> OrdPSQ k p v -> Maybe (p, v)
Files
- CHANGELOG +3/−0
- psqueues.cabal +1/−1
- src/Data/HashPSQ/Internal.hs +10/−16
- src/Data/IntPSQ/Internal.hs +16/−23
- src/Data/OrdPSQ/Internal.hs +10/−19
CHANGELOG view
@@ -1,3 +1,6 @@+- 0.2.1.0+ * Add Traversable instances+ - 0.2.0.3 * Bump HUnit dependency bounds
psqueues.cabal view
@@ -1,5 +1,5 @@ Name: psqueues-Version: 0.2.0.3+Version: 0.2.1.0 License: BSD3 License-file: LICENSE Maintainer: Jasper Van der Jeugt <jaspervdj@gmail.com>
src/Data/HashPSQ/Internal.hs view
@@ -1,4 +1,7 @@ {-# LANGUAGE BangPatterns #-}+{-# LANGUAGE DeriveFoldable #-}+{-# LANGUAGE DeriveFunctor #-}+{-# LANGUAGE DeriveTraversable #-} {-# LANGUAGE GeneralizedNewtypeDeriving #-} {-# LANGUAGE ScopedTypeVariables #-} module Data.HashPSQ.Internal@@ -50,12 +53,12 @@ , valid ) where -import Control.DeepSeq (NFData (..))-import Data.Foldable (Foldable (foldr))+import Control.DeepSeq (NFData (..))+import Data.Foldable (Foldable (foldr)) import Data.Hashable-import Data.Maybe (isJust)-import Prelude hiding (foldr, lookup, map, null)-import qualified Data.List as List+import qualified Data.List as List+import Data.Maybe (isJust)+import Prelude hiding (foldr, lookup, map, null) import qualified Data.IntPSQ.Internal as IntPSQ import qualified Data.OrdPSQ as OrdPSQ@@ -65,7 +68,7 @@ ------------------------------------------------------------------------------ data Bucket k p v = B !k !v !(OrdPSQ.OrdPSQ k p v)- deriving (Show)+ deriving (Foldable, Functor, Show, Traversable) -- | Smart constructor which takes care of placing the minimum element directly -- in the 'Bucket'.@@ -91,7 +94,7 @@ -- | A priority search queue with keys of type @k@ and priorities of type @p@ -- and values of type @v@. It is strict in keys, priorities and values. newtype HashPSQ k p v = HashPSQ (IntPSQ.IntPSQ p (Bucket k p v))- deriving (NFData, Show)+ deriving (Foldable, Functor, NFData, Show, Traversable) instance (Eq k, Eq p, Eq v, Hashable k, Ord k, Ord p) => Eq (HashPSQ k p v) where@@ -101,15 +104,6 @@ xk == yk && xp == yp && xv == yv && x' == y' (Just _ , Nothing ) -> False (Nothing , Just _ ) -> False--instance Foldable (HashPSQ k p) where- foldr f z0 (HashPSQ ipsq) =- foldr f' z0 ipsq- where- f' (B _ x opsq) z = f x (foldr f z opsq)--instance Functor (HashPSQ k p) where- fmap f = map (\_ _ v -> f v) ------------------------------------------------------------------------------
src/Data/IntPSQ/Internal.hs view
@@ -1,6 +1,9 @@-{-# LANGUAGE BangPatterns #-}-{-# LANGUAGE CPP #-}-{-# LANGUAGE UnboxedTuples #-}+{-# LANGUAGE BangPatterns #-}+{-# LANGUAGE CPP #-}+{-# LANGUAGE DeriveFoldable #-}+{-# LANGUAGE DeriveFunctor #-}+{-# LANGUAGE DeriveTraversable #-}+{-# LANGUAGE UnboxedTuples #-} module Data.IntPSQ.Internal ( -- * Type Nat@@ -58,19 +61,20 @@ , validMask ) where -import Control.DeepSeq (NFData(rnf)) import Control.Applicative ((<$>), (<*>))+import Control.DeepSeq (NFData (rnf)) -import Data.BitUtil import Data.Bits-import Data.List (foldl')-import Data.Maybe (isJust)-import Data.Word (Word)-import Data.Foldable (Foldable (foldr))+import Data.BitUtil+import Data.Foldable (Foldable (foldr))+import Data.List (foldl')+import Data.Maybe (isJust)+import Data.Word (Word) -import qualified Data.List as List+import qualified Data.List as List -import Prelude hiding (lookup, map, filter, foldr, foldl, null)+import Prelude hiding (filter, foldl, foldr, lookup, map,+ null) -- TODO (SM): get rid of bang patterns @@ -101,7 +105,7 @@ = Bin {-# UNPACK #-} !Key !p !v {-# UNPACK #-} !Mask !(IntPSQ p v) !(IntPSQ p v) | Tip {-# UNPACK #-} !Key !p !v | Nil- deriving (Show)+ deriving (Foldable, Functor, Show, Traversable) instance (NFData p, NFData v) => NFData (IntPSQ p v) where rnf (Bin _k p v _m l r) = rnf p `seq` rnf v `seq` rnf l `seq` rnf r@@ -115,17 +119,6 @@ xk == yk && xp == yp && xv == yv && x' == y' (Just _ , Nothing ) -> False (Nothing , Just _ ) -> False--instance Foldable (IntPSQ p) where- foldr _ z Nil = z- foldr f z (Tip _ _ v) = f v z- foldr f z (Bin _ _ v _ l r) = f v z''- where- z' = foldr f z l- z'' = foldr f z' r--instance Functor (IntPSQ p) where- fmap f = map (\_ _ v -> f v) -- bit twiddling
src/Data/OrdPSQ/Internal.hs view
@@ -1,6 +1,9 @@+{-# LANGUAGE BangPatterns #-}+{-# LANGUAGE DeriveFoldable #-}+{-# LANGUAGE DeriveFunctor #-}+{-# LANGUAGE DeriveTraversable #-} {-# LANGUAGE ScopedTypeVariables #-} {-# LANGUAGE Trustworthy #-}-{-# LANGUAGE BangPatterns #-} module Data.OrdPSQ.Internal ( -- * Type OrdPSQ (..)@@ -64,11 +67,11 @@ , valid ) where -import Prelude hiding (map, lookup, null, foldr)-import Control.DeepSeq (NFData(rnf))-import Data.Maybe (isJust)+import Control.DeepSeq (NFData (rnf)) import Data.Foldable (Foldable (foldr)) import qualified Data.List as List+import Data.Maybe (isJust)+import Prelude hiding (foldr, lookup, map, null) -------------------------------------------------------------------------------- -- Types@@ -76,7 +79,7 @@ -- | @E k p v@ binds the key @k@ to the value @v@ with priority @p@. data Elem k p v = E !k !p !v- deriving (Show)+ deriving (Foldable, Functor, Show, Traversable) instance (NFData k, NFData p, NFData v) => NFData (Elem k p v) where rnf (E k p v) = rnf k `seq` rnf p `seq` rnf v@@ -88,7 +91,7 @@ | Winner !(Elem k p v) !(LTree k p v) !k- deriving (Show)+ deriving (Foldable, Functor, Show, Traversable) instance (NFData k, NFData p, NFData v) => NFData (OrdPSQ k p v) where rnf Void = ()@@ -102,13 +105,6 @@ (Just _ , Nothing ) -> False (Nothing , Just _ ) -> False -instance Foldable (OrdPSQ k p) where- foldr _ z Void = z- foldr f z (Winner (E _ _ x) l _) = f x (foldr f z l)--instance Functor (OrdPSQ k p) where- fmap f = map (\_ _ v -> f v)- type Size = Int data LTree k p v@@ -123,17 +119,12 @@ !(LTree k p v) !k -- split key !(LTree k p v)- deriving (Show)+ deriving (Foldable, Functor, Show, Traversable) instance (NFData k, NFData p, NFData v) => NFData (LTree k p v) where rnf Start = () rnf (LLoser _ e l k r) = rnf e `seq` rnf l `seq` rnf k `seq` rnf r rnf (RLoser _ e l k r) = rnf e `seq` rnf l `seq` rnf k `seq` rnf r--instance Foldable (LTree k p) where- foldr _ z Start = z- foldr f z (LLoser _ (E _ _ x) l _ r) = f x (foldr f (foldr f z r) l)- foldr f z (RLoser _ (E _ _ x) l _ r) = f x (foldr f (foldr f z r) l) --------------------------------------------------------------------------------