multimap 1.0 → 1.1

raw patch · 2 files changed

+46/−7 lines, 2 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• multimap.cabal +5/−2
• src/Data/Multimap.hs +41/−5

@@ -1,7 +1,10 @@ Name:           multimap-Version:        1.0+Version:        1.1 Synopsis:       A multimap. Description:    This is a simple implementation of a multimap, based on "Data.Map".+                .+                [@v1.1@] @!@ had its arguments flipped. Fixed.+                    Also added @fromMap@.                  License:        MIT License-File:   LICENSE@@ -11,7 +14,7 @@ Cabal-Version:  >= 1.6 Category:       Data Structures Stability:      provisional-Homepage:       http://hub.darcs.net/scravy/strings+Homepage:       http://hub.darcs.net/scravy/multimap  Source-Repository head     type: darcs

@@ -49,6 +49,7 @@     toMapOfSets,     toList,     fromList,+    fromMap,          -- * Min/Max     findMin,@@ -84,10 +85,12 @@ -- ^ /O(1)./ Check whether the multimap is empty or not. null (Multimap (_, _, m)) = Map.null m + size :: Multimap k a -> Int -- ^ /O(1)./ The number of elements in the multimap. size (Multimap (_, size, _)) = fromIntegral size + numKeys :: Multimap k a -> Word32 -- ^ /O(1)./ The number of keys in the multimap. -- @@ -95,6 +98,7 @@ -- necessarily equal to the number of values. numKeys (Multimap (nk, _, _)) = nk + numValues :: Multimap k a -> Word32 -- ^ /O(1)./ The number of values in the multimap. --@@ -102,21 +106,24 @@ -- necessarily equal to the number of values. numValues (Multimap (_, nv, _)) = nv + notMember, member :: Ord k => Multimap k a -> k -> Bool -- | /O(log n)./ Is the key a member of the multimap? member (Multimap (_, _, map)) key = Map.member key map -- | /O(log n)./ Is the key not a member of the multimap? notMember key = not . member key -(!) :: Ord k => k -> Multimap k a -> [a]-(!) = lookup +(!) :: Ord k => Multimap k a -> k -> [a]+-- ^ As @flip lookup@+(!) = flip lookup++ lookup :: Ord k => k -> Multimap k a -> [a] -- ^ /O(log n)./ Lookup the value at a key in the map. ----- The function will return the corrsponding values as a List,--- or the empty list if no values are associated witht the--- given key.+-- The function will return the corrsponding values as a List, or the+-- empty list if no values are associated witht the given key. lookup key (Multimap (_, _, map)) = maybe [] id (Map.lookup key map)  @@ -137,14 +144,17 @@     Just v -> Multimap (pred nk, nv - fromIntegral (length v), Map.delete k map)     _      -> m + map :: (a -> b) -> Multimap k a -> Multimap k b -- ^ Map a function over all values in the map. map f (Multimap (nk, nv, map)) = Multimap (nk, nv, Map.map (P.map f) map) + mapKeys :: Ord k2 => (k1 -> k2) -> Multimap k1 a -> Multimap k2 a -- ^ mapKeys f s is the multimap obtained by applying f to each key of s. mapKeys f (Multimap (nk, nv, map)) = Multimap (nk, nv, Map.mapKeys f map) + mapWithKey :: (k -> a -> b) -> Multimap k a -> Multimap k b -- ^ Map a function over all key/value pairs in the map. mapWithKey f (Multimap (nk, nv, map))@@ -152,15 +162,24 @@   foldr :: (a -> b -> b) -> b -> Multimap k a -> b+-- ^ Fold the values in the map using the given right-associative binary operator. foldr f e = P.foldr f e . concat . elems + foldl :: (a -> b -> a) -> a -> Multimap k b -> a+-- ^  Fold the values in the map using the given left-associative binary operator. foldl f e = P.foldl f e . concat . elems + foldrWithKey :: (k -> a -> b -> b) -> b -> Multimap k a -> b+-- ^ /O(n)./ Fold the keys and values in the map using the given right-associative+-- binary operator, taking into account not only the value but also the key. foldrWithKey f e = P.foldr (uncurry f) e . toList + foldlWithKey :: (a -> k -> b -> a) -> a -> Multimap k b -> a+-- ^ /O(n)./ Fold the keys and values in the map using the given left-associative+-- binary operator, taking into account not only the value but also the key. foldlWithKey f e = P.foldl (\a (k,v) -> f a k v) e . toList  @@ -172,14 +191,17 @@ -- multiple values. Use 'concat' to flatten. elems (Multimap (_, _, map)) = Map.elems map + keys :: Multimap k a -> [k] -- ^ /O(n)./ Return all keys of the multimap in ascending order. keys (Multimap (_, _, map)) = Map.keys map + keysSet :: Multimap k a -> Set k -- ^ /O(n)./ The set of all keys of the multimap. keysSet (Multimap (_, _, map)) = Map.keysSet map + assocs :: Multimap k a -> [(k, [a])] -- ^ /O(n)./ Return all key/value pairs in the multimap -- in ascending key order.@@ -190,16 +212,19 @@ -- ^ /O(1)./ Return the map of lists. toMap (Multimap (_, _, theUnderlyingMap)) = theUnderlyingMap + toMapOfSets :: Ord a => Multimap k a -> Map k (Set a) -- ^ /O(k*m*log m) where k is the number of keys and m the -- maximum number of elements associated with a single key/ toMapOfSets (Multimap (_, _, map)) = Map.map Set.fromList map + toList :: Multimap k a -> [(k, a)] -- ^ Return a flattened list of key/value pairs. toList (Multimap (_, _, map))   = concat $ Map.elems $ Map.mapWithKey (\k -> zip (repeat k)) map + fromList :: Ord k => [(k, a)] -> Multimap k a -- ^ /O(n*log n)/ Create a multimap from a list of key/value pairs. --@@ -207,23 +232,34 @@ fromList = P.foldr (uncurry insert) empty  +fromMap :: Map k [a] -> Multimap k a+-- ^ Turns a map of lists into a multimap.+fromMap map = Multimap (numKeys, numValues, map)+  where+    numKeys   = fromIntegral $ Map.size map+    numValues = fromIntegral $ Map.foldr (\v s -> length v + s) 0 map++ findMin :: Multimap k a -> Maybe k -- ^ /O(log n)/ Find the minimal key of the multimap. findMin (Multimap (_, _, map))     | Map.null map = Nothing     | otherwise    = Just $ fst $ Map.findMin map + findMax :: Multimap k a -> Maybe k -- ^ /O(log n)/ Find the maximal key of the multimap. findMax (Multimap (_, _, map))     | Map.null map = Nothing     | otherwise    = Just $ fst $ Map.findMax map + findMinWithValues :: Multimap k a -> Maybe (k, [a]) -- ^ /O(log n)/ Find the minimal key and the values associated with it. findMinWithValues (Multimap (_, _, map))     | Map.null map = Nothing     | otherwise    = Just $ Map.findMin map+  findMaxWithValues :: Multimap k a -> Maybe (k, [a]) -- ^ /O(log n)/ Find the maximal key and the values associated with it.