Copyright	(c) Julian Fleischer 2013
License	MIT (See LICENSE file in cabal package)
Maintainer	julian.fleischer@fu-berlin.de
Portability	non-portable (DeriveDataTypeable)
Safe Haskell	Safe-Inferred
Language	Haskell2010

Data.MultiMap

Contents

MultiMap type
Query
Operators
Construction
- Insertion
- Delete
Traversal
Folds
Conversion
Min/Max

Description

A very simple MultiMap, based on Map from the containers package.

Synopsis

data MultiMap k v
null :: MultiMap k a -> Bool
size :: MultiMap k a -> Int
numKeys :: MultiMap k a -> Word32
numValues :: MultiMap k a -> Word32
member :: Ord k => MultiMap k a -> k -> Bool
notMember :: Ord k => MultiMap k a -> k -> Bool
lookup :: Ord k => k -> MultiMap k a -> [a]
(!) :: Ord k => MultiMap k a -> k -> [a]
empty :: MultiMap k a
insert :: Ord k => k -> a -> MultiMap k a -> MultiMap k a
delete :: Ord k => k -> MultiMap k a -> MultiMap k a
map :: (a -> b) -> MultiMap k a -> MultiMap k b
mapKeys :: Ord k2 => (k1 -> k2) -> MultiMap k1 a -> MultiMap k2 a
mapWithKey :: (k -> a -> b) -> MultiMap k a -> MultiMap k b
foldr :: (a -> b -> b) -> b -> MultiMap k a -> b
foldl :: (a -> b -> a) -> a -> MultiMap k b -> a
foldrWithKey :: (k -> a -> b -> b) -> b -> MultiMap k a -> b
foldlWithKey :: (a -> k -> b -> a) -> a -> MultiMap k b -> a
elems :: MultiMap k a -> [[a]]
keys :: MultiMap k a -> [k]
keysSet :: MultiMap k a -> Set k
assocs :: MultiMap k a -> [(k, [a])]
toMap :: MultiMap k a -> Map k [a]
toMapOfSets :: Ord a => MultiMap k a -> Map k (Set a)
toList :: MultiMap k a -> [(k, a)]
fromList :: Ord k => [(k, a)] -> MultiMap k a
fromMap :: Map k [a] -> MultiMap k a
findMin :: MultiMap k a -> Maybe k
findMax :: MultiMap k a -> Maybe k
findMinWithValues :: MultiMap k a -> Maybe (k, [a])
findMaxWithValues :: MultiMap k a -> Maybe (k, [a])

MultiMap type

data MultiMap k v Source #

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.

Instances

Instances details

(Data k, Data v, Ord k) => Data (MultiMap k v) Source #

Instance details

Defined in Data.MultiMap

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> MultiMap k v -> c (MultiMap k v) Source #

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (MultiMap k v) Source #

toConstr :: MultiMap k v -> Constr Source #

dataTypeOf :: MultiMap k v -> DataType Source #

dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (MultiMap k v)) Source #

dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (MultiMap k v)) Source #

gmapT :: (forall b. Data b => b -> b) -> MultiMap k v -> MultiMap k v Source #

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> MultiMap k v -> r Source #

gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> MultiMap k v -> r Source #

gmapQ :: (forall d. Data d => d -> u) -> MultiMap k v -> [u] Source #

gmapQi :: Int -> (forall d. Data d => d -> u) -> MultiMap k v -> u Source #

gmapM :: Monad m => (forall d. Data d => d -> m d) -> MultiMap k v -> m (MultiMap k v) Source #

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> MultiMap k v -> m (MultiMap k v) Source #

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> MultiMap k v -> m (MultiMap k v) Source #

Query

null :: MultiMap k a -> Bool Source #

O(1). Check whether the multimap is empty or not.

size :: MultiMap k a -> Int Source #

O(1). The number of elements in the multimap.

numKeys :: MultiMap k a -> Word32 Source #

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.

numValues :: MultiMap k a -> Word32 Source #

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.

member :: Ord k => MultiMap k a -> k -> Bool Source #

O(log n). Is the key a member of the multimap?

notMember :: Ord k => MultiMap k a -> k -> Bool Source #

O(log n). Is the key not a member of the multimap?

lookup :: Ord k => k -> MultiMap k a -> [a] Source #

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.

Operators

(!) :: Ord k => MultiMap k a -> k -> [a] Source #

As flip lookup

Construction

empty :: MultiMap k a Source #

O(1). The empty multimap.

Insertion

insert :: Ord k => k -> a -> MultiMap k a -> MultiMap k a Source #

O(log n). Insert a new key and value in the map.

Delete

delete :: Ord k => k -> MultiMap k a -> MultiMap k a Source #

O(log n). Delete a key and all its values from the map.

Traversal

map :: (a -> b) -> MultiMap k a -> MultiMap k b Source #

Map a function over all values in the map.

mapKeys :: Ord k2 => (k1 -> k2) -> MultiMap k1 a -> MultiMap k2 a Source #

mapKeys f s is the multimap obtained by applying f to each key of s.

mapWithKey :: (k -> a -> b) -> MultiMap k a -> MultiMap k b Source #

Map a function over all key/value pairs in the map.

Folds

foldr :: (a -> b -> b) -> b -> MultiMap k a -> b Source #

Fold the values in the map using the given right-associative binary operator.

foldl :: (a -> b -> a) -> a -> MultiMap k b -> a Source #

Fold the values in the map using the given left-associative binary operator.

foldrWithKey :: (k -> a -> b -> b) -> b -> MultiMap k a -> b Source #

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.

foldlWithKey :: (a -> k -> b -> a) -> a -> MultiMap k b -> a Source #

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.

Conversion

elems :: MultiMap k a -> [[a]] Source #

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.

keys :: MultiMap k a -> [k] Source #

O(n). Return all keys of the multimap in ascending order.

keysSet :: MultiMap k a -> Set k Source #

O(n). The set of all keys of the multimap.

assocs :: MultiMap k a -> [(k, [a])] Source #

O(n). Return all key/value pairs in the multimap in ascending key order.

toMap :: MultiMap k a -> Map k [a] Source #

O(1). Return the map of lists.

toMapOfSets :: Ord a => MultiMap k a -> Map k (Set a) Source #

/O(k*m*log m) where k is the number of keys and m the maximum number of elements associated with a single key/

toList :: MultiMap k a -> [(k, a)] Source #

Return a flattened list of key/value pairs.

fromList :: Ord k => [(k, a)] -> MultiMap k a Source #

O(n*log n) Create a multimap from a list of key/value pairs.

fromList xs == foldr (uncurry insert) empty

fromMap :: Map k [a] -> MultiMap k a Source #

Turns a map of lists into a multimap.

Min/Max

findMin :: MultiMap k a -> Maybe k Source #

O(log n) Find the minimal key of the multimap.

findMax :: MultiMap k a -> Maybe k Source #

O(log n) Find the maximal key of the multimap.

findMinWithValues :: MultiMap k a -> Maybe (k, [a]) Source #

O(log n) Find the minimal key and the values associated with it.

findMaxWithValues :: MultiMap k a -> Maybe (k, [a]) Source #

O(log n) Find the maximal key and the values associated with it.