linkedhashmap 0.1.0.0 → 0.1.1.0

raw patch · 8 files changed

+654/−155 lines, 8 filesdep +mtlPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

Dependencies added: mtl

API changes (from Hackage documentation)

Files

• README.md +1/−1
• benchmarks/linkedhashmap-benchmarks.cabal +33/−0
• linkedhashmap.cabal +17/−14
• src/Data/LinkedHashMap/IntMap.hs +226/−56
• src/Data/LinkedHashMap/Seq.hs +203/−23
• src/Data/LinkedHashSet.hs +55/−58
• tests/Main.hs +85/−3
• tests/linkedhashmap-tests.cabal +34/−0

@@ -1,7 +1,7 @@ Persistent LinkedHashMap ======================== -Haskell implementation of Java (Concurrent)LinkedHashMap.+Haskell implementation of Java LinkedHashMap.  Underlying HashMap is based on Data.HashMap.Strict. 

@@ -0,0 +1,33 @@+-- Initial benchmarks.cabal generated by cabal init.  For further +-- documentation, see http://haskell.org/cabal/users-guide/++name:                linkedhashmap-benchmarks+version:             0.1.0.0+-- synopsis:            +-- description:         +license:             BSD3+license-file:        LICENSE+author:              Andrey Basko+maintainer:          andrey_basko@yahoo.com+-- copyright:           +category:            Data+build-type:          Simple+-- extra-source-files:  +cabal-version:       >=1.10++executable benchmarks+  main-is:             Main.hs+  -- other-modules:       +  -- other-extensions:    +  build-depends:       base >=4.7 && <4.8+                     , containers >= 0.5.5.1+                     , hashable >= 1.2.2.0+                     , tasty >= 0.10.0.2+                     , tasty-hunit >= 0.9.0.1+                     , unordered-containers >= 0.2.5.0+                     , criterion >= 1.0.2.0+                     , deepseq >=1.3 && <1.4+  hs-source-dirs: +    ./+    ../src+  default-language:    Haskell2010

@@ -2,7 +2,7 @@ -- documentation, see http://haskell.org/cabal/users-guide/  name:                linkedhashmap-version:             0.1.0.0+version:             0.1.1.0 license:             BSD3 license-file:        LICENSE author:              Andrey Basko@@ -16,7 +16,7 @@ cabal-version:       >=1.10 synopsis:            Persistent LinkedHashMap data structure description:         -  Haskell implementation of Java (Concurrent)LinkedHashMap.+  Haskell implementation of Java LinkedHashMap.   .   Underlying HashMap is based on Data.HashMap.Strict.   .@@ -26,9 +26,11 @@  extra-source-files:   README.md+  tests/linkedhashmap-tests.cabal   benchmarks/Tests.java   benchmarks/report.html   benchmarks/runJava.sh+  benchmarks/linkedhashmap-benchmarks.cabal  source-repository head   type: git@@ -41,24 +43,25 @@                        Data.LinkedHashMap.IntMap   -- other-modules:          other-extensions:    BangPatterns-  build-depends:       base >=4.7 && <4.8, -                       hashable >=1.2 && <1.3, -                       containers >=0.5 && <0.6, -                       deepseq >= 1.1,-                       unordered-containers >=0.2 && <0.3+  build-depends:       base >=4.7 && <4.8+                     , containers >=0.5 && <0.6+                     , deepseq >= 1.1+                     , hashable >=1.2 && <1.3+                     , unordered-containers >=0.2 && <0.3   hs-source-dirs:      src   default-language:    Haskell2010  test-suite linkedhashmap-tests   type: exitcode-stdio-1.0   main-is: Main.hs-  build-depends:       base >=4.7 && <4.8,-                       containers >= 0.5.5.1, -                       hashable >= 1.2.2.0, -                       tasty >= 0.10.0.2, -                       deepseq >= 1.1,-                       tasty-hunit >= 0.9.0.1, -                       unordered-containers >= 0.2.5.0+  build-depends:       base >=4.7 && <4.8+                     , containers >= 0.5.5.1+                     , deepseq >= 1.1+                     , hashable >= 1.2.2.0+                     , tasty >= 0.10.0.2+                     , mtl >= 2.1.3.1+                     , tasty-hunit >= 0.9.0.1+                     , unordered-containers >= 0.2.5.0   hs-source-dirs:      tests                        src   default-language:    Haskell2010

