{-# LANGUAGE DeriveDataTypeable #-}
{-# LANGUAGE TupleSections #-}
{-# LANGUAGE TypeFamilies #-}

-----------------------------------------------------------------------------
-- |
-- Module      :  Data.Multimap.Set.Internal
-- Maintainer  :  Ziyang Liu <free@cofree.io>
--
module Data.Multimap.Set.Internal (
  -- * Multimap type
  SetMultimap (..)
  , Size

  -- * Construction
  , empty
  , singleton
  , fromMap

  -- ** From Unordered Lists
  , fromList

  -- * Insertion
  , insert

  -- * Deletion\/Update
  , delete
  , deleteWithValue
  , deleteMax
  , deleteMin
  , adjust
  , adjustWithKey
  , update
  , updateWithKey
  , alter
  , alterWithKey

  -- * Query
  -- ** Lookup
  , lookup
  , (!)
  , member
  , notMember

  -- ** Size
  , null
  , notNull
  , size

  -- * Combine
  -- ** Union
  , union
  , unions

  -- ** Difference
  , difference

  -- * Traversal
  -- ** Map
  , map
  , mapWithKey

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

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

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

  -- ** Lists
  , toList

  -- ** Ordered lists
  , toAscList
  , toDescList

  -- ** Maps
  , toMap

  -- * Filter
  , filter
  , filterWithKey
  , filterKey
  , filterM
  , filterWithKeyM

  , mapMaybe
  , mapMaybeWithKey
  , mapEither
  , mapEitherWithKey

  -- * Min\/Max
  , lookupMin
  , lookupMax
  , lookupLT
  , lookupGT
  , lookupLE
  , lookupGE
  ) where

import Prelude hiding (filter, foldl, foldr, lookup, map, null)

import           Control.Arrow ((&&&))
import qualified Control.Monad as List (filterM)
import           Data.Data (Data)
import qualified Data.Foldable as Foldable
import           Data.Functor.Classes
import           Data.Map.Lazy (Map)
import qualified Data.Map.Lazy as Map
import qualified Data.Maybe as Maybe
import           Data.Set (Set)
import qualified Data.Set as Set

infixl 9 !

type Size = Int

newtype SetMultimap k a = SetMultimap (Map k (Set a), Size)
  deriving (SetMultimap k a -> SetMultimap k a -> Bool
(SetMultimap k a -> SetMultimap k a -> Bool)
-> (SetMultimap k a -> SetMultimap k a -> Bool)
-> Eq (SetMultimap k a)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall k a.
(Eq k, Eq a) =>
SetMultimap k a -> SetMultimap k a -> Bool
/= :: SetMultimap k a -> SetMultimap k a -> Bool
$c/= :: forall k a.
(Eq k, Eq a) =>
SetMultimap k a -> SetMultimap k a -> Bool
== :: SetMultimap k a -> SetMultimap k a -> Bool
$c== :: forall k a.
(Eq k, Eq a) =>
SetMultimap k a -> SetMultimap k a -> Bool
Eq, Eq (SetMultimap k a)
Eq (SetMultimap k a)
-> (SetMultimap k a -> SetMultimap k a -> Ordering)
-> (SetMultimap k a -> SetMultimap k a -> Bool)
-> (SetMultimap k a -> SetMultimap k a -> Bool)
-> (SetMultimap k a -> SetMultimap k a -> Bool)
-> (SetMultimap k a -> SetMultimap k a -> Bool)
-> (SetMultimap k a -> SetMultimap k a -> SetMultimap k a)
-> (SetMultimap k a -> SetMultimap k a -> SetMultimap k a)
-> Ord (SetMultimap k a)
SetMultimap k a -> SetMultimap k a -> Bool
SetMultimap k a -> SetMultimap k a -> Ordering
SetMultimap k a -> SetMultimap k a -> SetMultimap k a
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall k a. (Ord k, Ord a) => Eq (SetMultimap k a)
forall k a.
(Ord k, Ord a) =>
SetMultimap k a -> SetMultimap k a -> Bool
forall k a.
(Ord k, Ord a) =>
SetMultimap k a -> SetMultimap k a -> Ordering
forall k a.
(Ord k, Ord a) =>
SetMultimap k a -> SetMultimap k a -> SetMultimap k a
min :: SetMultimap k a -> SetMultimap k a -> SetMultimap k a
$cmin :: forall k a.
(Ord k, Ord a) =>
SetMultimap k a -> SetMultimap k a -> SetMultimap k a
max :: SetMultimap k a -> SetMultimap k a -> SetMultimap k a
$cmax :: forall k a.
(Ord k, Ord a) =>
SetMultimap k a -> SetMultimap k a -> SetMultimap k a
>= :: SetMultimap k a -> SetMultimap k a -> Bool
$c>= :: forall k a.
(Ord k, Ord a) =>
SetMultimap k a -> SetMultimap k a -> Bool
> :: SetMultimap k a -> SetMultimap k a -> Bool
$c> :: forall k a.
(Ord k, Ord a) =>
SetMultimap k a -> SetMultimap k a -> Bool
<= :: SetMultimap k a -> SetMultimap k a -> Bool
$c<= :: forall k a.
(Ord k, Ord a) =>
SetMultimap k a -> SetMultimap k a -> Bool
< :: SetMultimap k a -> SetMultimap k a -> Bool
$c< :: forall k a.
(Ord k, Ord a) =>
SetMultimap k a -> SetMultimap k a -> Bool
compare :: SetMultimap k a -> SetMultimap k a -> Ordering
$ccompare :: forall k a.
(Ord k, Ord a) =>
SetMultimap k a -> SetMultimap k a -> Ordering
$cp1Ord :: forall k a. (Ord k, Ord a) => Eq (SetMultimap k a)
Ord, Typeable (SetMultimap k a)
DataType
Constr
Typeable (SetMultimap k a)
-> (forall (c :: * -> *).
    (forall d b. Data d => c (d -> b) -> d -> c b)
    -> (forall g. g -> c g) -> SetMultimap k a -> c (SetMultimap k a))
-> (forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c (SetMultimap k a))
-> (SetMultimap k a -> Constr)
-> (SetMultimap k a -> DataType)
-> (forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c (SetMultimap k a)))
-> (forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e))
    -> Maybe (c (SetMultimap k a)))
-> ((forall b. Data b => b -> b)
    -> SetMultimap k a -> SetMultimap k a)
-> (forall r r'.
    (r -> r' -> r)
    -> r -> (forall d. Data d => d -> r') -> SetMultimap k a -> r)
-> (forall r r'.
    (r' -> r -> r)
    -> r -> (forall d. Data d => d -> r') -> SetMultimap k a -> r)
-> (forall u.
    (forall d. Data d => d -> u) -> SetMultimap k a -> [u])
-> (forall u.
    Int -> (forall d. Data d => d -> u) -> SetMultimap k a -> u)
-> (forall (m :: * -> *).
    Monad m =>
    (forall d. Data d => d -> m d)
    -> SetMultimap k a -> m (SetMultimap k a))
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d)
    -> SetMultimap k a -> m (SetMultimap k a))
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d)
    -> SetMultimap k a -> m (SetMultimap k a))
-> Data (SetMultimap k a)
SetMultimap k a -> DataType
SetMultimap k a -> Constr
(forall b. Data b => b -> b) -> SetMultimap k a -> SetMultimap k a
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> SetMultimap k a -> c (SetMultimap k a)
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (SetMultimap k a)
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (SetMultimap k a))
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) -> SetMultimap k a -> u
forall u. (forall d. Data d => d -> u) -> SetMultimap k a -> [u]
forall k a.
(Data k, Data a, Ord a, Ord k) =>
Typeable (SetMultimap k a)
forall k a.
(Data k, Data a, Ord a, Ord k) =>
SetMultimap k a -> DataType
forall k a.
(Data k, Data a, Ord a, Ord k) =>
SetMultimap k a -> Constr
forall k a.
(Data k, Data a, Ord a, Ord k) =>
(forall b. Data b => b -> b) -> SetMultimap k a -> SetMultimap k a
forall k a u.
(Data k, Data a, Ord a, Ord k) =>
Int -> (forall d. Data d => d -> u) -> SetMultimap k a -> u
forall k a u.
(Data k, Data a, Ord a, Ord k) =>
(forall d. Data d => d -> u) -> SetMultimap k a -> [u]
forall k a r r'.
(Data k, Data a, Ord a, Ord k) =>
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> SetMultimap k a -> r
forall k a r r'.
(Data k, Data a, Ord a, Ord k) =>
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> SetMultimap k a -> r
forall k a (m :: * -> *).
(Data k, Data a, Ord a, Ord k, Monad m) =>
(forall d. Data d => d -> m d)
-> SetMultimap k a -> m (SetMultimap k a)
forall k a (m :: * -> *).
(Data k, Data a, Ord a, Ord k, MonadPlus m) =>
(forall d. Data d => d -> m d)
-> SetMultimap k a -> m (SetMultimap k a)
forall k a (c :: * -> *).
(Data k, Data a, Ord a, Ord k) =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (SetMultimap k a)
forall k a (c :: * -> *).
(Data k, Data a, Ord a, Ord k) =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> SetMultimap k a -> c (SetMultimap k a)
forall k a (t :: * -> *) (c :: * -> *).
(Data k, Data a, Ord a, Ord k, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (SetMultimap k a))
forall k a (t :: * -> * -> *) (c :: * -> *).
(Data k, Data a, Ord a, Ord k, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (SetMultimap k a))
forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> SetMultimap k a -> r
forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> SetMultimap k a -> r
forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d)
-> SetMultimap k a -> m (SetMultimap k a)
forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d)
-> SetMultimap k a -> m (SetMultimap k a)
forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (SetMultimap k a)
forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> SetMultimap k a -> c (SetMultimap k a)
forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c (SetMultimap k a))
forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (SetMultimap k a))
$cSetMultimap :: Constr
$tSetMultimap :: DataType
gmapMo :: (forall d. Data d => d -> m d)
-> SetMultimap k a -> m (SetMultimap k a)
$cgmapMo :: forall k a (m :: * -> *).
(Data k, Data a, Ord a, Ord k, MonadPlus m) =>
(forall d. Data d => d -> m d)
-> SetMultimap k a -> m (SetMultimap k a)
gmapMp :: (forall d. Data d => d -> m d)
-> SetMultimap k a -> m (SetMultimap k a)
$cgmapMp :: forall k a (m :: * -> *).
(Data k, Data a, Ord a, Ord k, MonadPlus m) =>
(forall d. Data d => d -> m d)
-> SetMultimap k a -> m (SetMultimap k a)
gmapM :: (forall d. Data d => d -> m d)
-> SetMultimap k a -> m (SetMultimap k a)
$cgmapM :: forall k a (m :: * -> *).
(Data k, Data a, Ord a, Ord k, Monad m) =>
(forall d. Data d => d -> m d)
-> SetMultimap k a -> m (SetMultimap k a)
gmapQi :: Int -> (forall d. Data d => d -> u) -> SetMultimap k a -> u
$cgmapQi :: forall k a u.
(Data k, Data a, Ord a, Ord k) =>
Int -> (forall d. Data d => d -> u) -> SetMultimap k a -> u
gmapQ :: (forall d. Data d => d -> u) -> SetMultimap k a -> [u]
$cgmapQ :: forall k a u.
(Data k, Data a, Ord a, Ord k) =>
(forall d. Data d => d -> u) -> SetMultimap k a -> [u]
gmapQr :: (r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> SetMultimap k a -> r
$cgmapQr :: forall k a r r'.
(Data k, Data a, Ord a, Ord k) =>
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> SetMultimap k a -> r
gmapQl :: (r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> SetMultimap k a -> r
$cgmapQl :: forall k a r r'.
(Data k, Data a, Ord a, Ord k) =>
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> SetMultimap k a -> r
gmapT :: (forall b. Data b => b -> b) -> SetMultimap k a -> SetMultimap k a
$cgmapT :: forall k a.
(Data k, Data a, Ord a, Ord k) =>
(forall b. Data b => b -> b) -> SetMultimap k a -> SetMultimap k a
dataCast2 :: (forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (SetMultimap k a))
$cdataCast2 :: forall k a (t :: * -> * -> *) (c :: * -> *).
(Data k, Data a, Ord a, Ord k, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (SetMultimap k a))
dataCast1 :: (forall d. Data d => c (t d)) -> Maybe (c (SetMultimap k a))
$cdataCast1 :: forall k a (t :: * -> *) (c :: * -> *).
(Data k, Data a, Ord a, Ord k, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (SetMultimap k a))
dataTypeOf :: SetMultimap k a -> DataType
$cdataTypeOf :: forall k a.
(Data k, Data a, Ord a, Ord k) =>
SetMultimap k a -> DataType
toConstr :: SetMultimap k a -> Constr
$ctoConstr :: forall k a.
(Data k, Data a, Ord a, Ord k) =>
SetMultimap k a -> Constr
gunfold :: (forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (SetMultimap k a)
$cgunfold :: forall k a (c :: * -> *).
(Data k, Data a, Ord a, Ord k) =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (SetMultimap k a)
gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> SetMultimap k a -> c (SetMultimap k a)
$cgfoldl :: forall k a (c :: * -> *).
(Data k, Data a, Ord a, Ord k) =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> SetMultimap k a -> c (SetMultimap k a)
$cp1Data :: forall k a.
(Data k, Data a, Ord a, Ord k) =>
Typeable (SetMultimap k a)
Data)

instance Eq k => Eq1 (SetMultimap k) where
  liftEq :: (a -> b -> Bool) -> SetMultimap k a -> SetMultimap k b -> Bool
liftEq = (k -> k -> Bool)
-> (a -> b -> Bool) -> SetMultimap k a -> SetMultimap k b -> Bool
forall (f :: * -> * -> *) a b c d.
Eq2 f =>
(a -> b -> Bool) -> (c -> d -> Bool) -> f a c -> f b d -> Bool
liftEq2 k -> k -> Bool
forall a. Eq a => a -> a -> Bool
(==)

instance Eq2 SetMultimap where
  liftEq2 :: (a -> b -> Bool)
-> (c -> d -> Bool) -> SetMultimap a c -> SetMultimap b d -> Bool
liftEq2 a -> b -> Bool
eqk c -> d -> Bool
eqv SetMultimap a c
m SetMultimap b d
n =
    Map a (Set c) -> Int
forall k a. Map k a -> Int
Map.size (SetMultimap a c -> Map a (Set c)
forall k a. SetMultimap k a -> Map k (Set a)
toMap SetMultimap a c
m) Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Map b (Set d) -> Int
forall k a. Map k a -> Int
Map.size (SetMultimap b d -> Map b (Set d)
forall k a. SetMultimap k a -> Map k (Set a)
toMap SetMultimap b d
n)
      Bool -> Bool -> Bool
&& ((a, c) -> (b, d) -> Bool) -> [(a, c)] -> [(b, d)] -> Bool
forall (f :: * -> *) a b.
Eq1 f =>
(a -> b -> Bool) -> f a -> f b -> Bool
liftEq ((a -> b -> Bool) -> (c -> d -> Bool) -> (a, c) -> (b, d) -> Bool
forall (f :: * -> * -> *) a b c d.
Eq2 f =>
(a -> b -> Bool) -> (c -> d -> Bool) -> f a c -> f b d -> Bool
liftEq2 a -> b -> Bool
eqk c -> d -> Bool
eqv) (SetMultimap a c -> [(a, c)]
forall k a. SetMultimap k a -> [(k, a)]
toList SetMultimap a c
m) (SetMultimap b d -> [(b, d)]
forall k a. SetMultimap k a -> [(k, a)]
toList SetMultimap b d
n)

instance Ord k => Ord1 (SetMultimap k) where
  liftCompare :: (a -> b -> Ordering)
-> SetMultimap k a -> SetMultimap k b -> Ordering
liftCompare = (k -> k -> Ordering)
-> (a -> b -> Ordering)
-> SetMultimap k a
-> SetMultimap k b
-> Ordering
forall (f :: * -> * -> *) a b c d.
Ord2 f =>
(a -> b -> Ordering)
-> (c -> d -> Ordering) -> f a c -> f b d -> Ordering
liftCompare2 k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare

instance Ord2 SetMultimap where
  liftCompare2 :: (a -> b -> Ordering)
-> (c -> d -> Ordering)
-> SetMultimap a c
-> SetMultimap b d
-> Ordering
liftCompare2 a -> b -> Ordering
cmpk c -> d -> Ordering
cmpv SetMultimap a c
m SetMultimap b d
n =
      ((a, c) -> (b, d) -> Ordering) -> [(a, c)] -> [(b, d)] -> Ordering
forall (f :: * -> *) a b.
Ord1 f =>
(a -> b -> Ordering) -> f a -> f b -> Ordering
liftCompare ((a -> b -> Ordering)
-> (c -> d -> Ordering) -> (a, c) -> (b, d) -> Ordering
forall (f :: * -> * -> *) a b c d.
Ord2 f =>
(a -> b -> Ordering)
-> (c -> d -> Ordering) -> f a c -> f b d -> Ordering
liftCompare2 a -> b -> Ordering
cmpk c -> d -> Ordering
cmpv) (SetMultimap a c -> [(a, c)]
forall k a. SetMultimap k a -> [(k, a)]
toList SetMultimap a c
m) (SetMultimap b d -> [(b, d)]
forall k a. SetMultimap k a -> [(k, a)]
toList SetMultimap b d
n)

instance (Show k, Show a) => Show (SetMultimap k a) where
  showsPrec :: Int -> SetMultimap k a -> ShowS
showsPrec Int
d SetMultimap k a
m = Bool -> ShowS -> ShowS
showParen (Int
d Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
10) (ShowS -> ShowS) -> ShowS -> ShowS
forall a b. (a -> b) -> a -> b
$
    String -> ShowS
showString String
"fromList " ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(k, a)] -> ShowS
forall a. Show a => a -> ShowS
shows (SetMultimap k a -> [(k, a)]
forall k a. SetMultimap k a -> [(k, a)]
toList SetMultimap k a
m)

instance Show k => Show1 (SetMultimap k) where
  liftShowsPrec :: (Int -> a -> ShowS)
-> ([a] -> ShowS) -> Int -> SetMultimap k a -> ShowS
liftShowsPrec = (Int -> k -> ShowS)
-> ([k] -> ShowS)
-> (Int -> a -> ShowS)
-> ([a] -> ShowS)
-> Int
-> SetMultimap k a
-> ShowS
forall (f :: * -> * -> *) a b.
Show2 f =>
(Int -> a -> ShowS)
-> ([a] -> ShowS)
-> (Int -> b -> ShowS)
-> ([b] -> ShowS)
-> Int
-> f a b
-> ShowS
liftShowsPrec2 Int -> k -> ShowS
forall a. Show a => Int -> a -> ShowS
showsPrec [k] -> ShowS
forall a. Show a => [a] -> ShowS
showList

instance Show2 SetMultimap where
  liftShowsPrec2 :: (Int -> a -> ShowS)
-> ([a] -> ShowS)
-> (Int -> b -> ShowS)
-> ([b] -> ShowS)
-> Int
-> SetMultimap a b
-> ShowS
liftShowsPrec2 Int -> a -> ShowS
spk [a] -> ShowS
slk Int -> b -> ShowS
spv [b] -> ShowS
slv Int
d SetMultimap a b
m =
      (Int -> [(a, b)] -> ShowS) -> String -> Int -> [(a, b)] -> ShowS
forall a. (Int -> a -> ShowS) -> String -> Int -> a -> ShowS
showsUnaryWith ((Int -> (a, b) -> ShowS)
-> ([(a, b)] -> ShowS) -> Int -> [(a, b)] -> ShowS
forall (f :: * -> *) a.
Show1 f =>
(Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> f a -> ShowS
liftShowsPrec Int -> (a, b) -> ShowS
sp [(a, b)] -> ShowS
sl) String
"fromList" Int
d (SetMultimap a b -> [(a, b)]
forall k a. SetMultimap k a -> [(k, a)]
toList SetMultimap a b
m)
    where
      sp :: Int -> (a, b) -> ShowS
sp = (Int -> a -> ShowS)
-> ([a] -> ShowS)
-> (Int -> b -> ShowS)
-> ([b] -> ShowS)
-> Int
-> (a, b)
-> ShowS
forall (f :: * -> * -> *) a b.
Show2 f =>
(Int -> a -> ShowS)
-> ([a] -> ShowS)
-> (Int -> b -> ShowS)
-> ([b] -> ShowS)
-> Int
-> f a b
-> ShowS
liftShowsPrec2 Int -> a -> ShowS
spk [a] -> ShowS
slk Int -> b -> ShowS
spv [b] -> ShowS
slv
      sl :: [(a, b)] -> ShowS
sl = (Int -> a -> ShowS)
-> ([a] -> ShowS)
-> (Int -> b -> ShowS)
-> ([b] -> ShowS)
-> [(a, b)]
-> ShowS
forall (f :: * -> * -> *) a b.
Show2 f =>
(Int -> a -> ShowS)
-> ([a] -> ShowS)
-> (Int -> b -> ShowS)
-> ([b] -> ShowS)
-> [f a b]
-> ShowS
liftShowList2 Int -> a -> ShowS
spk [a] -> ShowS
slk Int -> b -> ShowS
spv [b] -> ShowS
slv

instance (Ord k, Ord a, Read k, Read a) => Read (SetMultimap k a) where
  readsPrec :: Int -> ReadS (SetMultimap k a)
readsPrec Int
p = Bool -> ReadS (SetMultimap k a) -> ReadS (SetMultimap k a)
forall a. Bool -> ReadS a -> ReadS a
readParen (Int
p Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
10) (ReadS (SetMultimap k a) -> ReadS (SetMultimap k a))
-> ReadS (SetMultimap k a) -> ReadS (SetMultimap k a)
forall a b. (a -> b) -> a -> b
$ \ String
r -> do
    (String
"fromList",String
s) <- ReadS String
lex String
r
    ([(k, a)]
xs,String
t) <- ReadS [(k, a)]
forall a. Read a => ReadS a
reads String
s
    (SetMultimap k a, String) -> [(SetMultimap k a, String)]
forall (f :: * -> *) a. Applicative f => a -> f a
pure ([(k, a)] -> SetMultimap k a
forall k a. (Ord k, Ord a) => [(k, a)] -> SetMultimap k a
fromList [(k, a)]
xs,String
t)

instance Foldable.Foldable (SetMultimap k) where
  foldMap :: (a -> m) -> SetMultimap k a -> m
foldMap = (k -> a -> m) -> SetMultimap k a -> m
forall m k a. Monoid m => (k -> a -> m) -> SetMultimap k a -> m
foldMapWithKey ((k -> a -> m) -> SetMultimap k a -> m)
-> ((a -> m) -> k -> a -> m) -> (a -> m) -> SetMultimap k a -> m
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> m) -> k -> a -> m
forall a b. a -> b -> a
const
  {-# INLINE foldMap #-}

instance (Ord k, Ord a) => Semigroup (SetMultimap k a) where
  <> :: SetMultimap k a -> SetMultimap k a -> SetMultimap k a
(<>) = SetMultimap k a -> SetMultimap k a -> SetMultimap k a
forall k a.
(Ord k, Ord a) =>
SetMultimap k a -> SetMultimap k a -> SetMultimap k a
union

instance (Ord k, Ord a) => Monoid (SetMultimap k a) where
  mempty :: SetMultimap k a
mempty = SetMultimap k a
forall k a. SetMultimap k a
empty
  mappend :: SetMultimap k a -> SetMultimap k a -> SetMultimap k a
mappend = SetMultimap k a -> SetMultimap k a -> SetMultimap k a
forall a. Semigroup a => a -> a -> a
(<>)

------------------------------------------------------------------------------

-- | /O(1)/. The empty multimap.
--
-- > size empty === 0
empty :: SetMultimap k a
empty :: SetMultimap k a
empty = (Map k (Set a), Int) -> SetMultimap k a
forall k a. (Map k (Set a), Int) -> SetMultimap k a
SetMultimap (Map k (Set a)
forall k a. Map k a
Map.empty, Int
0)

-- | /O(1)/. A multimap with a single element.
--
-- > singleton 1 'a' === fromList [(1, 'a')]
-- > size (singleton 1 'a') === 1
singleton :: k -> a -> SetMultimap k a
singleton :: k -> a -> SetMultimap k a
singleton k
k a
a = (Map k (Set a), Int) -> SetMultimap k a
forall k a. (Map k (Set a), Int) -> SetMultimap k a
SetMultimap (k -> Set a -> Map k (Set a)
forall k a. k -> a -> Map k a
Map.singleton k
k (a -> Set a
forall a. a -> Set a
Set.singleton a
a), Int
1)

-- | /O(n*log n)/ where /n/ is the length of the input list.
--  Build a multimap from a list of key\/value pairs.
--
-- > fromList ([] :: [(Int, Char)]) === empty
-- > fromList [(1, 'b'), (2, 'a'), (1, 'b')] === fromList [(1, 'b'), (2, 'a')]
fromList :: (Ord k, Ord a) => [(k, a)] -> SetMultimap k a
fromList :: [(k, a)] -> SetMultimap k a
fromList = ((k, a) -> SetMultimap k a -> SetMultimap k a)
-> SetMultimap k a -> [(k, a)] -> SetMultimap k a
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
Foldable.foldr ((k -> a -> SetMultimap k a -> SetMultimap k a)
-> (k, a) -> SetMultimap k a -> SetMultimap k a
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry k -> a -> SetMultimap k a -> SetMultimap k a
forall k a.
(Ord k, Ord a) =>
k -> a -> SetMultimap k a -> SetMultimap k a
insert) SetMultimap k a
forall k a. SetMultimap k a
empty

-- | /O(k)/. A key is retained only if it is associated with a
-- non-empty set of values.
fromMap :: Map k (Set a) -> SetMultimap k a
fromMap :: Map k (Set a) -> SetMultimap k a
fromMap Map k (Set a)
m = (Map k (Set a), Int) -> SetMultimap k a
forall k a. (Map k (Set a), Int) -> SetMultimap k a
SetMultimap (Map k (Set a)
m', Map k Int -> Int
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
sum ((Set a -> Int) -> Map k (Set a) -> Map k Int
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Set a -> Int
forall a. Set a -> Int
Set.size Map k (Set a)
m'))
  where
    m' :: Map k (Set a)
m' = (Set a -> Bool) -> Map k (Set a) -> Map k (Set a)
forall a k. (a -> Bool) -> Map k a -> Map k a
Map.filter (Bool -> Bool
not (Bool -> Bool) -> (Set a -> Bool) -> Set a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Set a -> Bool
forall a. Set a -> Bool
Set.null) Map k (Set a)
m

------------------------------------------------------------------------------

-- | /O(log m * log k)/. If the key exists in the multimap, the new value will
-- be inserted into the set of values for the key. It is a no-op if the value
-- already exists in the set.
--
-- > insert 1 'a' empty === singleton 1 'a'
-- > insert 1 'a' (fromList [(1, 'b'), (2, 'a')]) === fromList [(1, 'a'), (1, 'b'), (2, 'a')]
-- > insert 1 'a' (fromList [(1, 'a'), (2, 'c')]) === fromList [(1, 'a'), (2, 'c')]
insert :: (Ord k, Ord a) => k -> a -> SetMultimap k a -> SetMultimap k a
insert :: k -> a -> SetMultimap k a -> SetMultimap k a
insert k
k a
a (SetMultimap (Map k (Set a)
m, Int
_)) = k -> Map k (Set a) -> SetMultimap k a
forall k a. Ord k => k -> Map k (Set a) -> SetMultimap k a
fromMap' k
k ((Maybe (Set a) -> Maybe (Set a))
-> k -> Map k (Set a) -> Map k (Set a)
forall k a.
Ord k =>
(Maybe a -> Maybe a) -> k -> Map k a -> Map k a
Map.alter Maybe (Set a) -> Maybe (Set a)
f k
k Map k (Set a)
m)
  where
    f :: Maybe (Set a) -> Maybe (Set a)
f (Just Set a
as) = Set a -> Maybe (Set a)
forall a. a -> Maybe a
Just (a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
Set.insert a
a Set a
as)
    f Maybe (Set a)
Nothing = Set a -> Maybe (Set a)
forall a. a -> Maybe a
Just (a -> Set a
forall a. a -> Set a
Set.singleton a
a)

-- | /O(log k)/. Delete a key and all its values from the map.
--
-- > delete 1 (fromList [(1,'a'),(1,'b'),(2,'c')]) === singleton 2 'c'
delete :: Ord k => k -> SetMultimap k a -> SetMultimap k a
delete :: k -> SetMultimap k a -> SetMultimap k a
delete = (Set a -> Set a) -> k -> SetMultimap k a -> SetMultimap k a
forall k a.
Ord k =>
(Set a -> Set a) -> k -> SetMultimap k a -> SetMultimap k a
alter (Set a -> Set a -> Set a
forall a b. a -> b -> a
const Set a
forall a. Set a
Set.empty)

-- | /O(log m * log k)/. Remove the first
-- occurrence of the value associated with the key, if exists.
--
-- > deleteWithValue 1 'c' (fromList [(1,'a'),(1,'b'),(2,'c')]) === fromList [(1,'a'),(1,'b'),(2,'c')]
-- > deleteWithValue 1 'c' (fromList [(2,'c'),(1,'c')]) === singleton 2 'c'
deleteWithValue :: (Ord k, Ord a) => k -> a -> SetMultimap k a -> SetMultimap k a
deleteWithValue :: k -> a -> SetMultimap k a -> SetMultimap k a
deleteWithValue k
k a
a = (Set a -> Set a) -> k -> SetMultimap k a -> SetMultimap k a
forall k a.
Ord k =>
(Set a -> Set a) -> k -> SetMultimap k a -> SetMultimap k a
alter (a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
Set.delete a
a) k
k

-- | /O(log m * log k)/. Remove the maximal value
-- associated with the key, if exists.
--
-- > deleteMax 3 (fromList [(1,'a'),(1,'b'),(2,'c')]) === fromList [(1,'a'),(1,'b'),(2,'c')]
-- > deleteMax 1 (fromList [(1,'a'),(1,'b'),(2,'c')]) === fromList [(1,'a'),(2,'c')]
deleteMax :: Ord k => k -> SetMultimap k a -> SetMultimap k a
deleteMax :: k -> SetMultimap k a -> SetMultimap k a
deleteMax = (Set a -> Set a) -> k -> SetMultimap k a -> SetMultimap k a
forall k a.
Ord k =>
(Set a -> Set a) -> k -> SetMultimap k a -> SetMultimap k a
alter Set a -> Set a
forall a. Set a -> Set a
Set.deleteMax

-- | /O(log m * log k)/. Remove the minimal value
-- associated with the key, if exists.
--
-- > deleteMin 3 (fromList [(1,'a'),(1,'b'),(2,'c')]) === fromList [(1,'a'),(1,'b'),(2,'c')]
-- > deleteMin 1 (fromList [(1,'a'),(1,'b'),(2,'c')]) === fromList [(1,'b'),(2,'c')]
deleteMin :: Ord k => k -> SetMultimap k a -> SetMultimap k a
deleteMin :: k -> SetMultimap k a -> SetMultimap k a
deleteMin = (Set a -> Set a) -> k -> SetMultimap k a -> SetMultimap k a
forall k a.
Ord k =>
(Set a -> Set a) -> k -> SetMultimap k a -> SetMultimap k a
alter Set a -> Set a
forall a. Set a -> Set a
Set.deleteMin

-- | /O(m * log m * log k)/, assuming the function @a -> a@ takes /O(1)/.
-- Update values at a specific key, if exists.
--
-- Since values are sets, the result may be smaller than the original multimap.
--
-- > adjust ("new " ++) 1 (fromList [(1,"a"),(1,"b"),(2,"c")]) === fromList [(1,"new a"),(1,"new b"),(2,"c")]
-- > adjust (const "z") 1 (fromList [(1,"a"),(1,"b"),(2,"c")]) === fromList [(1,"z"),(2,"c")]
adjust :: (Ord k, Ord a) => (a -> a) -> k -> SetMultimap k a -> SetMultimap k a
adjust :: (a -> a) -> k -> SetMultimap k a -> SetMultimap k a
adjust = (k -> a -> a) -> k -> SetMultimap k a -> SetMultimap k a
forall k a.
(Ord k, Ord a) =>
(k -> a -> a) -> k -> SetMultimap k a -> SetMultimap k a
adjustWithKey((k -> a -> a) -> k -> SetMultimap k a -> SetMultimap k a)
-> ((a -> a) -> k -> a -> a)
-> (a -> a)
-> k
-> SetMultimap k a
-> SetMultimap k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> a) -> k -> a -> a
forall a b. a -> b -> a
const

-- | /O(m * log m * log k)/, assuming the function @k -> a -> a@ takes /O(1)/.
-- Update values at a specific key, if exists.
--
-- Since values are sets, the result may be smaller than the original multimap.
--
-- > adjustWithKey (\k x -> show k ++ ":new " ++ x) 1 (fromList [(1,"a"),(1,"b"),(2,"c")])
-- >   === fromList [(1,"1:new a"),(1,"1:new b"),(2,"c")]
adjustWithKey :: (Ord k, Ord a) => (k -> a -> a) -> k -> SetMultimap k a -> SetMultimap k a
adjustWithKey :: (k -> a -> a) -> k -> SetMultimap k a -> SetMultimap k a
adjustWithKey k -> a -> a
f = (k -> Set a -> Set a) -> k -> SetMultimap k a -> SetMultimap k a
forall k a.
Ord k =>
(k -> Set a -> Set a) -> k -> SetMultimap k a -> SetMultimap k a
alterWithKey ((a -> a) -> Set a -> Set a
forall b a. Ord b => (a -> b) -> Set a -> Set b
Set.map ((a -> a) -> Set a -> Set a)
-> (k -> a -> a) -> k -> Set a -> Set a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. k -> a -> a
f)

-- | /O(m * log m * log k)/, assuming the function @a -> 'Maybe' a@
-- takes /O(1)/. The expression (@'update' f k map@) updates the
-- values at key @k@, if exists. If @f@ returns 'Nothing' for a value, the
-- value is deleted.
--
-- > let f x = if x == "a" then Just "new a" else Nothing in do
-- >   update f 1 (fromList [(1,"a"),(1,"b"),(2,"c")]) === fromList [(1,"new a"),(2, "c")]
-- >   update f 1 (fromList [(1,"b"),(1,"c"),(2,"c")]) === singleton 2 "c"
update :: (Ord k, Ord a) => (a -> Maybe a) -> k -> SetMultimap k a -> SetMultimap k a
update :: (a -> Maybe a) -> k -> SetMultimap k a -> SetMultimap k a
update = (k -> a -> Maybe a) -> k -> SetMultimap k a -> SetMultimap k a
forall k a.
(Ord k, Ord a) =>
(k -> a -> Maybe a) -> k -> SetMultimap k a -> SetMultimap k a
updateWithKey ((k -> a -> Maybe a) -> k -> SetMultimap k a -> SetMultimap k a)
-> ((a -> Maybe a) -> k -> a -> Maybe a)
-> (a -> Maybe a)
-> k
-> SetMultimap k a
-> SetMultimap k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Maybe a) -> k -> a -> Maybe a
forall a b. a -> b -> a
const

-- | /O(m * log m * log k)/, assuming the function @k -> a -> 'Maybe' a@
-- takes /O(1)/. The expression (@'updateWithKey' f k map@) updates the
-- values at key @k@, if exists. If @f@ returns 'Nothing' for a value, the
-- value is deleted.
--
-- > let f k x = if x == "a" then Just (show k ++ ":new a") else Nothing in do
-- >   updateWithKey f 1 (fromList [(1,"a"),(1,"b"),(2,"c")]) === fromList [(1,"1:new a"),(2,"c")]
-- >   updateWithKey f 1 (fromList [(1,"b"),(1,"c"),(2,"c")]) === singleton 2 "c"
updateWithKey :: (Ord k, Ord a) => (k -> a -> Maybe a) -> k -> SetMultimap k a -> SetMultimap k a
updateWithKey :: (k -> a -> Maybe a) -> k -> SetMultimap k a -> SetMultimap k a
updateWithKey k -> a -> Maybe a
f = (k -> Set a -> Set a) -> k -> SetMultimap k a -> SetMultimap k a
forall k a.
Ord k =>
(k -> Set a -> Set a) -> k -> SetMultimap k a -> SetMultimap k a
alterWithKey k -> Set a -> Set a
g
  where
    g :: k -> Set a -> Set a
g k
k = Set (Maybe a) -> Set a
forall a. Ord a => Set (Maybe a) -> Set a
catMaybes (Set (Maybe a) -> Set a)
-> (Set a -> Set (Maybe a)) -> Set a -> Set a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Maybe a) -> Set a -> Set (Maybe a)
forall b a. Ord b => (a -> b) -> Set a -> Set b
Set.map (k -> a -> Maybe a
f k
k)

-- | /O(log k)/, assuming the function @'Set' a -> 'Set' a@ takes /O(1)/.
-- The expression (@'alter' f k map@) alters the values at k, if exists.
--
-- > let (f, g) = (const Set.empty, Set.insert 'c') in do
-- >   alter f 1 (fromList [(1, 'a'), (2, 'b')]) === singleton 2 'b'
-- >   alter f 3 (fromList [(1, 'a'), (2, 'b')]) === fromList [(1, 'a'), (2, 'b')]
-- >   alter g 1 (fromList [(1, 'a'), (2, 'b')]) === fromList [(1, 'c'), (1, 'a'), (2, 'b')]
-- >   alter g 1 (fromList [(1, 'c'), (2, 'b')]) === fromList [(1, 'c'), (2, 'b')]
-- >   alter g 3 (fromList [(1, 'a'), (2, 'b')]) === fromList [(1, 'a'), (2, 'b'), (3, 'c')]
alter :: Ord k => (Set a -> Set a) -> k -> SetMultimap k a -> SetMultimap k a
alter :: (Set a -> Set a) -> k -> SetMultimap k a -> SetMultimap k a
alter = (k -> Set a -> Set a) -> k -> SetMultimap k a -> SetMultimap k a
forall k a.
Ord k =>
(k -> Set a -> Set a) -> k -> SetMultimap k a -> SetMultimap k a
alterWithKey ((k -> Set a -> Set a) -> k -> SetMultimap k a -> SetMultimap k a)
-> ((Set a -> Set a) -> k -> Set a -> Set a)
-> (Set a -> Set a)
-> k
-> SetMultimap k a
-> SetMultimap k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Set a -> Set a) -> k -> Set a -> Set a
forall a b. a -> b -> a
const

