-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | A multimap. -- -- This is a simple implementation of a multimap, based on -- Data.Map. -- -- @package multimap @version 1.2.1 module Data.SetMap -- | A SetMap with keys k and values v. data SetMap k v -- | O(1). Check whether the multimap is empty or not. null :: SetMap k a -> Bool -- | O(1). The number of elements in the multimap. size :: SetMap k a -> Int -- | 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 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 k a -> Word32 -- | O(log n). Is the key a member of the multimap? member :: Ord k => SetMap k a -> k -> Bool -- | O(log n). Is the key not a member of the multimap? notMember :: Ord k => SetMap k a -> k -> Bool -- | 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 :: Ord k => k -> SetMap k a -> Set a -- | As flip lookup (!) :: Ord k => SetMap k a -> k -> Set a -- | O(1). The empty multimap. empty :: SetMap k a -- | Insert a new key and value in the map. insert :: (Ord k, Ord a) => k -> a -> SetMap k a -> SetMap k a -- | Delete a key and all its values from the map. delete :: Ord k => k -> SetMap k a -> SetMap k a -- | Map a function over all values in the map. map :: (Ord a, Ord b) => (a -> b) -> SetMap k a -> SetMap k b -- | 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 k a -> [[a]] -- | O(n). Return all keys of the multimap in ascending order. keys :: SetMap k a -> [k] -- | O(1). Return the map of sets. toMap :: SetMap k a -> Map k (Set a) instance Typeable2 SetMap instance (Data k, Data v, Ord k, Ord v) => Data (SetMap k v) -- | A very simple MultiMap, based on Map from the containers -- package. module Data.MultiMap -- | 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. data MultiMap k v -- | O(1). Check whether the multimap is empty or not. null :: MultiMap k a -> Bool -- | O(1). The number of elements in the multimap. size :: MultiMap k a -> Int -- | 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 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 k a -> Word32 -- | O(log n). Is the key a member of the multimap? member :: Ord k => MultiMap k a -> k -> Bool -- | O(log n). Is the key not a member of the multimap? notMember :: Ord k => MultiMap k a -> k -> Bool -- | 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 :: Ord k => k -> MultiMap k a -> [a] -- | As flip lookup (!) :: Ord k => MultiMap k a -> k -> [a] -- | O(1). The empty multimap. empty :: MultiMap k a -- | O(log n). Insert a new key and value in the map. insert :: Ord k => k -> a -> MultiMap k a -> MultiMap k a -- | O(log n). Delete a key and all its values from the map. delete :: Ord k => k -> MultiMap k a -> MultiMap k a -- | Map a function over all values in the map. map :: (a -> b) -> MultiMap k a -> MultiMap k b -- | mapKeys f s is the multimap obtained by applying f to each key of s. mapKeys :: Ord k2 => (k1 -> k2) -> MultiMap k1 a -> MultiMap k2 a -- | Map a function over all key/value pairs in the map. mapWithKey :: (k -> a -> b) -> MultiMap k a -> MultiMap k b -- | Fold the values in the map using the given right-associative binary -- operator. foldr :: (a -> b -> b) -> b -> MultiMap k a -> b -- | Fold the values in the map using the given left-associative binary -- operator. foldl :: (a -> b -> a) -> a -> MultiMap k b -> a -- | 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 :: (k -> a -> b -> b) -> b -> MultiMap k a -> b -- | 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 :: (a -> k -> b -> a) -> a -> MultiMap k b -> 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 k a -> [[a]] -- | O(n). Return all keys of the multimap in ascending order. keys :: MultiMap k a -> [k] -- | O(n). The set of all keys of the multimap. keysSet :: MultiMap k a -> Set k -- | O(n). Return all key/value pairs in the multimap in ascending -- key order. assocs :: MultiMap k a -> [(k, [a])] -- | O(1). Return the map of lists. toMap :: MultiMap k a -> Map k [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 :: Ord a => MultiMap k a -> Map k (Set a) -- | Return a flattened list of key/value pairs. toList :: MultiMap k a -> [(k, a)] -- | O(n*log n) Create a multimap from a list of key/value pairs. -- -- 
--   fromList xs == foldr (uncurry insert) empty
--
fromList :: Ord k => [(k, a)] -> MultiMap k a -- | Turns a map of lists into a multimap. fromMap :: Map k [a] -> MultiMap k a -- | O(log n) Find the minimal key of the multimap. findMin :: MultiMap k a -> Maybe k -- | O(log n) Find the maximal key of the multimap. findMax :: MultiMap k a -> Maybe k -- | O(log n) Find the minimal key and the values associated with -- it. findMinWithValues :: MultiMap k a -> Maybe (k, [a]) -- | O(log n) Find the maximal key and the values associated with -- it. findMaxWithValues :: MultiMap k a -> Maybe (k, [a]) instance Typeable2 MultiMap instance (Data k, Data v, Ord k) => Data (MultiMap k v)