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

    -- Module       : Data.SetMap
    -- Copyright    : (c) Julian Fleischer 2013
    -- License      : MIT (See LICENSE file in cabal package)
    --
    -- Maintainer   : julian.fleischer@fu-berlin.de
    -- Portability  : non-portable (DeriveDataTypeable)
    --
    -- A SetMap allows the association of multiple values with a single key,
    -- but there are no duplicates per key.
    module Data.SetMap (

        -- * SetMap type
        SetMap,

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

        member,
        notMember,
        lookup,

        -- * Operators
        (!),

        -- * Construction
        empty,

        -- ** Insertion
        insert,

        -- ** Deletion
        delete,

        -- * Traversal
        map,

        -- * Conversion
        elems,
        keys,

        toMap,

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

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

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

    numKeys :: SetMap 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. SetMap k a -> Word32
    numKeys (SetMap (Word32
    nk, Word32
    _, Map k (Set a)
    _)) = Word32
    nk

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

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

    (!) :: Ord k => SetMap k a -> k -> Set a
    -- ^ As @flip lookup@
    ! :: forall k a. Ord k => SetMap k a -> k -> Set a
    (!) = (k -> SetMap k a -> Set a) -> SetMap k a -> k -> Set a
    forall a b c. (a -> b -> c) -> b -> a -> c
    flip k -> SetMap k a -> Set a
    forall k a. Ord k => k -> SetMap k a -> Set a
    lookup

    lookup :: Ord k => k -> SetMap k a -> Set 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 -> SetMap k a -> Set a
    lookup k
    key (SetMap (Word32
    _, Word32
    _, Map k (Set a)
    map)) = Set a -> (Set a -> Set a) -> Maybe (Set a) -> Set a
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe Set a
    forall a. Set a
    Set.empty Set a -> Set a
    forall a. a -> a
    id (k -> Map k (Set a) -> Maybe (Set a)
    forall k a. Ord k => k -> Map k a -> Maybe a
    Map.lookup k
    key Map k (Set a)
    map)

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

    insert :: (Ord k, Ord a) => k -> a -> SetMap k a -> SetMap k a
    -- ^ Insert a new key and value in the map.
    insert :: forall k a. (Ord k, Ord a) => k -> a -> SetMap k a -> SetMap k a
    insert k
    k a
    v (SetMap (Word32
    nk, Word32
    nv, Map k (Set a)
    map))
        | k -> Map k (Set a) -> Bool
    forall k a. Ord k => k -> Map k a -> Bool
    Map.member k
    k Map k (Set a)
    map =
            let oldSet :: Set a
    oldSet = Map k (Set a)
    map Map k (Set a) -> k -> Set a
    forall k a. Ord k => Map k a -> k -> a
    Map.! k
    k
                (Word32
    nv', Set a
    newSet) = if a
    v a -> Set a -> Bool
    forall a. Ord a => a -> Set a -> Bool
    `Set.member` Set a
    oldSet
                    then (Word32
    nv, Set a
    oldSet) else (Word32 -> Word32
    forall a. Enum a => a -> a
    succ Word32
    nv, a
    v a -> Set a -> Set a
    forall a. Ord a => a -> Set a -> Set a
    `Set.insert` Set a
    oldSet)
            in  (Word32, Word32, Map k (Set a)) -> SetMap k a
    forall k v. (Word32, Word32, Map k (Set v)) -> SetMap k v
    SetMap (Word32
    nk, Word32
    nv', k -> Set a -> Map k (Set a) -> Map k (Set a)
    forall k a. Ord k => k -> a -> Map k a -> Map k a
    Map.insert k
    k Set a
    newSet Map k (Set a)
    map)
        | Bool
    otherwise = (Word32, Word32, Map k (Set a)) -> SetMap k a
    forall k v. (Word32, Word32, Map k (Set v)) -> SetMap k v
    SetMap (Word32 -> Word32
    forall a. Enum a => a -> a
    succ Word32
    nk, Word32 -> Word32
    forall a. Enum a => a -> a
    succ Word32
    nv, k -> Set a -> Map k (Set a) -> Map k (Set a)
    forall k a. Ord k => k -> a -> Map k a -> Map k a
    Map.insert k
    k (a -> Set a
    forall a. a -> Set a
    Set.singleton a
    v) Map k (Set a)
    map)

    delete :: Ord k => k -> SetMap k a -> SetMap k a
    -- ^ Delete a key and all its values from the map.
    delete :: forall k a. Ord k => k -> SetMap k a -> SetMap k a
    delete k
    k m :: SetMap k a
    m@(SetMap (Word32
    nk, Word32
    nv, Map k (Set a)
    map)) = case k -> Map k (Set a) -> Maybe (Set a)
    forall k a. Ord k => k -> Map k a -> Maybe a
    Map.lookup k
    k Map k (Set a)
    map of
        Just Set a
    v -> (Word32, Word32, Map k (Set a)) -> SetMap k a
    forall k v. (Word32, Word32, Map k (Set v)) -> SetMap k v
    SetMap (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 (Set a -> Int
    forall a. Set a -> Int
    Set.size Set a
    v), k -> Map k (Set a) -> Map k (Set a)
    forall k a. Ord k => k -> Map k a -> Map k a
    Map.delete k
    k Map k (Set a)
    map)
        Maybe (Set a)
    _      -> SetMap k a
    m

    map :: (Ord a, Ord b) => (a -> b) -> SetMap k a -> SetMap k b
    -- ^ Map a function over all values in the map.
    map :: forall a b k.
    (Ord a, Ord b) =>
    (a -> b) -> SetMap k a -> SetMap k b
    map a -> b
    f (SetMap (Word32
    nk, Word32
    nv, Map k (Set a)
    map)) = (Word32, Word32, Map k (Set b)) -> SetMap k b
    forall k v. (Word32, Word32, Map k (Set v)) -> SetMap k v
    SetMap (Word32
    nk, Word32
    nv, (Set a -> Set b) -> Map k (Set a) -> Map k (Set b)
    forall a b k. (a -> b) -> Map k a -> Map k b
    Map.map ((a -> b) -> Set a -> Set b
    forall b a. Ord b => (a -> b) -> Set a -> Set b
    Set.map a -> b
    f) Map k (Set a)
    map)

    elems :: SetMap k a -> [[a]]
    -- ^ 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. SetMap k a -> [[a]]
    elems (SetMap (Word32
    _, Word32
    _, Map k (Set a)
    map)) = (Set a -> [a]) -> [Set a] -> [[a]]
    forall a b. (a -> b) -> [a] -> [b]
    P.map (Set a -> [a]
    forall a. Set a -> [a]
    Set.elems) ([Set a] -> [[a]]) -> [Set a] -> [[a]]
    forall a b. (a -> b) -> a -> b
    $ Map k (Set a) -> [Set a]
    forall k a. Map k a -> [a]
    Map.elems Map k (Set a)
    map

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

    toMap :: SetMap k a -> Map k (Set a)
    -- ^ /O(1)./ Return the map of sets.
    toMap :: forall k a. SetMap k a -> Map k (Set a)
    toMap (SetMap (Word32
    _, Word32
    _, Map k (Set a)
    theUnderlyingMap)) = Map k (Set a)
    theUnderlyingMap