-- | /O(log k)/, assuming the function @k -> 'Set' a -> 'Set' a@ takes /O(1)/.
-- The expression (@'alterWithKey' f k map@) alters the values at k, if exists.
--
-- > let (f, g) = (const (const Set.empty), Set.insert . show) in do
-- >   alterWithKey f 1 (fromList [(1, "a"), (2, "b")]) === singleton 2 "b"
-- >   alterWithKey f 3 (fromList [(1, "a"), (2, "b")]) === fromList [(1, "a"), (2, "b")]
-- >   alterWithKey g 1 (fromList [(1, "a"), (2, "b")]) === fromList [(1, "1"), (1, "a"), (2, "b")]
-- >   alterWithKey g 3 (fromList [(1, "a"), (2, "b")]) === fromList [(1, "a"), (2, "b"), (3, "3")]
alterWithKey :: Ord k => (k -> Set a -> Set a) -> k -> SetMultimap k a -> SetMultimap k a
alterWithKey :: (k -> Set a -> Set a) -> k -> SetMultimap k a -> SetMultimap k a
alterWithKey k -> Set a -> Set a
f k
k mm :: SetMultimap k a
mm@(SetMultimap (Map k (Set a)
m, Int
_))
    | Set a -> Bool
forall a. Set a -> Bool
Set.null Set a
as = Map k (Set a) -> SetMultimap k a
forall k a. Map k (Set a) -> SetMultimap k a
fromMap (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)
m)
    | Bool
