unordered-containers 0.1.4.2 → 0.1.4.3
raw patch · 7 files changed
+151/−7 lines, 7 filesdep ~basedep ~deepseq
Dependency ranges changed: base, deepseq
Files
- Data/FullList/Lazy.hs +36/−0
- Data/FullList/Strict.hs +38/−1
- Data/HashMap/Common.hs +4/−0
- Data/HashMap/Lazy.hs +25/−0
- Data/HashMap/Strict.hs +26/−1
- tests/MapProperties.hs +17/−0
- unordered-containers.cabal +5/−5
Data/FullList/Lazy.hs view
@@ -28,6 +28,7 @@ -- * Combine -- * Union , union+ , unionWith -- * Transformations , map@@ -39,6 +40,9 @@ -- * Filter , filterWithKey+ -- * For use by FL.Strict+ , lookupL+ , deleteL ) where import Control.Applicative@@ -241,6 +245,38 @@ | otherwise = Cons k' v' $ go ys #if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE unionL #-}+#endif++unionWith :: Eq k => (v -> v -> v) -> FullList k v -> FullList k v -> FullList k v+unionWith f xs (FL k vy ys) =+ case lookup k xs of+ Just vx ->+ let flCon = FL k (f vx vy)+ in case delete k xs of+ Nothing -> flCon ys+ Just xs' ->+ case unionWithL f xs' ys of+ FL k' v' zs -> flCon $ Cons k' v' zs+ Nothing ->+ case unionWithL f xs ys of+ FL k' v' zs -> FL k vy $ Cons k' v' zs+#if __GLASGOW_HASKELL__ >= 700+{-# INLINABLE unionWith #-}+#endif++unionWithL :: Eq k => (v -> v -> v) -> FullList k v -> List k v -> FullList k v+unionWithL f (FL k v zs) ys =+ case lookupL k ys of + Just vy -> FL k (f v vy) $ go zs (deleteL k ys)+ Nothing -> FL k v (go zs ys)+ where+ go ws Nil = ws+ go ws (Cons k' vy ys') =+ case lookupL k' ws of+ Just vx -> Cons k' (f vx vy) $ go (deleteL k' ws) ys'+ Nothing -> Cons k' vy $ go ws ys'+#if __GLASGOW_HASKELL__ >= 700+{-# INLINABLE unionWithL #-} #endif ------------------------------------------------------------------------
Data/FullList/Strict.hs view
@@ -24,6 +24,10 @@ , insertWith , adjust + -- * Combine+ -- ** Union+ , unionWith+ -- * Transformations , map , traverseWithKey@@ -38,7 +42,7 @@ import Prelude hiding (lookup, map) -import Data.FullList.Lazy hiding (insertWith, map, adjust)+import Data.FullList.Lazy hiding (insertWith, map, adjust, unionWith) insertWith :: Eq k => (v -> v -> v) -> k -> v -> FullList k v -> FullList k v insertWith f !k v (FL k' v' xs)@@ -93,3 +97,36 @@ go (Cons k v xs) = let !(k', !v') = f k v in Cons k' v' (go xs) {-# INLINE mapL #-}++unionWith :: Eq k => (v -> v -> v) -> FullList k v -> FullList k v -> FullList k v+unionWith f xs (FL k vy ys) =+ case lookup k xs of+ Just vx ->+ let !vFinal = f vx vy+ flCon = FL k vFinal+ in case delete k xs of+ Nothing -> flCon ys+ Just xs' ->+ case unionWithL f xs' ys of+ FL k' v' zs -> flCon $ Cons k' v' zs+ Nothing ->+ case unionWithL f xs ys of+ FL k' v' zs -> FL k vy $ Cons k' v' zs+#if __GLASGOW_HASKELL__ >= 700+{-# INLINABLE unionWith #-}+#endif++unionWithL :: Eq k => (v -> v -> v) -> FullList k v -> List k v -> FullList k v+unionWithL f (FL k v zs) ys =+ case lookupL k ys of+ Just vy -> let !vFinal = f v vy in FL k vFinal $ go zs (deleteL k ys)+ Nothing -> FL k v (go zs ys)+ where+ go ws Nil = ws+ go ws (Cons k' vy ys') =+ case lookupL k' ws of+ Just vx -> let !vFinal = f vx vy in Cons k' vFinal $ go (deleteL k' ws) ys'+ Nothing -> Cons k' vy $ go ws ys'+#if __GLASGOW_HASKELL__ >= 700+{-# INLINABLE unionWithL #-}+#endif
Data/HashMap/Common.hs view
@@ -26,6 +26,10 @@ -- * Folds , foldrWithKey++ -- * Helpers+ , shorter+ , insertCollidingWith ) where #include "MachDeps.h"
Data/HashMap/Lazy.hs view
@@ -48,6 +48,7 @@ -- * Combine -- ** Union , union+ , unionWith -- * Transformations , map@@ -229,6 +230,30 @@ go Nil = Nil f' k v = (k, f v) {-# INLINE map #-}++-- | /O(n+m)/ The union of two maps. If a key occurs in both maps,+-- the provided function (first argument) will be used to compute the result.+unionWith :: Eq k => (v -> v -> v) -> HashMap k v -> HashMap k v -> HashMap k v+unionWith f t1@(Bin sm1 l1 r1) t2@(Bin sm2 l2 r2)+ | sm1 == sm2 = Bin sm1 (unionWith f l1 l2) (unionWith f r1 r2)+ | shorter sm1 sm2 = union1+ | shorter sm2 sm1 = union2+ | otherwise = join sm1 t1 sm2 t2+ where+ union1 | nomatch sm2 sm1 = join sm1 t1 sm2 t2+ | zero sm2 sm1 = Bin sm1 (unionWith f l1 t2) r1+ | otherwise = Bin sm1 l1 (unionWith f r1 t2)++ union2 | nomatch sm1 sm2 = join sm1 t1 sm2 t2+ | zero sm1 sm2 = Bin sm2 (unionWith f t1 l2) r2+ | otherwise = Bin sm2 l2 (unionWith f t1 r2)+unionWith f (Tip h l) t = insertCollidingWith (FL.unionWith f) h l t+unionWith f t (Tip h l) = insertCollidingWith (flip (FL.unionWith f)) h l t -- right bias+unionWith _ Nil t = t+unionWith _ t Nil = t+#if __GLASGOW_HASKELL__ >= 700+{-# INLINABLE unionWith #-}+#endif -- | /O(n)/ Difference of two maps. Return elements of the first map -- not existing in the second.
Data/HashMap/Strict.hs view
@@ -49,6 +49,7 @@ -- * Combine -- ** Union , union+ , unionWith -- * Transformations , map@@ -84,7 +85,7 @@ import qualified Data.FullList.Strict as FL import Data.HashMap.Common import Data.HashMap.Lazy hiding (fromList, fromListWith, insert, insertWith,- adjust, map, singleton)+ adjust, map, singleton, unionWith) import qualified Data.HashMap.Lazy as L import qualified Data.List as List @@ -170,6 +171,30 @@ go Nil = Nil f' k v = (k, f v) {-# INLINE map #-}++-- | /O(n+m)/ The union of two maps. If a key occurs in both maps,+-- the provided function (first argument) will be used to compute the result.+unionWith :: Eq k => (v -> v -> v) -> HashMap k v -> HashMap k v -> HashMap k v+unionWith f t1@(Bin sm1 l1 r1) t2@(Bin sm2 l2 r2)+ | sm1 == sm2 = Bin sm1 (unionWith f l1 l2) (unionWith f r1 r2)+ | shorter sm1 sm2 = union1+ | shorter sm2 sm1 = union2+ | otherwise = join sm1 t1 sm2 t2+ where+ union1 | nomatch sm2 sm1 = join sm1 t1 sm2 t2+ | zero sm2 sm1 = Bin sm1 (unionWith f l1 t2) r1+ | otherwise = Bin sm1 l1 (unionWith f r1 t2)++ union2 | nomatch sm1 sm2 = join sm1 t1 sm2 t2+ | zero sm1 sm2 = Bin sm2 (unionWith f t1 l2) r2+ | otherwise = Bin sm2 l2 (unionWith f t1 r2)+unionWith f (Tip h l) t = insertCollidingWith (FL.unionWith f) h l t+unionWith f t (Tip h l) = insertCollidingWith (flip (FL.unionWith f)) h l t -- right bias+unionWith _ Nil t = t+unionWith _ t Nil = t+#if __GLASGOW_HASKELL__ >= 700+{-# INLINABLE unionWith #-}+#endif ------------------------------------------------------------------------ -- Conversions
tests/MapProperties.hs view
@@ -71,6 +71,13 @@ as = fromList xs bs = fromList ys +pUnionWith :: [(Key, Int)] -> [(Key, Int)] -> Bool+pUnionWith xs ys = L.sort (unionByKeyWith (-) as bs) ==+ toAscList (M.unionWith (-) (M.fromList as) (M.fromList bs))+ where+ as = fromList xs+ bs = fromList ys+ ------------------------------------------------------------------------ -- ** Transformations @@ -127,6 +134,7 @@ ] -- Combine , testProperty "union" pUnion+ , testProperty "unionWith" pUnionWith -- Transformations , testProperty "map" pMap -- Folds@@ -200,6 +208,15 @@ unionByKey :: (Eq k, Eq v) => [(k, v)] -> [(k, v)] -> [(k, v)] unionByKey = L.unionBy ((==) `on` fst)++unionByKeyWith :: (Eq k, Eq v) => (v -> v -> v) -> [(k,v)] -> [(k,v)] -> [(k,v)]+unionByKeyWith f a b = go a b+ where+ go [] ys = ys+ go (x:xs) ys =+ case L.lookup (fst x) ys of+ Just z -> (fst x, f (snd x) z) : go xs (filter ((/= fst x) . fst) ys)+ Nothing -> x : go xs ys toAscList :: (Ord k, Ord v) => M.HashMap k v -> [(k, v)] toAscList = L.sort . M.toList
unordered-containers.cabal view
@@ -1,5 +1,5 @@ name: unordered-containers-version: 0.1.4.2+version: 0.1.4.3 synopsis: Efficient hashing-based container types description: Efficient hashing-based container types. The containers have been@@ -35,8 +35,8 @@ Data.HashSet build-depends:- base < 4.5,- deepseq == 1.1.*,+ base >= 4 && < 4.5,+ deepseq >= 1.1 && < 1.3, hashable >= 1.0.1.1 && < 1.2 other-modules:@@ -59,7 +59,7 @@ type: exitcode-stdio-1.0 build-depends:- base,+ base >= 4 && < 4.5, hashable >= 1.0.1.1 && < 1.2, QuickCheck >= 2.4.0.1, test-framework >= 0.3.3 && < 0.5,@@ -75,7 +75,7 @@ type: exitcode-stdio-1.0 build-depends:- base,+ base >= 4 && < 4.5, containers, hashable >= 1.0.1.1 && < 1.2, QuickCheck >= 2.4.0.1,