{-# LANGUAGE CPP #-}
{-# LANGUAGE DeriveDataTypeable #-}
{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE TypeFamilies #-}

-- | This internal module implements functionality shared by all multimaps.
module Data.Multimap.Generic (
  Multimap(..), Group,
  null, size, distinctSize,
  empty, singleton,
#if __GLASGOW_HASKELL__ >= 708
  fromList, inverse,
#endif
  fromListWith, fromGroupList, fromMap,
  member, notMember, count,
  find, (!),
  prepend, prependMany, append, appendMany,
  deleteMany,
  inverseWith,
  filter, filterGroups,
  mapGroups,
  toList, toGroupList, toMap,
  keys, keysSet, keysMultiset,
  maxViewWith, minViewWith,
  modifyMany, modifyManyF
) where

import Data.Multimap.Collection (Collection)
import qualified Data.Multimap.Collection as Col
import Data.Multiset (Multiset)
import qualified Data.Multiset as Mset

import Prelude hiding (filter, null)
import qualified Prelude as Prelude
import Data.Binary (Binary(..))
import Data.Data (Data, Typeable)
import Data.Foldable (foldl')
import Data.Map.Strict (Map)
import qualified Data.Map.Strict as Map
import Data.Maybe (fromMaybe)
#if !MIN_VERSION_base(4, 11, 0)
import Data.Semigroup (Semigroup, (<>))
#endif
import Data.Set (Set)
import Data.Tuple (swap)
import qualified GHC.Exts

-- | A map where the same key can be present multiple times.
newtype Multimap c k v = Multimap
  { Multimap c k v -> Map k (c v)
_toMap :: Map k (c v)
  } deriving (
    Multimap c k v -> Multimap c k v -> Bool
(Multimap c k v -> Multimap c k v -> Bool)
-> (Multimap c k v -> Multimap c k v -> Bool)
-> Eq (Multimap c k v)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall (c :: * -> *) k v.
(Eq k, Eq (c v)) =>
Multimap c k v -> Multimap c k v -> Bool
/= :: Multimap c k v -> Multimap c k v -> Bool
$c/= :: forall (c :: * -> *) k v.
(Eq k, Eq (c v)) =>
Multimap c k v -> Multimap c k v -> Bool
== :: Multimap c k v -> Multimap c k v -> Bool
$c== :: forall (c :: * -> *) k v.
(Eq k, Eq (c v)) =>
Multimap c k v -> Multimap c k v -> Bool
Eq, Eq (Multimap c k v)
Eq (Multimap c k v)
-> (Multimap c k v -> Multimap c k v -> Ordering)
-> (Multimap c k v -> Multimap c k v -> Bool)
-> (Multimap c k v -> Multimap c k v -> Bool)
-> (Multimap c k v -> Multimap c k v -> Bool)
-> (Multimap c k v -> Multimap c k v -> Bool)
-> (Multimap c k v -> Multimap c k v -> Multimap c k v)
-> (Multimap c k v -> Multimap c k v -> Multimap c k v)
-> Ord (Multimap c k v)
Multimap c k v -> Multimap c k v -> Bool
Multimap c k v -> Multimap c k v -> Ordering
Multimap c k v -> Multimap c k v -> Multimap c k v
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 (c :: * -> *) k v. (Ord k, Ord (c v)) => Eq (Multimap c k v)
forall (c :: * -> *) k v.
(Ord k, Ord (c v)) =>
Multimap c k v -> Multimap c k v -> Bool
forall (c :: * -> *) k v.
(Ord k, Ord (c v)) =>
Multimap c k v -> Multimap c k v -> Ordering
forall (c :: * -> *) k v.
(Ord k, Ord (c v)) =>
Multimap c k v -> Multimap c k v -> Multimap c k v
min :: Multimap c k v -> Multimap c k v -> Multimap c k v
$cmin :: forall (c :: * -> *) k v.
(Ord k, Ord (c v)) =>
Multimap c k v -> Multimap c k v -> Multimap c k v
max :: Multimap c k v -> Multimap c k v -> Multimap c k v
$cmax :: forall (c :: * -> *) k v.
(Ord k, Ord (c v)) =>
Multimap c k v -> Multimap c k v -> Multimap c k v
>= :: Multimap c k v -> Multimap c k v -> Bool
$c>= :: forall (c :: * -> *) k v.
(Ord k, Ord (c v)) =>
Multimap c k v -> Multimap c k v -> Bool
> :: Multimap c k v -> Multimap c k v -> Bool
$c> :: forall (c :: * -> *) k v.
(Ord k, Ord (c v)) =>
Multimap c k v -> Multimap c k v -> Bool
<= :: Multimap c k v -> Multimap c k v -> Bool
$c<= :: forall (c :: * -> *) k v.
(Ord k, Ord (c v)) =>
Multimap c k v -> Multimap c k v -> Bool
< :: Multimap c k v -> Multimap c k v -> Bool
$c< :: forall (c :: * -> *) k v.
(Ord k, Ord (c v)) =>
Multimap c k v -> Multimap c k v -> Bool
compare :: Multimap c k v -> Multimap c k v -> Ordering
$ccompare :: forall (c :: * -> *) k v.
(Ord k, Ord (c v)) =>
Multimap c k v -> Multimap c k v -> Ordering
$cp1Ord :: forall (c :: * -> *) k v. (Ord k, Ord (c v)) => Eq (Multimap c k v)
Ord, ReadPrec [Multimap c k v]
ReadPrec (Multimap c k v)
Int -> ReadS (Multimap c k v)
ReadS [Multimap c k v]
(Int -> ReadS (Multimap c k v))
-> ReadS [Multimap c k v]
-> ReadPrec (Multimap c k v)
-> ReadPrec [Multimap c k v]
-> Read (Multimap c k v)
forall a.
(Int -> ReadS a)
-> ReadS [a] -> ReadPrec a -> ReadPrec [a] -> Read a
forall (c :: * -> *) k v.
(Ord k, Read k, Read (c v)) =>
ReadPrec [Multimap c k v]
forall (c :: * -> *) k v.
(Ord k, Read k, Read (c v)) =>
ReadPrec (Multimap c k v)
forall (c :: * -> *) k v.
(Ord k, Read k, Read (c v)) =>
Int -> ReadS (Multimap c k v)
forall (c :: * -> *) k v.
(Ord k, Read k, Read (c v)) =>
ReadS [Multimap c k v]
readListPrec :: ReadPrec [Multimap c k v]
$creadListPrec :: forall (c :: * -> *) k v.
(Ord k, Read k, Read (c v)) =>
ReadPrec [Multimap c k v]
readPrec :: ReadPrec (Multimap c k v)
$creadPrec :: forall (c :: * -> *) k v.
(Ord k, Read k, Read (c v)) =>
ReadPrec (Multimap c k v)
readList :: ReadS [Multimap c k v]
$creadList :: forall (c :: * -> *) k v.
(Ord k, Read k, Read (c v)) =>
ReadS [Multimap c k v]
readsPrec :: Int -> ReadS (Multimap c k v)
$creadsPrec :: forall (c :: * -> *) k v.
(Ord k, Read k, Read (c v)) =>
Int -> ReadS (Multimap c k v)
Read, Int -> Multimap c k v -> ShowS
[Multimap c k v] -> ShowS
Multimap c k v -> String
(Int -> Multimap c k v -> ShowS)
-> (Multimap c k v -> String)
-> ([Multimap c k v] -> ShowS)
-> Show (Multimap c k v)
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
forall (c :: * -> *) k v.
(Show k, Show (c v)) =>
Int -> Multimap c k v -> ShowS
forall (c :: * -> *) k v.
(Show k, Show (c v)) =>
[Multimap c k v] -> ShowS
forall (c :: * -> *) k v.
(Show k, Show (c v)) =>
Multimap c k v -> String
showList :: [Multimap c k v] -> ShowS
$cshowList :: forall (c :: * -> *) k v.
(Show k, Show (c v)) =>
[Multimap c k v] -> ShowS
show :: Multimap c k v -> String
$cshow :: forall (c :: * -> *) k v.
(Show k, Show (c v)) =>
Multimap c k v -> String
showsPrec :: Int -> Multimap c k v -> ShowS
$cshowsPrec :: forall (c :: * -> *) k v.
(Show k, Show (c v)) =>
Int -> Multimap c k v -> ShowS
Show, a -> Multimap c k b -> Multimap c k a
(a -> b) -> Multimap c k a -> Multimap c k b
(forall a b. (a -> b) -> Multimap c k a -> Multimap c k b)
-> (forall a b. a -> Multimap c k b -> Multimap c k a)
-> Functor (Multimap c k)
forall a b. a -> Multimap c k b -> Multimap c k a
forall a b. (a -> b) -> Multimap c k a -> Multimap c k b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
forall (c :: * -> *) k a b.
Functor c =>
a -> Multimap c k b -> Multimap c k a
forall (c :: * -> *) k a b.
Functor c =>
(a -> b) -> Multimap c k a -> Multimap c k b
<$ :: a -> Multimap c k b -> Multimap c k a
$c<$ :: forall (c :: * -> *) k a b.
Functor c =>
a -> Multimap c k b -> Multimap c k a
fmap :: (a -> b) -> Multimap c k a -> Multimap c k b
$cfmap :: forall (c :: * -> *) k a b.
Functor c =>
(a -> b) -> Multimap c k a -> Multimap c k b
Functor,
    {-| @since 0.2.1.1 -} Data, {-| @since 0.2.1.1 -} Typeable
  )

-- | A group of values.
type Group k cv = (k, cv)

instance (Ord k, Semigroup (c v)) => Semigroup (Multimap c k v) where
  Multimap Map k (c v)
m1 <> :: Multimap c k v -> Multimap c k v -> Multimap c k v
<> Multimap Map k (c v)
m2 = Map k (c v) -> Multimap c k v
forall (c :: * -> *) k v. Map k (c v) -> Multimap c k v
Multimap (Map k (c v) -> Multimap c k v) -> Map k (c v) -> Multimap c k v
forall a b. (a -> b) -> a -> b
$ (c v -> c v -> c v) -> Map k (c v) -> Map k (c v) -> Map k (c v)
forall k a. Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k a
Map.unionWith c v -> c v -> c v
forall a. Semigroup a => a -> a -> a
(<>) Map k (c v)
m1 Map k (c v)
m2

instance (Ord k, Monoid (c v)) => Monoid (Multimap c k v) where
  mempty :: Multimap c k v
mempty = Multimap c k v
forall (c :: * -> *) k v. Multimap c k v
empty

instance Foldable c => Foldable (Multimap c k) where
  foldr :: (a -> b -> b) -> b -> Multimap c k a -> b
foldr a -> b -> b
f b
r0 (Multimap Map k (c a)
m) = (c a -> b -> b) -> b -> Map k (c a) -> b
forall a b k. (a -> b -> b) -> b -> Map k a -> b
Map.foldr (\c a
c b
r -> (a -> b -> b) -> b -> c a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> b -> b
f b
r c a
c) b
r0 Map k (c a)
m

instance Traversable c => Traversable (Multimap c k) where
  sequenceA :: Multimap c k (f a) -> f (Multimap c k a)
sequenceA (Multimap Map k (c (f a))
m) = Map k (c a) -> Multimap c k a
forall (c :: * -> *) k v. Map k (c v) -> Multimap c k v
Multimap (Map k (c a) -> Multimap c k a)
-> f (Map k (c a)) -> f (Multimap c k a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Map k (f (c a)) -> f (Map k (c a))
forall (t :: * -> *) (f :: * -> *) a.
(Traversable t, Applicative f) =>
t (f a) -> f (t a)
sequenceA ((c (f a) -> f (c a)) -> Map k (c (f a)) -> Map k (f (c a))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap c (f a) -> f (c a)
forall (t :: * -> *) (f :: * -> *) a.
(Traversable t, Applicative f) =>
t (f a) -> f (t a)
sequenceA Map k (c (f a))
m)

-- | @since 0.2.1.0
instance (Binary k, Binary (c v)) => Binary (Multimap c k v) where
  put :: Multimap c k v -> Put
put (Multimap Map k (c v)
m) = Map k (c v) -> Put
forall t. Binary t => t -> Put
put Map k (c v)
m
  get :: Get (Multimap c k v)
get = Map k (c v) -> Multimap c k v
forall (c :: * -> *) k v. Map k (c v) -> Multimap c k v
Multimap (Map k (c v) -> Multimap c k v)
-> Get (Map k (c v)) -> Get (Multimap c k v)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Get (Map k (c v))
forall t. Binary t => Get t
get

#if __GLASGOW_HASKELL__ >= 708
instance (Collection c, GHC.Exts.IsList (c v), GHC.Exts.Item (c v) ~ v, Ord k) => GHC.Exts.IsList (Multimap c k v) where
  type Item (Multimap c k v) = (k, v)
  fromList :: [Item (Multimap c k v)] -> Multimap c k v
fromList = [Item (Multimap c k v)] -> Multimap c k v
forall (c :: * -> *) v k.
(Collection c, IsList (c v), Item (c v) ~ v, Ord k) =>
[(k, v)] -> Multimap c k v
fromList
  toList :: Multimap c k v -> [Item (Multimap c k v)]
toList = Multimap c k v -> [Item (Multimap c k v)]
forall (c :: * -> *) k v.
Collection c =>
Multimap c k v -> [(k, v)]
toList

-- | /O(n * log n)/ Builds a multimap from a list of key, value tuples. The values are in the same
-- order as in the original list.
fromList
  :: (Collection c, GHC.Exts.IsList (c v), GHC.Exts.Item (c v) ~ v, Ord k)
  => [(k, v)] -> Multimap c k v
fromList :: [(k, v)] -> Multimap c k v
fromList = ([v] -> c v) -> [(k, v)] -> Multimap c k v
forall k v (c :: * -> *).
Ord k =>
([v] -> c v) -> [(k, v)] -> Multimap c k v
fromListWith [v] -> c v
forall l. IsList l => [Item l] -> l
GHC.Exts.fromList

-- | /O(n)/ Inverts keys and values inside a multimap.
inverse
  :: (Collection c, GHC.Exts.IsList (c k), GHC.Exts.Item (c k) ~ k, Ord k, Ord v)
  => Multimap c k v -> Multimap c v k
inverse :: Multimap c k v -> Multimap c v k
inverse = ([k] -> c k) -> Multimap c k v -> Multimap c v k
forall (c1 :: * -> *) k v (c2 :: * -> *).
(Collection c1, Ord k, Ord v) =>
([k] -> c2 k) -> Multimap c1 k v -> Multimap c2 v k
inverseWith [k] -> c k
forall l. IsList l => [Item l] -> l
GHC.Exts.fromList
#endif

-- | /O(1)/ Checks whether the multimap is empty.
null :: Multimap c k v -> Bool
null :: Multimap c k v -> Bool
null = Map k (c v) -> Bool
forall k a. Map k a -> Bool
Map.null (Map k (c v) -> Bool)
-> (Multimap c k v -> Map k (c v)) -> Multimap c k v -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Multimap c k v -> Map k (c v)
forall (c :: * -> *) k v. Multimap c k v -> Map k (c v)
_toMap

-- | /O(m * C)/ Returns the size of the multimap.
size :: Collection c => Multimap c k v -> Int
size :: Multimap c k v -> Int
size (Multimap Map k (c v)
m) = (Int -> c v -> Int) -> Int -> Map k (c v) -> Int
forall a b k. (a -> b -> a) -> a -> Map k b -> a
Map.foldl' (\Int
n c v
c -> Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
+ c v -> Int
forall (c :: * -> *) v. Collection c => c v -> Int
Col.size c v
c) Int
0 Map k (c v)
m

-- | /O(1)/ Returns the number of distinct keys in the multimap.
distinctSize :: Multimap c k v -> Int
distinctSize :: Multimap c k v -> Int
distinctSize = Map k (c v) -> Int
forall k a. Map k a -> Int
Map.size (Map k (c v) -> Int)
-> (Multimap c k v -> Map k (c v)) -> Multimap c k v -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Multimap c k v -> Map k (c v)
forall (c :: * -> *) k v. Multimap c k v -> Map k (c v)
_toMap

-- | /O(1)/ Creates an empty multimap.
empty :: Multimap c k v
empty :: Multimap c k v
empty = Map k (c v) -> Multimap c k v
forall (c :: * -> *) k v. Map k (c v) -> Multimap c k v
Multimap Map k (c v)
forall k a. Map k a
Map.empty

-- | /O(1)/ Creates a multimap with a single entry.
singleton :: Collection c => k -> v -> Multimap c k v
singleton :: k -> v -> Multimap c k v
singleton k
k v
v = Map k (c v) -> Multimap c k v
forall (c :: * -> *) k v. Map k (c v) -> Multimap c k v
Multimap (Map k (c v) -> Multimap c k v) -> Map k (c v) -> Multimap c k v
forall a b. (a -> b) -> a -> b
$ k -> c v -> Map k (c v)
forall k a. k -> a -> Map k a
Map.singleton k
k (v -> c v
forall (c :: * -> *) v. Collection c => v -> c v
Col.singleton v
v)

-- | /O(m)/ Builds a multimap from already grouped collections.
fromGroupList :: (Collection c, Monoid (c v), Ord k) => [Group k (c v)] -> Multimap c k v
fromGroupList :: [Group k (c v)] -> Multimap c k v
fromGroupList = Map k (c v) -> Multimap c k v
forall (c :: * -> *) k v.
Collection c =>
Map k (c v) -> Multimap c k v
fromMap (Map k (c v) -> Multimap c k v)
-> ([Group k (c v)] -> Map k (c v))
-> [Group k (c v)]
-> Multimap c k v
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (c v -> c v -> c v) -> [Group k (c v)] -> Map k (c v)
forall k a. Ord k => (a -> a -> a) -> [(k, a)] -> Map k a
Map.fromListWith c v -> c v -> c v
forall a. Semigroup a => a -> a -> a
(<>)

-- | /O(n * log n)/ Transforms a list of entries into a multimap, combining the values for each key
-- into the chosen collection. The values are in the same order as in the original list.
fromListWith :: Ord k => ([v] -> c v) -> [(k, v)] -> Multimap c k v
fromListWith :: ([v] -> c v) -> [(k, v)] -> Multimap c k v
fromListWith [v] -> c v
f [(k, v)]
ts = Map k (c v) -> Multimap c k v
forall (c :: * -> *) k v. Map k (c v) -> Multimap c k v
Multimap (Map k (c v) -> Multimap c k v) -> Map k (c v) -> Multimap c k v
forall a b. (a -> b) -> a -> b
$ ([v] -> c v) -> Map k [v] -> Map k (c v)
forall a b k. (a -> b) -> Map k a -> Map k b
Map.map ([v] -> c v
f ([v] -> c v) -> ([v] -> [v]) -> [v] -> c v
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [v] -> [v]
forall a. [a] -> [a]
reverse) (Map k [v] -> Map k (c v)) -> Map k [v] -> Map k (c v)
forall a b. (a -> b) -> a -> b
$ Map k [v]
m where
  Multimap Map k [v]
m = (Multimap [] k v -> (k, v) -> Multimap [] k v)
-> Multimap [] k v -> [(k, v)] -> Multimap [] k v
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\Multimap [] k v
r (k
k, v
v) -> ([v] -> [v]) -> k -> Multimap [] k v -> Multimap [] k v
forall (c :: * -> *) v k.
(Collection c, Monoid (c v), Ord k) =>
(c v -> c v) -> k -> Multimap c k v -> Multimap c k v
modifyMany (v
vv -> [v] -> [v]
forall a. a -> [a] -> [a]
:) k
k Multimap [] k v
r) Multimap [] k v
forall (c :: * -> *) k v. Multimap c k v
empty [(k, v)]
ts

-- | /O(m * C)/ Transforms a map of collections into a multimap.
fromMap :: Collection c => Map k (c v) -> Multimap c k v
fromMap :: Map k (c v) -> Multimap c k v
fromMap = Map k (c v) -> Multimap c k v
forall (c :: * -> *) k v. Map k (c v) -> Multimap c k v
Multimap (Map k (c v) -> Multimap c k v)
-> (Map k (c v) -> Map k (c v)) -> Map k (c v) -> Multimap c k v
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (c v -> Bool) -> Map k (c v) -> Map k (c v)
forall a k. (a -> Bool) -> Map k a -> Map k a
Map.filter (Bool -> Bool
not (Bool -> Bool) -> (c v -> Bool) -> c v -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. c v -> Bool
forall (c :: * -> *) v. Collection c => c v -> Bool
Col.null)

-- | /O(log m)/ Returns the collection of values associated with a key.
find :: (Monoid (c v), Ord k) => k -> Multimap c k v -> c v
find :: k -> Multimap c k v -> c v
find k
k (Multimap Map k (c v)
m) = c v -> k -> Map k (c v) -> c v
forall k a. Ord k => a -> k -> Map k a -> a
Map.findWithDefault c v
forall a. Monoid a => a
mempty k
k Map k (c v)
m

-- | /O(log m)/ Infix version of 'find'.
(!) :: (Monoid (c v), Ord k) => Multimap c k v -> k -> c v
(!) = (k -> Multimap c k v -> c v) -> Multimap c k v -> k -> c v
forall a b c. (a -> b -> c) -> b -> a -> c
flip k -> Multimap c k v -> c v
forall (c :: * -> *) v k.
(Monoid (c v), Ord k) =>
k -> Multimap c k v -> c v
find

-- | /O(log m * C)/ Returns the number of times a key is present in a multimap. The complexity of
-- the operation depends on the complexity of the underlying collection's 'Data.Collection.size'
-- operation.
count :: (Collection c, Ord k) => k -> Multimap c k v -> Int
count :: k -> Multimap c k v -> Int
count k
k (Multimap Map k (c v)
m) = Int -> (c v -> Int) -> Maybe (c v) -> Int
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Int
0 c v -> Int
forall (c :: * -> *) v. Collection c => c v -> Int
Col.size (Maybe (c v) -> Int) -> Maybe (c v) -> Int
forall a b. (a -> b) -> a -> b
$ k -> Map k (c v) -> Maybe (c v)
forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup k
k Map k (c v)
m

-- | /O(log m)/ Checks whether a key is present at least once in a multimap.
member :: Ord k => k -> Multimap c k v -> Bool
member :: k -> Multimap c k v -> Bool
member k
k = k -> Map k (c v) -> Bool
forall k a. Ord k => k -> Map k a -> Bool
Map.member k
k (Map k (c v) -> Bool)
-> (Multimap c k v -> Map k (c v)) -> Multimap c k v -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Multimap c k v -> Map k (c v)
forall (c :: * -> *) k v. Multimap c k v -> Map k (c v)
_toMap

-- | /O(log m)/ Checks whether a key is absent from a multimap.
notMember :: Ord k => k -> Multimap c k v -> Bool
notMember :: k -> Multimap c k v -> Bool
notMember k
k = k -> Map k (c v) -> Bool
forall k a. Ord k => k -> Map k a -> Bool
Map.notMember k
k (Map k (c v) -> Bool)
-> (Multimap c k v -> Map k (c v)) -> Multimap c k v -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Multimap c k v -> Map k (c v)
forall (c :: * -> *) k v. Multimap c k v -> Map k (c v)
_toMap

-- | Modifies a key's collection using an arbitrary function. More specifically, this function lifts
-- an operation over a collection of values into a multimap operation.
--
-- Sample use to filter even values from a 'Data.Multimap.SetMultimap':
--
-- @
--    let ms = fromList [(\'a\', 1), (\'a\', 2)] :: SetMultimap Char Int
--    modifyMany (Set.filter even) \'a\' ms == fromList [(\'a\', 1)]
-- @
modifyMany
  :: (Collection c, Monoid (c v), Ord k)
  => (c v -> c v)
  -> k
  -> Multimap c k v
  -> Multimap c k v
modifyMany :: (c v -> c v) -> k -> Multimap c k v -> Multimap c k v
modifyMany c v -> c v
f k
k (Multimap Map k (c v)
m) = Map k (c v) -> Multimap c k v
forall (c :: * -> *) k v. Map k (c v) -> Multimap c k v
Multimap (Map k (c v) -> Multimap c k v) -> Map k (c v) -> Multimap c k v
forall a b. (a -> b) -> a -> b
$ (Maybe (c v) -> Maybe (c v)) -> k -> Map k (c v) -> Map k (c v)
forall k a.
Ord k =>
(Maybe a -> Maybe a) -> k -> Map k a -> Map k a
Map.alter (c v -> Maybe (c v)
forall (c :: * -> *) v. Collection c => c v -> Maybe (c v)
wrap (c v -> Maybe (c v))
-> (Maybe (c v) -> c v) -> Maybe (c v) -> Maybe (c v)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. c v -> c v
f (c v -> c v) -> (Maybe (c v) -> c v) -> Maybe (c v) -> c v
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Maybe (c v) -> c v
unwrap) k
k Map k (c v)
m where
  unwrap :: Maybe (c v) -> c v
unwrap = c v -> Maybe (c v) -> c v
forall a. a -> Maybe a -> a
fromMaybe c v
forall a. Monoid a => a
mempty
  wrap :: c v -> Maybe (c v)
wrap c v
c = if c v -> Bool
forall (c :: * -> *) v. Collection c => c v -> Bool
Col.null c v
c then Maybe (c v)
forall a. Maybe a
Nothing else c v -> Maybe (c v)
forall a. a -> Maybe a
Just c v
c

-- | Modifies a key's collection using an arbitrary function. This is the applicative version of
-- 'modifyMany'.
modifyManyF
  :: (Collection c, Monoid (c v), Ord k, Functor f)
  => (c v -> f (c v))
  -> k
  -> Multimap c k v
  -> f (Multimap c k v)
modifyManyF :: (c v -> f (c v)) -> k -> Multimap c k v -> f (Multimap c k v)
modifyManyF c v -> f (c v)
f k
k (Multimap Map k (c v)
m) = Map k (c v) -> Multimap c k v
forall (c :: * -> *) k v. Map k (c v) -> Multimap c k v
Multimap (Map k (c v) -> Multimap c k v)
-> f (Map k (c v)) -> f (Multimap c k v)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (Maybe (c v) -> f (Maybe (c v)))
-> k -> Map k (c v) -> f (Map k (c v))
forall (f :: * -> *) k a.
(Functor f, Ord k) =>
(Maybe a -> f (Maybe a)) -> k -> Map k a -> f (Map k a)
Map.alterF ((c v -> Maybe (c v)) -> f (c v) -> f (Maybe (c v))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap c v -> Maybe (c v)
forall (c :: * -> *) v. Collection c => c v -> Maybe (c v)
wrap (f (c v) -> f (Maybe (c v)))
-> (Maybe (c v) -> f (c v)) -> Maybe (c v) -> f (Maybe (c v))
forall b c a. (b -> c) -> (a -> b) -> a -> c
. c v -> f (c v)
f (c v -> f (c v)) -> (Maybe (c v) -> c v) -> Maybe (c v) -> f (c v)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Maybe (c v) -> c v
unwrap) k
k Map k (c v)
m where
  unwrap :: Maybe (c v) -> c v
unwrap = c v -> Maybe (c v) -> c v
forall a. a -> Maybe a -> a
fromMaybe c v
forall a. Monoid a => a
mempty
  wrap :: c v -> Maybe (c v)
wrap c v
c = if c v -> Bool
forall (c :: * -> *) v. Collection c => c v -> Bool
Col.null c v
c then Maybe (c v)
forall a. Maybe a
Nothing else c v -> Maybe (c v)
forall a. a -> Maybe a
Just c v
c

-- | /O(log m * C)/ Prepends a value to a key's collection.
prepend :: (Collection c, Monoid (c v), Ord k) => k -> v -> Multimap c k v -> Multimap c k v
prepend :: k -> v -> Multimap c k v -> Multimap c k v
prepend k
k v
v = k -> c v -> Multimap c k v -> Multimap c k v
forall (c :: * -> *) v k.
(Collection c, Monoid (c v), Ord k) =>
k -> c v -> Multimap c k v -> Multimap c k v
prependMany k
k (v -> c v
forall (c :: * -> *) v. Collection c => v -> c v
Col.singleton v
v)

-- | /O(log m * C)/ Prepends a collection of values to a key's collection.
prependMany :: (Collection c, Monoid (c v), Ord k) => k -> c v -> Multimap c k v -> Multimap c k v
prependMany :: k -> c v -> Multimap c k v -> Multimap c k v
prependMany k
k c v
c = (c v -> c v) -> k -> Multimap c k v -> Multimap c k v
forall (c :: * -> *) v k.
(Collection c, Monoid (c v), Ord k) =>
(c v -> c v) -> k -> Multimap c k v -> Multimap c k v
modifyMany (c v
c c v -> c v -> c v
forall a. Semigroup a => a -> a -> a
<>) k
k

-- | /O(log m * C)/ Appends a value to a key's collection.
append :: (Collection c, Monoid (c v), Ord k) => k -> v -> Multimap c k v -> Multimap c k v
append :: k -> v -> Multimap c k v -> Multimap c k v
append k
k v
v = k -> c v -> Multimap c k v -> Multimap c k v
forall (c :: * -> *) v k.
(Collection c, Monoid (c v), Ord k) =>
k -> c v -> Multimap c k v -> Multimap c k v
appendMany k
k (v -> c v
forall (c :: * -> *) v. Collection c => v -> c v
Col.singleton v
v)

-- | /O(log m * C)/ Appends a collection of values to a key's collection.
appendMany :: (Collection c, Monoid (c v), Ord k) => k -> c v -> Multimap c k v -> Multimap c k v
appendMany :: k -> c v -> Multimap c k v -> Multimap c k v
appendMany k
k c v
c = (c v -> c v) -> k -> Multimap c k v -> Multimap c k v
forall (c :: * -> *) v k.
(Collection c, Monoid (c v), Ord k) =>
(c v -> c v) -> k -> Multimap c k v -> Multimap c k v
modifyMany (c v -> c v -> c v
forall a. Semigroup a => a -> a -> a
<> c v
c) k
k

-- | /O(log m)/ Removes all entries for the given key.
deleteMany :: Ord k => k -> Multimap c k v -> Multimap c k v
deleteMany :: k -> Multimap c k v -> Multimap c k v
deleteMany k
k = Map k (c v) -> Multimap c k v
forall (c :: * -> *) k v. Map k (c v) -> Multimap c k v
Multimap (Map k (c v) -> Multimap c k v)
-> (Multimap c k v -> Map k (c v))
-> Multimap c k v
-> Multimap c k v
forall b c a. (b -> c) -> (a -> b) -> a -> c
. k -> Map k (c v) -> Map k (c v)
forall k a. Ord k => k -> Map k a -> Map k a
Map.delete k
k (Map k (c v) -> Map k (c v))
-> (Multimap c k v -> Map k (c v)) -> Multimap c k v -> Map k (c v)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Multimap c k v -> Map k (c v)
forall (c :: * -> *) k v. Multimap c k v -> Map k (c v)
_toMap

-- | /O(n)/ Inverts keys and values inside a multimap, potentially changing the collection type.
inverseWith :: (Collection c1, Ord k, Ord v) => ([k] -> c2 k) -> Multimap c1 k v -> Multimap c2 v k
inverseWith :: ([k] -> c2 k) -> Multimap c1 k v -> Multimap c2 v k
inverseWith [k] -> c2 k
f = ([k] -> c2 k) -> [(v, k)] -> Multimap c2 v k
forall k v (c :: * -> *).
Ord k =>
([v] -> c v) -> [(k, v)] -> Multimap c k v
fromListWith [k] -> c2 k
f ([(v, k)] -> Multimap c2 v k)
-> (Multimap c1 k v -> [(v, k)])
-> Multimap c1 k v
-> Multimap c2 v k
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((k, v) -> (v, k)) -> [(k, v)] -> [(v, k)]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (k, v) -> (v, k)
forall a b. (a, b) -> (b, a)
swap ([(k, v)] -> [(v, k)])
-> (Multimap c1 k v -> [(k, v)]) -> Multimap c1 k v -> [(v, k)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Multimap c1 k v -> [(k, v)]
forall (c :: * -> *) k v.
Collection c =>
Multimap c k v -> [(k, v)]
toList

-- | /O(n)/ Filters multimap entries by value.
filter :: (Collection c, Monoid (c v), Ord k) => (v -> Bool) -> Multimap c k v -> Multimap c k v
filter :: (v -> Bool) -> Multimap c k v -> Multimap c k v
filter v -> Bool
f = [Group k (c v)] -> Multimap c k v
forall (c :: * -> *) v k.
(Collection c, Monoid (c v), Ord k) =>
[Group k (c v)] -> Multimap c k v
fromGroupList ([Group k (c v)] -> Multimap c k v)
-> (Multimap c k v -> [Group k (c v)])
-> Multimap c k v
-> Multimap c k v
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Group k (c v) -> Group k (c v))
-> [Group k (c v)] -> [Group k (c v)]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((c v -> c v) -> Group k (c v) -> Group k (c v)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((v -> Bool) -> c v -> c v
forall (c :: * -> *) v. Collection c => (v -> Bool) -> c v -> c v
Col.filter v -> Bool
f)) ([Group k (c v)] -> [Group k (c v)])
-> (Multimap c k v -> [Group k (c v)])
-> Multimap c k v
-> [Group k (c v)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Multimap c k v -> [Group k (c v)]
forall (c :: * -> *) k v. Multimap c k v -> [Group k (c v)]
toGroupList

-- | /O(m)/ Filters multimap groups. This enables filtering by key and collection.
filterGroups
  :: (Collection c, Monoid (c v), Ord k)
  => (Group k (c v) -> Bool) -> Multimap c k v -> Multimap c k v
filterGroups :: (Group k (c v) -> Bool) -> Multimap c k v -> Multimap c k v
filterGroups Group k (c v) -> Bool
f = [Group k (c v)] -> Multimap c k v
forall (c :: * -> *) v k.
(Collection c, Monoid (c v), Ord k) =>
[Group k (c v)] -> Multimap c k v
fromGroupList ([Group k (c v)] -> Multimap c k v)
-> (Multimap c k v -> [Group k (c v)])
-> Multimap c k v
-> Multimap c k v
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Group k (c v) -> Bool) -> [Group k (c v)] -> [Group k (c v)]
forall a. (a -> Bool) -> [a] -> [a]
Prelude.filter Group k (c v) -> Bool
f ([Group k (c v)] -> [Group k (c v)])
-> (Multimap c k v -> [Group k (c v)])
-> Multimap c k v
-> [Group k (c v)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Multimap c k v -> [Group k (c v)]
forall (c :: * -> *) k v. Multimap c k v -> [Group k (c v)]
toGroupList

-- | Maps over the multimap's groups. This method can be used to convert between specific multimaps,
-- for example:
--
-- > let m1 = fromList [('a', 1), ('a', 1)] :: ListMultimap Char Int
-- > let m2 = mapGroups (fmap Set.fromList) m1 :: SetMultimap Char Int
mapGroups
  :: (Collection c2, Monoid (c2 v2), Ord k2)
  => (Group k1 (c1 v1) -> Group k2 (c2 v2)) -> Multimap c1 k1 v1 -> Multimap c2 k2 v2
mapGroups :: (Group k1 (c1 v1) -> Group k2 (c2 v2))
-> Multimap c1 k1 v1 -> Multimap c2 k2 v2
mapGroups Group k1 (c1 v1) -> Group k2 (c2 v2)
f = [Group k2 (c2 v2)] -> Multimap c2 k2 v2
forall (c :: * -> *) v k.
(Collection c, Monoid (c v), Ord k) =>
[Group k (c v)] -> Multimap c k v
fromGroupList ([Group k2 (c2 v2)] -> Multimap c2 k2 v2)
-> (Multimap c1 k1 v1 -> [Group k2 (c2 v2)])
-> Multimap c1 k1 v1
-> Multimap c2 k2 v2
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Group k1 (c1 v1) -> Group k2 (c2 v2))
-> [Group k1 (c1 v1)] -> [Group k2 (c2 v2)]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Group k1 (c1 v1) -> Group k2 (c2 v2)
f ([Group k1 (c1 v1)] -> [Group k2 (c2 v2)])
-> (Multimap c1 k1 v1 -> [Group k1 (c1 v1)])
-> Multimap c1 k1 v1
-> [Group k2 (c2 v2)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Multimap c1 k1 v1 -> [Group k1 (c1 v1)]
forall (c :: * -> *) k v. Multimap c k v -> [Group k (c v)]
toGroupList

-- | /O(n)/ Converts a multimap into its list of entries. Note that this is different from
-- 'Data.Foldable.toList' which returns the multimap's values (similar to "Data.Map").
toList :: Collection c => Multimap c k v -> [(k, v)]
toList :: Multimap c k v -> [(k, v)]
toList (Multimap Map k (c v)
m) = [[(k, v)]] -> [(k, v)]
forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat ([[(k, v)]] -> [(k, v)]) -> [[(k, v)]] -> [(k, v)]
forall a b. (a -> b) -> a -> b
$ ((k, c v) -> [(k, v)]) -> [(k, c v)] -> [[(k, v)]]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (k, c v) -> [(k, v)]
forall (t :: * -> *) a b. Foldable t => (a, t b) -> [(a, b)]
go ([(k, c v)] -> [[(k, v)]]) -> [(k, c v)] -> [[(k, v)]]
forall a b. (a -> b) -> a -> b
$ Map k (c v) -> [(k, c v)]
forall k a. Map k a -> [(k, a)]
Map.toList Map k (c v)
m where
  go :: (a, t b) -> [(a, b)]
go (a
k,t b
c) = (b -> [(a, b)] -> [(a, b)]) -> [(a, b)] -> t b -> [(a, b)]
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (\b
v [(a, b)]
a -> (a
k,b
v) (a, b) -> [(a, b)] -> [(a, b)]
forall a. a -> [a] -> [a]
: [(a, b)]
a) [] t b
c

-- | /O(m)/ Converts a multimap into its list of collections.
toGroupList :: Multimap c k v -> [Group k (c v)]
toGroupList :: Multimap c k v -> [Group k (c v)]
toGroupList = Map k (c v) -> [Group k (c v)]
forall k a. Map k a -> [(k, a)]
Map.toList (Map k (c v) -> [Group k (c v)])
-> (Multimap c k v -> Map k (c v))
-> Multimap c k v
-> [Group k (c v)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Multimap c k v -> Map k (c v)
forall (c :: * -> *) k v. Multimap c k v -> Map k (c v)
_toMap

-- | /O(1)/ Converts a multimap into a map of collections.
toMap :: Multimap c k v -> Map k (c v)
toMap :: Multimap c k v -> Map k (c v)
toMap = Multimap c k v -> Map k (c v)
forall (c :: * -> *) k v. Multimap c k v -> Map k (c v)
_toMap

viewWith
  :: (Collection c, Ord k)
  => (Map k (c v) -> Maybe ((k, c v), Map k (c v)))
  -> (c v -> Maybe (v, c v)) -> Multimap c k v -> Maybe ((k, v), Multimap c k v)
viewWith :: (Map k (c v) -> Maybe ((k, c v), Map k (c v)))
-> (c v -> Maybe (v, c v))
-> Multimap c k v
-> Maybe ((k, v), Multimap c k v)
viewWith Map k (c v) -> Maybe ((k, c v), Map k (c v))
mapView c v -> Maybe (v, c v)
f (Multimap Map k (c v)
m) = case Map k (c v) -> Maybe ((k, c v), Map k (c v))
mapView Map k (c v)
m of
  Maybe ((k, c v), Map k (c v))
Nothing -> Maybe ((k, v), Multimap c k v)
forall a. Maybe a
Nothing
  Just ((k
k, c v
c), Map k (c v)
m') -> case c v -> Maybe (v, c v)
f c v
c of
    Maybe (v, c v)
Nothing -> Maybe ((k, v), Multimap c k v)
forall a. Maybe a
Nothing
    Just (v
v, c v
c') -> ((k, v), Multimap c k v) -> Maybe ((k, v), Multimap c k v)
forall a. a -> Maybe a
Just ((k
k, v
v), Map k (c v) -> Multimap c k v
forall (c :: * -> *) k v. Map k (c v) -> Multimap c k v
Multimap (if c v -> Bool
forall (c :: * -> *) v. Collection c => c v -> Bool
Col.null c v
c' then Map k (c v)
m' else k -> c v -> Map k (c v) -> Map k (c v)
forall k a. Ord k => k -> a -> Map k a -> Map k a
Map.insert k
k c v
c' Map k (c v)
m'))

-- | Returns the multimap's maximum key and value. The input function is guaranteed to be called
-- with a non-empty collection.
--
-- @since 0.2.1.2
maxViewWith :: (Collection c, Ord k) => (c v -> Maybe (v, c v)) -> Multimap c k v -> Maybe ((k, v), Multimap c k v)
maxViewWith :: (c v -> Maybe (v, c v))
-> Multimap c k v -> Maybe ((k, v), Multimap c k v)
maxViewWith = (Map k (c v) -> Maybe ((k, c v), Map k (c v)))
-> (c v -> Maybe (v, c v))
-> Multimap c k v
-> Maybe ((k, v), Multimap c k v)
forall (c :: * -> *) k v.
(Collection c, Ord k) =>
(Map k (c v) -> Maybe ((k, c v), Map k (c v)))
-> (c v -> Maybe (v, c v))
-> Multimap c k v
-> Maybe ((k, v), Multimap c k v)
viewWith Map k (c v) -> Maybe ((k, c v), Map k (c v))
forall k a. Map k a -> Maybe ((k, a), Map k a)
Map.maxViewWithKey

-- | Returns the multimap's minimum key and value. The input function is guaranteed to be called
-- with a non-empty collection.
--
-- @since 0.2.1.2
minViewWith :: (Collection c, Ord k) => (c v -> Maybe (v, c v)) -> Multimap c k v -> Maybe ((k, v), Multimap c k v)
minViewWith :: (c v -> Maybe (v, c v))
-> Multimap c k v -> Maybe ((k, v), Multimap c k v)
minViewWith = (Map k (c v) -> Maybe ((k, c v), Map k (c v)))
-> (c v -> Maybe (v, c v))
-> Multimap c k v
-> Maybe ((k, v), Multimap c k v)
forall (c :: * -> *) k v.
(Collection c, Ord k) =>
(Map k (c v) -> Maybe ((k, c v), Map k (c v)))
-> (c v -> Maybe (v, c v))
-> Multimap c k v
-> Maybe ((k, v), Multimap c k v)
viewWith Map k (c v) -> Maybe ((k, c v), Map k (c v))
forall k a. Map k a -> Maybe ((k, a), Map k a)
Map.minViewWithKey

-- | /O(m)/ Returns a list of the multimap's keys. Each key will be repeated as many times as it is
-- present in the multimap.
keys :: Collection c => Multimap c k v -> [k]
keys :: Multimap c k v -> [k]
keys (Multimap Map k (c v)
m) = (k -> c v -> [k] -> [k]) -> [k] -> Map k (c v) -> [k]
forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
Map.foldrWithKey k -> c v -> [k] -> [k]
forall (c :: * -> *) a v. Collection c => a -> c v -> [a] -> [a]
go [] Map k (c v)
m where
  go :: a -> c v -> [a] -> [a]
go a
k c v
c [a]
r = Int -> a -> [a]
forall a. Int -> a -> [a]
replicate (c v -> Int
forall (c :: * -> *) v. Collection c => c v -> Int
Col.size c v
c) a
k [a] -> [a] -> [a]
forall a. Semigroup a => a -> a -> a
<> [a]
r

-- | /O(m)/ Returns a set of the multimap's (distinct) keys.
keysSet :: Multimap c k v -> Set k
keysSet :: Multimap c k v -> Set k
keysSet = Map k (c v) -> Set k
forall k a. Map k a -> Set k
Map.keysSet (Map k (c v) -> Set k)
-> (Multimap c k v -> Map k (c v)) -> Multimap c k v -> Set k
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Multimap c k v -> Map k (c v)
forall (c :: * -> *) k v. Multimap c k v -> Map k (c v)
_toMap

-- | /O(m * C)/ Returns a multiset of the map's keys with matching multiplicities.
keysMultiset :: (Collection c, Ord k) => Multimap c k v -> Multiset k
keysMultiset :: Multimap c k v -> Multiset k
keysMultiset = Map k Int -> Multiset k
forall v. Ord v => Map v Int -> Multiset v
Mset.fromCountMap (Map k Int -> Multiset k)
-> (Multimap c k v -> Map k Int) -> Multimap c k v -> Multiset k
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (c v -> Int) -> Map k (c v) -> Map k Int
forall a b k. (a -> b) -> Map k a -> Map k b
Map.map c v -> Int
forall (c :: * -> *) v. Collection c => c v -> Int
Col.size (Map k (c v) -> Map k Int)
-> (Multimap c k v -> Map k (c v)) -> Multimap c k v -> Map k Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Multimap c k v -> Map k (c v)
forall (c :: * -> *) k v. Multimap c k v -> Map k (c v)
_toMap