@@ -1,5 +1,4 @@ {-# LANGUAGE BangPatterns #-}- module Data.LinkedHashMap.IntMap      (      LinkedHashMap(..)@@ -16,35 +15,35 @@     , lookupDefault     , (!)     , insert-    -- , insertWith+    , insertWith     , delete-    -- , adjust+    , adjust        -- * Combine       -- ** Union-    -- , union-    -- , unionWith-    -- , unions+    , union+    , unionWith+    , unions        -- * Transformations     , map-    -- , mapWithKey-    -- , traverseWithKey+    , mapWithKey+    , traverseWithKey        -- * Difference and intersection-    -- , difference-    -- , intersection-    -- , intersectionWith+    , difference+    , intersection+    , intersectionWith        -- * Folds-    -- , foldl'-    -- , foldlWithKey'-    -- , foldr-    -- , foldrWithKey+    , foldl'+    , foldlWithKey'+    , foldr+    , foldrWithKey        -- * Filter-    -- , filter-    -- , filterWithKey+    , filter+    , filterWithKey        -- * Conversions     , keys@@ -53,16 +52,20 @@       -- ** Lists     , toList     , fromList-    -- , fromListWith+    , fromListWith     )  where -import Prelude hiding (null, lookup)+import Prelude hiding (foldr, map, null, lookup, filter)+import Data.Maybe import Data.IORef import System.IO.Unsafe import Data.Hashable (Hashable) import Control.DeepSeq (NFData(rnf))+import Control.Applicative ((<$>), Applicative)+import qualified Data.List as L import qualified Data.Foldable as F+import qualified Data.Traversable as T import qualified Data.HashMap.Strict as M import qualified Data.IntMap.Strict as IM @@ -94,6 +97,31 @@                                      Nothing -> Nothing {-# INLINABLE lookup #-} +-- | /O(log n)/ Return the value to which the specified key is mapped,+-- or the default value if this map contains no mapping for the key.+lookupDefault :: (Eq k, Hashable k)+              => v          -- ^ Default value to return.+              -> k -> LinkedHashMap k v -> v+lookupDefault def k t = case lookup k t of+  Just v -> v+  _      -> def+{-# INLINABLE lookupDefault #-}++-- | /O(log n)/ Return the value to which the specified key is mapped.+-- Calls 'error' if this map contains no mapping for the key.+(!) :: (Eq k, Hashable k) => LinkedHashMap k v -> k -> v+(!) m k = case lookup k m of+    Just v  -> v+    Nothing -> error "Data.LinkedHashMap.IntMap.(!): key not found"+{-# INLINABLE (!) #-}++-- | /O(log n)/ Remove the mapping for the specified key from this map+-- if present.+delete :: (Eq k, Hashable k) => k -> LinkedHashMap k v -> LinkedHashMap k v+delete k0 (LinkedHashMap m s rn) = LinkedHashMap (M.delete k0 m) (case M.lookup k0 m of+                                                                    Nothing -> s+                                                                    Just (Entry (i, _)) -> IM.delete i s) rn+ -- | /O(1)/ Construct an empty map. empty :: LinkedHashMap k v empty = LinkedHashMap M.empty IM.empty (newCounter minBound)@@ -102,16 +130,32 @@ singleton :: (Eq k, Hashable k) => k -> v -> LinkedHashMap k v singleton k v = fromList [(k, v)] +-- | /O(1)/ Return 'True' if this map is empty, 'False' otherwise.+null :: LinkedHashMap k v -> Bool+null (LinkedHashMap m _ _) = M.null m++-- | /O(log n)/ Return 'True' if the specified key is present in the+-- map, 'False' otherwise.+member :: (Eq k, Hashable k) => k -> LinkedHashMap k a -> Bool+member k m = case lookup k m of+  Nothing -> False+  Just _  -> True+{-# INLINABLE member #-}++-- | /O(1)/ Return the number of key-value mappings in this map.+size :: LinkedHashMap k v -> Int+size (LinkedHashMap _ s _) = IM.size s+ -- | /O(n)/ Return a list of this map's keys.  The list is produced -- lazily. keys :: (Eq k, Hashable k) => LinkedHashMap k v -> [k]-keys m = map (\(k, _) -> k) $ toList m+keys m = fmap (\(k, _) -> k) $ toList m {-# INLINE keys #-}  -- | /O(n)/ Return a list of this map's values.  The list is produced -- lazily. elems :: (Eq k, Hashable k) => LinkedHashMap k v -> [v]-elems m = map (\(_, v) -> v) $ toList m+elems m = fmap (\(_, v) -> v) $ toList m {-# INLINE elems #-}  -- | /O(n*log n)/ Construct a map with the supplied mappings.  If the@@ -139,49 +183,175 @@           Nothing -> incCounter rn {-# INLINABLE insert #-} --- | /O(log n)/ Remove the mapping for the specified key from this map--- if present.-delete :: (Eq k, Hashable k) => k -> LinkedHashMap k v -> LinkedHashMap k v-delete k0 (LinkedHashMap m s rn) = LinkedHashMap (M.delete k0 m) (case M.lookup k0 m of-                                                                    Nothing -> s-                                                                    Just (Entry (i, _)) -> IM.delete i s) rn+-- | /O(log n)/ Associate the value with the key in this map.  If+-- this map previously contained a mapping for the key, the old value+-- is replaced by the result of applying the given function to the new+-- and old value.  Example:+--+-- > insertWith f k v map+-- >   where f new old = new + old+insertWith :: (Eq k, Hashable k) => (v -> v -> v) -> k -> v -> LinkedHashMap k v -> LinkedHashMap k v+insertWith f k v0 (LinkedHashMap m s rn) = s' `seq` LinkedHashMap m' s' rn+  where+    m' = M.insert k (Entry (n', v')) m+    s' = IM.insert n' (k, v') s+    (n', v') = case M.lookup k m of+                 Just (Entry (n, v)) -> (n, f v0 v)+                 Nothing -> (incCounter rn, v0) --- | /O(1)/ Return 'True' if this map is empty, 'False' otherwise.-null :: LinkedHashMap k v -> Bool-null (LinkedHashMap m _ _) = M.null m+-- | /O(log n)/ Adjust the value tied to a given key in this map only+-- if it is present. Otherwise, leave the map alone.+adjust :: (Eq k, Hashable k) => (v -> v) -> k -> LinkedHashMap k v -> LinkedHashMap k v+adjust f k (LinkedHashMap m s rn) = s' `seq` LinkedHashMap m' s' rn+  where+    m' = M.adjust f' k m+    f' (Entry (ix, v)) = Entry (ix, f v)+    s' = case M.lookup k m' of+           Just (Entry (ix, v)) -> IM.insert ix (k, v) s+           Nothing -> s --- | /O(log n)/ Return 'True' if the specified key is present in the--- map, 'False' otherwise.-member :: (Eq k, Hashable k) => k -> LinkedHashMap k a -> Bool-member k m = case lookup k m of-  Nothing -> False-  Just _  -> True-{-# INLINABLE member #-}+-- | /O(m*log n)/ The union of two maps, n - size of the first map. If a key occurs in both maps,+-- the mapping from the first will be the mapping in the result.+union :: (Eq k, Hashable k) => LinkedHashMap k v -> LinkedHashMap k v -> LinkedHashMap k v+union = unionWith const+{-# INLINABLE union #-} --- | /O(1)/ Return the number of key-value mappings in this map.-size :: LinkedHashMap k v -> Int-size (LinkedHashMap _ s _) = IM.size s+-- | /O(m*log n)/ The union of two maps, n - size of the first map.  If a key occurs in both maps,+-- the provided function (first argument) will be used to compute the result.+unionWith :: (Eq k, Hashable k) => (v -> v -> v) -> LinkedHashMap k v -> LinkedHashMap k v+          -> LinkedHashMap k v+unionWith f m1 m2 = m'+  where+    m' = F.foldl' (\m (k, v) -> insertWith (flip f) k v m) m1 $ toList m2 --- | /O(log n)/ Return the value to which the specified key is mapped,--- or the default value if this map contains no mapping for the key.-lookupDefault :: (Eq k, Hashable k)-              => v          -- ^ Default value to return.-              -> k -> LinkedHashMap k v -> v-lookupDefault def k t = case lookup k t of-  Just v -> v-  _      -> def-{-# INLINABLE lookupDefault #-}+-- | Construct a set containing all elements from a list of sets.+unions :: (Eq k, Hashable k) => [LinkedHashMap k v] -> LinkedHashMap k v+unions = F.foldl' union empty+{-# INLINE unions #-} --- | /O(log n)/ Return the value to which the specified key is mapped.--- Calls 'error' if this map contains no mapping for the key.-(!) :: (Eq k, Hashable k) => LinkedHashMap k v -> k -> v-(!) m k = case lookup k m of-    Just v  -> v-    Nothing -> error "Data.LinkedHashMap.IntMap.(!): key not found"-{-# INLINABLE (!) #-}+-- | /O(n)/ Transform this map by applying a function to every value.+map :: (v1 -> v2) -> LinkedHashMap k v1 -> LinkedHashMap k v2+map f = mapWithKey (const f)+{-# INLINE map #-} +-- | /O(n)/ Transform this map by applying a function to every value.+mapWithKey :: (k -> v1 -> v2) -> LinkedHashMap k v1 -> LinkedHashMap k v2+mapWithKey f (LinkedHashMap m s n) = (LinkedHashMap m' s' n)+  where+    m' = M.mapWithKey f' m+    s' = fmap f'' s+    f' k (Entry (ix, v1)) = Entry (ix, f k v1)+    f'' (k, v1) = (k, f k v1)++-- | /O(n*log(n))/ Transform this map by accumulating an Applicative result+-- from every value.+traverseWithKey :: Applicative f => (k -> v1 -> f v2) -> LinkedHashMap k v1+                -> f (LinkedHashMap k v2)+traverseWithKey f (LinkedHashMap m0 s0 n) = (\s -> LinkedHashMap (M.map (getV2 s) m0) s n) <$> s'+  where+    s' = T.traverse f' s0+    f' (k, v1) = (\v -> (k, v)) <$> f k v1+    getV2 s (Entry (ix, _)) = let (_, v2) = fromJust $ IM.lookup ix s in Entry (ix, v2)+{-# INLINE traverseWithKey #-}++-- | /O(n*log m)/ Difference of two maps. Return elements of the first map+-- not existing in the second.+difference :: (Eq k, Hashable k) => LinkedHashMap k v -> LinkedHashMap k w -> LinkedHashMap k v+difference a b = foldlWithKey' go empty a+  where+    go m k v = case lookup k b of+                 Nothing -> insert k v m+                 _       -> m+{-# INLINABLE difference #-}++-- | /O(n*log m)/ Intersection of two maps. Return elements of the first+-- map for keys existing in the second.+intersection :: (Eq k, Hashable k) => LinkedHashMap k v -> LinkedHashMap k w -> LinkedHashMap k v+intersection a b = foldlWithKey' go empty a+  where+    go m k v = case lookup k b of+                 Just _ -> insert k v m+                 _      -> m+{-# INLINABLE intersection #-}++-- | /O(n+m)/ Intersection of two maps. If a key occurs in both maps+-- the provided function is used to combine the values from the two+-- maps.+intersectionWith :: (Eq k, Hashable k) => (v1 -> v2 -> v3) -> LinkedHashMap k v1+                 -> LinkedHashMap k v2 -> LinkedHashMap k v3+intersectionWith f a b = foldlWithKey' go empty a+  where+    go m k v = case lookup k b of+                 Just w -> insert k (f v w) m+                 _      -> m+{-# INLINABLE intersectionWith #-}++-- | /O(n)/ Reduce this map by applying a binary operator to all+-- elements, using the given starting value (typically the+-- left-identity of the operator).  Each application of the operator+-- is evaluated before before using the result in the next+-- application.  This function is strict in the starting value.+foldl' :: (a -> v -> a) -> a -> LinkedHashMap k v -> a+foldl' f b0 (LinkedHashMap _ s _) = F.foldl' f' b0 s+  where+    f' b (_, v) = f b v++-- | /O(n)/ Reduce this map by applying a binary operator to all+-- elements, using the given starting value (typically the+-- right-identity of the operator).+foldr :: (v -> a -> a) -> a -> LinkedHashMap k v -> a+foldr = F.foldr+{-# INLINE foldr #-}++-- | /O(n)/ Reduce this map by applying a binary operator to all+-- elements, using the given starting value (typically the+-- left-identity of the operator).  Each application of the operator+-- is evaluated before before using the result in the next+-- application.  This function is strict in the starting value.+foldlWithKey' :: (a -> k -> v -> a) -> a -> LinkedHashMap k v -> a+foldlWithKey' f b0 (LinkedHashMap _ s _) = F.foldl' f' b0 s+  where+    f' b (k, v) = f b k v+{-# INLINE foldlWithKey' #-}++-- | /O(n)/ Reduce this map by applying a binary operator to all+-- elements, using the given starting value (typically the+-- right-identity of the operator).+foldrWithKey :: (k -> v -> a -> a) -> a -> LinkedHashMap k v -> a+foldrWithKey f b0 (LinkedHashMap _ s _) = F.foldr f' b0 s+  where+    f' (k, v) b = f k v b++-- | /O(n*log(n))/ Filter this map by retaining only elements satisfying a+-- predicate.+filterWithKey :: (Eq k, Hashable k) => (k -> v -> Bool) -> LinkedHashMap k v -> LinkedHashMap k v+filterWithKey p m = fromList $ L.filter (uncurry p) $ toList m++-- | /O(n*log(n))/ Filter this map by retaining only elements which values+-- satisfy a predicate.+filter :: (Eq k, Hashable k) => (v -> Bool) -> LinkedHashMap k v -> LinkedHashMap k v+filter p = filterWithKey (\_ v -> p v)+{-# INLINE filter #-}++-- | /O(n*log n)/ Construct a map from a list of elements.  Uses+-- the provided function to merge duplicate entries.+fromListWith :: (Eq k, Hashable k) => (v -> v -> v) -> [(k, v)] -> LinkedHashMap k v+fromListWith f = L.foldl' (\ m (k, v) -> insertWith f k v m) empty+{-# INLINE fromListWith #-}+ instance (NFData a) => NFData (Entry a) where     rnf (Entry a) = rnf a  instance (NFData k, NFData v) => NFData (LinkedHashMap k v) where     rnf (LinkedHashMap m s _) = rnf m `seq` rnf s++instance Functor (LinkedHashMap k) where+    fmap = map++instance F.Foldable (LinkedHashMap k) where+    foldr f b0 (LinkedHashMap _ s _) = F.foldr f' b0 s+      where+        f' (_, v) b = f v b+        +instance T.Traversable (LinkedHashMap k) where+    traverse f = traverseWithKey (const f)

@@ -15,35 +15,35 @@     , lookupDefault     , (!)     , insert-    -- , insertWith+    , insertWith     , delete-    -- , adjust+    , adjust        -- * Combine       -- ** Union-    -- , union-    -- , unionWith-    -- , unions+    , union+    , unionWith+    , unions        -- * Transformations     , map-    -- , mapWithKey-    -- , traverseWithKey+    , mapWithKey+    , traverseWithKey        -- * Difference and intersection-    -- , difference-    -- , intersection-    -- , intersectionWith+    , difference+    , intersection+    , intersectionWith        -- * Folds-    -- , foldl'-    -- , foldlWithKey'-    -- , foldr-    -- , foldrWithKey+    , foldl'+    , foldlWithKey'+    , foldr+    , foldrWithKey        -- * Filter-    -- , filter-    -- , filterWithKey+    , filter+    , filterWithKey        -- * Conversions     , keys@@ -52,17 +52,22 @@       -- ** Lists     , toList     , fromList-    -- , fromListWith+    , fromListWith+     , pack     ) where -import Prelude hiding (null, lookup)+import Prelude hiding (foldr, map, null, lookup, filter) import Data.Maybe+import Control.Applicative ((<$>), Applicative(pure)) import Control.DeepSeq (NFData(rnf)) import Data.Hashable (Hashable)-import Data.Sequence (Seq, (|>))+import Data.Sequence (Seq, (|>)) +import Data.Traversable (Traversable(..)) import qualified Data.Sequence as S import qualified Data.Foldable as F+import qualified Data.Traversable as T+import qualified Data.List as L import qualified Data.HashMap.Strict as M  newtype Entry a = Entry { unEntry :: (Int, a) } deriving (Show)@@ -85,14 +90,20 @@                                      Nothing -> Nothing {-# INLINABLE lookup #-} +-- | /O(n*log n)/ Construct a map from a list of elements.  Uses+-- the provided function to merge duplicate entries.+fromListWith :: (Eq k, Hashable k) => (v -> v -> v) -> [(k, v)] -> LinkedHashMap k v+fromListWith f = L.foldl' (\ m (k, v) -> insertWith f k v m) empty+{-# INLINE fromListWith #-}+ -- | /O(n*log n)/ Construct a map with the supplied mappings.  If the -- list contains duplicate mappings, the later mappings take -- precedence. fromList :: (Eq k, Hashable k) => [(k, v)] -> LinkedHashMap k v fromList ps = LinkedHashMap m' s' len'   where-    m0 = M.fromList $ map (\(i, (k, v)) -> (k, Entry (i, v))) $ zip [0..] ps-    s0 = S.fromList $ map (\(k, v) -> Just (k, v)) ps+    m0 = M.fromList $ L.map (\(i, (k, v)) -> (k, Entry (i, v))) $ zip [0..] ps+    s0 = S.fromList $ L.map (\(k, v) -> Just (k, v)) ps     len = M.size m0     (m', s', len') = if len == S.length s0                      then (m0, s0, len)@@ -182,17 +193,186 @@ -- | /O(n)/ Return a list of this map's keys.  The list is produced -- lazily. keys :: (Eq k, Hashable k) => LinkedHashMap k v -> [k]-keys m = map (\(k, _) -> k) $ toList m+keys m = L.map (\(k, _) -> k) $ toList m {-# INLINE keys #-}  -- | /O(n)/ Return a list of this map's values.  The list is produced -- lazily. elems :: (Eq k, Hashable k) => LinkedHashMap k v -> [v]-elems m = map (\(_, v) -> v) $ toList m+elems m = L.map (\(_, v) -> v) $ toList m {-# INLINE elems #-} +-- | /O(log n)/ Associate the value with the key in this map.  If+-- this map previously contained a mapping for the key, the old value+-- is replaced by the result of applying the given function to the new+-- and old value.  Example:+--+-- > insertWith f k v map+-- >   where f new old = new + old+insertWith :: (Eq k, Hashable k) => (v -> v -> v) -> k -> v -> LinkedHashMap k v -> LinkedHashMap k v+insertWith f k v (LinkedHashMap m s n) = LinkedHashMap m' s' n'+  where+    m' = M.insertWith f' k v' m+    f' (Entry (_, v1)) (Entry (ix, v2)) = Entry (ix, f v1 v2)+    slen = S.length s+    v' = Entry (slen, v)+    (ixnew, vnew) = unEntry $ fromJust $ M.lookup k m'+    (s', n') = if ixnew == slen +               then (s |> Just (k, vnew), n + 1)+               else (S.update ixnew (Just (k, vnew)) s, n)++-- | /O(log n)/ Adjust the value tied to a given key in this map only+-- if it is present. Otherwise, leave the map alone.+adjust :: (Eq k, Hashable k) => (v -> v) -> k -> LinkedHashMap k v -> LinkedHashMap k v+adjust f k (LinkedHashMap m s n) = LinkedHashMap m' s' n+  where+    m' = M.adjust f' k m+    f' (Entry (ix, v)) = Entry (ix, f v)+    s' = case M.lookup k m' of+           Just (Entry (ix, v)) -> S.update ix (Just (k, v)) s+           Nothing -> s++-- | /O(m*log n)/ The union of two maps, n - size of the first map. If a key occurs in both maps,+-- the mapping from the first will be the mapping in the result.+union :: (Eq k, Hashable k) => LinkedHashMap k v -> LinkedHashMap k v -> LinkedHashMap k v+union = unionWith const+{-# INLINABLE union #-}++-- | /O(m*log n)/ The union of two maps, n - size of the first map.  If a key occurs in both maps,+-- the provided function (first argument) will be used to compute the result.+unionWith :: (Eq k, Hashable k) => (v -> v -> v) -> LinkedHashMap k v -> LinkedHashMap k v+          -> LinkedHashMap k v+unionWith f m1 m2 = m'+  where+    m' = F.foldl' (\m (k, v) -> insertWith (flip f) k v m) m1 $ toList m2++-- | Construct a set containing all elements from a list of sets.+unions :: (Eq k, Hashable k) => [LinkedHashMap k v] -> LinkedHashMap k v+unions = F.foldl' union empty+{-# INLINE unions #-}++-- | /O(n)/ Transform this map by applying a function to every value.+map :: (v1 -> v2) -> LinkedHashMap k v1 -> LinkedHashMap k v2+map f = mapWithKey (const f)+{-# INLINE map #-}++-- | /O(n)/ Transform this map by applying a function to every value.+mapWithKey :: (k -> v1 -> v2) -> LinkedHashMap k v1 -> LinkedHashMap k v2+mapWithKey f (LinkedHashMap m s n) = (LinkedHashMap m' s' n)+  where+    m' = M.mapWithKey f' m+    s' = fmap f'' s+    f' k (Entry (ix, v1)) = Entry (ix, f k v1)+    f'' (Just (k, v1)) = Just (k, f k v1)+    f'' _  = Nothing++-- | /O(n*log(n))/ Transform this map by accumulating an Applicative result+-- from every value.+traverseWithKey :: Applicative f => (k -> v1 -> f v2) -> LinkedHashMap k v1+                -> f (LinkedHashMap k v2)+traverseWithKey f (LinkedHashMap m0 s0 n) = (\s -> LinkedHashMap (M.map (getV2 s) m0) s n) <$> s'+  where+    s' = T.traverse f' s0+    f' (Just (k, v1)) = (\v -> Just (k, v)) <$> f k v1+    f' Nothing = pure Nothing+    getV2 s (Entry (ix, _)) = let (_, v2) = fromJust $ S.index s ix in Entry (ix, v2)+{-# INLINE traverseWithKey #-}++-- | /O(n*log m)/ Difference of two maps. Return elements of the first map+-- not existing in the second.+difference :: (Eq k, Hashable k) => LinkedHashMap k v -> LinkedHashMap k w -> LinkedHashMap k v+difference a b = foldlWithKey' go empty a+  where+    go m k v = case lookup k b of+                 Nothing -> insert k v m+                 _       -> m+{-# INLINABLE difference #-}++-- | /O(n*log m)/ Intersection of two maps. Return elements of the first+-- map for keys existing in the second.+intersection :: (Eq k, Hashable k) => LinkedHashMap k v -> LinkedHashMap k w -> LinkedHashMap k v+intersection a b = foldlWithKey' go empty a+  where+    go m k v = case lookup k b of+                 Just _ -> insert k v m+                 _      -> m+{-# INLINABLE intersection #-}++-- | /O(n+m)/ Intersection of two maps. If a key occurs in both maps+-- the provided function is used to combine the values from the two+-- maps.+intersectionWith :: (Eq k, Hashable k) => (v1 -> v2 -> v3) -> LinkedHashMap k v1+                 -> LinkedHashMap k v2 -> LinkedHashMap k v3+intersectionWith f a b = foldlWithKey' go empty a+  where+    go m k v = case lookup k b of+                 Just w -> insert k (f v w) m+                 _      -> m+{-# INLINABLE intersectionWith #-}++-- | /O(n)/ Reduce this map by applying a binary operator to all+-- elements, using the given starting value (typically the+-- left-identity of the operator).  Each application of the operator+-- is evaluated before before using the result in the next+-- application.  This function is strict in the starting value.+foldl' :: (a -> v -> a) -> a -> LinkedHashMap k v -> a+foldl' f b0 (LinkedHashMap _ s _) = F.foldl' f' b0 s+  where+    f' b (Just (_, v)) = f b v+    f' b _ = b++-- | /O(n)/ Reduce this map by applying a binary operator to all+-- elements, using the given starting value (typically the+-- right-identity of the operator).+foldr :: (v -> a -> a) -> a -> LinkedHashMap k v -> a+foldr = F.foldr+{-# INLINE foldr #-}++-- | /O(n)/ Reduce this map by applying a binary operator to all+-- elements, using the given starting value (typically the+-- left-identity of the operator).  Each application of the operator+-- is evaluated before before using the result in the next+-- application.  This function is strict in the starting value.+foldlWithKey' :: (a -> k -> v -> a) -> a -> LinkedHashMap k v -> a+foldlWithKey' f b0 (LinkedHashMap _ s _) = F.foldl' f' b0 s+  where+    f' b (Just (k, v)) = f b k v+    f' b _ = b++-- | /O(n)/ Reduce this map by applying a binary operator to all+-- elements, using the given starting value (typically the+-- right-identity of the operator).+foldrWithKey :: (k -> v -> a -> a) -> a -> LinkedHashMap k v -> a+foldrWithKey f b0 (LinkedHashMap _ s _) = F.foldr f' b0 s+  where+    f' (Just (k, v)) b = f k v b+    f' _ b = b++-- | /O(n*log(n))/ Filter this map by retaining only elements satisfying a+-- predicate.+filterWithKey :: (Eq k, Hashable k) => (k -> v -> Bool) -> LinkedHashMap k v -> LinkedHashMap k v+filterWithKey p m = fromList $ L.filter (uncurry p) $ toList m++-- | /O(n*log(n))/ Filter this map by retaining only elements which values+-- satisfy a predicate.+filter :: (Eq k, Hashable k) => (v -> Bool) -> LinkedHashMap k v -> LinkedHashMap k v+filter p = filterWithKey (\_ v -> p v)+{-# INLINE filter #-}+ instance (NFData a) => NFData (Entry a) where     rnf (Entry a) = rnf a  instance (NFData k, NFData v) => NFData (LinkedHashMap k v) where     rnf (LinkedHashMap m s _) = rnf m `seq` rnf s++instance Functor (LinkedHashMap k) where+    fmap = map++instance F.Foldable (LinkedHashMap k) where+    foldr f b0 (LinkedHashMap _ s _) = F.foldr f' b0 s+      where+        f' (Just (_, v)) b = f v b+        f' _ b = b+        +instance T.Traversable (LinkedHashMap k) where+    traverse f = traverseWithKey (const f)

@@ -7,8 +7,8 @@     , singleton      -- * Combine-    -- , union-    -- , unions+    , union+    , unions      -- * Basic interface     , null@@ -18,25 +18,25 @@     , delete      -- * Transformations-    -- , map+    , map        -- * Difference and intersection-    -- , difference-    -- , intersection+    , difference+    , intersection      -- * Folds-    -- , foldl'-    -- , foldr+    , foldl'+    , foldr      -- * Filter-    -- , filter+    , filter      -- ** Lists     , toList     , fromList     ) where -import Prelude hiding (null, lookup)+import Prelude hiding (null, lookup, map, foldr, filter) import Control.DeepSeq (NFData(rnf)) import Data.Hashable (Hashable) import qualified Data.List as L@@ -60,18 +60,15 @@ singleton a = LinkedHashSet (M.singleton a ()) {-# INLINABLE singleton #-} --- -- | /O(n+m)/ Construct a set containing all elements from both sets.--- ----- -- To obtain good performance, the smaller set must be presented as--- -- the first argument.--- union :: (Eq a, Hashable a) => LinkedHashSet a -> LinkedHashSet a -> LinkedHashSet a--- union s1 s2 = LinkedHashSet $ M.union (asMap s1) (asMap s2)--- {-# INLINE union #-}+-- | /O(m*log n)/ Construct a set containing all elements from both sets, n - size of first map.+union :: (Eq a, Hashable a) => LinkedHashSet a -> LinkedHashSet a -> LinkedHashSet a+union s1 s2 = LinkedHashSet $ M.union (asMap s1) (asMap s2)+{-# INLINE union #-} --- -- | Construct a set containing all elements from a list of sets.--- unions :: (Eq a, Hashable a) => [LinkedHashSet a] -> LinkedHashSet a--- unions = List.foldl' union empty--- {-# INLINE unions #-}+-- | Construct a set containing all elements from a list of sets.+unions :: (Eq a, Hashable a) => [LinkedHashSet a] -> LinkedHashSet a+unions = L.foldl' union empty+{-# INLINE unions #-}  -- | /O(1)/ Return 'True' if this set is empty, 'False' otherwise. null :: LinkedHashSet a -> Bool@@ -102,52 +99,52 @@ delete a = LinkedHashSet . M.delete a . asMap {-# INLINABLE delete #-} --- -- | /O(n)/ Transform this set by applying a function to every value.--- -- The resulting set may be smaller than the source.--- map :: (Hashable b, Eq b) => (a -> b) -> LinkedHashSet a -> LinkedHashSet b--- map f = fromList . List.map f . toList--- {-# INLINE map #-}+-- | /O(n)/ Transform this set by applying a function to every value.+-- The resulting set may be smaller than the source.+map :: (Hashable b, Eq b) => (a -> b) -> LinkedHashSet a -> LinkedHashSet b+map f = fromList . L.map f . toList+{-# INLINE map #-} --- -- | /O(n)/ Difference of two sets. Return elements of the first set--- -- not existing in the second.--- difference :: (Eq a, Hashable a) => LinkedHashSet a -> LinkedHashSet a -> LinkedHashSet a--- difference (LinkedHashSet a) (LinkedHashSet b) = LinkedHashSet (M.difference a b)--- {-# INLINABLE difference #-}+-- | /O(n)/ Difference of two sets. Return elements of the first set+-- not existing in the second.+difference :: (Eq a, Hashable a) => LinkedHashSet a -> LinkedHashSet a -> LinkedHashSet a+difference (LinkedHashSet a) (LinkedHashSet b) = LinkedHashSet (M.difference a b)+{-# INLINABLE difference #-} --- -- | /O(n)/ Intersection of two sets. Return elements present in both--- -- the first set and the second.--- intersection :: (Eq a, Hashable a) => LinkedHashSet a -> LinkedHashSet a -> LinkedHashSet a--- intersection (LinkedHashSet a) (LinkedHashSet b) = LinkedHashSet (M.intersection a b)--- {-# INLINABLE intersection #-}+-- | /O(n)/ Intersection of two sets. Return elements present in both+-- the first set and the second.+intersection :: (Eq a, Hashable a) => LinkedHashSet a -> LinkedHashSet a -> LinkedHashSet a+intersection (LinkedHashSet a) (LinkedHashSet b) = LinkedHashSet (M.intersection a b)+{-# INLINABLE intersection #-} --- -- | /O(n)/ Reduce this set by applying a binary operator to all--- -- elements, using the given starting value (typically the--- -- left-identity of the operator).  Each application of the operator--- -- is evaluated before before using the result in the next--- -- application.  This function is strict in the starting value.--- foldl' :: (a -> b -> a) -> a -> LinkedHashSet b -> a--- foldl' f z0 = M.foldlWithKey' g z0 . asMap---   where g z k _ = f z k--- {-# INLINE foldl' #-}+-- | /O(n)/ Reduce this set by applying a binary operator to all+-- elements, using the given starting value (typically the+-- left-identity of the operator).  Each application of the operator+-- is evaluated before before using the result in the next+-- application.  This function is strict in the starting value.+foldl' :: (a -> b -> a) -> a -> LinkedHashSet b -> a+foldl' f z0 = M.foldlWithKey' g z0 . asMap+  where g z k _ = f z k+{-# INLINE foldl' #-} --- -- | /O(n)/ Reduce this set by applying a binary operator to all--- -- elements, using the given starting value (typically the--- -- right-identity of the operator).--- foldr :: (b -> a -> a) -> a -> LinkedHashSet b -> a--- foldr f z0 = foldrWithKey g z0 . asMap---   where g k _ z = f k z--- {-# INLINE foldr #-}+-- | /O(n)/ Reduce this set by applying a binary operator to all+-- elements, using the given starting value (typically the+-- right-identity of the operator).+foldr :: (b -> a -> a) -> a -> LinkedHashSet b -> a+foldr f z0 = M.foldrWithKey g z0 . asMap+  where g k _ z = f k z+{-# INLINE foldr #-} --- -- | /O(n)/ Filter this set by retaining only elements satisfying a--- -- predicate.--- filter :: (a -> Bool) -> LinkedHashSet a -> LinkedHashSet a--- filter p = LinkedHashSet . H.filterWithKey q . asMap---   where q k _ = p k--- {-# INLINE filter #-}+-- | /O(n)/ Filter this set by retaining only elements satisfying a+-- predicate.+filter :: (Eq a, Hashable a) => (a -> Bool) -> LinkedHashSet a -> LinkedHashSet a+filter p = LinkedHashSet . M.filterWithKey q . asMap+  where q k _ = p k+{-# INLINE filter #-}  -- | /O(n)/ Return a list of this set's elements.  The list is produced lazily. toList :: LinkedHashSet a -> [a]-toList t = map (\(k, _) -> k) $ M.toList (asMap t)+toList t = L.map (\(k, _) -> k) $ M.toList (asMap t) {-# INLINE toList #-}  -- | /O(n*min(W, n))/ Construct a set from a list of elements.

@@ -2,6 +2,8 @@  import Test.Tasty import Test.Tasty.HUnit+import Control.Monad.State+import Control.Applicative ((<$>))  import qualified Data.LinkedHashMap.Seq as LM1 import qualified Data.LinkedHashMap.IntMap as LM2@@ -36,6 +38,67 @@ test9_1 = LM1.fromList ([] :: [(Int, String)]) test9_2 = LM2.fromList ([] :: [(Int, String)]) +test10_1 = LM1.insertWith (++) 5 "ZZZ_" test0_1+test10_2 = LM2.insertWith (++) 5 "ZZZ_" test0_2+test10_3 = LM1.insertWith (++) 11 "ZZZ_" test0_1+test10_4 = LM2.insertWith (++) 11 "ZZZ_" test0_2++test11_1 = LM1.adjust (\v0 -> v0 ++ "_adjusted") 5 test0_1+test11_2 = LM2.adjust (\v0 -> v0 ++ "_adjusted") 5 test0_2+test11_3 = LM1.adjust (\v0 -> v0 ++ "_adjusted") 123 test0_1+test11_4 = LM2.adjust (\v0 -> v0 ++ "_adjusted") 123 test0_2++t0_1 = LM1.fromList [(1 :: Int,"A"), (5, "B"), (7, "C"), (-6, "D")]+t1_1 = LM1.fromList [(2 :: Int,"2A"), (3, "2B"), (7, "2C"), (-6, "2D")]+t2_1 = LM1.fromList [(0 :: Int,"3A"), (5, "3B"), (17, "3C"), (-6, "3D")]++t0_2 = LM2.fromList [(1 :: Int,"A"), (5, "B"), (7, "C"), (-6, "D")]+t1_2 = LM2.fromList [(2 :: Int,"2A"), (3, "2B"), (7, "2C"), (-6, "2D")]+t2_2 = LM2.fromList [(0 :: Int,"3A"), (5, "3B"), (17, "3C"), (-6, "3D")]++test12_1 = LM1.union t0_1 t1_1+test12_2 = LM2.union t0_2 t1_2+test12_3 = LM1.union t1_1 t2_1+test12_4 = LM2.union t1_2 t2_2+test12_5 = LM1.unionWith (++) t0_1 t1_1+test12_6 = LM2.unionWith (++) t0_2 t1_2+test12_7 = LM1.unions [t0_1, t1_1, t2_1]+test12_8 = LM2.unions [t0_2, t1_2, t2_2]++joinPrev :: Int -> String -> State String String+joinPrev _ v = do+  prev <- get+  put v+  return $ v ++ ":" ++ prev++test13_1 = m where (m, _) = runState (LM1.traverseWithKey joinPrev test0_1) "0"+test13_2 = m where (m, _) = runState (LM2.traverseWithKey joinPrev test0_2) "0"++test14_1 = LM1.difference test6_1 (LM1.delete 1 $ LM1.delete 7 $ test0_1)+test14_2 = LM2.difference test6_2 (LM2.delete 1 $ LM2.delete 7 $ test0_2)+test15_1 = LM1.intersection test6_1 (LM1.delete 1 $ LM1.delete 7 $ test0_1)+test15_2 = LM2.intersection test6_2 (LM2.delete 1 $ LM2.delete 7 $ test0_2)+test16_1 = LM1.intersectionWith (\v1 v2 -> v1 ++ v2) test6_1 (LM1.delete 1 $ LM1.delete 7 $ test0_1)+test16_2 = LM2.intersectionWith (\v1 v2 -> v1 ++ v2) test6_2 (LM2.delete 1 $ LM2.delete 7 $ test0_2)++test17_1 = LM1.foldr (++) "" test6_1+test17_2 = LM2.foldr (++) "" test6_2+test18_1 = LM1.foldl' (++) "" test6_1+test18_2 = LM2.foldl' (++) "" test6_2++test19_1 = LM1.foldlWithKey' (\a k v -> a ++ (show k) ++ "=" ++ v ++ ",") "" test6_1+test19_2 = LM2.foldlWithKey' (\a k v -> a ++ (show k) ++ "=" ++ v ++ ",") "" test6_2+test20_1 = LM1.foldrWithKey (\k v a -> a ++ (show k) ++ "=" ++ v ++ ",") "" test6_1+test20_2 = LM2.foldrWithKey (\k v a -> a ++ (show k) ++ "=" ++ v ++ ",") "" test6_2++test21_1 = LM1.filter (\v -> v == "B" || v == "C") test0_1+test21_2 = LM2.filter (\v -> v == "B" || v == "C") test0_2+test22_1 = LM1.filterWithKey (\k v -> v == "B" || k == -6) test0_1+test22_2 = LM2.filterWithKey (\k v -> v == "B" || k == -6) test0_2++test23_1 = LM1.fromListWith (\v1 v2 -> v2 ++ v1) [(1 :: Int,"A"), (5, "B"), (7, "C"), (-6, "D"), (1 :: Int,"ZZZ")]+test23_2 = LM2.fromListWith (\v1 v2 -> v2 ++ v1) [(1 :: Int,"A"), (5, "B"), (7, "C"), (-6, "D"), (1 :: Int,"ZZZ")]+ unitTests :: TestTree unitTests = testGroup "Unit tests"   [ testCase "test0" $ LM1.toList test0_1 @?= LM2.toList test0_2,@@ -45,11 +108,30 @@     testCase "test4" $ LM1.toList test4_1 @?= LM2.toList test4_2,     testCase "test5" $ LM1.toList test5_1 @?= LM2.toList test5_2,     testCase "test6" $ LM1.toList test6_1 @?= LM2.toList test6_2,-    testCase "test7" $ LM1.toList test7_1 @?= LM2.toList test7_2,+    testCase "test7_1" $ LM1.toList test7_1 @?= LM2.toList test7_2,     testCase "test7_2" $ LM1.toList test7_1 @?= [(1,"AA"),(5,"BB"),(7,"CCC"),(-6,"D")],-    testCase "test8" $ LM1.toList test8_1 @?= LM2.toList test8_2,+    testCase "test8_1" $ LM1.toList test8_1 @?= LM2.toList test8_2,     testCase "test8_2" $ LM1.toList test8_1 @?= [(1::Int, "D")],-    testCase "test9" $ LM1.toList test9_1 @?= LM2.toList test9_2+    testCase "test9" $ LM1.toList test9_1 @?= LM2.toList test9_2,+    testCase "test10_1" $ LM1.toList test10_1 @?= LM2.toList test10_2,+    testCase "test10_2" $ LM1.toList test10_3 @?= LM2.toList test10_4,+    testCase "test11_1" $ LM1.toList test11_1 @?= LM2.toList test11_2,+    testCase "test11_2" $ LM1.toList test11_3 @?= LM2.toList test11_4,+    testCase "test12_1" $ LM1.toList test12_1 @?= LM2.toList test12_2,+    testCase "test12_1" $ LM1.toList test12_3 @?= LM2.toList test12_4,+    testCase "test12_2" $ LM1.toList test12_5 @?= LM2.toList test12_6,+    testCase "test12_3" $ LM1.toList test12_7 @?= LM2.toList test12_8,+    testCase "test13" $ LM1.toList test13_1 @?= LM2.toList test13_2,+    testCase "test14" $ LM1.toList test14_1 @?= LM2.toList test14_2,+    testCase "test15" $ LM1.toList test15_1 @?= LM2.toList test15_2,+    testCase "test16" $ LM1.toList test16_1 @?= LM2.toList test16_2,+    testCase "test17" $ test17_1 @?= test17_2,+    testCase "test18" $ test18_1 @?= test18_2,+    testCase "test19" $ test19_1 @?= test19_2,+    testCase "test20" $ test20_1 @?= test20_2,+    testCase "test21" $ LM1.toList test21_1 @?= LM2.toList test21_2,+    testCase "test22" $ LM1.toList test22_1 @?= LM2.toList test22_2,+    testCase "test23" $ LM1.toList test23_1 @?= LM2.toList test23_2   ]  main :: IO ()

@@ -0,0 +1,34 @@+-- Initial linkedhashmap-tests.cabal generated by cabal init.  For further +-- documentation, see http://haskell.org/cabal/users-guide/++name:                linkedhashmap-tests+version:             0.1.0.0+-- synopsis:            +-- description:         +license:             BSD3+license-file:        LICENSE+author:              Andrey Basko+maintainer:          andrey_basko@yahoo.com+-- copyright:           +category:            Data+build-type:          Simple+-- extra-source-files:  +cabal-version:       >=1.10++executable linkedhashmap-tests+  main-is:             Main.hs+  -- other-modules:       +  -- other-extensions:    +  build-depends:       base >=4.7 && <4.8+                     , containers >= 0.5.5.1+                     , hashable >= 1.2.2.0+                     , tasty >= 0.10.0.2+                     , tasty-hunit >= 0.9.0.1+                     , mtl >= 2.1.3.1+                     , unordered-containers >= 0.2.5.0+                     , deepseq >= 1.1+  -- hs-source-dirs:      +  default-language:    Haskell2010+  hs-source-dirs: +    ./+    ../src