rosso-1.0: General purpose utility library

Data.MultiMap.Rosso1

Description

MultiMap data structure: similar to a map (Data.Map), but allows multiple values with the same key.

Synopsis

Documentation

data MultiMap k a Source

Instances

(Show k, Show a) => Show (MultiMap k a) 

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

Converts an association list into a multimap. If the association list contains duplicate keys, then the corresponding lists of values become concatenated.

>>> fromList [(4, "dca"), (1, "aba"), (2, "b"), (1, "ac"), (3, "")]
fromList [(1,"abaac"),(2,"b"),(4,"dca")]

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

Converts a multimap into an association list, with the keys in ascending order.

>>> toList $ fromList [(4, "dca"), (1, "aba"), (2, "b"), (1, "ac"), (3, "")]
[(1,"abaac"),(2,"b"),(4,"dca")]

empty :: MultiMap k aSource

The empty multimap.

singleton :: k -> a -> MultiMap k aSource

A multimap with a single entry.

insert :: Ord k => k -> a -> MultiMap k a -> MultiMap k aSource

Inserts a new key-value pair. If other entries already exist with the same key, then the new entry is inserted just before them.

>>> insert 2 'a' $ fromList [(1, "efg"), (2, "jzw"), (3, "abc")]
fromList [(1,"efg"),(2,"ajzw"),(3,"abc")]

insertMany :: Ord k => [(k, a)] -> MultiMap k a -> MultiMap k aSource

Passes down the list from left to right, inserting each entry into the multimap.

>>> insertMany [(1, 'a'), (5, 'a'), (1, 'a'), (1, 'b')] empty
fromList [(1,"baa"),(5,"a")]

insertList :: Ord k => k -> [a] -> MultiMap k a -> MultiMap k aSource

Prepends a list of values onto the entry with the given key.

>>> insertList 7 "hello" $ fromList [(5, "ab"), (7, "efg")]
fromList [(5,"ab"),(7,"helloefg")]

insertManyLists :: Ord k => [(k, [a])] -> MultiMap k a -> MultiMap k aSource

Passes down the given list from left to right invoking insertList.

null :: MultiMap k a -> BoolSource

Tests if the multimap is empty.

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

Returns the list of values associated with the given key.

>>> lookup 5 $ fromList [(1, "abc"), (5, "aagf"), (6, "c")]
"aagf"

deleteList :: Ord k => k -> MultiMap k a -> MultiMap k aSource

Deletes all the values associated with the given key.

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

Simultaneous lookup and deleteList.

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

For each key that maps to a non-empty list of values, returns that key and its corresponding values as well as the multimap with those values removed. The keys are enumerated in ascending order.

alter :: Ord k => ([a] -> [a]) -> k -> MultiMap k a -> MultiMap k aSource

Modifies the list of values associated with a given key.

maxView :: MultiMap k a -> Maybe (a, MultiMap k a)Source

Returns Nothing if the multimap is empty, otherwise returns the first value associated with the maximal key of the multimap, and the multimap stripped of that value.

>>> maxView $ fromList [(1, "ab"), (2, "efg")]
Just ('e',fromList [(1,"ab"),(2,"fg")])

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

Returns all of the values in the multimap in ascending order of their keys.

>>> elems $ fromList [(1, "aba"), (2, "adf"), (3, "z")]
"abaadfz"

descElems :: MultiMap k a -> [a]Source

Returns all of the values in the multimap in descending order of their keys. The values are enumerated in the same order as with maxView.

>>> descElems $ fromList [(1, "aba"), (2, "adf"), (3, "z")]
"zadfaba"

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

Returns all of the key-value pairs in the multimap in ascending order of keys.

>>> assocs $ fromList [(1, "ab"), (4, "cda")]
[(1,'a'),(1,'b'),(4,'c'),(4,'d'),(4,'a')]

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

Returns all of the key-value pairs in the multimap in descending order of keys. The values are enumerated in the same order as with maxView.

>>> descAssocs (fromList [(1, "ab"), (4, "cda")])
[(4,'c'),(4,'d'),(4,'a'),(1,'a'),(1,'b')]