otherwise = Map k (Set a) -> SetMultimap k a
forall k a. Map k (Set a) -> SetMultimap k a
fromMap (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
as Map k (Set a)
m)
  where
    as :: Set a
as = k -> Set a -> Set a
f k
k (SetMultimap k a
mm SetMultimap k a -> k -> Set a
forall k a. Ord k => SetMultimap k a -> k -> Set a
! k
k)

------------------------------------------------------------------------------

-- | /O(log k)/. Lookup the values at a key in the map. It returns an empty
-- set if the key is not in the map.
lookup :: Ord k => k -> SetMultimap k a -> Set a
lookup :: k -> SetMultimap k a -> Set a
lookup k
k (SetMultimap (Map k (Set a)
m, Int
_)) = Set a -> Maybe (Set a) -> Set a
forall a. a -> Maybe a -> a
Maybe.fromMaybe Set a
forall a. Set a
Set.empty (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)
m)

-- | /O(log k)/. Lookup the values at a key in the map. It returns an empty
-- set if the key is not in the map.
--
-- > fromList [(3, 'a'), (5, 'b'), (3, 'c')] ! 3 === Set.fromList "ac"
-- > fromList [(3, 'a'), (5, 'b'), (3, 'c')] ! 2 === Set.empty
(!) :: Ord k => SetMultimap k a -> k -> Set a
(!) = (k -> SetMultimap k a -> Set a) -> SetMultimap k a -> k -> Set a
forall a b c. (a -> b -> c) -> b -> a -> c
flip k -> SetMultimap k a -> Set a
forall k a. Ord k => k -> SetMultimap k a -> Set a
lookup

