| 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
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
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
| (Data k, Data v, Ord k) => Data (MultiMap k v) Source # | |
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
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.
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
Construction
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
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.
assocs :: MultiMap k a -> [(k, [a])] Source #
O(n). Return all key/value pairs in the multimap in ascending key order.
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/
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
Min/Max
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.