    {-# LANGUAGE Haskell2010
        , DeriveDataTypeable
     #-}
    {-# OPTIONS
        -Wall
        -fno-warn-name-shadowing
     #-}

    -- |
    -- Module       : Data.MultiMap
    -- Copyright    : (c) Julian Fleischer 2013
    -- License      : MIT (See LICENSE file in cabal package)
    --
    -- Maintainer   : julian.fleischer@fu-berlin.de
    -- Portability  : non-portable (DeriveDataTypeable)
    --
    -- A very simple MultiMap, based on 'Data.Map.Map' from the containers package.
    module Data.MultiMap (

        -- * MultiMap type
        MultiMap,

        -- * Query
        null,
        size,
        numKeys,
        numValues,

        member,
        notMember,
        lookup,

        -- * Operators
        (!),

        -- * Construction
        empty,

        -- ** Insertion
        insert,

        -- ** Delete
        delete,

        -- * Traversal
        map,
        mapKeys,
        mapWithKey,

        -- * Folds
        foldr,
        foldl,
        foldrWithKey,
        foldlWithKey,

        -- * Conversion
        elems,
        keys,
        keysSet,
        assocs,

        toMap,
        toMapOfSets,
        toList,
        fromList,
        fromMap,

        -- * Min/Max
        findMin,
        findMax,
        findMinWithValues,
        findMaxWithValues

      ) where

    import Prelude hiding (lookup, map, null, foldr, foldl)
    import qualified Prelude as P

    import qualified Data.Set as Set
    import Data.Set (Set)

    import qualified Data.Map as Map
    import Data.Map (Map)

    import Data.Word
    import Data.Data

    -- | 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'.
    newtype MultiMap k v = MultiMap (Word32, Word32, Map k [v])
        deriving (Typeable (MultiMap k v)
    Typeable (MultiMap k v) =>
    (forall (c :: * -> *).
     (forall d b. Data d => c (d -> b) -> d -> c b)
     -> (forall g. g -> c g) -> MultiMap k v -> c (MultiMap k v))
    -> (forall (c :: * -> *).
        (forall b r. Data b => c (b -> r) -> c r)
        -> (forall r. r -> c r) -> Constr -> c (MultiMap k v))
    -> (MultiMap k v -> Constr)
    -> (MultiMap k v -> DataType)
    -> (forall (t :: * -> *) (c :: * -> *).
        Typeable t =>
        (forall d. Data d => c (t d)) -> Maybe (c (MultiMap k v)))
    -> (forall (t :: * -> * -> *) (c :: * -> *).
        Typeable t =>
        (forall d e. (Data d, Data e) => c (t d e))
        -> Maybe (c (MultiMap k v)))
    -> ((forall b. Data b => b -> b) -> MultiMap k v -> MultiMap k v)
    -> (forall r r'.
        (r -> r' -> r)
        -> r -> (forall d. Data d => d -> r') -> MultiMap k v -> r)
    -> (forall r r'.
        (r' -> r -> r)
        -> r -> (forall d. Data d => d -> r') -> MultiMap k v -> r)
    -> (forall u. (forall d. Data d => d -> u) -> MultiMap k v -> [u])
    -> (forall u.
        Int -> (forall d. Data d => d -> u) -> MultiMap k v -> u)
    -> (forall (m :: * -> *).
        Monad m =>
        (forall d. Data d => d -> m d) -> MultiMap k v -> m (MultiMap k v))
    -> (forall (m :: * -> *).
        MonadPlus m =>
        (forall d. Data d => d -> m d) -> MultiMap k v -> m (MultiMap k v))
    -> (forall (m :: * -> *).
        MonadPlus m =>
        (forall d. Data d => d -> m d) -> MultiMap k v -> m (MultiMap k v))
    -> Data (MultiMap k v)
    MultiMap k v -> Constr
    MultiMap k v -> DataType
    (forall b. Data b => b -> b) -> MultiMap k v -> MultiMap k v
    forall a.
    Typeable a =>
    (forall (c :: * -> *).
     (forall d b. Data d => c (d -> b) -> d -> c b)
     -> (forall g. g -> c g) -> a -> c a)
    -> (forall (c :: * -> *).
        (forall b r. Data b => c (b -> r) -> c r)
        -> (forall r. r -> c r) -> Constr -> c a)
    -> (a -> Constr)
    -> (a -> DataType)
    -> (forall (t :: * -> *) (c :: * -> *).
        Typeable t =>
        (forall d. Data d => c (t d)) -> Maybe (c a))
    -> (forall (t :: * -> * -> *) (c :: * -> *).
        Typeable t =>
        (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c a))
    -> ((forall b. Data b => b -> b) -> a -> a)
    -> (forall r r'.
        (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
    -> (forall r r'.
        (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
    -> (forall u. (forall d. Data d => d -> u) -> a -> [u])
    -> (forall u. Int -> (forall d. Data d => d -> u) -> a -> u)
    -> (forall (m :: * -> *).
        Monad m =>
        (forall d. Data d => d -> m d) -> a -> m a)
    -> (forall (m :: * -> *).
        MonadPlus m =>
        (forall d. Data d => d -> m d) -> a -> m a)
    -> (forall (m :: * -> *).
        MonadPlus m =>
        (forall d. Data d => d -> m d) -> a -> m a)
    -> Data a
    forall u. Int -> (forall d. Data d => d -> u) -> MultiMap k v -> u
    forall u. (forall d. Data d => d -> u) -> MultiMap k v -> [u]
    forall k v. (Data k, Data v, Ord k) => Typeable (MultiMap k v)
    forall k v. (Data k, Data v, Ord k) => MultiMap k v -> Constr
    forall k v. (Data k, Data v, Ord k) => MultiMap k v -> DataType
    forall k v.
    (Data k, Data v, Ord k) =>
    (forall b. Data b => b -> b) -> MultiMap k v -> MultiMap k v
    forall k v u.
    (Data k, Data v, Ord k) =>
    Int -> (forall d. Data d => d -> u) -> MultiMap k v -> u
    forall k v u.
    (Data k, Data v, Ord k) =>
    (forall d. Data d => d -> u) -> MultiMap k v -> [u]
    forall k v r r'.
    (Data k, Data v, Ord k) =>
    (r -> r' -> r)
    -> r -> (forall d. Data d => d -> r') -> MultiMap k v -> r
    forall k v r r'.
    (Data k, Data v, Ord k) =>
    (r' -> r -> r)
    -> r -> (forall d. Data d => d -> r') -> MultiMap k v -> r
    forall k v (m :: * -> *).
    (Data k, Data v, Ord k, Monad m) =>
    (forall d. Data d => d -> m d) -> MultiMap k v -> m (MultiMap k v)
    forall k v (m :: * -> *).
    (Data k, Data v, Ord k, MonadPlus m) =>
    (forall d. Data d => d -> m d) -> MultiMap k v -> m (MultiMap k v)
    forall k v (c :: * -> *).
    (Data k, Data v, Ord k) =>
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c (MultiMap k v)
    forall k v (c :: * -> *).
    (Data k, Data v, Ord k) =>
    (forall d b. Data d => c (d -> b) -> d -> c b)
    -> (forall g. g -> c g) -> MultiMap k v -> c (MultiMap k v)
    forall k v (t :: * -> *) (c :: * -> *).
    (Data k, Data v, Ord k, Typeable t) =>
    (forall d. Data d => c (t d)) -> Maybe (c (MultiMap k v))
    forall k v (t :: * -> * -> *) (c :: * -> *).
    (Data k, Data v, Ord k, Typeable t) =>
    (forall d e. (Data d, Data e) => c (t d e))
    -> Maybe (c (MultiMap k v))
    forall r r'.
    (r -> r' -> r)
    -> r -> (forall d. Data d => d -> r') -> MultiMap k v -> r
    forall r r'.
    (r' -> r -> r)
    -> r -> (forall d. Data d => d -> r') -> MultiMap k v -> r
    forall (m :: * -> *).
    Monad m =>
    (forall d. Data d => d -> m d) -> MultiMap k v -> m (MultiMap k v)
    forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> MultiMap k v -> m (MultiMap k v)
    forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c (MultiMap k v)
    forall (c :: * -> *).
    (forall d b. Data d => c (d -> b) -> d -> c b)
    -> (forall g. g -> c g) -> MultiMap k v -> c (MultiMap k v)
    forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c (MultiMap k v))
    forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e))
    -> Maybe (c (MultiMap k v))
    $cgfoldl :: forall k v (c :: * -> *).
    (Data k, Data v, Ord k) =>
    (forall d b. Data d => c (d -> b) -> d -> c b)
    -> (forall g. g -> c g) -> MultiMap k v -> c (MultiMap k v)
    gfoldl :: forall (c :: * -> *).
    (forall d b. Data d => c (d -> b) -> d -> c b)
    -> (forall g. g -> c g) -> MultiMap k v -> c (MultiMap k v)
    $cgunfold :: forall k v (c :: * -> *).
    (Data k, Data v, Ord k) =>
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c (MultiMap k v)
    gunfold :: forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c (MultiMap k v)
    $ctoConstr :: forall k v. (Data k, Data v, Ord k) => MultiMap k v -> Constr
    toConstr :: MultiMap k v -> Constr
    $cdataTypeOf :: forall k v. (Data k, Data v, Ord k) => MultiMap k v -> DataType
    dataTypeOf :: MultiMap k v -> DataType
    $cdataCast1 :: forall k v (t :: * -> *) (c :: * -> *).
    (Data k, Data v, Ord k, Typeable t) =>
    (forall d. Data d => c (t d)) -> Maybe (c (MultiMap k v))
    dataCast1 :: forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c (MultiMap k v))
    $cdataCast2 :: forall k v (t :: * -> * -> *) (c :: * -> *).
    (Data k, Data v, Ord k, Typeable t) =>
    (forall d e. (Data d, Data e) => c (t d e))
    -> Maybe (c (MultiMap k v))
    dataCast2 :: forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e))
    -> Maybe (c (MultiMap k v))
    $cgmapT :: forall k v.
    (Data k, Data v, Ord k) =>
    (forall b. Data b => b -> b) -> MultiMap k v -> MultiMap k v
    gmapT :: (forall b. Data b => b -> b) -> MultiMap k v -> MultiMap k v
    $cgmapQl :: forall k v r r'.
    (Data k, Data v, Ord k) =>
    (r -> r' -> r)
    -> r -> (forall d. Data d => d -> r') -> MultiMap k v -> r
    gmapQl :: forall r r'.
    (r -> r' -> r)
    -> r -> (forall d. Data d => d -> r') -> MultiMap k v -> r
    $cgmapQr :: forall k v r r'.
    (Data k, Data v, Ord k) =>
    (r' -> r -> r)
    -> r -> (forall d. Data d => d -> r') -> MultiMap k v -> r
    gmapQr :: forall r r'.
    (r' -> r -> r)
    -> r -> (forall d. Data d => d -> r') -> MultiMap k v -> r
    $cgmapQ :: forall k v u.
    (Data k, Data v, Ord k) =>
    (forall d. Data d => d -> u) -> MultiMap k v -> [u]
    gmapQ :: forall u. (forall d. Data d => d -> u) -> MultiMap k v -> [u]
    $cgmapQi :: forall k v u.
    (Data k, Data v, Ord k) =>
    Int -> (forall d. Data d => d -> u) -> MultiMap k v -> u
    gmapQi :: forall u. Int -> (forall d. Data d => d -> u) -> MultiMap k v -> u
    $cgmapM :: forall k v (m :: * -> *).
    (Data k, Data v, Ord k, Monad m) =>
    (forall d. Data d => d -> m d) -> MultiMap k v -> m (MultiMap k v)
    gmapM :: forall (m :: * -> *).
    Monad m =>
    (forall d. Data d => d -> m d) -> MultiMap k v -> m (MultiMap k v)
    $cgmapMp :: forall k v (m :: * -> *).
    (Data k, Data v, Ord k, MonadPlus m) =>
    (forall d. Data d => d -> m d) -> MultiMap k v -> m (MultiMap k v)
    gmapMp :: forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> MultiMap k v -> m (MultiMap k v)
    $cgmapMo :: forall k v (m :: * -> *).
    (Data k, Data v, Ord k, MonadPlus m) =>
    (forall d. Data d => d -> m d) -> MultiMap k v -> m (MultiMap k v)
    gmapMo :: forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> MultiMap k v -> m (MultiMap k v)
    Data, Typeable)

    null :: MultiMap k a -> Bool
    -- ^ /O(1)./ Check whether the multimap is empty or not.
    null :: forall k a. MultiMap k a -> Bool
    null (MultiMap (Word32
    _, Word32
    _, Map k [a]
    m)) = Map k [a] -> Bool
    forall k a. Map k a -> Bool
    Map.null Map k [a]
    m

    size :: MultiMap k a -> Int
    -- ^ /O(1)./ The number of elements in the multimap.
    size :: forall k a. MultiMap k a -> Int
    size (MultiMap (Word32
    _, Word32
    size, Map k [a]
    _)) = Word32 -> Int
    forall a b. (Integral a, Num b) => a -> b
    fromIntegral Word32
    size

    numKeys :: MultiMap k a -> Word32
    -- ^ /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 :: forall k a. MultiMap k a -> Word32
    numKeys (MultiMap (Word32
    nk, Word32
    _, Map k [a]
    _)) = Word32
    nk

    numValues :: 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 :: forall k a. MultiMap k a -> Word32
    numValues (MultiMap (Word32
    _, Word32
    nv, Map k [a]
    _)) = Word32
    nv

    notMember, member :: Ord k => MultiMap k a -> k -> Bool
    -- | /O(log n)./ Is the key a member of the multimap?
    member :: forall k a. Ord k => MultiMap k a -> k -> Bool
    member (MultiMap (Word32
    _, Word32
    _, Map k [a]
    map)) k
    key = k -> Map k [a] -> Bool
    forall k a. Ord k => k -> Map k a -> Bool
    Map.member k
    key Map k [a]
    map
    -- | /O(log n)./ Is the key not a member of the multimap?
    notMember :: forall k a. Ord k => MultiMap k a -> k -> Bool
    notMember MultiMap k a
    key = Bool -> Bool
    not (Bool -> Bool) -> (k -> Bool) -> k -> Bool
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . MultiMap k a -> k -> Bool
    forall k a. Ord k => MultiMap k a -> k -> Bool
    member MultiMap k a
    key

    (!) :: Ord k => MultiMap k a -> k -> [a]
    -- ^ As @flip lookup@
    ! :: forall k a. Ord k => MultiMap k a -> k -> [a]
    (!) = (k -> MultiMap k a -> [a]) -> MultiMap k a -> k -> [a]
    forall a b c. (a -> b -> c) -> b -> a -> c
    flip k -> MultiMap k a -> [a]
    forall k a. Ord k => k -> MultiMap k a -> [a]
    lookup

    lookup :: Ord k => k -> MultiMap k a -> [a]
    -- ^ /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 :: forall k a. Ord k => k -> MultiMap k a -> [a]
    lookup k
    key (MultiMap (Word32
    _, Word32
    _, Map k [a]
    map)) = [a] -> ([a] -> [a]) -> Maybe [a] -> [a]
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe [] [a] -> [a]
    forall a. a -> a
    id (k -> Map k [a] -> Maybe [a]
    forall k a. Ord k => k -> Map k a -> Maybe a
    Map.lookup k
    key Map k [a]
    map)

    empty :: MultiMap k a
    -- ^ /O(1)./ The empty multimap.
    empty :: forall k a. MultiMap k a
    empty = (Word32, Word32, Map k [a]) -> MultiMap k a
    forall k v. (Word32, Word32, Map k [v]) -> MultiMap k v
    MultiMap (Word32
    0, Word32
    0, Map k [a]
    forall k a. Map k a
    Map.empty)

    insert :: Ord k => k -> a -> MultiMap k a -> MultiMap k a
    -- ^ /O(log n)./ Insert a new key and value in the map.
    insert :: forall k a. Ord k => k -> a -> MultiMap k a -> MultiMap k a
    insert k
    k a
    v (MultiMap (Word32
    nk, Word32
    nv, Map k [a]
    map))
        | k -> Map k [a] -> Bool
    forall k a. Ord k => k -> Map k a -> Bool
    Map.member k
    k Map k [a]
    map = (Word32, Word32, Map k [a]) -> MultiMap k a
    forall k v. (Word32, Word32, Map k [v]) -> MultiMap k v
    MultiMap (Word32
    nk, Word32 -> Word32
    forall a. Enum a => a -> a
    succ Word32
    nv, k -> [a] -> Map k [a] -> Map k [a]
    forall k a. Ord k => k -> a -> Map k a -> Map k a
    Map.insert k
    k (a
    v a -> [a] -> [a]
    forall a. a -> [a] -> [a]
    : Map k [a]
    map Map k [a] -> k -> [a]
    forall k a. Ord k => Map k a -> k -> a
    Map.! k
    k) Map k [a]
    map)
        | Bool
    otherwise = (Word32, Word32, Map k [a]) -> MultiMap k a
    forall k v. (Word32, Word32, Map k [v]) -> MultiMap k v
    MultiMap (Word32 -> Word32
    forall a. Enum a => a -> a
    succ Word32
    nk, Word32 -> Word32
    forall a. Enum a => a -> a
    succ Word32
    nv, k -> [a] -> Map k [a] -> Map k [a]
    forall k a. Ord k => k -> a -> Map k a -> Map k a
    Map.insert k
    k [a
    v] Map k [a]
    map)

    delete :: Ord k => k -> MultiMap k a -> MultiMap k a
    -- ^ /O(log n)./ Delete a key and all its values from the map.
    delete :: forall k a. Ord k => k -> MultiMap k a -> MultiMap k a
    delete k
    k m :: MultiMap k a
    m@(MultiMap (Word32
    nk, Word32
    nv, Map k [a]
    map)) = case k -> Map k [a] -> Maybe [a]
    forall k a. Ord k => k -> Map k a -> Maybe a
    Map.lookup k
    k Map k [a]
    map of
        Just [a]
    v -> (Word32, Word32, Map k [a]) -> MultiMap k a
    forall k v. (Word32, Word32, Map k [v]) -> MultiMap k v
    MultiMap (Word32 -> Word32
    forall a. Enum a => a -> a
    pred Word32
    nk, Word32
    nv Word32 -> Word32 -> Word32
    forall a. Num a => a -> a -> a
    - Int -> Word32
    forall a b. (Integral a, Num b) => a -> b
    fromIntegral ([a] -> Int
    forall a. [a] -> Int
    forall (t :: * -> *) a. Foldable t => t a -> Int
    length [a]
    v), k -> Map k [a] -> Map k [a]
    forall k a. Ord k => k -> Map k a -> Map k a
    Map.delete k
    k Map k [a]
    map)
        Maybe [a]
    _      -> MultiMap k a
    m

    map :: (a -> b) -> MultiMap k a -> MultiMap k b
    -- ^ Map a function over all values in the map.
    map :: forall a b k. (a -> b) -> MultiMap k a -> MultiMap k b
    map a -> b
    f (MultiMap (Word32
    nk, Word32
    nv, Map k [a]
    map)) = (Word32, Word32, Map k [b]) -> MultiMap k b
    forall k v. (Word32, Word32, Map k [v]) -> MultiMap k v
    MultiMap (Word32
    nk, Word32
    nv, ([a] -> [b]) -> Map k [a] -> Map k [b]
    forall a b k. (a -> b) -> Map k a -> Map k b
    Map.map ((a -> b) -> [a] -> [b]
    forall a b. (a -> b) -> [a] -> [b]
    P.map a -> b
    f) Map k [a]
    map)

    mapKeys :: Ord k2 => (k1 -> k2) -> MultiMap k1 a -> MultiMap k2 a
    -- ^ mapKeys f s is the multimap obtained by applying f to each key of s.
    mapKeys :: forall k2 k1 a.
    Ord k2 =>
    (k1 -> k2) -> MultiMap k1 a -> MultiMap k2 a
    mapKeys k1 -> k2
    f (MultiMap (Word32
    nk, Word32
    nv, Map k1 [a]
    map)) = (Word32, Word32, Map k2 [a]) -> MultiMap k2 a
    forall k v. (Word32, Word32, Map k [v]) -> MultiMap k v
    MultiMap (Word32
    nk, Word32
    nv, (k1 -> k2) -> Map k1 [a] -> Map k2 [a]
    forall k2 k1 a. Ord k2 => (k1 -> k2) -> Map k1 a -> Map k2 a
    Map.mapKeys k1 -> k2
    f Map k1 [a]
    map)

    mapWithKey :: (k -> a -> b) -> MultiMap k a -> MultiMap k b
    -- ^ Map a function over all key/value pairs in the map.
    mapWithKey :: forall k a b. (k -> a -> b) -> MultiMap k a -> MultiMap k b
    mapWithKey k -> a -> b
    f (MultiMap (Word32
    nk, Word32
    nv, Map k [a]
    map))
      = (Word32, Word32, Map k [b]) -> MultiMap k b
    forall k v. (Word32, Word32, Map k [v]) -> MultiMap k v
    MultiMap (Word32
    nk, Word32
    nv, (k -> [a] -> [b]) -> Map k [a] -> Map k [b]
    forall k a b. (k -> a -> b) -> Map k a -> Map k b
    Map.mapWithKey (\k
    k -> (a -> b) -> [a] -> [b]
    forall a b. (a -> b) -> [a] -> [b]
    P.map (k -> a -> b
    f k
    k)) Map k [a]
    map)

    foldr :: (a -> b -> b) -> b -> MultiMap k a -> b
    -- ^ Fold the values in the map using the given right-associative binary operator.
    foldr :: forall a b k. (a -> b -> b) -> b -> MultiMap k a -> b
    foldr a -> b -> b
    f b
    e = (a -> b -> b) -> b -> [a] -> b
    forall a b. (a -> b -> b) -> b -> [a] -> b
    forall (t :: * -> *) a b.
    Foldable t =>
    (a -> b -> b) -> b -> t a -> b
    P.foldr a -> b -> b
    f b
    e ([a] -> b) -> (MultiMap k a -> [a]) -> MultiMap k a -> b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . [[a]] -> [a]
    forall (t :: * -> *) a. Foldable t => t [a] -> [a]
    concat ([[a]] -> [a]) -> (MultiMap k a -> [[a]]) -> MultiMap k a -> [a]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . MultiMap k a -> [[a]]
    forall k a. MultiMap k a -> [[a]]
    elems

    foldl :: (a -> b -> a) -> a -> MultiMap k b -> a
    -- ^  Fold the values in the map using the given left-associative binary operator.
    foldl :: forall a b k. (a -> b -> a) -> a -> MultiMap k b -> a
    foldl a -> b -> a
    f a
    e = (a -> b -> a) -> a -> [b] -> a
    forall b a. (b -> a -> b) -> b -> [a] -> b
    forall (t :: * -> *) b a.
    Foldable t =>
    (b -> a -> b) -> b -> t a -> b
    P.foldl a -> b -> a
    f a
    e ([b] -> a) -> (MultiMap k b -> [b]) -> MultiMap k b -> a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . [[b]] -> [b]
    forall (t :: * -> *) a. Foldable t => t [a] -> [a]
    concat ([[b]] -> [b]) -> (MultiMap k b -> [[b]]) -> MultiMap k b -> [b]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . MultiMap k b -> [[b]]
    forall k a. MultiMap k a -> [[a]]
    elems

    foldrWithKey :: (k -> a -> b -> b) -> b -> MultiMap k a -> b
    -- ^ /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 :: forall k a b. (k -> a -> b -> b) -> b -> MultiMap k a -> b
    foldrWithKey k -> a -> b -> b
    f b
    e = ((k, a) -> b -> b) -> b -> [(k, a)] -> b
    forall a b. (a -> b -> b) -> b -> [a] -> b
    forall (t :: * -> *) a b.
    Foldable t =>
    (a -> b -> b) -> b -> t a -> b
    P.foldr ((k -> a -> b -> b) -> (k, a) -> b -> b
    forall a b c. (a -> b -> c) -> (a, b) -> c
    uncurry k -> a -> b -> b
    f) b
    e ([(k, a)] -> b) -> (MultiMap k a -> [(k, a)]) -> MultiMap k a -> b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . MultiMap k a -> [(k, a)]
    forall k a. MultiMap k a -> [(k, a)]
    toList

    foldlWithKey :: (a -> k -> b -> a) -> a -> MultiMap k b -> a
    -- ^ /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 :: forall a k b. (a -> k -> b -> a) -> a -> MultiMap k b -> a
    foldlWithKey a -> k -> b -> a
    f a
    e = (a -> (k, b) -> a) -> a -> [(k, b)] -> a
    forall b a. (b -> a -> b) -> b -> [a] -> b
    forall (t :: * -> *) b a.
    Foldable t =>
    (b -> a -> b) -> b -> t a -> b
    P.foldl (\a
    a (k
    k,b
    v) -> a -> k -> b -> a
    f a
    a k
    k b
    v) a
    e ([(k, b)] -> a) -> (MultiMap k b -> [(k, b)]) -> MultiMap k b -> a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . MultiMap k b -> [(k, b)]
    forall k a. MultiMap k a -> [(k, a)]
    toList

    elems :: MultiMap k a -> [[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 :: forall k a. MultiMap k a -> [[a]]
    elems (MultiMap (Word32
    _, Word32
    _, Map k [a]
    map)) = Map k [a] -> [[a]]
    forall k a. Map k a -> [a]
    Map.elems Map k [a]
    map

    keys :: MultiMap k a -> [k]
    -- ^ /O(n)./ Return all keys of the multimap in ascending order.
    keys :: forall k a. MultiMap k a -> [k]
    keys (MultiMap (Word32
    _, Word32
    _, Map k [a]
    map)) = Map k [a] -> [k]
    forall k a. Map k a -> [k]
    Map.keys Map k [a]
    map

    keysSet :: MultiMap k a -> Set k
    -- ^ /O(n)./ The set of all keys of the multimap.
    keysSet :: forall k a. MultiMap k a -> Set k
    keysSet (MultiMap (Word32
    _, Word32
    _, Map k [a]
    map)) = Map k [a] -> Set k
    forall k a. Map k a -> Set k
    Map.keysSet Map k [a]
    map

    assocs :: MultiMap k a -> [(k, [a])]
    -- ^ /O(n)./ Return all key/value pairs in the multimap
    -- in ascending key order.
    assocs :: forall k a. MultiMap k a -> [(k, [a])]
    assocs (MultiMap (Word32
    _, Word32
    _, Map k [a]
    map)) = Map k [a] -> [(k, [a])]
    forall k a. Map k a -> [(k, a)]
    Map.assocs Map k [a]
    map

    toMap :: MultiMap k a -> Map k [a]
    -- ^ /O(1)./ Return the map of lists.
    toMap :: forall k a. MultiMap k a -> Map k [a]
    toMap (MultiMap (Word32
    _, Word32
    _, Map k [a]
    theUnderlyingMap)) = Map k [a]
    theUnderlyingMap

    toMapOfSets :: Ord a => MultiMap k a -> Map k (Set 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 :: forall a k. Ord a => MultiMap k a -> Map k (Set a)
    toMapOfSets (MultiMap (Word32
    _, Word32
    _, Map k [a]
    map)) = ([a] -> Set a) -> Map k [a] -> Map k (Set a)
    forall a b k. (a -> b) -> Map k a -> Map k b
    Map.map [a] -> Set a
    forall a. Ord a => [a] -> Set a
    Set.fromList Map k [a]
    map

    toList :: MultiMap k a -> [(k, a)]
    -- ^ Return a flattened list of key/value pairs.
    toList :: forall k a. MultiMap k a -> [(k, a)]
    toList (MultiMap (Word32
    _, Word32
    _, Map k [a]
    map))
      = [[(k, a)]] -> [(k, a)]
    forall (t :: * -> *) a. Foldable t => t [a] -> [a]
    concat ([[(k, a)]] -> [(k, a)]) -> [[(k, a)]] -> [(k, a)]
    forall a b. (a -> b) -> a -> b
    $ Map k [(k, a)] -> [[(k, a)]]
    forall k a. Map k a -> [a]
    Map.elems (Map k [(k, a)] -> [[(k, a)]]) -> Map k [(k, a)] -> [[(k, a)]]
    forall a b. (a -> b) -> a -> b
    $ (k -> [a] -> [(k, a)]) -> Map k [a] -> Map k [(k, a)]
    forall k a b. (k -> a -> b) -> Map k a -> Map k b
    Map.mapWithKey (\k
    k -> [k] -> [a] -> [(k, a)]
    forall a b. [a] -> [b] -> [(a, b)]
    zip (k -> [k]
    forall a. a -> [a]
    repeat k
    k)) Map k [a]
    map

    fromList :: Ord k => [(k, a)] -> MultiMap k a
    -- ^ /O(n*log n)/ Create a multimap from a list of key/value pairs.
    --
    -- > fromList xs == foldr (uncurry insert) empty
    fromList :: forall k a. Ord k => [(k, a)] -> MultiMap k a
    fromList = ((k, a) -> MultiMap k a -> MultiMap k a)
    -> MultiMap k a -> [(k, a)] -> MultiMap k a
    forall a b. (a -> b -> b) -> b -> [a] -> b
    forall (t :: * -> *) a b.
    Foldable t =>
    (a -> b -> b) -> b -> t a -> b
    P.foldr ((k -> a -> MultiMap k a -> MultiMap k a)
    -> (k, a) -> MultiMap k a -> MultiMap k a
    forall a b c. (a -> b -> c) -> (a, b) -> c
    uncurry k -> a -> MultiMap k a -> MultiMap k a
    forall k a. Ord k => k -> a -> MultiMap k a -> MultiMap k a
    insert) MultiMap k a
    forall k a. MultiMap k a
    empty

    fromMap :: Map k [a] -> MultiMap k a
    -- ^ Turns a map of lists into a multimap.
    fromMap :: forall k a. Map k [a] -> MultiMap k a
    fromMap Map k [a]
    map = (Word32, Word32, Map k [a]) -> MultiMap k a
    forall k v. (Word32, Word32, Map k [v]) -> MultiMap k v
    MultiMap (Word32
    numKeys, Word32
    numValues, Map k [a]
    map)
      where
        numKeys :: Word32
    numKeys   = Int -> Word32
    forall a b. (Integral a, Num b) => a -> b
    fromIntegral (Int -> Word32) -> Int -> Word32
    forall a b. (a -> b) -> a -> b
    $ Map k [a] -> Int
    forall k a. Map k a -> Int
    Map.size Map k [a]
    map
        numValues :: Word32
    numValues = Int -> Word32
    forall a b. (Integral a, Num b) => a -> b
    fromIntegral (Int -> Word32) -> Int -> Word32
    forall a b. (a -> b) -> a -> b
    $ ([a] -> Int -> Int) -> Int -> Map k [a] -> Int
    forall a b k. (a -> b -> b) -> b -> Map k a -> b
    Map.foldr (\[a]
    v Int
    s -> [a] -> Int
    forall a. [a] -> Int
    forall (t :: * -> *) a. Foldable t => t a -> Int
    length [a]
    v Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + Int
    s) Int
    0 Map k [a]
    map

    findMin :: MultiMap k a -> Maybe k
    -- ^ /O(log n)/ Find the minimal key of the multimap.
    findMin :: forall k a. MultiMap k a -> Maybe k
    findMin (MultiMap (Word32
    _, Word32
    _, Map k [a]
    map))
        | Map k [a] -> Bool
    forall k a. Map k a -> Bool
    Map.null Map k [a]
    map = Maybe k
    forall a. Maybe a
    Nothing
        | Bool
    otherwise    = k -> Maybe k
    forall a. a -> Maybe a
    Just (k -> Maybe k) -> k -> Maybe k
    forall a b. (a -> b) -> a -> b
    $ (k, [a]) -> k
    forall a b. (a, b) -> a
    fst ((k, [a]) -> k) -> (k, [a]) -> k
    forall a b. (a -> b) -> a -> b
    $ Map k [a] -> (k, [a])
    forall k a. Map k a -> (k, a)
    Map.findMin Map k [a]
    map

    findMax :: MultiMap k a -> Maybe k
    -- ^ /O(log n)/ Find the maximal key of the multimap.
    findMax :: forall k a. MultiMap k a -> Maybe k
    findMax (MultiMap (Word32
    _, Word32
    _, Map k [a]
    map))
        | Map k [a] -> Bool
    forall k a. Map k a -> Bool
    Map.null Map k [a]
    map = Maybe k
    forall a. Maybe a
    Nothing
        | Bool
    otherwise    = k -> Maybe k
    forall a. a -> Maybe a
    Just (k -> Maybe k) -> k -> Maybe k
    forall a b. (a -> b) -> a -> b
    $ (k, [a]) -> k
    forall a b. (a, b) -> a
    fst ((k, [a]) -> k) -> (k, [a]) -> k
    forall a b. (a -> b) -> a -> b
    $ Map k [a] -> (k, [a])
    forall k a. Map k a -> (k, a)
    Map.findMax Map k [a]
    map

    findMinWithValues :: MultiMap k a -> Maybe (k, [a])
    -- ^ /O(log n)/ Find the minimal key and the values associated with it.
    findMinWithValues :: forall k a. MultiMap k a -> Maybe (k, [a])
    findMinWithValues (MultiMap (Word32
    _, Word32
    _, Map k [a]
    map))
        | Map k [a] -> Bool
    forall k a. Map k a -> Bool
    Map.null Map k [a]
    map = Maybe (k, [a])
    forall a. Maybe a
    Nothing
        | Bool
    otherwise    = (k, [a]) -> Maybe (k, [a])
    forall a. a -> Maybe a
    Just ((k, [a]) -> Maybe (k, [a])) -> (k, [a]) -> Maybe (k, [a])
    forall a b. (a -> b) -> a -> b
    $ Map k [a] -> (k, [a])
    forall k a. Map k a -> (k, a)
    Map.findMin Map k [a]
    map

    findMaxWithValues :: MultiMap k a -> Maybe (k, [a])
    -- ^ /O(log n)/ Find the maximal key and the values associated with it.
    findMaxWithValues :: forall k a. MultiMap k a -> Maybe (k, [a])
    findMaxWithValues (MultiMap (Word32
    _, Word32
    _, Map k [a]
    map))
        | Map k [a] -> Bool
    forall k a. Map k a -> Bool
    Map.null Map k [a]
    map = Maybe (k, [a])
    forall a. Maybe a
    Nothing
        | Bool
    otherwise    = (k, [a]) -> Maybe (k, [a])
    forall a. a -> Maybe a
    Just ((k, [a]) -> Maybe (k, [a])) -> (k, [a]) -> Maybe (k, [a])
    forall a b. (a -> b) -> a -> b
    $ Map k [a] -> (k, [a])
    forall k a. Map k a -> (k, a)
    Map.findMax Map k [a]
    map