-- | /O(log k)/. Is the key a member of the map?
--
-- A key is a member of the map if and only if there is at least one value
-- associated with it.
--
-- > member 1 (fromList [(1, 'a'), (2, 'b'), (2, 'c')]) === True
-- > member 1 (deleteMax 1 (fromList [(2, 'c'), (1, 'c')])) === False
member :: Ord k => k -> SetMultimap k a -> Bool
member :: k -> SetMultimap k a -> Bool
member k
k (SetMultimap (Map k (Set a)
m, Int
_)) = k -> Map k (Set a) -> Bool
forall k a. Ord k => k -> Map k a -> Bool
Map.member k
k Map k (Set a)
m

-- | /O(log k)/. Is the key not a member of the map?
--
-- A key is a member of the map if and only if there is at least one value
-- associated with it.
--
-- > notMember 1 (fromList [(1, 'a'), (2, 'b'), (2, 'c')]) === False
-- > notMember 1 (deleteMin 1 (fromList [(2, 'c'), (1, 'c')])) === True
notMember :: Ord k => k -> SetMultimap k a -> Bool
notMember :: k -> SetMultimap k a -> Bool
notMember k
k = Bool -> Bool
not (Bool -> Bool)
-> (SetMultimap k a -> Bool) -> SetMultimap k a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. k -> SetMultimap k a -> Bool
forall k a. Ord k => k -> SetMultimap k a -> Bool
member k
k

-- | /O(1)/. Is the multimap empty?
--
-- > Data.Multimap.Set.null empty === True
-- > Data.Multimap.Set.null (singleton 1 'a') === False
null :: SetMultimap k a -> Bool
null :: SetMultimap k a -> Bool
null (SetMultimap (Map k (Set a)
m, Int
_)) = Map k (Set a) -> Bool
forall k a. Map k a -> Bool
Map.null Map k (Set a)
m

-- | /O(1)/. Is the multimap non-empty?
--
-- > notNull empty === False
-- > notNull (singleton 1 'a') === True
notNull :: SetMultimap k a -> Bool
notNull :: SetMultimap k a -> Bool
notNull = Bool -> Bool
not (Bool -> Bool)
-> (SetMultimap k a -> Bool) -> SetMultimap k a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. SetMultimap k a -> Bool
forall k a. SetMultimap k a -> Bool
null

