packages feed

multimap 1.1 → 1.2

raw patch · 4 files changed

+451/−275 lines, 4 files

Files

multimap.cabal view
@@ -1,10 +1,16 @@ Name:           multimap-Version:        1.1+Version:        1.2 Synopsis:       A multimap. Description:    This is a simple implementation of a multimap, based on "Data.Map".                 .-                [@v1.1@] @!@ had its arguments flipped. Fixed.+                [@v1.1@]+                    @!@ had its arguments flipped. Fixed.                     Also added @fromMap@.+                .+                [@v1.2]+                    Added "Data.SetMap", renamed @Multimap@ to "Data.MultiMap".+                    Fixed the type of @delete@. Derive instances for @Data@+                    and @Typeable@.                  License:        MIT License-File:   LICENSE@@ -21,7 +27,8 @@     location: hub.darcs.net:multimap  Library-    Exposed-Modules:    Data.Multimap+    Exposed-Modules:    Data.MultiMap+                        , Data.SetMap     Build-Depends:      base >= 3 && < 5, containers     Hs-Source-Dirs:     src
+ src/Data/MultiMap.hs view
@@ -0,0 +1,281 @@+{-# LANGUAGE Haskell2010+    , DeriveDataTypeable+ #-}+{-# OPTIONS+    -Wall+    -fno-warn-name-shadowing+ #-}++-- | A very simple MultiMap, based on 'Data.Map.Map' from the containers package.+module Data.MultiMap (++    -- * MultiMap type+    MultiMap,++    -- * Query+    null,+    size,+    numKeys,+    numValues,++    member,+    notMember,+    lookup,++    -- * Operators+    (!),++    -- * Construction+    empty,+    +    -- ** Insertion+    insert,++    -- ** Delete+    delete,++    -- * Traversal+    map,+    mapKeys,+    mapWithKey,+    +    -- * Folds+    foldr,+    foldl,+    foldrWithKey,+    foldlWithKey,++    -- * Conversion+    elems,+    keys,+    keysSet,+    assocs,++    toMap,+    toMapOfSets,+    toList,+    fromList,+    fromMap,+    +    -- * Min/Max+    findMin,+    findMax,+    findMinWithValues,+    findMaxWithValues++  ) where++import Prelude hiding (lookup, map, null, foldr, foldl)+import qualified Prelude as P++import qualified Data.Set as Set+import Data.Set (Set)++import qualified Data.Map as Map+import Data.Map (Map)++import Data.Word+import Data.Data+++-- | A MultiMap with keys @k@ and values @v@.+--+-- A key can have multiple values (but not zero).+-- The same value can be added multiple times (thus no+-- constraints are ever imposed on @v@).+--+-- Internally this is simply a @Map k [v]@.+-- See 'toMap' for accessing the underlying 'Map'.+newtype MultiMap k v = MultiMap (Word32, Word32, Map k [v])+    deriving (Data, Typeable)+++null :: MultiMap k a -> Bool+-- ^ /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.+-- +-- As this is a multimap, the number of keys is not+-- 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.+--+-- As this is a multimap, the number of keys is not+-- 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 => 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.+lookup key (MultiMap (_, _, map)) = maybe [] id (Map.lookup key map)+++empty :: MultiMap k a+-- ^ /O(1)./ The empty multimap.+empty = MultiMap (0, 0, Map.empty)+++insert :: Ord k => k -> a -> MultiMap k a -> MultiMap k a+-- ^ /O(log n)./ Insert a new key and value in the map.+insert k v (MultiMap (nk, nv, map))+    | Map.member k map = MultiMap (nk, succ nv, Map.insert k (v : map Map.! k) map)+    | otherwise = MultiMap (succ nk, succ nv, Map.insert k [v] map)++delete :: Ord k => k -> MultiMap k a -> MultiMap k a+-- ^ /O(log n)./ Delete a key and all its values from the map.+delete k m@(MultiMap (nk, nv, map)) = case Map.lookup k map of+    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))+  = MultiMap (nk, nv, Map.mapWithKey (\k -> P.map (f k)) map)+++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+++elems :: MultiMap k a -> [[a]]+-- ^ /O(n)./ Return all elements of the multimap in the+-- ascending order of their keys.+--+-- A list of lists is returned since a key can have+-- 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.+assocs (MultiMap (_, _, map)) = Map.assocs map+++toMap :: MultiMap k a -> Map k [a]+-- ^ /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.+--+-- > fromList xs == foldr (uncurry insert) empty+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.+findMaxWithValues (MultiMap (_, _, map))+    | Map.null map = Nothing+    | otherwise    = Just $ Map.findMax map++++
− src/Data/Multimap.hs 
@@ -1,272 +0,0 @@-{-# LANGUAGE Haskell2010 #-}---- | A very simple Multimap, based on 'Data.Map.Map' from the containers package.-module Data.Multimap (--    -- * Multimap type-    Multimap,--    -- * Query-    null,-    size,-    numKeys,-    numValues,--    member,-    notMember,-    lookup,--    -- * Operators-    (!),--    -- * Construction-    empty,-    -    -- ** Insertion-    insert,--    -- ** Delete-    delete,--    -- * Traversal-    map,-    mapKeys,-    mapWithKey,-    -    -- * Folds-    foldr,-    foldl,-    foldrWithKey,-    foldlWithKey,--    -- * Conversion-    elems,-    keys,-    keysSet,-    assocs,--    toMap,-    toMapOfSets,-    toList,-    fromList,-    fromMap,-    -    -- * Min/Max-    findMin,-    findMax,-    findMinWithValues,-    findMaxWithValues--  ) where--import Prelude hiding (lookup, map, null, foldr, foldl)-import qualified Prelude as P--import qualified Data.Set as Set-import Data.Set (Set)--import qualified Data.Map as Map-import Data.Map (Map)--import Data.Word---- | A Multimap with keys @k@ and values @v@.------ A key can have multiple values (but not zero).--- The same value can be added multiple times (thus no--- constraints are ever imposed on @v@).------ Internally this is simply a @Map k [v]@.--- See 'toMap' for accessing the underlying 'Map'.-newtype Multimap k v = Multimap (Word32, Word32, Map k [v])---null :: Multimap k a -> Bool--- ^ /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.--- --- As this is a multimap, the number of keys is not--- 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.------ As this is a multimap, the number of keys is not--- 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 => 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.-lookup key (Multimap (_, _, map)) = maybe [] id (Map.lookup key map)---empty :: Multimap k a--- ^ /O(1)./ The empty multimap.-empty = Multimap (0, 0, Map.empty)---insert :: Ord k => k -> a -> Multimap k a -> Multimap k a--- ^ /O(log n)./ Insert a new key and value in the map.-insert k v (Multimap (nk, nv, map))-    | Map.member k map = Multimap (nk, succ nv, Map.insert k (v : map Map.! k) map)-    | otherwise = Multimap (succ nk, succ nv, Map.insert k [v] map)--delete :: Ord k => k -> a -> Multimap k a -> Multimap k a--- ^ /O(log n)./ Delete a key and all its values from the map.-delete k v m@(Multimap (nk, nv, map)) = case Map.lookup k map of-    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))-  = Multimap (nk, nv, Map.mapWithKey (\k -> P.map (f k)) map)---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---elems :: Multimap k a -> [[a]]--- ^ /O(n)./ Return all elements of the multimap in the--- ascending order of their keys.------ A list of lists is returned since a key can have--- 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.-assocs (Multimap (_, _, map)) = Map.assocs map---toMap :: Multimap k a -> Map k [a]--- ^ /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.------ > fromList xs == foldr (uncurry insert) empty-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.-findMaxWithValues (Multimap (_, _, map))-    | Map.null map = Nothing-    | otherwise    = Just $ Map.findMax map----
+ src/Data/SetMap.hs view
@@ -0,0 +1,160 @@+{-# LANGUAGE Haskell2010+    , DeriveDataTypeable+ #-}+{-# OPTIONS+    -Wall+    -fno-warn-name-shadowing+ #-}++-- | A SetMap allows the association of multiple values with a single key,+-- but there are no duplicates per key.+module Data.SetMap (++    -- * SetMap type+    SetMap,++    -- * Query+    null,+    size,+    numKeys,+    numValues,++    member,+    notMember,+    lookup,++    -- * Operators+    (!),++    -- * Construction+    empty,+    +    -- ** Insertion+    insert,++    -- ** Deletion+    delete,++    -- * Traversal+    map,++    -- * Conversion+    elems,+    keys,++    toMap,++  ) where+++import Prelude hiding (lookup, map, null, foldr, foldl)+import qualified Prelude as P++import qualified Data.Set as Set+import Data.Set (Set)++import qualified Data.Map as Map+import Data.Map (Map)++import Data.Word+import Data.Data+++-- | A SetMap with keys @k@ and values @v@.+newtype SetMap k v = SetMap (Word32, Word32, Map k (Set v))+    deriving (Data, Typeable)+++null :: SetMap k a -> Bool+-- ^ /O(1)./ Check whether the multimap is empty or not.+null (SetMap (_, _, m)) = Map.null m+++size :: SetMap k a -> Int+-- ^ /O(1)./ The number of elements in the multimap.+size (SetMap (_, size, _)) = fromIntegral size+++numKeys :: SetMap k a -> Word32+-- ^ /O(1)./ The number of keys in the multimap.+-- +-- As this is a multimap, the number of keys is not+-- necessarily equal to the number of values.+numKeys (SetMap (nk, _, _)) = nk+++numValues :: SetMap k a -> Word32+-- ^ /O(1)./ The number of values in the multimap.+--+-- As this is a multimap, the number of keys is not+-- necessarily equal to the number of values.+numValues (SetMap (_, nv, _)) = nv+++notMember, member :: Ord k => SetMap k a -> k -> Bool+-- | /O(log n)./ Is the key a member of the multimap?+member (SetMap (_, _, 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 => SetMap k a -> k -> Set a+-- ^ As @flip lookup@+(!) = flip lookup+++lookup :: Ord k => k -> SetMap k a -> Set 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.+lookup key (SetMap (_, _, map)) = maybe Set.empty id (Map.lookup key map)+++empty :: SetMap k a+-- ^ /O(1)./ The empty multimap.+empty = SetMap (0, 0, Map.empty)+++insert :: (Ord k, Ord a) => k -> a -> SetMap k a -> SetMap k a+-- ^ Insert a new key and value in the map.+insert k v (SetMap (nk, nv, map))+    | Map.member k map =+        let oldSet = map Map.! k+            (nv', newSet) = if v `Set.member` oldSet+                then (nv, oldSet) else (succ nv, v `Set.insert` oldSet)+        in  SetMap (nk, nv', Map.insert k newSet map)+    | otherwise = SetMap (succ nk, succ nv, Map.insert k (Set.singleton v) map)+++delete :: Ord k => k -> SetMap k a -> SetMap k a+-- ^ Delete a key and all its values from the map.+delete k m@(SetMap (nk, nv, map)) = case Map.lookup k map of+    Just v -> SetMap (pred nk, nv - fromIntegral (Set.size v), Map.delete k map)+    _      -> m+++map :: (Ord a, Ord b) => (a -> b) -> SetMap k a -> SetMap k b+-- ^ Map a function over all values in the map.+map f (SetMap (nk, nv, map)) = SetMap (nk, nv, Map.map (Set.map f) map)+++elems :: SetMap k a -> [[a]]+-- ^ Return all elements of the multimap in the+-- ascending order of their keys.+--+-- A list of lists is returned since a key can have+-- multiple values. Use 'concat' to flatten.+elems (SetMap (_, _, map)) = P.map (Set.elems) $ Map.elems map+++keys :: SetMap k a -> [k]+-- ^ /O(n)./ Return all keys of the multimap in ascending order.+keys (SetMap (_, _, map)) = Map.keys map+++toMap :: SetMap k a -> Map k (Set a)+-- ^ /O(1)./ Return the map of sets.+toMap (SetMap (_, _, theUnderlyingMap)) = theUnderlyingMap++