identifiers 0.4.1.0 → 0.4.2.0

raw patch · 4 files changed

+131/−9 lines, 4 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• identifiers.cabal +8/−3
• src/Data/Identifiers/Hashable.hs +60/−3
• src/Data/Identifiers/ListLike.hs +59/−3
• test/TestAll.hs +4/−0

@@ -1,8 +1,13 @@ name:                identifiers-version:             0.4.1.0+version:             0.4.2.0 synopsis:            Numeric identifiers for values.-description:         Useful for situations where repeated-storage requirements-                     of values become too costly.+description:         This library allows you to turn costly repetitive values+                     into numbers in order to save memory.++                     An Identifiers value acts like a bi-directional map that+                     allows you to effeciently toggle between a numeric key+                     and the original value push into the map.+ license:             BSD3 license-file:        LICENSE author:              Adam Wagner

@@ -1,9 +1,28 @@+{-|+Module      : Data.Identifiers.Hashable+Description : Identifiers for Hashable values+Copyright   : (c) Adam Wagner, 2017++Identifiers for Hashable values.++Example usage:++>>> xs = fromList ["foo", "bar", "baz", "foo"]+>>> lookupId xs "baz"+Just 2+>>> lookupKey xs 2+Just "baz"++-}+{-# LANGUAGE CPP #-}+{-# LANGUAGE ViewPatterns #-} module Data.Identifiers.Hashable     ( Identifiers ()          -- * Construction     , empty     , fromList+    , combine          -- * Insertion     , insert@@ -29,21 +48,30 @@     , prop_keyRetrieval     , prop_keyRetrievalUnsafe     , prop_idempotent+    , prop_stableCombine+    , prop_properMigration      ) where +#if __GLASGOW_HASKELL__ < 710 import Control.Applicative hiding (empty)+#endif++import Control.Arrow ((&&&)) import Control.DeepSeq import Data.Binary-import Data.List (foldl')+import Data.List (foldl', isPrefixOf) import Data.Hashable import Data.HashMap.Lazy (HashMap)+import Data.Map (Map) import Data.Maybe import Data.Sequence (Seq, (|>)) import Data.Serialize (Serialize)+import qualified Data.Map as M import qualified Data.HashMap.Lazy as H import qualified Data.Sequence as S import qualified Data.Serialize as C+import qualified Data.Foldable as F   data Identifiers i a = Identifiers { ids   :: !(HashMap a i)@@ -51,7 +79,7 @@                                    } deriving Eq  instance Show a => Show (Identifiers i a) where-    show s = "insertMany empty " ++ show (H.keys (ids s))+    show s = "insertMany empty " ++ show (toList s)  instance (Binary i, Eq a, Hashable a, Binary a) => Binary (Identifiers i a) where     put s = put (H.toList $ ids s) >> put (names s)@@ -72,6 +100,18 @@ fromList :: (Integral i, Hashable a, Eq a) => [a] -> Identifiers i a fromList = insertMany empty +-- | Combine two identifier sets into one.+--   Because the ids will change while combining two sets, a map is also+--   returned that identifies the new location of old ids for the second+--   set passed in.+combine+    :: (Integral i, Hashable a, Eq a)+    => Identifiers i a -> Identifiers i a -> (Identifiers i a, Map i i)+combine a b = let c  = (insertMany a) xs+                  xs = toList b+                  m  = M.fromList $ map (unsafeLookupId b &&& unsafeLookupId c) xs+              in (c, m)+ -- | Insert item into set (given it a new id) insert :: (Integral i, Hashable a, Eq a) => Identifiers i a -> a -> Identifiers i a insert xs v = case H.lookup v (ids xs) of@@ -85,15 +125,17 @@  -- | New List from Identifiers toList :: Identifiers i a -> [a]-toList = H.keys . ids+toList (names -> xs) = F.toList xs  -- | Find id for given key lookupId :: (Hashable a, Eq a) => Identifiers i a -> a -> Maybe i lookupId = flip H.lookup . ids +-- | Number of items in Identifiers value size :: Identifiers i a -> Int size = S.length . names +-- | Find numeric id for given value.  Will error when the value is not a member of the Identifiers map. unsafeLookupId :: (Hashable a, Eq a) => Identifiers i a -> a -> i unsafeLookupId = (H.!) . ids @@ -108,9 +150,11 @@ lookupKeys :: (Integral i) => Identifiers i a -> [i] -> [a] lookupKeys s = mapMaybe (lookupKey s) +-- | Find id for given value.  Will error when the id has no associated value. unsafeLookupKey :: Integral i => Identifiers i a -> i -> a unsafeLookupKey xs x = S.index (names xs) (fromIntegral x) +-- | Infix version of unsafeLookupKey (!) :: Integral i => Identifiers i a -> i -> a (!) = unsafeLookupKey @@ -142,4 +186,17 @@ prop_idempotent :: String -> Bool prop_idempotent x = insert (empty :: Identifiers Int String) x                         == insert (insert empty x) x++-- | Ids for the first set passed to combine remain unchanged+prop_stableCombine :: [String] -> [String] -> Bool+prop_stableCombine (fromList -> xs) (fromList -> ys) =+    let (zs, _) = combine xs (ys :: Identifiers Int String)+    in (toList xs) `isPrefixOf` (toList zs)++-- | Ensure the migration points to the same value in both old and new sets+prop_properMigration :: [String] -> [String] -> Bool+prop_properMigration (fromList -> xs) (fromList -> ys) =+    let (zs, m) = combine xs (ys :: Identifiers Int String)+    in and [ (unsafeLookupKey ys k) == (unsafeLookupKey zs v)+             | (k, v) <- M.toList m ] 

@@ -1,3 +1,20 @@+{-|+Module      : Data.Identifiers.ListLike+Description : Identifiers for ListLike values+Copyright   : (c) Adam Wagner, 2017++Identifiers for ListLike values.++Example usage:++>>> xs = fromList ["foo", "bar", "baz", "foo"]+>>> lookupId xs "baz"+Just 2+>>> lookupKey xs 2+Just "baz"++-}+{-# LANGUAGE CPP #-} {-# LANGUAGE ViewPatterns #-} module Data.Identifiers.ListLike     ( Identifiers ()@@ -5,6 +22,7 @@     -- * Construction     , empty     , fromList+    , combine          -- * Insertion     , insert@@ -30,18 +48,26 @@     , prop_keyRetrieval     , prop_keyRetrievalUnsafe     , prop_idempotent+    , prop_stableCombine+    , prop_properMigration      ) where +#if __GLASGOW_HASKELL__ < 710 import Control.Applicative hiding (empty)+#endif++import Control.Arrow ((&&&)) import Control.DeepSeq import Data.Binary-import Data.List (foldl')+import Data.List (foldl', isPrefixOf)+import Data.Map (Map) import Data.Maybe import Data.Sequence (Seq, (|>)) import Data.Serialize (Serialize) import Data.ListLike (ListLike) import Data.TrieMap (TrieMap)+import qualified Data.Map as M import qualified Data.TrieMap as TM import qualified Data.Sequence as S import qualified Data.Serialize as C@@ -77,6 +103,18 @@ fromList :: (ListLike n u, Eq u, Integral i) => [n] -> Identifiers i n u fromList = insertMany empty +-- | Combine two identifier sets into one.+--   Because the ids will change while combining two sets, a map is also+--   returned that identifies the new location of old ids for the second+--   set passed in.+combine+    :: (ListLike n u, Integral i, Eq u)+    => Identifiers i n u -> Identifiers i n u -> (Identifiers i n u, Map i i)+combine a b = let c  = (insertMany a) xs+                  xs = toList b+                  m  = M.fromList $ map (unsafeLookupId b &&& unsafeLookupId c) xs+              in (c, m)+ -- | Insert item into set (given it a new id) insert :: (ListLike n u, Eq u, Integral i)     => Identifiers i n u -> n -> Identifiers i n u@@ -94,13 +132,15 @@ toList :: Identifiers i n u -> [n] toList = F.toList . names --- | Find id for given key+-- | Find id for given value lookupId :: (Eq u, ListLike n u) => Identifiers i n u -> n -> Maybe i lookupId (ids -> m) (LL.toList -> k) = TM.lookup m k +-- | Number of items in Identifiers value size :: Identifiers i n u -> Int size = S.length . names +-- | Find numeric id for given value.  Will error when the value is not a member of the Identifiers map. unsafeLookupId :: (ListLike n u, Eq u) => Identifiers i n u -> n -> i unsafeLookupId (ids -> m) (LL.toList -> k) = m TM.! k @@ -111,13 +151,15 @@                        then Nothing                        else Just $ unsafeLookupKey ident x --- | Given many ids, return many keys+-- | Given many ids, return many keys.  Ids with no associated values will be omitted from the resulting list. lookupKeys :: (Integral i) => Identifiers i n u -> [i] -> [n] lookupKeys s = mapMaybe (lookupKey s) +-- | Find id for given value.  Will error when the id has no associated value. unsafeLookupKey :: Integral i => Identifiers i n u -> i -> n unsafeLookupKey xs x = S.index (names xs) (fromIntegral x) +-- | Infix version of unsafeLookupKey (!) :: Integral i => Identifiers i n u -> i -> n (!) = unsafeLookupKey @@ -149,3 +191,17 @@ prop_idempotent :: String -> Bool prop_idempotent x = insert (empty :: Identifiers Int String Char) x                         == insert (insert empty x) x++-- | Ids for the first set passed to combine remain unchanged+prop_stableCombine :: [String] -> [String] -> Bool+prop_stableCombine (fromList -> xs) (fromList -> ys) =+    let (zs, _) = combine xs (ys :: Identifiers Int String Char)+    in (toList xs) `isPrefixOf` (toList zs)++-- | Ensure the migration points to the same value in both old and new sets+prop_properMigration :: [String] -> [String] -> Bool+prop_properMigration (fromList -> xs) (fromList -> ys) =+    let (zs, m) = combine xs (ys :: Identifiers Int String Char)+    in and [ (unsafeLookupKey ys k) == (unsafeLookupKey zs v)+             | (k, v) <- M.toList m ]+

@@ -17,6 +17,8 @@             , testProperty "keyRetrieval"         H.prop_keyRetrieval             , testProperty "keyRetrievalUnsafe"   H.prop_keyRetrievalUnsafe             , testProperty "idempotent"           H.prop_idempotent+            , testProperty "stableCombine"        H.prop_stableCombine+            , testProperty "propermigration"      H.prop_properMigration             ]         , testGroup "QuickCheck Data.Identifiers.ListLike"             [ testProperty "hasId"                L.prop_hasId@@ -24,6 +26,8 @@             , testProperty "keyRetrieval"         L.prop_keyRetrieval             , testProperty "keyRetrievalUnsafe"   L.prop_keyRetrievalUnsafe             , testProperty "idempotent"           L.prop_idempotent+            , testProperty "stableCombine"        L.prop_stableCombine+            , testProperty "propermigration"      L.prop_properMigration             ]         ]