-- | The total number of values for all keys.
--
-- @size@ is evaluated lazily. Forcing the size for the first time takes up to
-- /O(k)/ and subsequent forces take /O(1)/.
--
-- > size empty === 0
-- > size (singleton 1 'a') === 1
-- > size (fromList [(1, 'a'), (2, 'b'), (2, 'c'), (2, 'b')]) === 3
size :: SetMultimap k a -> Int
size :: SetMultimap k a -> Int
size (SetMultimap (Map k (Set a)
_, Int
sz)) = Int
sz

------------------------------------------------------------------------------

-- | Union two multimaps, unioning values for duplicate keys.
--
-- > union (fromList [(1,'a'),(2,'b'),(2,'c')]) (fromList [(1,'d'),(2,'b')])
-- >   === fromList [(1,'a'),(1,'d'),(2,'b'),(2,'c')]
union :: (Ord k, Ord a) => SetMultimap k a -> SetMultimap k a -> SetMultimap k a
union :: SetMultimap k a -> SetMultimap k a -> SetMultimap k a
union (SetMultimap (Map k (Set a)
m1, Int
_)) (SetMultimap (Map k (Set a)
m2, Int
_)) =
  Map k (Set a) -> SetMultimap k a
forall k a. Map k (Set a) -> SetMultimap k a
fromMap ((Set a -> Set a -> Set a)
-> Map k (Set a) -> Map k (Set a) -> Map k (Set a)
forall k a. Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k a
Map.unionWith Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
Set.union Map k (Set a)
m1 Map k (Set a)
m2)

-- | Union a number of multimaps, unioning values for duplicate keys.
--
-- > unions [fromList [(1,'a'),(2,'b'),(2,'c')], fromList [(1,'d'),(2,'b')]]
-- >   === fromList [(1,'a'),(1,'d'),(2,'b'),(2,'c')]
unions :: (Foldable f, Ord k, Ord a) => f (SetMultimap k a) -> SetMultimap k a
unions :: f (SetMultimap k a) -> SetMultimap k a
unions = (SetMultimap k a -> SetMultimap k a -> SetMultimap k a)
-> SetMultimap k a -> f (SetMultimap k a) -> SetMultimap k a
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
Foldable.foldr SetMultimap k a -> SetMultimap k a -> SetMultimap k a
forall k a.
(Ord k, Ord a) =>
SetMultimap k a -> SetMultimap k a -> SetMultimap k a
union SetMultimap k a
forall k a. SetMultimap k a
empty

-- | Difference of two multimaps.
--
-- If a key exists in the first multimap but not the second, it remains
-- unchanged in the result. If a key exists in both multimaps, a set
-- difference is performed on their values.
--
-- > difference (fromList [(1,'a'),(2,'b'),(2,'c')]) (fromList [(1,'d'),(2,'b'),(2,'a')])
-- >   === fromList [(1,'a'),(2,'c')]
difference :: (Ord k, Ord a) => SetMultimap k a -> SetMultimap k a -> SetMultimap k a
difference :: SetMultimap k a -> SetMultimap k a -> SetMultimap k a
difference (SetMultimap (Map k (Set a)
m1, Int
_)) (SetMultimap (Map k (Set a)
m2, Int
_)) = Map k (Set a) -> SetMultimap k a
forall k a. Map k (Set a) -> SetMultimap k a
fromMap (Map k (Set a) -> SetMultimap k a)
-> Map k (Set a) -> SetMultimap k a
forall a b. (a -> b) -> a -> b
$
  (Set a -> Set a -> Maybe (Set a))
-> Map k (Set a) -> Map k (Set a) -> Map k (Set a)
forall k a b.
Ord k =>
(a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
Map.differenceWith (\Set a
xs Set a
ys -> Set a -> Maybe (Set a)
forall a. a -> Maybe a
Just (Set a
xs Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
Set.\\ Set a
ys)) Map k (Set a)
m1 Map k (Set a)
m2

------------------------------------------------------------------------------

-- | /O(n * log m)/, assuming the function @a -> b@ takes /O(1)/.
-- Map a function over all values in the map.
--
-- Since values are sets, the result may be smaller than the original multimap.
--
-- > Data.Multimap.Set.map (++ "x") (fromList [(1,"a"),(2,"b")]) === fromList [(1,"ax"),(2,"bx")]
-- > Data.Multimap.Set.map (const "c") (fromList [(1,"a"),(1,"b"),(2,"b")]) === fromList [(1,"c"),(2,"c")]
map :: Ord b => (a -> b) -> SetMultimap k a -> SetMultimap k b
map :: (a -> b) -> SetMultimap k a -> SetMultimap k b
map = (k -> a -> b) -> SetMultimap k a -> SetMultimap k b
forall b k a.
Ord b =>
(k -> a -> b) -> SetMultimap k a -> SetMultimap k b
mapWithKey ((k -> a -> b) -> SetMultimap k a -> SetMultimap k b)
-> ((a -> b) -> k -> a -> b)
-> (a -> b)
-> SetMultimap k a
-> SetMultimap k b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> b) -> k -> a -> b
forall a b. a -> b -> a
const

-- | /O(n * log m)/, assuming the function @k -> a -> b@ takes /O(1)/.
-- Map a function over all values in the map.
--
-- Since values are sets, the result may be smaller than the original multimap.
--
-- > mapWithKey (\k x -> show k ++ ":" ++ x) (fromList [(1,"a"),(2,"b")]) === fromList [(1,"1:a"),(2,"2:b")]
mapWithKey :: Ord b => (k -> a -> b) -> SetMultimap k a -> SetMultimap k b
mapWithKey :: (k -> a -> b) -> SetMultimap k a -> SetMultimap k b
mapWithKey k -> a -> b
f (SetMultimap (Map k (Set a)
m, Int
_)) = Map k (Set b) -> SetMultimap k b
forall k a. Map k (Set a) -> SetMultimap k a
fromMap (Map k (Set b) -> SetMultimap k b)
-> Map k (Set b) -> SetMultimap k b
forall a b. (a -> b) -> a -> b
$ (k -> Set a -> Set b) -> Map k (Set a) -> Map k (Set b)
forall k a b. (k -> a -> b) -> Map k a -> Map k b
Map.mapWithKey ((a -> b) -> Set a -> Set b
forall b a. Ord b => (a -> b) -> Set a -> Set b
Set.map ((a -> b) -> Set a -> Set b)
-> (k -> a -> b) -> k -> Set a -> Set b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. k -> a -> b
f) Map k (Set a)
m

-- | /O(n)/. Fold the values in the map using the given right-associative
-- binary operator.
--
-- > Data.Multimap.Set.foldr ((+) . length) 0 (fromList [(1, "hello"), (1, "world"), (2, "!")]) === 11
foldr :: (a -> b -> b) -> b -> SetMultimap k a -> b
foldr :: (a -> b -> b) -> b -> SetMultimap k a -> b
foldr = (k -> a -> b -> b) -> b -> SetMultimap k a -> b
forall k a b. (k -> a -> b -> b) -> b -> SetMultimap k a -> b
foldrWithKey ((k -> a -> b -> b) -> b -> SetMultimap k a -> b)
-> ((a -> b -> b) -> k -> a -> b -> b)
-> (a -> b -> b)
-> b
-> SetMultimap k a
-> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> b -> b) -> k -> a -> b -> b
forall a b. a -> b -> a
const

-- | /O(n)/. Fold the values in the map using the given left-associative
-- binary operator.
--
-- > Data.Multimap.Set.foldl (\len -> (+ len) . length) 0 (fromList [(1, "hello"), (1, "world"), (2, "!")]) === 11
foldl :: (a -> b -> a) -> a -> SetMultimap k b -> a
foldl :: (a -> b -> a) -> a -> SetMultimap k b -> a
foldl = (a -> k -> b -> a) -> a -> SetMultimap k b -> a
forall a k b. (a -> k -> b -> a) -> a -> SetMultimap k b -> a
foldlWithKey ((a -> k -> b -> a) -> a -> SetMultimap k b -> a)
-> ((a -> b -> a) -> a -> k -> b -> a)
-> (a -> b -> a)
-> a
-> SetMultimap k b
-> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((b -> a) -> k -> b -> a
forall a b. a -> b -> a
const ((b -> a) -> k -> b -> a) -> (a -> b -> a) -> a -> k -> b -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
.)

-- | /O(n)/. Fold the key\/value pairs in the map using the given
-- right-associative binary operator.
--
-- > foldrWithKey (\k a len -> length (show k) + length a + len) 0 (fromList [(1, "hello"), (1, "world"), (20, "!")]) === 15
foldrWithKey :: (k -> a -> b -> b) -> b -> SetMultimap k a -> b
foldrWithKey :: (k -> a -> b -> b) -> b -> SetMultimap k a -> b
foldrWithKey k -> a -> b -> b
f b
b (SetMultimap (Map k (Set a)
m, Int
_)) = (k -> Set a -> b -> b) -> b -> Map k (Set a) -> b
forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
Map.foldrWithKey k -> Set a -> b -> b
f' b
b Map k (Set a)
m
  where
    f' :: k -> Set a -> b -> b
f' = (b -> Set a -> b) -> Set a -> b -> b
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((b -> Set a -> b) -> Set a -> b -> b)
-> (k -> b -> Set a -> b) -> k -> Set a -> b -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> b -> b) -> b -> Set a -> b
forall a b. (a -> b -> b) -> b -> Set a -> b
Set.foldr ((a -> b -> b) -> b -> Set a -> b)
-> (k -> a -> b -> b) -> k -> b -> Set a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. k -> a -> b -> b
f

-- | /O(n)/. Fold the key\/value pairs in the map using the given
-- left-associative binary operator.
--
-- > foldlWithKey (\len k a -> length (show k) + length a + len) 0 (fromList [(1, "hello"), (1, "world"), (20, "!")]) === 15
foldlWithKey :: (a -> k -> b -> a) -> a -> SetMultimap k b -> a
foldlWithKey :: (a -> k -> b -> a) -> a -> SetMultimap k b -> a
foldlWithKey a -> k -> b -> a
f a
a (SetMultimap (Map k (Set b)
m, Int
_)) = (a -> k -> Set b -> a) -> a -> Map k (Set b) -> a
forall a k b. (a -> k -> b -> a) -> a -> Map k b -> a
Map.foldlWithKey a -> k -> Set b -> a
f' a
a Map k (Set b)
m
  where
    f' :: a -> k -> Set b -> a
f' = (k -> a -> Set b -> a) -> a -> k -> Set b -> a
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((a -> b -> a) -> a -> Set b -> a
forall a b. (a -> b -> a) -> a -> Set b -> a
Set.foldl ((a -> b -> a) -> a -> Set b -> a)
-> (k -> a -> b -> a) -> k -> a -> Set b -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> k -> b -> a) -> k -> a -> b -> a
forall a b c. (a -> b -> c) -> b -> a -> c
flip a -> k -> b -> a
f)

