-- ----------------------------------------------------------------------------
{- |
Module : Holumbus.Data.MultiMap
Copyright : Copyright (C) 2008 Stefan Schmidt
License : MIT
Maintainer : Stefan Schmidt (stefanschmidt@web.de)
Stability : experimental
Portability: portable
Version : 0.1
This module provides a MultiMap, that means a Map, which can hold
multiple values for one key, but every distinct value is only stores once.
So adding the same key-value-pair twice will only create one new entry in
the map.
This Map is helpfull to examine how many different key-values-pairs you
have in your application.
Most of the functions are borrowed from Data.Map
-}
-- ----------------------------------------------------------------------------
module Holumbus.Data.MultiMap
(
MultiMap
, empty
, null
, insert
, insertSet
, insertKeys
, lookup
, keys
, elems
, filterElements
, member
, delete
, deleteKey
, deleteElem
, deleteAllElems
, fromList
, fromTupleList
, toList
, toAscList
)
where
import Prelude hiding (null, lookup)
import qualified Data.Map as Map
import qualified Data.Set as Set
-- | A MultiMap, it can hold more (different!!!) Elements for one key.
data MultiMap k a = MM (Map.Map k (Set.Set a))
deriving (Show, Eq, Ord)
{-
instance (Show k, Show a) => Show (MultiMap k a) where
show (MM m) = msShow
where
ms = map (\(k,s) -> (k, Set.toList s)) (Map.toList m)
msShow = concat $ map (\(k,s) -> (show k) ++ "\n" ++ (showL s)) ms
showL ls = concat $ map (\s -> show s ++ "\n") ls
-}
-- | The empty MultiMap.
empty :: (Ord k, Ord a) => MultiMap k a
empty = MM Map.empty
-- | Test, if the MultiMap is empty.
null :: (Ord k, Ord a) => MultiMap k a -> Bool
null (MM m) = Map.null m
-- | Inserts an element in the MultiMap.
insert :: (Ord k, Ord a) => k -> a -> MultiMap k a -> MultiMap k a
insert k a (MM m) = MM $ Map.alter altering k m
where
altering Nothing = Just $ Set.singleton a
altering (Just s) = Just $ Set.insert a s
-- | Inserts multiple elements in a set to the MultiMap.
insertSet :: (Ord k, Ord a) => k -> Set.Set a -> MultiMap k a -> MultiMap k a
insertSet k newSet mm@(MM m) =
if (Set.null newSet) then mm else MM $ Map.alter altering k m
where
altering Nothing = Just newSet
altering (Just s) = Just $ Set.union newSet s
-- | Inserts multiple keys with the same values.
insertKeys :: (Ord k, Ord a) => [k] -> Set.Set a -> MultiMap k a -> MultiMap k a
insertKeys ks a m = foldl (\m' k -> insertSet k a m') m ks
-- | Gets all different elements for one key or an empty set.
lookup :: (Ord k, Ord a) => k -> MultiMap k a -> Set.Set a
lookup k (MM m) = maybe (Set.empty) (id) (Map.lookup k m)
-- | Get all different elements from a list of keys.
lookupKeys :: (Ord k, Ord a) => [k] -> MultiMap k a -> Set.Set a
lookupKeys ks m = Set.unions $ map (\k -> lookup k m) ks
-- | Get all different keys from the map.
keys :: (Ord k, Ord a) => MultiMap k a -> Set.Set k
keys (MM m) = Set.fromList $ Map.keys m
-- | Get all different values in the map without regarding their keys.
elems :: (Ord k, Ord a) => MultiMap k a -> Set.Set a
elems (MM m) = Set.unions $ Map.elems m
-- | Like lookup keys, but an empty input list will give all elements back,
-- not the empty set.
filterElements :: (Ord k, Ord a) => [k] -> MultiMap k a -> Set.Set a
filterElements [] m = elems m -- get all
filterElements ks m = lookupKeys ks m
-- | Test, if a key is in the Map.
member :: (Ord k, Ord a) => k -> MultiMap k a -> Bool
member k m = Set.empty /= lookup k m
-- | Deletes an Element from the Map, if the data in Nothing, the whole key is
-- deleted.
delete :: (Ord k, Ord a) => k -> Maybe a -> MultiMap k a -> MultiMap k a
delete k Nothing m = deleteKey k m
delete k (Just a) m = deleteElem k a m
-- | Deletes a whole key from the map.
deleteKey :: (Ord k, Ord a) => k -> MultiMap k a -> MultiMap k a
deleteKey k (MM m) = MM $ Map.delete k m
-- | Deletes a single Element from the map.
deleteElem :: (Ord k, Ord a) => k -> a -> MultiMap k a -> MultiMap k a
deleteElem k a (MM m) = MM $ Map.alter delSet k m
where
delSet Nothing = Nothing
delSet (Just set) = filterEmpty $ Set.delete a set
filterEmpty set
| set == Set.empty = Nothing
| otherwise = Just set
-- | Deletes all Elements (*,a) (slow!!!).
deleteAllElems :: (Ord k, Ord a) => a -> MultiMap k a -> MultiMap k a
deleteAllElems a m = foldl (\m'' k -> deleteElem k a m'') m ks
where
ks = Set.toList $ keys m
-- | Creates a MultiMap from a list of pairs (key,set value).
fromList :: (Ord k, Ord a) => [(k,Set.Set a)] -> MultiMap k a
fromList ks = foldl (\m (k,as) -> insertSet k as m) empty ks
-- | Creates a MultiMap from a list of tuples.
fromTupleList :: (Ord k, Ord a) => [(k,a)] -> MultiMap k a
fromTupleList ks = foldl (\m (k,a) -> insert k a m) empty ks
-- | Transforms a MultiMap to a list of pairs (key,set value).
toList :: (Ord k, Ord a) => MultiMap k a -> [(k,Set.Set a)]
toList (MM m) = Map.toList m
-- | The same as toList, but the keys are in ascending order.
toAscList :: (Ord k, Ord a) => MultiMap k a -> [(k,Set.Set a)]
toAscList (MM m) = Map.toAscList m