-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | A multimap.
--   
@package multimap
@version 1.2


-- | A SetMap allows the association of multiple values with a single key,
--   but there are no duplicates per key.
module Data.SetMap

-- | A SetMap with keys <tt>k</tt> and values <tt>v</tt>.
data SetMap k v

-- | <i>O(1).</i> Check whether the multimap is empty or not.
null :: SetMap k a -> Bool

-- | <i>O(1).</i> The number of elements in the multimap.
size :: SetMap k a -> Int

-- | <i>O(1).</i> 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

-- | <i>O(1).</i> 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

-- | <i>O(log n).</i> Is the key a member of the multimap?
member :: Ord k => SetMap k a -> k -> Bool

-- | <i>O(log n).</i> Is the key not a member of the multimap?
notMember :: Ord k => SetMap k a -> k -> Bool

-- | <i>O(log n).</i> 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 <tt>flip lookup</tt>
(!) :: Ord k => SetMap k a -> k -> Set a

-- | <i>O(1).</i> 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
--   <a>concat</a> to flatten.
elems :: SetMap k a -> [[a]]

-- | <i>O(n).</i> Return all keys of the multimap in ascending order.
keys :: SetMap k a -> [k]

-- | <i>O(1).</i> Return the map of sets.
toMap :: SetMap k a -> Map k (Set a)
instance Typeable SetMap
instance (Data k, Data v, Ord k, Ord v) => Data (SetMap k v)


-- | A very simple MultiMap, based on <a>Map</a> from the containers
--   package.
module Data.MultiMap

-- | A MultiMap with keys <tt>k</tt> and values <tt>v</tt>.
--   
--   A key can have multiple values (but not zero). The same value can be
--   added multiple times (thus no constraints are ever imposed on
--   <tt>v</tt>).
--   
--   Internally this is simply a <tt>Map k [v]</tt>. See <a>toMap</a> for
--   accessing the underlying <a>Map</a>.
data MultiMap k v

-- | <i>O(1).</i> Check whether the multimap is empty or not.
null :: MultiMap k a -> Bool

-- | <i>O(1).</i> The number of elements in the multimap.
size :: MultiMap k a -> Int

-- | <i>O(1).</i> 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

-- | <i>O(1).</i> 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

-- | <i>O(log n).</i> Is the key a member of the multimap?
member :: Ord k => MultiMap k a -> k -> Bool

-- | <i>O(log n).</i> Is the key not a member of the multimap?
notMember :: Ord k => MultiMap k a -> k -> Bool

-- | <i>O(log n).</i> 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 <tt>flip lookup</tt>
(!) :: Ord k => MultiMap k a -> k -> [a]

-- | <i>O(1).</i> The empty multimap.
empty :: MultiMap k a

-- | <i>O(log n).</i> Insert a new key and value in the map.
insert :: Ord k => k -> a -> MultiMap k a -> MultiMap k a

-- | <i>O(log n).</i> 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

-- | <i>O(n).</i> 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

-- | <i>O(n).</i> 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

-- | <i>O(n).</i> 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
--   <a>concat</a> to flatten.
elems :: MultiMap k a -> [[a]]

-- | <i>O(n).</i> Return all keys of the multimap in ascending order.
keys :: MultiMap k a -> [k]

-- | <i>O(n).</i> The set of all keys of the multimap.
keysSet :: MultiMap k a -> Set k

-- | <i>O(n).</i> Return all key/value pairs in the multimap in ascending
--   key order.
assocs :: MultiMap k a -> [(k, [a])]

-- | <i>O(1).</i> 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)]

-- | <i>O(n*log n)</i> Create a multimap from a list of key/value pairs.
--   
--   <pre>
--   fromList xs == foldr (uncurry insert) empty
--   </pre>
fromList :: Ord k => [(k, a)] -> MultiMap k a

-- | Turns a map of lists into a multimap.
fromMap :: Map k [a] -> MultiMap k a

-- | <i>O(log n)</i> Find the minimal key of the multimap.
findMin :: MultiMap k a -> Maybe k

-- | <i>O(log n)</i> Find the maximal key of the multimap.
findMax :: MultiMap k a -> Maybe k

-- | <i>O(log n)</i> Find the minimal key and the values associated with
--   it.
findMinWithValues :: MultiMap k a -> Maybe (k, [a])

-- | <i>O(log n)</i> Find the maximal key and the values associated with
--   it.
findMaxWithValues :: MultiMap k a -> Maybe (k, [a])
instance Typeable MultiMap
instance (Data k, Data v, Ord k) => Data (MultiMap k v)