-- | /O(n)/. A strict version of 'foldr'. Each application of the
-- operator is evaluated before using the result in the next application.
-- This function is strict in the starting value.
--
-- > Data.Multimap.Set.foldr' ((+) . length) 0 (fromList [(1, "hello"), (1, "world"), (2, "!")]) === 11
foldr' :: (a -> b -> b) -> b -> SetMultimap k a -> b
foldr' :: (a -> b -> b) -> b -> SetMultimap k a -> b
foldr' = (k -> a -> b -> b) -> b -> SetMultimap k a -> b
forall k a b. (k -> a -> b -> b) -> b -> SetMultimap k a -> b
foldrWithKey' ((k -> a -> b -> b) -> b -> SetMultimap k a -> b)
-> ((a -> b -> b) -> k -> a -> b -> b)
-> (a -> b -> b)
-> b
-> SetMultimap k a
-> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> b -> b) -> k -> a -> b -> b
forall a b. a -> b -> a
const

-- | /O(n)/. A strict version of 'foldl'. Each application of the
-- operator is evaluated before using the result in the next application.
-- This function is strict in the starting value.
--
-- > Data.Multimap.Set.foldl' (\len -> (+ len) . length) 0 (fromList [(1, "hello"), (1, "world"), (2, "!")]) === 11
foldl' :: (a -> b -> a) -> a -> SetMultimap k b -> a
foldl' :: (a -> b -> a) -> a -> SetMultimap k b -> a
foldl' = (a -> k -> b -> a) -> a -> SetMultimap k b -> a
forall a k b. (a -> k -> b -> a) -> a -> SetMultimap k b -> a
foldlWithKey' ((a -> k -> b -> a) -> a -> SetMultimap k b -> a)
-> ((a -> b -> a) -> a -> k -> b -> a)
-> (a -> b -> a)
-> a
-> SetMultimap k b
-> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((b -> a) -> k -> b -> a
forall a b. a -> b -> a
const ((b -> a) -> k -> b -> a) -> (a -> b -> a) -> a -> k -> b -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
.)

-- | /O(n)/. A strict version of 'foldrWithKey'. Each application of the
-- operator is evaluated before using the result in the next application.
-- This function is strict in the starting value.
--
-- > foldrWithKey' (\k a len -> length (show k) + length a + len) 0 (fromList [(1, "hello"), (1, "world"), (20, "!")]) === 15
foldrWithKey' :: (k -> a -> b -> b) -> b -> SetMultimap k a -> b
foldrWithKey' :: (k -> a -> b -> b) -> b -> SetMultimap k a -> b
foldrWithKey' k -> a -> b -> b
f b
b (SetMultimap (Map k (Set a)
m, Int
_)) = (k -> Set a -> b -> b) -> b -> Map k (Set a) -> b
forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
Map.foldrWithKey k -> Set a -> b -> b
f' b
b Map k (Set a)
m
  where
    f' :: k -> Set a -> b -> b
f' = (b -> Set a -> b) -> Set a -> b -> b
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((b -> Set a -> b) -> Set a -> b -> b)
-> (k -> b -> Set a -> b) -> k -> Set a -> b -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> b -> b) -> b -> Set a -> b
forall a b. (a -> b -> b) -> b -> Set a -> b
Set.foldr' ((a -> b -> b) -> b -> Set a -> b)
-> (k -> a -> b -> b) -> k -> b -> Set a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. k -> a -> b -> b
f

-- | /O(n)/. A strict version of 'foldlWithKey'. Each application of the
-- operator is evaluated before using the result in the next application.
-- This function is strict in the starting value.
--
-- > foldlWithKey' (\len k a -> length (show k) + length a + len) 0 (fromList [(1, "hello"), (1, "world"), (20, "!")]) === 15
foldlWithKey' :: (a -> k -> b -> a) -> a -> SetMultimap k b -> a
foldlWithKey' :: (a -> k -> b -> a) -> a -> SetMultimap k b -> a
foldlWithKey' a -> k -> b -> a
f a
a (SetMultimap (Map k (Set b)
m, Int
_)) = (a -> k -> Set b -> a) -> a -> Map k (Set b) -> a
forall a k b. (a -> k -> b -> a) -> a -> Map k b -> a
Map.foldlWithKey a -> k -> Set b -> a
f' a
a Map k (Set b)
m
  where
    f' :: a -> k -> Set b -> a
f' = (k -> a -> Set b -> a) -> a -> k -> Set b -> a
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((a -> b -> a) -> a -> Set b -> a
forall a b. (a -> b -> a) -> a -> Set b -> a
Set.foldl' ((a -> b -> a) -> a -> Set b -> a)
-> (k -> a -> b -> a) -> k -> a -> Set b -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> k -> b -> a) -> k -> a -> b -> a
forall a b c. (a -> b -> c) -> b -> a -> c
flip a -> k -> b -> a
f)

-- | /O(n)/. Fold the key\/value pairs in the map using the given monoid.
--
-- > foldMapWithKey (\k x -> show k ++ ":" ++ x) (fromList [(1, "a"), (1, "c"), (2, "b")]) === "1:a1:c2:b"
foldMapWithKey :: Monoid m => (k -> a -> m) -> SetMultimap k a -> m
foldMapWithKey :: (k -> a -> m) -> SetMultimap k a -> m
foldMapWithKey k -> a -> m
f (SetMultimap (Map k (Set a)
m, Int
_)) = (k -> Set a -> m) -> Map k (Set a) -> m
forall m k a. Monoid m => (k -> a -> m) -> Map k a -> m
Map.foldMapWithKey k -> Set a -> m
f' Map k (Set a)
m
  where
    f' :: k -> Set a -> m
f' = (a -> m) -> Set a -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
Foldable.foldMap ((a -> m) -> Set a -> m) -> (k -> a -> m) -> k -> Set a -> m
forall b c a. (b -> c) -> (a -> b) -> a -> c
. k -> a -> m
f

------------------------------------------------------------------------------

-- | /O(n)/. Return all elements of the multimap in ascending order of
-- their keys. Elements of each key appear in ascending order.
--
-- > elems (fromList [(2,'a'),(1,'b'),(3,'d'),(3,'c'),(1,'b')]) === "bacd"
-- > elems (empty :: SetMultimap Int Char) === []
elems :: SetMultimap k a -> [a]
elems :: SetMultimap k a -> [a]
elems (SetMultimap (Map k (Set a)
m, Int
_)) = Map k (Set a) -> [Set a]
forall k a. Map k a -> [a]
Map.elems Map k (Set a)
m [Set a] -> (Set a -> [a]) -> [a]
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= Set a -> [a]
forall a. Set a -> [a]
Set.toList

-- | /O(k)/. Return all keys of the multimap in ascending order.
--
-- > keys (fromList [(2,'a'),(1,'b'),(3,'c'),(1,'b')]) === [1,2,3]
-- > keys (empty :: SetMultimap Int Char) === []
keys :: SetMultimap k a -> [k]
keys :: SetMultimap k a -> [k]
keys (SetMultimap (Map k (Set a)
m, Int
_)) = Map k (Set a) -> [k]
forall k a. Map k a -> [k]
Map.keys Map k (Set a)
m

-- | /O(k)/. The set of all keys of the multimap.
--
-- > keysSet (fromList [(2,'a'),(1,'b'),(3,'c'),(1,'b')]) === Set.fromList [1,2,3]
-- > keysSet (empty :: SetMultimap Int Char) === Set.empty
keysSet :: SetMultimap k a -> Set k
keysSet :: SetMultimap k a -> Set k
keysSet (SetMultimap (Map k (Set a)
m, Int
_)) = Map k (Set a) -> Set k
forall k a. Map k a -> Set k
Map.keysSet Map k (Set a)
m

-- | An alias for 'toAscList'.
assocs :: SetMultimap k a -> [(k, a)]
assocs :: SetMultimap k a -> [(k, a)]
assocs = SetMultimap k a -> [(k, a)]
forall k a. SetMultimap k a -> [(k, a)]
toAscList

-- | Convert the multimap into a list of key/value pairs.
--
-- > toList (fromList [(2,'a'),(1,'b'),(3,'c'),(1,'a')]) === [(1,'a'),(1,'b'),(2,'a'),(3,'c')]
toList :: SetMultimap k a -> [(k, a)]
toList :: SetMultimap k a -> [(k, a)]
toList = SetMultimap k a -> [(k, a)]
forall k a. SetMultimap k a -> [(k, a)]
toAscList

-- | Convert the multimap into a list of key/value pairs in ascending
-- order of keys. Elements of each key appear in ascending order.
--
-- > toAscList (fromList [(2,'a'),(1,'b'),(3,'c'),(1,'a')]) === [(1,'a'),(1,'b'),(2,'a'),(3,'c')]
toAscList :: SetMultimap k a -> [(k, a)]
toAscList :: SetMultimap k a -> [(k, a)]
toAscList (SetMultimap (Map k (Set a)
m, Int
_)) =
  Map k (Set a) -> [(k, Set a)]
forall k a. Map k a -> [(k, a)]
Map.toAscList Map k (Set a)
m [(k, Set a)] -> ((k, Set a) -> [(k, a)]) -> [(k, a)]
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= (k -> Set a -> [(k, a)]) -> (k, Set a) -> [(k, a)]
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry (\k
k -> (a -> (k, a)) -> [a] -> [(k, a)]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (k
k,) ([a] -> [(k, a)]) -> (Set a -> [a]) -> Set a -> [(k, a)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Set a -> [a]
forall a. Set a -> [a]
Set.toAscList)

-- | Convert the multimap into a list of key/value pairs in descending
-- order of keys. Elements of each key appear in descending order.
--
-- > toDescList (fromList [(2,'a'),(1,'b'),(3,'c'),(1,'a')]) === [(3,'c'),(2,'a'),(1,'b'),(1,'a')]
toDescList :: SetMultimap k a -> [(k, a)]
toDescList :: SetMultimap k a -> [(k, a)]
toDescList (SetMultimap (Map k (Set a)
m, Int
_)) =
  Map k (Set a) -> [(k, Set a)]
forall k a. Map k a -> [(k, a)]
Map.toDescList Map k (Set a)
m [(k, Set a)] -> ((k, Set a) -> [(k, a)]) -> [(k, a)]
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= (k -> Set a -> [(k, a)]) -> (k, Set a) -> [(k, a)]
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry (\k
k -> (a -> (k, a)) -> [a] -> [(k, a)]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (k
k,) ([a] -> [(k, a)]) -> (Set a -> [a]) -> Set a -> [(k, a)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Set a -> [a]
forall a. Set a -> [a]
Set.toDescList)

-- | /O(1)/. Convert the multimap into a regular map.
toMap :: SetMultimap k a -> Map k (Set a)
toMap :: SetMultimap k a -> Map k (Set a)
toMap (SetMultimap (Map k (Set a)
m, Int
_)) = Map k (Set a)
m

------------------------------------------------------------------------------

-- | /O(n)/, assuming the predicate function takes /O(1)/.
-- Retain all values that satisfy the predicate. A key is removed if
-- none of its values satisfies the predicate.
--
-- > Data.Multimap.Set.filter (> 'a') (fromList [(1,'a'),(1,'b'),(2,'a')]) === singleton 1 'b'
-- > Data.Multimap.Set.filter (< 'a') (fromList [(1,'a'),(1,'b'),(2,'a')]) === empty
filter :: (a -> Bool) -> SetMultimap k a -> SetMultimap k a
filter :: (a -> Bool) -> SetMultimap k a -> SetMultimap k a
filter = (k -> a -> Bool) -> SetMultimap k a -> SetMultimap k a
forall k a. (k -> a -> Bool) -> SetMultimap k a -> SetMultimap k a
filterWithKey ((k -> a -> Bool) -> SetMultimap k a -> SetMultimap k a)
-> ((a -> Bool) -> k -> a -> Bool)
-> (a -> Bool)
-> SetMultimap k a
-> SetMultimap k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Bool) -> k -> a -> Bool
forall a b. a -> b -> a
const

-- | /O(k)/, assuming the predicate function takes /O(1)/.
-- Retain all keys that satisfy the predicate.
filterKey :: (k -> Bool) -> SetMultimap k a -> SetMultimap k a
filterKey :: (k -> Bool) -> SetMultimap k a -> SetMultimap k a
filterKey k -> Bool
p (SetMultimap (Map k (Set a)
m, Int
_)) = Map k (Set a) -> SetMultimap k a
forall k a. Map k (Set a) -> SetMultimap k a
fromMap Map k (Set a)
m'
  where
    m' :: Map k (Set a)
m' = (k -> Set a -> Bool) -> Map k (Set a) -> Map k (Set a)
forall k a. (k -> a -> Bool) -> Map k a -> Map k a
Map.filterWithKey (Bool -> Set a -> Bool
forall a b. a -> b -> a
const (Bool -> Set a -> Bool) -> (k -> Bool) -> k -> Set a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. k -> Bool
p) Map k (Set a)
m

-- | /O(n)/, assuming the predicate function takes /O(1)/.
-- Retain all key\/value pairs that satisfy the predicate. A key is removed if
-- none of its values satisfies the predicate.
--
-- > filterWithKey (\k a -> even k && a > 'a') (fromList [(1,'a'),(1,'b'),(2,'a'),(2,'b')]) === singleton 2 'b'
filterWithKey :: (k -> a -> Bool) -> SetMultimap k a -> SetMultimap k a
filterWithKey :: (k -> a -> Bool) -> SetMultimap k a -> SetMultimap k a
filterWithKey k -> a -> Bool
p (SetMultimap (Map k (Set a)
m, Int
_)) = Map k (Set a) -> SetMultimap k a
forall k a. Map k (Set a) -> SetMultimap k a
fromMap Map k (Set a)
m'
  where
    m' :: Map k (Set a)
m' = (k -> Set a -> Set a) -> Map k (Set a) -> Map k (Set a)
forall k a b. (k -> a -> b) -> Map k a -> Map k b
Map.mapWithKey ((a -> Bool) -> Set a -> Set a
forall a. (a -> Bool) -> Set a -> Set a
Set.filter ((a -> Bool) -> Set a -> Set a)
-> (k -> a -> Bool) -> k -> Set a -> Set a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. k -> a -> Bool
p) Map k (Set a)
m

-- | Generalized 'filter'.
--
-- > let f a | a > 'b' = Just True
-- >         | a < 'b' = Just False
-- >         | a == 'b' = Nothing
-- >  in do
-- >    filterM f (fromList [(1,'a'),(1,'b'),(2,'a'),(2,'c')]) === Nothing
-- >    filterM f (fromList [(1,'a'),(1,'c'),(2,'a'),(2,'c')]) === Just (fromList [(1,'c'),(2,'c')])
filterM
  :: (Ord k, Ord a, Applicative t)
  => (a -> t Bool) -> SetMultimap k a -> t (SetMultimap k a)
filterM :: (a -> t Bool) -> SetMultimap k a -> t (SetMultimap k a)
filterM = (k -> a -> t Bool) -> SetMultimap k a -> t (SetMultimap k a)
forall k a (t :: * -> *).
(Ord k, Ord a, Applicative t) =>
(k -> a -> t Bool) -> SetMultimap k a -> t (SetMultimap k a)
filterWithKeyM ((k -> a -> t Bool) -> SetMultimap k a -> t (SetMultimap k a))
-> ((a -> t Bool) -> k -> a -> t Bool)
-> (a -> t Bool)
-> SetMultimap k a
-> t (SetMultimap k a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> t Bool) -> k -> a -> t Bool
forall a b. a -> b -> a
const

-- | Generalized 'filterWithKey'.
-- | Generalized 'filterWithKey'.
--
-- > let f k a | even k && a > 'b' = Just True
-- >           | odd k && a < 'b' = Just False
-- >           | otherwise = Nothing
-- >  in do
-- >    filterWithKeyM f (fromList [(1,'a'),(1,'c'),(2,'a'),(2,'c')]) === Nothing
-- >    filterWithKeyM f (fromList [(1,'a'),(3,'a'),(2,'c'),(4,'c')]) === Just (fromList [(2,'c'),(4,'c')])
filterWithKeyM
  :: (Ord k, Ord a, Applicative t)
  => (k -> a -> t Bool) -> SetMultimap k a -> t (SetMultimap k a)
filterWithKeyM :: (k -> a -> t Bool) -> SetMultimap k a -> t (SetMultimap k a)
filterWithKeyM k -> a -> t Bool
f = ([(k, a)] -> SetMultimap k a) -> t [(k, a)] -> t (SetMultimap k a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap [(k, a)] -> SetMultimap k a
forall k a. (Ord k, Ord a) => [(k, a)] -> SetMultimap k a
fromList (t [(k, a)] -> t (SetMultimap k a))
-> (SetMultimap k a -> t [(k, a)])
-> SetMultimap k a
-> t (SetMultimap k a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((k, a) -> t Bool) -> [(k, a)] -> t [(k, a)]
forall (m :: * -> *) a.
Applicative m =>
(a -> m Bool) -> [a] -> m [a]
List.filterM ((k -> a -> t Bool) -> (k, a) -> t Bool
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry k -> a -> t Bool
f) ([(k, a)] -> t [(k, a)])
-> (SetMultimap k a -> [(k, a)]) -> SetMultimap k a -> t [(k, a)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. SetMultimap k a -> [(k, a)]
forall k a. SetMultimap k a -> [(k, a)]
toList

-- | /O(n * log m)/, assuming the function @a -> 'Maybe' b@ takes /O(1)/.
-- Map values and collect the 'Just' results.
--
-- > mapMaybe (\a -> if a == "a" then Just "new a" else Nothing) (fromList [(1,"a"),(1,"b"),(2,"a"),(2,"c")])
-- >   === fromList [(1,"new a"),(2,"new a")]
mapMaybe :: Ord b => (a -> Maybe b) -> SetMultimap k a -> SetMultimap k b
mapMaybe :: (a -> Maybe b) -> SetMultimap k a -> SetMultimap k b
mapMaybe = (k -> a -> Maybe b) -> SetMultimap k a -> SetMultimap k b
forall b k a.
Ord b =>
(k -> a -> Maybe b) -> SetMultimap k a -> SetMultimap k b
mapMaybeWithKey ((k -> a -> Maybe b) -> SetMultimap k a -> SetMultimap k b)
-> ((a -> Maybe b) -> k -> a -> Maybe b)
-> (a -> Maybe b)
-> SetMultimap k a
-> SetMultimap k b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Maybe b) -> k -> a -> Maybe b
forall a b. a -> b -> a
const

-- | /O(n * log m)/, assuming the function @k -> a -> 'Maybe' b@ takes /O(1)/.
-- Map key\/value pairs and collect the 'Just' results.
--
-- > mapMaybeWithKey (\k a -> if k > 1 && a == "a" then Just "new a" else Nothing) (fromList [(1,"a"),(1,"b"),(2,"a"),(2,"c")])
-- >   === singleton 2 "new a"
mapMaybeWithKey :: Ord b => (k -> a -> Maybe b) -> SetMultimap k a -> SetMultimap k b
mapMaybeWithKey :: (k -> a -> Maybe b) -> SetMultimap k a -> SetMultimap k b
mapMaybeWithKey k -> a -> Maybe b
f (SetMultimap (Map k (Set a)
m, Int
_)) = Map k (Set b) -> SetMultimap k b
forall k a. Map k (Set a) -> SetMultimap k a
fromMap (Map k (Set b) -> SetMultimap k b)
-> Map k (Set b) -> SetMultimap k b
forall a b. (a -> b) -> a -> b
$
  (k -> Set a -> Set b) -> Map k (Set a) -> Map k (Set b)
forall k a b. (k -> a -> b) -> Map k a -> Map k b
Map.mapWithKey (\k
k -> Set (Maybe b) -> Set b
forall a. Ord a => Set (Maybe a) -> Set a
catMaybes (Set (Maybe b) -> Set b)
-> (Set a -> Set (Maybe b)) -> Set a -> Set b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Maybe b) -> Set a -> Set (Maybe b)
forall b a. Ord b => (a -> b) -> Set a -> Set b
Set.map (k -> a -> Maybe b
f k
k)) Map k (Set a)
m

-- | /O(n * log m)/, assuming the function @a -> 'Either' b c@ takes /O(1)/.
-- Map values and separate the 'Left' and 'Right' results.
--
-- > mapEither (\a -> if a < 'b' then Left a else Right a) (fromList [(1,'a'),(1,'c'),(2,'a'),(2,'c')])
-- >   === (fromList [(1,'a'),(2,'a')],fromList [(1,'c'),(2,'c')])
mapEither
  :: (Ord b, Ord c)
  => (a -> Either b c) -> SetMultimap k a -> (SetMultimap k b, SetMultimap k c)
mapEither :: (a -> Either b c)
-> SetMultimap k a -> (SetMultimap k b, SetMultimap k c)
mapEither = (k -> a -> Either b c)
-> SetMultimap k a -> (SetMultimap k b, SetMultimap k c)
forall b c k a.
(Ord b, Ord c) =>
(k -> a -> Either b c)
-> SetMultimap k a -> (SetMultimap k b, SetMultimap k c)
mapEitherWithKey ((k -> a -> Either b c)
 -> SetMultimap k a -> (SetMultimap k b, SetMultimap k c))
-> ((a -> Either b c) -> k -> a -> Either b c)
-> (a -> Either b c)
-> SetMultimap k a
-> (SetMultimap k b, SetMultimap k c)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Either b c) -> k -> a -> Either b c
forall a b. a -> b -> a
const

-- | /O(n * log m)/, assuming the function @k -> a -> 'Either' b c@ takes /O(1)/.
-- Map key\/value pairs and separate the 'Left' and 'Right' results.
--
-- > mapEitherWithKey (\k a -> if even k && a < 'b' then Left a else Right a) (fromList [(1,'a'),(1,'c'),(2,'a'),(2,'c')])
-- >   === (fromList [(2,'a')],fromList [(1,'a'),(1,'c'),(2,'c')])
mapEitherWithKey
  :: (Ord b, Ord c)
  => (k -> a -> Either b c) -> SetMultimap k a -> (SetMultimap k b, SetMultimap k c)
mapEitherWithKey :: (k -> a -> Either b c)
-> SetMultimap k a -> (SetMultimap k b, SetMultimap k c)
mapEitherWithKey k -> a -> Either b c
f (SetMultimap (Map k (Set a)
m, Int
_)) =
  (Map k (Set b) -> SetMultimap k b
forall k a. Map k (Set a) -> SetMultimap k a
fromMap (Map k (Set b) -> SetMultimap k b)
-> (Map k (Set b, Set c) -> Map k (Set b))
-> Map k (Set b, Set c)
-> SetMultimap k b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k -> (Set b, Set c) -> Set b)
-> Map k (Set b, Set c) -> Map k (Set b)
forall k a b. (k -> a -> b) -> Map k a -> Map k b
Map.mapWithKey (((Set b, Set c) -> Set b) -> k -> (Set b, Set c) -> Set b
forall a b. a -> b -> a
const (Set b, Set c) -> Set b
forall a b. (a, b) -> a
fst) (Map k (Set b, Set c) -> SetMultimap k b)
-> (Map k (Set b, Set c) -> SetMultimap k c)
-> Map k (Set b, Set c)
-> (SetMultimap k b, SetMultimap k c)
forall (a :: * -> * -> *) b c c'.
Arrow a =>
a b c -> a b c' -> a b (c, c')
&&& Map k (Set c) -> SetMultimap k c
forall k a. Map k (Set a) -> SetMultimap k a
fromMap (Map k (Set c) -> SetMultimap k c)
-> (Map k (Set b, Set c) -> Map k (Set c))
-> Map k (Set b, Set c)
-> SetMultimap k c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k -> (Set b, Set c) -> Set c)
-> Map k (Set b, Set c) -> Map k (Set c)
forall k a b. (k -> a -> b) -> Map k a -> Map k b
Map.mapWithKey (((Set b, Set c) -> Set c) -> k -> (Set b, Set c) -> Set c
forall a b. a -> b -> a
const (Set b, Set c) -> Set c
forall a b. (a, b) -> b
snd))
      (Map k (Set b, Set c) -> (SetMultimap k b, SetMultimap k c))
-> Map k (Set b, Set c) -> (SetMultimap k b, SetMultimap k c)
forall a b. (a -> b) -> a -> b
$ (k -> Set a -> (Set b, Set c))
-> Map k (Set a) -> Map k (Set b, Set c)
forall k a b. (k -> a -> b) -> Map k a -> Map k b
Map.mapWithKey k -> Set a -> (Set b, Set c)
g Map k (Set a)
m
  where
    g :: k -> Set a -> (Set b, Set c)
g k
k = Set (Either b c) -> (Set b, Set c)
forall a b. (Ord a, Ord b) => Set (Either a b) -> (Set a, Set b)
partitionEithers (Set (Either b c) -> (Set b, Set c))
-> (Set a -> Set (Either b c)) -> Set a -> (Set b, Set c)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Either b c) -> Set a -> Set (Either b c)
forall b a. Ord b => (a -> b) -> Set a -> Set b
Set.map (k -> a -> Either b c
f k
k)

------------------------------------------------------------------------------

-- | /O(log n)/. Return the smallest key and the associated values. Returns 'Nothing'
-- if the map is empty.
--
-- > lookupMin (fromList [(1,'a'),(1,'c'),(2,'c')]) === Just (1, Set.fromList "ac")
-- > lookupMin (empty :: SetMultimap Int Char) === Nothing
lookupMin :: SetMultimap k a -> Maybe (k, Set a)
lookupMin :: SetMultimap k a -> Maybe (k, Set a)
lookupMin (SetMultimap (Map k (Set a)
m, Int
_)) = Map k (Set a) -> Maybe (k, Set a)
forall k a. Map k a -> Maybe (k, a)
Map.lookupMin Map k (Set a)
m

-- | /O(log n)/. Return the largest key and the associated values. Returns 'Nothing'
-- if the map is empty.
--
-- > lookupMax (fromList [(1,'a'),(1,'c'),(2,'c')]) === Just (2, Set.fromList "c")
-- > lookupMax (empty :: SetMultimap Int Char) === Nothing
lookupMax :: SetMultimap k a -> Maybe (k, Set a)
lookupMax :: SetMultimap k a -> Maybe (k, Set a)
lookupMax (SetMultimap (Map k (Set a)
m, Int
_)) = Map k (Set a) -> Maybe (k, Set a)
forall k a. Map k a -> Maybe (k, a)
Map.lookupMax Map k (Set a)
m

-- | /O(log n)/. Return the largest key smaller than the given one, and the associated
-- values, if exist.
--
-- > lookupLT 1 (fromList [(1,'a'),(3,'b'),(3,'c'),(5,'c')]) === Nothing
-- > lookupLT 4 (fromList [(1,'a'),(3,'b'),(3,'c'),(5,'c')]) === Just (3, Set.fromList "bc")
lookupLT :: Ord k => k -> SetMultimap k a -> Maybe (k, Set a)
lookupLT :: k -> SetMultimap k a -> Maybe (k, Set a)
lookupLT k
k (SetMultimap (Map k (Set a)
m, Int
_)) = k -> Map k (Set a) -> Maybe (k, Set a)
forall k v. Ord k => k -> Map k v -> Maybe (k, v)
Map.lookupLT k
k Map k (Set a)
m

-- | /O(log n)/. Return the smallest key larger than the given one, and the associated
-- values, if exist.
--
-- > lookupGT 5 (fromList [(1,'a'),(3,'b'),(3,'c'),(5,'c')]) === Nothing
-- > lookupGT 2 (fromList [(1,'a'),(3,'b'),(3,'c'),(5,'c')]) === Just (3, Set.fromList "bc")
lookupGT :: Ord k => k -> SetMultimap k a -> Maybe (k, Set a)
lookupGT :: k -> SetMultimap k a -> Maybe (k, Set a)
lookupGT k
k (SetMultimap (Map k (Set a)
m, Int
_)) = k -> Map k (Set a) -> Maybe (k, Set a)
forall k v. Ord k => k -> Map k v -> Maybe (k, v)
Map.lookupGT k
k Map k (Set a)
m

-- | /O(log n)/. Return the largest key smaller than or equal to the given one, and the associated
-- values, if exist.
--
-- > lookupLE 0 (fromList [(1,'a'),(3,'b'),(3,'c'),(5,'c')]) === Nothing
-- > lookupLE 1 (fromList [(1,'a'),(3,'b'),(3,'c'),(5,'c')]) === Just (1, Set.fromList "a")
-- > lookupLE 4 (fromList [(1,'a'),(3,'b'),(3,'c'),(5,'c')]) === Just (3, Set.fromList "bc")
lookupLE :: Ord k => k -> SetMultimap k a -> Maybe (k, Set a)
lookupLE :: k -> SetMultimap k a -> Maybe (k, Set a)
lookupLE k
k (SetMultimap (Map k (Set a)
m, Int
_)) = k -> Map k (Set a) -> Maybe (k, Set a)
forall k v. Ord k => k -> Map k v -> Maybe (k, v)
Map.lookupLE k
k Map k (Set a)
m

-- | /O(log n)/. Return the smallest key larger than or equal to the given one, and the associated
-- values, if exist.
--
-- > lookupGE 6 (fromList [(1,'a'),(3,'b'),(3,'c'),(5,'c')]) === Nothing
-- > lookupGE 5 (fromList [(1,'a'),(3,'b'),(3,'c'),(5,'c')]) === Just (5, Set.fromList "c")
-- > lookupGE 2 (fromList [(1,'a'),(3,'b'),(3,'c'),(5,'c')]) === Just (3, Set.fromList "bc")
lookupGE :: Ord k => k -> SetMultimap k a -> Maybe (k, Set a)
lookupGE :: k -> SetMultimap k a -> Maybe (k, Set a)
lookupGE k
k (SetMultimap (Map k (Set a)
m, Int
_)) = k -> Map k (Set a) -> Maybe (k, Set a)
forall k v. Ord k => k -> Map k v -> Maybe (k, v)
Map.lookupGE k
k Map k (Set a)
m

------------------------------------------------------------------------------
-- * Non exported functions
------------------------------------------------------------------------------

catMaybes :: Ord a => Set (Maybe a) -> Set a
catMaybes :: Set (Maybe a) -> Set a
catMaybes = (Set a -> Maybe a -> Set a) -> Set a -> Set (Maybe a) -> Set a
forall a b. (a -> b -> a) -> a -> Set b -> a
Set.foldl' (\Set a
s -> Set a -> (a -> Set a) -> Maybe a -> Set a
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Set a
s (a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
`Set.insert` Set a
s)) Set a
forall a. Set a
Set.empty

partitionEithers :: (Ord a, Ord b) => Set (Either a b) -> (Set a, Set b)
partitionEithers :: Set (Either a b) -> (Set a, Set b)
partitionEithers = (Either a b -> (Set a, Set b) -> (Set a, Set b))
-> (Set a, Set b) -> Set (Either a b) -> (Set a, Set b)
forall a b. (a -> b -> b) -> b -> Set a -> b
Set.foldr' ((a -> (Set a, Set b) -> (Set a, Set b))
-> (b -> (Set a, Set b) -> (Set a, Set b))
-> Either a b
-> (Set a, Set b)
-> (Set a, Set b)
forall a c b. (a -> c) -> (b -> c) -> Either a b -> c
either a -> (Set a, Set b) -> (Set a, Set b)
forall a b. Ord a => a -> (Set a, b) -> (Set a, b)
left b -> (Set a, Set b) -> (Set a, Set b)
forall a a. Ord a => a -> (a, Set a) -> (a, Set a)
right) (Set a
forall a. Set a
Set.empty, Set b
forall a. Set a
Set.empty)
  where
    left :: a -> (Set a, b) -> (Set a, b)
left a
a (Set a
l,b
r) = (a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
Set.insert a
a Set a
l, b
r)
    right :: a -> (a, Set a) -> (a, Set a)
right a
b (a
l,Set a
r) = (a
l, a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
Set.insert a
b Set a
r)

fromMap' :: Ord k => k -> Map k (Set a) -> SetMultimap k a
fromMap' :: k -> Map k (Set a) -> SetMultimap k a
fromMap' k
k Map k (Set a)
m = (Map k (Set a), Int) -> SetMultimap k a
forall k a. (Map k (Set a), Int) -> SetMultimap k a
SetMultimap (Map k (Set a)
m', Map k Int -> Int
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
sum ((Set a -> Int) -> Map k (Set a) -> Map k Int
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Set a -> Int
forall a. Set a -> Int
Set.size Map k (Set a)
m'))
  where
    m' :: Map k (Set a)
m' = 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)
m of
      Just Set a
as | Set a -> Bool
forall a. Set a -> Bool
Set.null Set a
as -> 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)
m
      Maybe (Set a)
_ -> Map k (Set a)
m