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

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

  -- * Construction
  , empty
  , singleton
  , fromMap
  , fromMap'

  -- ** From Unordered Lists
  , fromList

  -- * Insertion
  , insert

  -- * Deletion\/Update
  , delete
  , deleteWithValue
  , deleteOne
  , adjust
  , adjustWithKey
  , update
  , update'
  , updateWithKey
  , updateWithKey'
  , alter
  , alterWithKey

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

  -- ** Size
  , null
  , notNull
  , size

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

  -- ** Difference
  , difference

  -- * Traversal
  -- ** Map
  , map
  , mapWithKey
  , traverseWithKey
  , traverseMaybeWithKey

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

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

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

  -- ** Lists
  , toList

  -- ** Ordered lists
  , toAscList
  , toDescList
  , toAscListBF
  , toDescListBF

  -- ** Maps
  , toMap

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

  , mapMaybe
  , mapMaybeWithKey
  , mapEither
  , mapEitherWithKey

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

import           Control.Arrow ((&&&))
import           Control.Monad (join)
import qualified Control.Monad as List (filterM)
import           Data.Data (Data)
import qualified Data.Either as Either
import qualified Data.Foldable as Foldable
import           Data.Functor.Classes
import qualified Data.List as List
import           Data.List.NonEmpty (NonEmpty(..), (<|), nonEmpty)
import qualified Data.List.NonEmpty as Nel
import           Data.Map.Lazy (Map)
import qualified Data.Map.Lazy as Map
import qualified Data.Maybe as Maybe
import           Data.Set (Set)

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

infixl 9 !

type Size = Int

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

instance Eq k => Eq1 (Multimap k) where
  liftEq :: (a -> b -> Bool) -> Multimap k a -> Multimap k b -> Bool
liftEq = (k -> k -> Bool)
-> (a -> b -> Bool) -> Multimap k a -> Multimap 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 Multimap where
  liftEq2 :: (a -> b -> Bool)
-> (c -> d -> Bool) -> Multimap a c -> Multimap b d -> Bool
liftEq2 a -> b -> Bool
eqk c -> d -> Bool
eqv Multimap a c
m Multimap b d
n =
    Map a (NonEmpty c) -> Int
forall k a. Map k a -> Int
Map.size (Multimap a c -> Map a (NonEmpty c)
forall k a. Multimap k a -> Map k (NonEmpty a)
toMap Multimap a c
m) Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Map b (NonEmpty d) -> Int
forall k a. Map k a -> Int
Map.size (Multimap b d -> Map b (NonEmpty d)
forall k a. Multimap k a -> Map k (NonEmpty a)
toMap Multimap 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) (Multimap a c -> [(a, c)]
forall k a. Multimap k a -> [(k, a)]
toList Multimap a c
m) (Multimap b d -> [(b, d)]
forall k a. Multimap k a -> [(k, a)]
toList Multimap b d
n)

instance Ord k => Ord1 (Multimap k) where
  liftCompare :: (a -> b -> Ordering) -> Multimap k a -> Multimap k b -> Ordering
liftCompare = (k -> k -> Ordering)
-> (a -> b -> Ordering) -> Multimap k a -> Multimap 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 Multimap where
  liftCompare2 :: (a -> b -> Ordering)
-> (c -> d -> Ordering) -> Multimap a c -> Multimap b d -> Ordering
liftCompare2 a -> b -> Ordering
cmpk c -> d -> Ordering
cmpv Multimap a c
m Multimap 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) (Multimap a c -> [(a, c)]
forall k a. Multimap k a -> [(k, a)]
toList Multimap a c
m) (Multimap b d -> [(b, d)]
forall k a. Multimap k a -> [(k, a)]
toList Multimap b d
n)

instance (Show k, Show a) => Show (Multimap k a) where
  showsPrec :: Int -> Multimap k a -> ShowS
showsPrec Int
d Multimap 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 (Multimap k a -> [(k, a)]
forall k a. Multimap k a -> [(k, a)]
toList Multimap k a
m)

instance Show k => Show1 (Multimap k) where
  liftShowsPrec :: (Int -> a -> ShowS)
-> ([a] -> ShowS) -> Int -> Multimap k a -> ShowS
liftShowsPrec = (Int -> k -> ShowS)
-> ([k] -> ShowS)
-> (Int -> a -> ShowS)
-> ([a] -> ShowS)
-> Int
-> Multimap 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 Multimap where
  liftShowsPrec2 :: (Int -> a -> ShowS)
-> ([a] -> ShowS)
-> (Int -> b -> ShowS)
-> ([b] -> ShowS)
-> Int
-> Multimap a b
-> ShowS
liftShowsPrec2 Int -> a -> ShowS
spk [a] -> ShowS
slk Int -> b -> ShowS
spv [b] -> ShowS
slv Int
d Multimap 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 (Multimap a b -> [(a, b)]
forall k a. Multimap k a -> [(k, a)]
toList Multimap 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, Read k, Read e) => Read (Multimap k e) where
  readsPrec :: Int -> ReadS (Multimap k e)
readsPrec Int
p = Bool -> ReadS (Multimap k e) -> ReadS (Multimap k e)
forall a. Bool -> ReadS a -> ReadS a
readParen (Int
p Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
10) (ReadS (Multimap k e) -> ReadS (Multimap k e))
-> ReadS (Multimap k e) -> ReadS (Multimap k e)
forall a b. (a -> b) -> a -> b
$ \ String
r -> do
    (String
"fromList",String
s) <- ReadS String
lex String
r
    ([(k, e)]
xs,String
t) <- ReadS [(k, e)]
forall a. Read a => ReadS a
reads String
s
    (Multimap k e, String) -> [(Multimap k e, String)]
forall (f :: * -> *) a. Applicative f => a -> f a
pure ([(k, e)] -> Multimap k e
forall k a. Ord k => [(k, a)] -> Multimap k a
fromList [(k, e)]
xs,String
t)

instance (Ord k, Read k) => Read1 (Multimap k) where
  liftReadsPrec :: (Int -> ReadS a) -> ReadS [a] -> Int -> ReadS (Multimap k a)
liftReadsPrec Int -> ReadS a
rp ReadS [a]
rl = (String -> ReadS (Multimap k a)) -> Int -> ReadS (Multimap k a)
forall a. (String -> ReadS a) -> Int -> ReadS a
readsData ((String -> ReadS (Multimap k a)) -> Int -> ReadS (Multimap k a))
-> (String -> ReadS (Multimap k a)) -> Int -> ReadS (Multimap k a)
forall a b. (a -> b) -> a -> b
$
      (Int -> ReadS [(k, a)])
-> String
-> ([(k, a)] -> Multimap k a)
-> String
-> ReadS (Multimap k a)
forall a t.
(Int -> ReadS a) -> String -> (a -> t) -> String -> ReadS t
readsUnaryWith ((Int -> ReadS (k, a)) -> ReadS [(k, a)] -> Int -> ReadS [(k, a)]
forall (f :: * -> *) a.
Read1 f =>
(Int -> ReadS a) -> ReadS [a] -> Int -> ReadS (f a)
liftReadsPrec Int -> ReadS (k, a)
rp' ReadS [(k, a)]
rl') String
"fromList" [(k, a)] -> Multimap k a
forall k a. Ord k => [(k, a)] -> Multimap k a
fromList
    where
      rp' :: Int -> ReadS (k, a)
rp' = (Int -> ReadS a) -> ReadS [a] -> Int -> ReadS (k, a)
forall (f :: * -> *) a.
Read1 f =>
(Int -> ReadS a) -> ReadS [a] -> Int -> ReadS (f a)
liftReadsPrec Int -> ReadS a
rp ReadS [a]
rl
      rl' :: ReadS [(k, a)]
rl' = (Int -> ReadS a) -> ReadS [a] -> ReadS [(k, a)]
forall (f :: * -> *) a.
Read1 f =>
(Int -> ReadS a) -> ReadS [a] -> ReadS [f a]
liftReadList Int -> ReadS a
rp ReadS [a]
rl

instance Functor (Multimap k) where
  fmap :: (a -> b) -> Multimap k a -> Multimap k b
fmap = (a -> b) -> Multimap k a -> Multimap k b
forall a b k. (a -> b) -> Multimap k a -> Multimap k b
map

instance Foldable.Foldable (Multimap k) where
  foldMap :: (a -> m) -> Multimap k a -> m
foldMap = (k -> a -> m) -> Multimap k a -> m
forall m k a. Monoid m => (k -> a -> m) -> Multimap k a -> m
foldMapWithKey ((k -> a -> m) -> Multimap k a -> m)
-> ((a -> m) -> k -> a -> m) -> (a -> m) -> Multimap 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 Traversable (Multimap k) where
  traverse :: (a -> f b) -> Multimap k a -> f (Multimap k b)
traverse = (k -> a -> f b) -> Multimap k a -> f (Multimap k b)
forall (t :: * -> *) k a b.
Applicative t =>
(k -> a -> t b) -> Multimap k a -> t (Multimap k b)
traverseWithKey ((k -> a -> f b) -> Multimap k a -> f (Multimap k b))
-> ((a -> f b) -> k -> a -> f b)
-> (a -> f b)
-> Multimap k a
-> f (Multimap k b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> f b) -> k -> a -> f b
forall a b. a -> b -> a
const
  {-# INLINE traverse #-}

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

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

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

-- | /O(1)/. The empty multimap.
--
-- > size empty === 0
empty :: Multimap k a
empty :: Multimap k a
empty = (Map k (NonEmpty a), Int) -> Multimap k a
forall k a. (Map k (NonEmpty a), Int) -> Multimap k a
Multimap (Map k (NonEmpty 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 -> Multimap k a
singleton :: k -> a -> Multimap k a
singleton k
k a
a = (Map k (NonEmpty a), Int) -> Multimap k a
forall k a. (Map k (NonEmpty a), Int) -> Multimap k a
Multimap (k -> NonEmpty a -> Map k (NonEmpty a)
forall k a. k -> a -> Map k a
Map.singleton k
k (a -> NonEmpty a
forall (f :: * -> *) a. Applicative f => a -> f a
pure 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 :: Ord k => [(k, a)] -> Multimap k a
fromList :: [(k, a)] -> Multimap k a
fromList = ((k, a) -> Multimap k a -> Multimap k a)
-> Multimap k a -> [(k, a)] -> Multimap k a
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
Foldable.foldr ((k -> a -> Multimap k a -> Multimap k a)
-> (k, a) -> Multimap k a -> Multimap k a
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry k -> a -> Multimap k a -> Multimap k a
forall k a. Ord k => k -> a -> Multimap k a -> Multimap k a
insert) Multimap k a
forall k a. Multimap k a
empty

-- | /O(1)/.
fromMap :: Map k (NonEmpty a) -> Multimap k a
fromMap :: Map k (NonEmpty a) -> Multimap k a
fromMap Map k (NonEmpty a)
m = (Map k (NonEmpty a), Int) -> Multimap k a
forall k a. (Map k (NonEmpty a), Int) -> Multimap k a
Multimap (Map k (NonEmpty a)
m, Map k Int -> Int
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
sum ((NonEmpty a -> Int) -> Map k (NonEmpty a) -> Map k Int
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap NonEmpty a -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length Map k (NonEmpty a)
m))

-- | /O(k)/. A key is retained only if it is associated with a
-- non-empty list of values.
--
-- > fromMap' (Map.fromList [(1, "ab"), (2, ""), (3, "c")]) === fromList [(1, 'a'), (1, 'b'), (3, 'c')]
fromMap' :: Map k [a] -> Multimap k a
fromMap' :: Map k [a] -> Multimap k a
fromMap' Map k [a]
m = (Map k (NonEmpty a), Int) -> Multimap k a
forall k a. (Map k (NonEmpty a), Int) -> Multimap k a
Multimap (([a] -> Maybe (NonEmpty a)) -> Map k [a] -> Map k (NonEmpty a)
forall a b k. (a -> Maybe b) -> Map k a -> Map k b
Map.mapMaybe [a] -> Maybe (NonEmpty a)
forall a. [a] -> Maybe (NonEmpty a)
nonEmpty Map k [a]
m, Map k Int -> Int
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
sum (([a] -> Int) -> Map k [a] -> Map k Int
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length Map k [a]
m))

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

-- | /O(log k)/. If the key exists in the multimap, the new value will be
-- prepended to the list of values for the key.
--
-- > insert 1 'a' empty === singleton 1 'a'
-- > insert 1 'a' (fromList [(2, 'b'), (2, 'c')]) === fromList [(1, 'a'), (2, 'b'), (2, 'c')]
-- > insert 1 'a' (fromList [(1, 'b'), (2, 'c')]) === fromList [(1, 'a'), (1, 'b'), (2, 'c')]
insert :: Ord k => k -> a -> Multimap k a -> Multimap k a
insert :: k -> a -> Multimap k a -> Multimap k a
insert k
k a
a (Multimap (Map k (NonEmpty a)
m, Int
_)) = Map k (NonEmpty a) -> Multimap k a
forall k a. Map k (NonEmpty a) -> Multimap k a
fromMap ((Maybe (NonEmpty a) -> Maybe (NonEmpty a))
-> k -> Map k (NonEmpty a) -> Map k (NonEmpty a)
forall k a.
Ord k =>
(Maybe a -> Maybe a) -> k -> Map k a -> Map k a
Map.alter Maybe (NonEmpty a) -> Maybe (NonEmpty a)
f k
k Map k (NonEmpty a)
m)
  where
    f :: Maybe (NonEmpty a) -> Maybe (NonEmpty a)
f (Just NonEmpty a
as) = NonEmpty a -> Maybe (NonEmpty a)
forall a. a -> Maybe a
Just (a
a a -> NonEmpty a -> NonEmpty a
forall a. a -> NonEmpty a -> NonEmpty a
<| NonEmpty a
as)
    f Maybe (NonEmpty a)
Nothing = NonEmpty a -> Maybe (NonEmpty a)
forall a. a -> Maybe a
Just (a -> NonEmpty a
forall (f :: * -> *) a. Applicative f => a -> f a
pure 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 -> Multimap k a -> Multimap k a
delete :: k -> Multimap k a -> Multimap k a
delete = (NonEmpty a -> [a]) -> k -> Multimap k a -> Multimap k a
forall k a.
Ord k =>
(NonEmpty a -> [a]) -> k -> Multimap k a -> Multimap k a
update' ([a] -> NonEmpty a -> [a]
forall a b. a -> b -> a
const [])

-- | /O(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 [(1, 'a'), (1, 'b'), (2, 'c'), (1, 'c')]) === fromList [(1, 'a'), (1, 'b'), (2, 'c')]
-- > deleteWithValue 1 'c' (fromList [(2, 'c'), (1, 'c')]) === singleton 2 'c'
deleteWithValue :: (Ord k, Eq a) => k -> a -> Multimap k a -> Multimap k a
deleteWithValue :: k -> a -> Multimap k a -> Multimap k a
deleteWithValue k
k a
a = (NonEmpty a -> [a]) -> k -> Multimap k a -> Multimap k a
forall k a.
Ord k =>
(NonEmpty a -> [a]) -> k -> Multimap k a -> Multimap k a
update' (a -> [a] -> [a]
forall a. Eq a => a -> [a] -> [a]
List.delete a
a ([a] -> [a]) -> (NonEmpty a -> [a]) -> NonEmpty a -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. NonEmpty a -> [a]
forall a. NonEmpty a -> [a]
Nel.toList) k
k

-- | /O(log k)/. Remove the first
-- value associated with the key. If the key is associated with a single value,
-- the key will be removed from the multimap.
--
-- > deleteOne 1 (fromList [(1, 'a'), (1, 'b'), (2, 'c')]) === fromList [(1, 'b'), (2, 'c')]
-- > deleteOne 1 (fromList [(2, 'c'), (1, 'c')]) === singleton 2 'c'
deleteOne :: Ord k => k -> Multimap k a -> Multimap k a
deleteOne :: k -> Multimap k a -> Multimap k a
deleteOne = (NonEmpty a -> [a]) -> k -> Multimap k a -> Multimap k a
forall k a.
Ord k =>
(NonEmpty a -> [a]) -> k -> Multimap k a -> Multimap k a
update' NonEmpty a -> [a]
forall a. NonEmpty a -> [a]
Nel.tail

-- | /O(m*log k)/, assuming the function @a -> a@ takes /O(1)/.
-- Update values at a specific key, if exists.
--
-- > adjust ("new " ++) 1 (fromList [(1,"a"),(1,"b"),(2,"c")]) === fromList [(1,"new a"),(1,"new b"),(2,"c")]
adjust :: Ord k => (a -> a) -> k -> Multimap k a -> Multimap k a
adjust :: (a -> a) -> k -> Multimap k a -> Multimap k a
adjust = (k -> a -> a) -> k -> Multimap k a -> Multimap k a
forall k a.
Ord k =>
(k -> a -> a) -> k -> Multimap k a -> Multimap k a
adjustWithKey ((k -> a -> a) -> k -> Multimap k a -> Multimap k a)
-> ((a -> a) -> k -> a -> a)
-> (a -> a)
-> k
-> Multimap k a
-> Multimap 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 k)/, assuming the function @k -> a -> a@ takes /O(1)/.
-- Update values at a specific key, if exists.
--
-- > 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 => (k -> a -> a) -> k -> Multimap k a -> Multimap k a
adjustWithKey :: (k -> a -> a) -> k -> Multimap k a -> Multimap k a
adjustWithKey k -> a -> a
f k
k (Multimap (Map k (NonEmpty a)
m, Int
sz)) = (Map k (NonEmpty a), Int) -> Multimap k a
forall k a. (Map k (NonEmpty a), Int) -> Multimap k a
Multimap (Map k (NonEmpty a)
m', Int
sz)
  where
    m' :: Map k (NonEmpty a)
m' = (k -> NonEmpty a -> NonEmpty a)
-> k -> Map k (NonEmpty a) -> Map k (NonEmpty a)
forall k a. Ord k => (k -> a -> a) -> k -> Map k a -> Map k a
Map.adjustWithKey ((a -> a) -> NonEmpty a -> NonEmpty a
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((a -> a) -> NonEmpty a -> NonEmpty a)
-> (k -> a -> a) -> k -> NonEmpty a -> NonEmpty a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. k -> a -> a
f) k
k Map k (NonEmpty a)
m

-- | /O(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, "b"),(2,"c")]) === singleton 2 "c"
update :: Ord k => (a -> Maybe a) -> k -> Multimap k a -> Multimap k a
update :: (a -> Maybe a) -> k -> Multimap k a -> Multimap k a
update = (k -> a -> Maybe a) -> k -> Multimap k a -> Multimap k a
forall k a.
Ord k =>
(k -> a -> Maybe a) -> k -> Multimap k a -> Multimap k a
updateWithKey ((k -> a -> Maybe a) -> k -> Multimap k a -> Multimap k a)
-> ((a -> Maybe a) -> k -> a -> Maybe a)
-> (a -> Maybe a)
-> k
-> Multimap k a
-> Multimap 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(log k)/, assuming the function @'NonEmpty' a -> [a]@ takes /O(1)/.
-- The expression (@'update' f k map@) updates the values at key @k@, if
-- exists. If @f@ returns 'Nothing', the key is deleted.
--
-- > update' NonEmpty.tail 1 (fromList [(1, "a"), (1, "b"), (2, "c")]) === fromList [(1, "b"), (2, "c")]
-- > update' NonEmpty.tail 1 (fromList [(1, "a"), (2, "b")]) === singleton 2 "b"
update' :: Ord k => (NonEmpty a -> [a]) -> k -> Multimap k a -> Multimap k a
update' :: (NonEmpty a -> [a]) -> k -> Multimap k a -> Multimap k a
update' = (k -> NonEmpty a -> [a]) -> k -> Multimap k a -> Multimap k a
forall k a.
Ord k =>
(k -> NonEmpty a -> [a]) -> k -> Multimap k a -> Multimap k a
updateWithKey' ((k -> NonEmpty a -> [a]) -> k -> Multimap k a -> Multimap k a)
-> ((NonEmpty a -> [a]) -> k -> NonEmpty a -> [a])
-> (NonEmpty a -> [a])
-> k
-> Multimap k a
-> Multimap k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (NonEmpty a -> [a]) -> k -> NonEmpty a -> [a]
forall a b. a -> b -> a
const

-- | /O(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,"b"),(2,"c")]) === singleton 2 "c"
updateWithKey :: Ord k => (k -> a -> Maybe a) -> k -> Multimap k a -> Multimap k a
updateWithKey :: (k -> a -> Maybe a) -> k -> Multimap k a -> Multimap k a
updateWithKey k -> a -> Maybe a
f = (k -> [a] -> [a]) -> k -> Multimap k a -> Multimap k a
forall k a.
Ord k =>
(k -> [a] -> [a]) -> k -> Multimap k a -> Multimap k a
alterWithKey ((a -> Maybe a) -> [a] -> [a]
forall a b. (a -> Maybe b) -> [a] -> [b]
Maybe.mapMaybe ((a -> Maybe a) -> [a] -> [a])
-> (k -> a -> Maybe a) -> k -> [a] -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. k -> a -> Maybe a
f)

-- | /O(log k)/, assuming the function @k -> 'NonEmpty' a -> [a]@ takes /O(1)/.
-- The expression (@'update' f k map@) updates the values at key @k@, if
-- exists. If @f@ returns 'Nothing', the key is deleted.
--
-- > let f k xs = if NonEmpty.length xs == 1 then (show k : NonEmpty.toList xs) else [] in do
-- >   updateWithKey' f 1 (fromList [(1, "a"), (1, "b"), (2, "c")]) === singleton 2 "c"
-- >   updateWithKey' f 1 (fromList [(1, "a"), (2, "b"), (2, "c")]) === fromList [(1, "1"), (1, "a"), (2, "b"), (2, "c")]
updateWithKey' :: Ord k => (k -> NonEmpty a -> [a]) -> k -> Multimap k a -> Multimap k a
updateWithKey' :: (k -> NonEmpty a -> [a]) -> k -> Multimap k a -> Multimap k a
updateWithKey' k -> NonEmpty a -> [a]
f = (k -> [a] -> [a]) -> k -> Multimap k a -> Multimap k a
forall k a.
Ord k =>
(k -> [a] -> [a]) -> k -> Multimap k a -> Multimap k a
alterWithKey k -> [a] -> [a]
g
  where
    g :: k -> [a] -> [a]
g k
_ [] = []
    g k
k (a
a:[a]
as) = k -> NonEmpty a -> [a]
f k
k (a
a a -> [a] -> NonEmpty a
forall a. a -> [a] -> NonEmpty a
:| [a]
as)

-- | /O(log k)/, assuming the function @[a] -> [a]@ takes /O(1)/.
-- The expression (@'alter' f k map@) alters the values at k, if exists.
--
-- > let (f, g) = (const [], ('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 3 (fromList [(1, 'a'), (2, 'b')]) === fromList [(1, 'a'), (2, 'b'), (3, 'c')]
alter :: Ord k => ([a] -> [a]) -> k -> Multimap k a -> Multimap k a
alter :: ([a] -> [a]) -> k -> Multimap k a -> Multimap k a
alter = (k -> [a] -> [a]) -> k -> Multimap k a -> Multimap k a
forall k a.
Ord k =>
(k -> [a] -> [a]) -> k -> Multimap k a -> Multimap k a
alterWithKey ((k -> [a] -> [a]) -> k -> Multimap k a -> Multimap k a)
-> (([a] -> [a]) -> k -> [a] -> [a])
-> ([a] -> [a])
-> k
-> Multimap k a
-> Multimap 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(log k)/, assuming the function @k -> [a] -> [a]@ takes /O(1)/.
-- The expression (@'alterWithKey' f k map@) alters the values at k, if exists.
--
-- > let (f, g) = (const (const []), (:) . 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 -> [a] -> [a]) -> k -> Multimap k a -> Multimap k a
alterWithKey :: (k -> [a] -> [a]) -> k -> Multimap k a -> Multimap k a
alterWithKey k -> [a] -> [a]
f k
k mm :: Multimap k a
mm@(Multimap (Map k (NonEmpty a)
m, Int
_)) = case [a] -> Maybe (NonEmpty a)
forall a. [a] -> Maybe (NonEmpty a)
nonEmpty (k -> [a] -> [a]
f k
k (Multimap k a
mm Multimap k a -> k -> [a]
forall k a. Ord k => Multimap k a -> k -> [a]
! k
k)) of
    Just NonEmpty a
as' -> Map k (NonEmpty a) -> Multimap k a
forall k a. Map k (NonEmpty a) -> Multimap k a
fromMap (k -> NonEmpty a -> Map k (NonEmpty a) -> Map k (NonEmpty a)
forall k a. Ord k => k -> a -> Map k a -> Map k a
Map.insert k
k NonEmpty a
as' Map k (NonEmpty a)
m)
    Maybe (NonEmpty a)
Nothing -> Map k (NonEmpty a) -> Multimap k a
forall k a. Map k (NonEmpty a) -> Multimap k a
fromMap (k -> Map k (NonEmpty a) -> Map k (NonEmpty a)
forall k a. Ord k => k -> Map k a -> Map k a
Map.delete k
k Map k (NonEmpty a)
m)

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

-- | /O(log k)/. Lookup the values at a key in the map. It returns an empty
-- list if the key is not in the map.
lookup :: Ord k => k -> Multimap k a -> [a]
lookup :: k -> Multimap k a -> [a]
lookup k
k (Multimap (Map k (NonEmpty a)
m, Int
_)) = [a] -> (NonEmpty a -> [a]) -> Maybe (NonEmpty a) -> [a]
forall b a. b -> (a -> b) -> Maybe a -> b
maybe [] NonEmpty a -> [a]
forall a. NonEmpty a -> [a]
Nel.toList (k -> Map k (NonEmpty a) -> Maybe (NonEmpty a)
forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup k
k Map k (NonEmpty a)
m)

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

-- | /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 (deleteOne 1 (fromList [(2, 'c'), (1, 'c')])) === False
member :: Ord k => k -> Multimap k a -> Bool
member :: k -> Multimap k a -> Bool
member k
k (Multimap (Map k (NonEmpty a)
m, Int
_)) = k -> Map k (NonEmpty a) -> Bool
forall k a. Ord k => k -> Map k a -> Bool
Map.member k
k Map k (NonEmpty 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 (deleteOne 1 (fromList [(2, 'c'), (1, 'c')])) === True
notMember :: Ord k => k -> Multimap k a -> Bool
notMember :: k -> Multimap k a -> Bool
notMember k
k = Bool -> Bool
not (Bool -> Bool) -> (Multimap k a -> Bool) -> Multimap k a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. k -> Multimap k a -> Bool
forall k a. Ord k => k -> Multimap k a -> Bool
member k
k

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

-- | /O(1)/. Is the multimap non-empty?
--
-- > notNull empty === False
-- > notNull (singleton 1 'a') === True
notNull :: Multimap k a -> Bool
notNull :: Multimap k a -> Bool
notNull = Bool -> Bool
not (Bool -> Bool) -> (Multimap k a -> Bool) -> Multimap k a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Multimap k a -> Bool
forall k a. Multimap 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(n)/ and subsequent forces take /O(1)/.
--
-- > size empty === 0
-- > size (singleton 1 'a') === 1
-- > size (fromList [(1, 'a'), (2, 'b'), (2, 'c')]) === 3
size :: Multimap k a -> Int
size :: Multimap k a -> Int
size (Multimap (Map k (NonEmpty a)
_, Int
sz)) = Int
sz

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

-- | Union two multimaps, concatenating 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'),(2,'b')]
union :: Ord k => Multimap k a -> Multimap k a -> Multimap k a
union :: Multimap k a -> Multimap k a -> Multimap k a
union (Multimap (Map k (NonEmpty a)
m1, Int
_)) (Multimap (Map k (NonEmpty a)
m2, Int
_)) =
  Map k (NonEmpty a) -> Multimap k a
forall k a. Map k (NonEmpty a) -> Multimap k a
fromMap ((NonEmpty a -> NonEmpty a -> NonEmpty a)
-> Map k (NonEmpty a) -> Map k (NonEmpty a) -> Map k (NonEmpty a)
forall k a. Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k a
Map.unionWith NonEmpty a -> NonEmpty a -> NonEmpty a
forall a. Semigroup a => a -> a -> a
(<>) Map k (NonEmpty a)
m1 Map k (NonEmpty a)
m2)

-- | Union a number of multimaps, concatenating 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'),(2,'b')]
unions :: (Foldable f, Ord k) => f (Multimap k a) -> Multimap k a
unions :: f (Multimap k a) -> Multimap k a
unions = (Multimap k a -> Multimap k a -> Multimap k a)
-> Multimap k a -> f (Multimap k a) -> Multimap k a
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
Foldable.foldr Multimap k a -> Multimap k a -> Multimap k a
forall k a. Ord k => Multimap k a -> Multimap k a -> Multimap k a
union Multimap k a
forall k a. Multimap 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 list
-- difference is performed on their values, i.e., the first occurrence
-- of each value in the second multimap is removed from the
-- first multimap.
--
-- > difference (fromList [(1,'a'),(2,'b'),(2,'c'),(2,'b')]) (fromList [(1,'d'),(2,'b'),(2,'a')])
-- >   === fromList [(1,'a'), (2,'c'), (2,'b')]
difference :: (Ord k, Eq a) => Multimap k a -> Multimap k a -> Multimap k a
difference :: Multimap k a -> Multimap k a -> Multimap k a
difference (Multimap (Map k (NonEmpty a)
m1, Int
_)) (Multimap (Map k (NonEmpty a)
m2, Int
_)) = Map k (NonEmpty a) -> Multimap k a
forall k a. Map k (NonEmpty a) -> Multimap k a
fromMap (Map k (NonEmpty a) -> Multimap k a)
-> Map k (NonEmpty a) -> Multimap k a
forall a b. (a -> b) -> a -> b
$
  (NonEmpty a -> NonEmpty a -> Maybe (NonEmpty a))
-> Map k (NonEmpty a) -> Map k (NonEmpty a) -> Map k (NonEmpty a)
forall k a b.
Ord k =>
(a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
Map.differenceWith (\NonEmpty a
xs NonEmpty a
ys -> [a] -> Maybe (NonEmpty a)
forall a. [a] -> Maybe (NonEmpty a)
nonEmpty (NonEmpty a -> [a]
forall a. NonEmpty a -> [a]
Nel.toList NonEmpty a
xs [a] -> [a] -> [a]
forall a. Eq a => [a] -> [a] -> [a]
List.\\ NonEmpty a -> [a]
forall a. NonEmpty a -> [a]
Nel.toList NonEmpty a
ys)) Map k (NonEmpty a)
m1 Map k (NonEmpty a)
m2

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

-- | /O(n)/, assuming the function @a -> b@ takes /O(1)/.
-- Map a function over all values in the map.
--
-- > Data.Multimap.map (++ "x") (fromList [(1,"a"),(1,"a"),(2,"b")]) === fromList [(1,"ax"),(1,"ax"),(2,"bx")]
map :: (a -> b) -> Multimap k a -> Multimap k b
map :: (a -> b) -> Multimap k a -> Multimap k b
map = (k -> a -> b) -> Multimap k a -> Multimap k b
forall k a b. (k -> a -> b) -> Multimap k a -> Multimap k b
mapWithKey ((k -> a -> b) -> Multimap k a -> Multimap k b)
-> ((a -> b) -> k -> a -> b)
-> (a -> b)
-> Multimap k a
-> Multimap 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)/, assuming the function @k -> a -> b@ takes /O(1)/.
-- Map a function over all key\/value pairs in the map.
--
-- > mapWithKey (\k x -> show k ++ ":" ++ x) (fromList [(1,"a"),(1,"a"),(2,"b")]) === fromList [(1,"1:a"),(1,"1:a"),(2,"2:b")]
mapWithKey :: (k -> a -> b) -> Multimap k a -> Multimap k b
mapWithKey :: (k -> a -> b) -> Multimap k a -> Multimap k b
mapWithKey k -> a -> b
f (Multimap (Map k (NonEmpty a)
m, Int
sz)) = (Map k (NonEmpty b), Int) -> Multimap k b
forall k a. (Map k (NonEmpty a), Int) -> Multimap k a
Multimap ((k -> NonEmpty a -> NonEmpty b)
-> Map k (NonEmpty a) -> Map k (NonEmpty b)
forall k a b. (k -> a -> b) -> Map k a -> Map k b
Map.mapWithKey ((a -> b) -> NonEmpty a -> NonEmpty b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((a -> b) -> NonEmpty a -> NonEmpty b)
-> (k -> a -> b) -> k -> NonEmpty a -> NonEmpty b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. k -> a -> b
f) Map k (NonEmpty a)
m, Int
sz)

-- | Traverse key\/value pairs and collect the results.
--
-- > let f k a = if odd k then Just (succ a) else Nothing in do
-- >   traverseWithKey f (fromList [(1, 'a'), (1, 'b'), (3, 'b'), (3, 'c')]) === Just (fromList [(1, 'b'), (1, 'c'), (3, 'c'), (3, 'd')])
-- >   traverseWithKey f (fromList [(1, 'a'), (1, 'b'), (2, 'b')]) === Nothing
traverseWithKey :: Applicative t => (k -> a -> t b) -> Multimap k a -> t (Multimap k b)
traverseWithKey :: (k -> a -> t b) -> Multimap k a -> t (Multimap k b)
traverseWithKey k -> a -> t b
f (Multimap (Map k (NonEmpty a)
m, Int
_)) =
  Map k (NonEmpty b) -> Multimap k b
forall k a. Map k (NonEmpty a) -> Multimap k a
fromMap (Map k (NonEmpty b) -> Multimap k b)
-> t (Map k (NonEmpty b)) -> t (Multimap k b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (k -> NonEmpty a -> t (NonEmpty b))
-> Map k (NonEmpty a) -> t (Map k (NonEmpty b))
forall (t :: * -> *) k a b.
Applicative t =>
(k -> a -> t b) -> Map k a -> t (Map k b)
Map.traverseWithKey ((a -> t b) -> NonEmpty a -> t (NonEmpty b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse ((a -> t b) -> NonEmpty a -> t (NonEmpty b))
-> (k -> a -> t b) -> k -> NonEmpty a -> t (NonEmpty b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. k -> a -> t b
f) Map k (NonEmpty a)
m

-- | Traverse key\/value pairs and collect the 'Just' results.
traverseMaybeWithKey :: Applicative t => (k -> a -> t (Maybe b)) -> Multimap k a -> t (Multimap k b)
traverseMaybeWithKey :: (k -> a -> t (Maybe b)) -> Multimap k a -> t (Multimap k b)
traverseMaybeWithKey k -> a -> t (Maybe b)
f (Multimap (Map k (NonEmpty a)
m, Int
_)) =
    Map k (NonEmpty b) -> Multimap k b
forall k a. Map k (NonEmpty a) -> Multimap k a
fromMap (Map k (NonEmpty b) -> Multimap k b)
-> t (Map k (NonEmpty b)) -> t (Multimap k b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (k -> NonEmpty a -> t (Maybe (NonEmpty b)))
-> Map k (NonEmpty a) -> t (Map k (NonEmpty b))
forall (f :: * -> *) k a b.
Applicative f =>
(k -> a -> f (Maybe b)) -> Map k a -> f (Map k b)
Map.traverseMaybeWithKey k -> NonEmpty a -> t (Maybe (NonEmpty b))
f' Map k (NonEmpty a)
m
  where
    f' :: k -> NonEmpty a -> t (Maybe (NonEmpty b))
f' k
k = ([Maybe b] -> Maybe (NonEmpty b))
-> t [Maybe b] -> t (Maybe (NonEmpty b))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ([b] -> Maybe (NonEmpty b)
forall a. [a] -> Maybe (NonEmpty a)
nonEmpty ([b] -> Maybe (NonEmpty b))
-> ([Maybe b] -> [b]) -> [Maybe b] -> Maybe (NonEmpty b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Maybe b] -> [b]
forall a. [Maybe a] -> [a]
Maybe.catMaybes) (t [Maybe b] -> t (Maybe (NonEmpty b)))
-> (NonEmpty a -> t [Maybe b])
-> NonEmpty a
-> t (Maybe (NonEmpty b))
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> t (Maybe b)) -> [a] -> t [Maybe b]
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse (k -> a -> t (Maybe b)
f k
k) ([a] -> t [Maybe b])
-> (NonEmpty a -> [a]) -> NonEmpty a -> t [Maybe b]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. NonEmpty a -> [a]
forall a. NonEmpty a -> [a]
Nel.toList

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

-- | /O(n)/. Fold the values in the map using the given right-associative
-- binary operator.
--
-- > Data.Multimap.foldr ((+) . length) 0 (fromList [(1, "hello"), (1, "world"), (2, "!")]) === 11
foldr :: (a -> b -> b) -> b -> Multimap k a -> b
foldr :: (a -> b -> b) -> b -> Multimap k a -> b
foldr = (k -> a -> b -> b) -> b -> Multimap k a -> b
forall k a b. (k -> a -> b -> b) -> b -> Multimap k a -> b
foldrWithKey ((k -> a -> b -> b) -> b -> Multimap k a -> b)
-> ((a -> b -> b) -> k -> a -> b -> b)
-> (a -> b -> b)
-> b
-> Multimap 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.foldl (\len -> (+ len) . length) 0 (fromList [(1, "hello"), (1, "world"), (2, "!")]) === 11
foldl :: (a -> b -> a) -> a -> Multimap k b -> a
foldl :: (a -> b -> a) -> a -> Multimap k b -> a
foldl = (a -> k -> b -> a) -> a -> Multimap k b -> a
forall a k b. (a -> k -> b -> a) -> a -> Multimap k b -> a
foldlWithKey ((a -> k -> b -> a) -> a -> Multimap k b -> a)
-> ((a -> b -> a) -> a -> k -> b -> a)
-> (a -> b -> a)
-> a
-> Multimap 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 -> Multimap k a -> b
foldrWithKey :: (k -> a -> b -> b) -> b -> Multimap k a -> b
foldrWithKey k -> a -> b -> b
f b
b (Multimap (Map k (NonEmpty a)
m, Int
_)) = (k -> NonEmpty a -> b -> b) -> b -> Map k (NonEmpty a) -> b
forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
Map.foldrWithKey k -> NonEmpty a -> b -> b
f' b
b Map k (NonEmpty a)
m
  where
    f' :: k -> NonEmpty a -> b -> b
f' = (b -> NonEmpty a -> b) -> NonEmpty a -> b -> b
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((b -> NonEmpty a -> b) -> NonEmpty a -> b -> b)
-> (k -> b -> NonEmpty a -> b) -> k -> NonEmpty a -> b -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> b -> b) -> b -> NonEmpty a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
Foldable.foldr ((a -> b -> b) -> b -> NonEmpty a -> b)
-> (k -> a -> b -> b) -> k -> b -> NonEmpty 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 -> Multimap k b -> a
foldlWithKey :: (a -> k -> b -> a) -> a -> Multimap k b -> a
foldlWithKey a -> k -> b -> a
f a
a (Multimap (Map k (NonEmpty b)
m, Int
_)) = (a -> k -> NonEmpty b -> a) -> a -> Map k (NonEmpty b) -> a
forall a k b. (a -> k -> b -> a) -> a -> Map k b -> a
Map.foldlWithKey a -> k -> NonEmpty b -> a
f' a
a Map k (NonEmpty b)
m
  where
    f' :: a -> k -> NonEmpty b -> a
f' = (k -> a -> NonEmpty b -> a) -> a -> k -> NonEmpty b -> a
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((a -> b -> a) -> a -> NonEmpty b -> a
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
Foldable.foldl ((a -> b -> a) -> a -> NonEmpty b -> a)
-> (k -> a -> b -> a) -> k -> a -> NonEmpty 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.foldr' ((+) . length) 0 (fromList [(1, "hello"), (1, "world"), (2, "!")]) === 11
foldr' :: (a -> b -> b) -> b -> Multimap k a -> b
foldr' :: (a -> b -> b) -> b -> Multimap k a -> b
foldr' = (k -> a -> b -> b) -> b -> Multimap k a -> b
forall k a b. (k -> a -> b -> b) -> b -> Multimap k a -> b
foldrWithKey' ((k -> a -> b -> b) -> b -> Multimap k a -> b)
-> ((a -> b -> b) -> k -> a -> b -> b)
-> (a -> b -> b)
-> b
-> Multimap 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.foldl' (\len -> (+ len) . length) 0 (fromList [(1, "hello"), (1, "world"), (2, "!")]) === 11
foldl' :: (a -> b -> a) -> a -> Multimap k b -> a
foldl' :: (a -> b -> a) -> a -> Multimap k b -> a
foldl' = (a -> k -> b -> a) -> a -> Multimap k b -> a
forall a k b. (a -> k -> b -> a) -> a -> Multimap k b -> a
foldlWithKey' ((a -> k -> b -> a) -> a -> Multimap k b -> a)
-> ((a -> b -> a) -> a -> k -> b -> a)
-> (a -> b -> a)
-> a
-> Multimap 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 -> Multimap k a -> b
foldrWithKey' :: (k -> a -> b -> b) -> b -> Multimap k a -> b
foldrWithKey' k -> a -> b -> b
f b
b (Multimap (Map k (NonEmpty a)
m, Int
_)) = (k -> NonEmpty a -> b -> b) -> b -> Map k (NonEmpty a) -> b
forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
Map.foldrWithKey' k -> NonEmpty a -> b -> b
f' b
b Map k (NonEmpty a)
m
  where
    f' :: k -> NonEmpty a -> b -> b
f' = (b -> NonEmpty a -> b) -> NonEmpty a -> b -> b
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((b -> NonEmpty a -> b) -> NonEmpty a -> b -> b)
-> (k -> b -> NonEmpty a -> b) -> k -> NonEmpty a -> b -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> b -> b) -> b -> NonEmpty a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
Foldable.foldr ((a -> b -> b) -> b -> NonEmpty a -> b)
-> (k -> a -> b -> b) -> k -> b -> NonEmpty 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 -> Multimap k b -> a
foldlWithKey' :: (a -> k -> b -> a) -> a -> Multimap k b -> a
foldlWithKey' a -> k -> b -> a
f a
a (Multimap (Map k (NonEmpty b)
m, Int
_)) = (a -> k -> NonEmpty b -> a) -> a -> Map k (NonEmpty b) -> a
forall a k b. (a -> k -> b -> a) -> a -> Map k b -> a
Map.foldlWithKey' a -> k -> NonEmpty b -> a
f' a
a Map k (NonEmpty b)
m
  where
    f' :: a -> k -> NonEmpty b -> a
f' = (k -> a -> NonEmpty b -> a) -> a -> k -> NonEmpty b -> a
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((a -> b -> a) -> a -> NonEmpty b -> a
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
Foldable.foldl' ((a -> b -> a) -> a -> NonEmpty b -> a)
-> (k -> a -> b -> a) -> k -> a -> NonEmpty 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, "a"), (2, "b")]) === "1:a1:a2:b"
foldMapWithKey :: Monoid m => (k -> a -> m) -> Multimap k a -> m
foldMapWithKey :: (k -> a -> m) -> Multimap k a -> m
foldMapWithKey k -> a -> m
f (Multimap (Map k (NonEmpty a)
m, Int
_)) = (k -> NonEmpty a -> m) -> Map k (NonEmpty a) -> m
forall m k a. Monoid m => (k -> a -> m) -> Map k a -> m
Map.foldMapWithKey k -> NonEmpty a -> m
f' Map k (NonEmpty a)
m
  where
    f' :: k -> NonEmpty a -> m
f' = (a -> m) -> NonEmpty a -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
Foldable.foldMap ((a -> m) -> NonEmpty a -> m)
-> (k -> a -> m) -> k -> NonEmpty 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.
--
-- > elems (fromList [(2, 'a'), (1, 'b'), (3, 'c'), (1, 'b')]) === "bbac"
-- > elems (empty :: Multimap Int Char) === []
elems :: Multimap k a -> [a]
elems :: Multimap k a -> [a]
elems (Multimap (Map k (NonEmpty a)
m, Int
_)) = Map k (NonEmpty a) -> [NonEmpty a]
forall k a. Map k a -> [a]
Map.elems Map k (NonEmpty a)
m [NonEmpty a] -> (NonEmpty a -> [a]) -> [a]
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= NonEmpty a -> [a]
forall a. NonEmpty a -> [a]
Nel.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 :: Multimap Int Char) === []
keys :: Multimap k a -> [k]
keys :: Multimap k a -> [k]
keys (Multimap (Map k (NonEmpty a)
m, Int
_)) = Map k (NonEmpty a) -> [k]
forall k a. Map k a -> [k]
Map.keys Map k (NonEmpty 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 :: Multimap Int Char) === Set.empty
keysSet :: Multimap k a -> Set k
keysSet :: Multimap k a -> Set k
keysSet (Multimap (Map k (NonEmpty a)
m, Int
_)) = Map k (NonEmpty a) -> Set k
forall k a. Map k a -> Set k
Map.keysSet Map k (NonEmpty a)
m

-- | An alias for 'toAscList'.
--
-- > assocs (fromList [(2,'a'),(1,'b'),(3,'c'),(1,'a')]) === [(1,'b'),(1,'a'),(2,'a'),(3,'c')]
assocs :: Multimap k a -> [(k, a)]
assocs :: Multimap k a -> [(k, a)]
assocs = Multimap k a -> [(k, a)]
forall k a. Multimap 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,'b'),(1,'a'),(2,'a'),(3,'c')]
toList :: Multimap k a -> [(k, a)]
toList :: Multimap k a -> [(k, a)]
toList = Multimap k a -> [(k, a)]
forall k a. Multimap k a -> [(k, a)]
toAscList

-- | Convert the multimap into a list of key/value pairs in ascending
-- order of keys.
--
-- > toAscList (fromList [(2,'a'),(1,'b'),(3,'c'),(1,'a')]) === [(1,'b'),(1,'a'),(2,'a'),(3,'c')]
toAscList :: Multimap k a -> [(k, a)]
toAscList :: Multimap k a -> [(k, a)]
toAscList (Multimap (Map k (NonEmpty a)
m, Int
_)) =
  Map k (NonEmpty a) -> [(k, NonEmpty a)]
forall k a. Map k a -> [(k, a)]
Map.toAscList Map k (NonEmpty a)
m [(k, NonEmpty a)] -> ((k, NonEmpty a) -> [(k, a)]) -> [(k, a)]
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= (k -> NonEmpty a -> [(k, a)]) -> (k, NonEmpty 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)]) -> (NonEmpty a -> [a]) -> NonEmpty a -> [(k, a)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. NonEmpty a -> [a]
forall a. NonEmpty a -> [a]
Nel.toList)

-- | Convert the multimap into a list of key/value pairs in descending
-- order of keys.
--
-- > toDescList (fromList [(2,'a'),(1,'b'),(3,'c'),(1,'a')]) === [(3,'c'),(2,'a'),(1,'b'),(1,'a')]
toDescList :: Multimap k a -> [(k, a)]
toDescList :: Multimap k a -> [(k, a)]
toDescList (Multimap (Map k (NonEmpty a)
m, Int
_)) =
  Map k (NonEmpty a) -> [(k, NonEmpty a)]
forall k a. Map k a -> [(k, a)]
Map.toDescList Map k (NonEmpty a)
m [(k, NonEmpty a)] -> ((k, NonEmpty a) -> [(k, a)]) -> [(k, a)]
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= (k -> NonEmpty a -> [(k, a)]) -> (k, NonEmpty 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)]) -> (NonEmpty a -> [a]) -> NonEmpty a -> [(k, a)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. NonEmpty a -> [a]
forall a. NonEmpty a -> [a]
Nel.toList)

-- | Convert the multimap into a list of key/value pairs, in a
-- breadth-first manner, in ascending order of keys.
--
-- > toAscListBF (fromList [("Foo",1),("Foo",2),("Foo",3),("Bar",4),("Bar",5),("Baz",6)])
-- >   === [("Bar",4),("Baz",6),("Foo",1),("Bar",5),("Foo",2),("Foo",3)]
toAscListBF :: Multimap k a -> [(k, a)]
toAscListBF :: Multimap k a -> [(k, a)]
toAscListBF (Multimap (Map k (NonEmpty a)
m, Int
_)) =
  [[(k, a)]] -> [(k, a)]
forall (m :: * -> *) a. Monad m => m (m a) -> m a
join
  ([[(k, a)]] -> [(k, a)])
-> ([(k, NonEmpty a)] -> [[(k, a)]])
-> [(k, NonEmpty a)]
-> [(k, a)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [[(k, a)]] -> [[(k, a)]]
forall a. [[a]] -> [[a]]
List.transpose
  ([[(k, a)]] -> [[(k, a)]])
-> ([(k, NonEmpty a)] -> [[(k, a)]])
-> [(k, NonEmpty a)]
-> [[(k, a)]]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((k, NonEmpty a) -> [(k, a)]) -> [(k, NonEmpty a)] -> [[(k, a)]]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((k -> NonEmpty a -> [(k, a)]) -> (k, NonEmpty 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)]) -> (NonEmpty a -> [a]) -> NonEmpty a -> [(k, a)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. NonEmpty a -> [a]
forall a. NonEmpty a -> [a]
Nel.toList))
  ([(k, NonEmpty a)] -> [(k, a)]) -> [(k, NonEmpty a)] -> [(k, a)]
forall a b. (a -> b) -> a -> b
$ Map k (NonEmpty a) -> [(k, NonEmpty a)]
forall k a. Map k a -> [(k, a)]
Map.toAscList Map k (NonEmpty a)
m

-- | Convert the multimap into a list of key/value pairs, in a
-- breadth-first manner, in descending order of keys.
--
-- > toDescListBF (fromList [("Foo",1),("Foo",2),("Foo",3),("Bar",4),("Bar",5),("Baz",6)])
-- >   === [("Foo",1),("Baz",6),("Bar",4),("Foo",2),("Bar",5),("Foo",3)]
toDescListBF :: Multimap k a -> [(k, a)]
toDescListBF :: Multimap k a -> [(k, a)]
toDescListBF (Multimap (Map k (NonEmpty a)
m, Int
_)) =
  [[(k, a)]] -> [(k, a)]
forall (m :: * -> *) a. Monad m => m (m a) -> m a
join
  ([[(k, a)]] -> [(k, a)])
-> ([(k, NonEmpty a)] -> [[(k, a)]])
-> [(k, NonEmpty a)]
-> [(k, a)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [[(k, a)]] -> [[(k, a)]]
forall a. [[a]] -> [[a]]
List.transpose
  ([[(k, a)]] -> [[(k, a)]])
-> ([(k, NonEmpty a)] -> [[(k, a)]])
-> [(k, NonEmpty a)]
-> [[(k, a)]]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((k, NonEmpty a) -> [(k, a)]) -> [(k, NonEmpty a)] -> [[(k, a)]]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((k -> NonEmpty a -> [(k, a)]) -> (k, NonEmpty 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)]) -> (NonEmpty a -> [a]) -> NonEmpty a -> [(k, a)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. NonEmpty a -> [a]
forall a. NonEmpty a -> [a]
Nel.toList))
  ([(k, NonEmpty a)] -> [(k, a)]) -> [(k, NonEmpty a)] -> [(k, a)]
forall a b. (a -> b) -> a -> b
$ Map k (NonEmpty a) -> [(k, NonEmpty a)]
forall k a. Map k a -> [(k, a)]
Map.toDescList Map k (NonEmpty a)
m

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

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

-- | /O(n)/, assuming the predicate function takes /O(1)/.
-- Retain all values that satisfy the predicate.
--
-- > Data.Multimap.filter (> 'a') (fromList [(1,'a'),(1,'b'),(2,'a')]) === singleton 1 'b'
-- > Data.Multimap.filter (< 'a') (fromList [(1,'a'),(1,'b'),(2,'a')]) === empty
filter :: (a -> Bool) -> Multimap k a -> Multimap k a
filter :: (a -> Bool) -> Multimap k a -> Multimap k a
filter = (k -> a -> Bool) -> Multimap k a -> Multimap k a
forall k a. (k -> a -> Bool) -> Multimap k a -> Multimap k a
filterWithKey ((k -> a -> Bool) -> Multimap k a -> Multimap k a)
-> ((a -> Bool) -> k -> a -> Bool)
-> (a -> Bool)
-> Multimap k a
-> Multimap 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 even (fromList [(1,'a'),(1,'b'),(2,'a')]) === singleton 2 'a'
filterKey :: (k -> Bool) -> Multimap k a -> Multimap k a
filterKey :: (k -> Bool) -> Multimap k a -> Multimap k a
filterKey k -> Bool
p (Multimap (Map k (NonEmpty a)
m, Int
_)) = Map k (NonEmpty a) -> Multimap k a
forall k a. Map k (NonEmpty a) -> Multimap k a
fromMap Map k (NonEmpty a)
m'
  where
    m' :: Map k (NonEmpty a)
m' = (k -> NonEmpty a -> Bool)
-> Map k (NonEmpty a) -> Map k (NonEmpty a)
forall k a. (k -> a -> Bool) -> Map k a -> Map k a
Map.filterWithKey (Bool -> NonEmpty a -> Bool
forall a b. a -> b -> a
const (Bool -> NonEmpty a -> Bool)
-> (k -> Bool) -> k -> NonEmpty a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. k -> Bool
p) Map k (NonEmpty a)
m

-- | /O(n)/, assuming the predicate function takes /O(1)/.
-- Retain all key\/value pairs that satisfy 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) -> Multimap k a -> Multimap k a
filterWithKey :: (k -> a -> Bool) -> Multimap k a -> Multimap k a
filterWithKey k -> a -> Bool
p (Multimap (Map k (NonEmpty a)
m, Int
_)) = Map k (NonEmpty a) -> Multimap k a
forall k a. Map k (NonEmpty a) -> Multimap k a
fromMap Map k (NonEmpty a)
m'
  where
    m' :: Map k (NonEmpty a)
m' = (k -> NonEmpty a -> Maybe (NonEmpty a))
-> Map k (NonEmpty a) -> Map k (NonEmpty a)
forall k a b. (k -> a -> Maybe b) -> Map k a -> Map k b
Map.mapMaybeWithKey (\k
k -> [a] -> Maybe (NonEmpty a)
forall a. [a] -> Maybe (NonEmpty a)
nonEmpty ([a] -> Maybe (NonEmpty a))
-> (NonEmpty a -> [a]) -> NonEmpty a -> Maybe (NonEmpty a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Bool) -> NonEmpty a -> [a]
forall a. (a -> Bool) -> NonEmpty a -> [a]
Nel.filter (k -> a -> Bool
p k
k)) Map k (NonEmpty 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, Applicative t) => (a -> t Bool) -> Multimap k a -> t (Multimap k a)
filterM :: (a -> t Bool) -> Multimap k a -> t (Multimap k a)
filterM = (k -> a -> t Bool) -> Multimap k a -> t (Multimap k a)
forall k (t :: * -> *) a.
(Ord k, Applicative t) =>
(k -> a -> t Bool) -> Multimap k a -> t (Multimap k a)
filterWithKeyM ((k -> a -> t Bool) -> Multimap k a -> t (Multimap k a))
-> ((a -> t Bool) -> k -> a -> t Bool)
-> (a -> t Bool)
-> Multimap k a
-> t (Multimap 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'.
--
-- > 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'),(1,'a'),(2,'c'),(2,'c')]) === Just (fromList [(2,'c'),(2,'c')])
filterWithKeyM :: (Ord k, Applicative t) => (k -> a -> t Bool) -> Multimap k a -> t (Multimap k a)
filterWithKeyM :: (k -> a -> t Bool) -> Multimap k a -> t (Multimap k a)
filterWithKeyM k -> a -> t Bool
f = ([(k, a)] -> Multimap k a) -> t [(k, a)] -> t (Multimap k a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap [(k, a)] -> Multimap k a
forall k a. Ord k => [(k, a)] -> Multimap k a
fromList (t [(k, a)] -> t (Multimap k a))
-> (Multimap k a -> t [(k, a)]) -> Multimap k a -> t (Multimap 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)])
-> (Multimap k a -> [(k, a)]) -> Multimap k a -> t [(k, a)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Multimap k a -> [(k, a)]
forall k a. Multimap k a -> [(k, a)]
toList

-- | /O(n)/, 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 :: (a -> Maybe b) -> Multimap k a -> Multimap k b
mapMaybe :: (a -> Maybe b) -> Multimap k a -> Multimap k b
mapMaybe = (k -> a -> Maybe b) -> Multimap k a -> Multimap k b
forall k a b. (k -> a -> Maybe b) -> Multimap k a -> Multimap k b
mapMaybeWithKey ((k -> a -> Maybe b) -> Multimap k a -> Multimap k b)
-> ((a -> Maybe b) -> k -> a -> Maybe b)
-> (a -> Maybe b)
-> Multimap k a
-> Multimap 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)/, 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 :: (k -> a -> Maybe b) -> Multimap k a -> Multimap k b
mapMaybeWithKey :: (k -> a -> Maybe b) -> Multimap k a -> Multimap k b
mapMaybeWithKey k -> a -> Maybe b
f (Multimap (Map k (NonEmpty a)
m, Int
_)) = Map k (NonEmpty b) -> Multimap k b
forall k a. Map k (NonEmpty a) -> Multimap k a
fromMap (Map k (NonEmpty b) -> Multimap k b)
-> Map k (NonEmpty b) -> Multimap k b
forall a b. (a -> b) -> a -> b
$
  (k -> NonEmpty a -> Maybe (NonEmpty b))
-> Map k (NonEmpty a) -> Map k (NonEmpty b)
forall k a b. (k -> a -> Maybe b) -> Map k a -> Map k b
Map.mapMaybeWithKey (\k
k -> [b] -> Maybe (NonEmpty b)
forall a. [a] -> Maybe (NonEmpty a)
nonEmpty ([b] -> Maybe (NonEmpty b))
-> (NonEmpty a -> [b]) -> NonEmpty a -> Maybe (NonEmpty b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Maybe b) -> [a] -> [b]
forall a b. (a -> Maybe b) -> [a] -> [b]
Maybe.mapMaybe (k -> a -> Maybe b
f k
k) ([a] -> [b]) -> (NonEmpty a -> [a]) -> NonEmpty a -> [b]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. NonEmpty a -> [a]
forall a. NonEmpty a -> [a]
Nel.toList) Map k (NonEmpty a)
m

-- | /O(n)/, 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 :: (a -> Either b c) -> Multimap k a -> (Multimap k b, Multimap k c)
mapEither :: (a -> Either b c) -> Multimap k a -> (Multimap k b, Multimap k c)
mapEither = (k -> a -> Either b c)
-> Multimap k a -> (Multimap k b, Multimap k c)
forall k a b c.
(k -> a -> Either b c)
-> Multimap k a -> (Multimap k b, Multimap k c)
mapEitherWithKey ((k -> a -> Either b c)
 -> Multimap k a -> (Multimap k b, Multimap k c))
-> ((a -> Either b c) -> k -> a -> Either b c)
-> (a -> Either b c)
-> Multimap k a
-> (Multimap k b, Multimap 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)/, 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 :: (k -> a -> Either b c) -> Multimap k a -> (Multimap k b, Multimap k c)
mapEitherWithKey :: (k -> a -> Either b c)
-> Multimap k a -> (Multimap k b, Multimap k c)
mapEitherWithKey k -> a -> Either b c
f (Multimap (Map k (NonEmpty a)
m, Int
_)) =
    (Map k [b] -> Multimap k b
forall k a. Map k [a] -> Multimap k a
fromMap' (Map k [b] -> Multimap k b)
-> (Map k ([b], [c]) -> Map k [b])
-> Map k ([b], [c])
-> Multimap k b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k -> ([b], [c]) -> [b]) -> Map k ([b], [c]) -> Map k [b]
forall k a b. (k -> a -> b) -> Map k a -> Map k b
Map.mapWithKey ((([b], [c]) -> [b]) -> k -> ([b], [c]) -> [b]
forall a b. a -> b -> a
const ([b], [c]) -> [b]
forall a b. (a, b) -> a
fst) (Map k ([b], [c]) -> Multimap k b)
-> (Map k ([b], [c]) -> Multimap k c)
-> Map k ([b], [c])
-> (Multimap k b, Multimap k c)
forall (a :: * -> * -> *) b c c'.
Arrow a =>
a b c -> a b c' -> a b (c, c')
&&& Map k [c] -> Multimap k c
forall k a. Map k [a] -> Multimap k a
fromMap' (Map k [c] -> Multimap k c)
-> (Map k ([b], [c]) -> Map k [c])
-> Map k ([b], [c])
-> Multimap k c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k -> ([b], [c]) -> [c]) -> Map k ([b], [c]) -> Map k [c]
forall k a b. (k -> a -> b) -> Map k a -> Map k b
Map.mapWithKey ((([b], [c]) -> [c]) -> k -> ([b], [c]) -> [c]
forall a b. a -> b -> a
const ([b], [c]) -> [c]
forall a b. (a, b) -> b
snd))
      (Map k ([b], [c]) -> (Multimap k b, Multimap k c))
-> Map k ([b], [c]) -> (Multimap k b, Multimap k c)
forall a b. (a -> b) -> a -> b
$ (k -> NonEmpty a -> ([b], [c]))
-> Map k (NonEmpty a) -> Map k ([b], [c])
forall k a b. (k -> a -> b) -> Map k a -> Map k b
Map.mapWithKey k -> NonEmpty a -> ([b], [c])
g Map k (NonEmpty a)
m
  where
    g :: k -> NonEmpty a -> ([b], [c])
g k
k NonEmpty a
as = [Either b c] -> ([b], [c])
forall a b. [Either a b] -> ([a], [b])
Either.partitionEithers ([Either b c] -> ([b], [c])) -> [Either b c] -> ([b], [c])
forall a b. (a -> b) -> a -> b
$ (a -> Either b c) -> [a] -> [Either b c]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (k -> a -> Either b c
f k
k) (NonEmpty a -> [a]
forall a. NonEmpty a -> [a]
Nel.toList NonEmpty a
as)

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

-- | /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, NonEmpty.fromList "ac")
-- > lookupMin (empty :: Multimap Int Char) === Nothing
lookupMin :: Multimap k a -> Maybe (k, NonEmpty a)
lookupMin :: Multimap k a -> Maybe (k, NonEmpty a)
lookupMin (Multimap (Map k (NonEmpty a)
m, Int
_)) = Map k (NonEmpty a) -> Maybe (k, NonEmpty a)
forall k a. Map k a -> Maybe (k, a)
Map.lookupMin Map k (NonEmpty 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, NonEmpty.fromList "c")
-- > lookupMax (empty :: Multimap Int Char) === Nothing
lookupMax :: Multimap k a -> Maybe (k, NonEmpty a)
lookupMax :: Multimap k a -> Maybe (k, NonEmpty a)
lookupMax (Multimap (Map k (NonEmpty a)
m, Int
_)) = Map k (NonEmpty a) -> Maybe (k, NonEmpty a)
forall k a. Map k a -> Maybe (k, a)
Map.lookupMax Map k (NonEmpty 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, NonEmpty.fromList "bc")
lookupLT :: Ord k => k -> Multimap k a -> Maybe (k, NonEmpty a)
lookupLT :: k -> Multimap k a -> Maybe (k, NonEmpty a)
lookupLT k
k (Multimap (Map k (NonEmpty a)
m, Int
_)) = k -> Map k (NonEmpty a) -> Maybe (k, NonEmpty a)
forall k v. Ord k => k -> Map k v -> Maybe (k, v)
Map.lookupLT k
k Map k (NonEmpty 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, NonEmpty.fromList "bc")
lookupGT :: Ord k => k -> Multimap k a -> Maybe (k, NonEmpty a)
lookupGT :: k -> Multimap k a -> Maybe (k, NonEmpty a)
lookupGT k
k (Multimap (Map k (NonEmpty a)
m, Int
_)) = k -> Map k (NonEmpty a) -> Maybe (k, NonEmpty a)
forall k v. Ord k => k -> Map k v -> Maybe (k, v)
Map.lookupGT k
k Map k (NonEmpty 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, NonEmpty.fromList "a")
-- > lookupLE 4 (fromList [(1,'a'),(3,'b'),(3,'c'),(5,'c')]) === Just (3, NonEmpty.fromList "bc")
lookupLE :: Ord k => k -> Multimap k a -> Maybe (k, NonEmpty a)
lookupLE :: k -> Multimap k a -> Maybe (k, NonEmpty a)
lookupLE k
k (Multimap (Map k (NonEmpty a)
m, Int
_)) = k -> Map k (NonEmpty a) -> Maybe (k, NonEmpty a)
forall k v. Ord k => k -> Map k v -> Maybe (k, v)
Map.lookupLE k
k Map k (NonEmpty 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, NonEmpty.fromList "c")
-- > lookupGE 2 (fromList [(1,'a'),(3,'b'),(3,'c'),(5,'c')]) === Just (3, NonEmpty.fromList "bc")
lookupGE :: Ord k => k -> Multimap k a -> Maybe (k, NonEmpty a)
lookupGE :: k -> Multimap k a -> Maybe (k, NonEmpty a)
lookupGE k
k (Multimap (Map k (NonEmpty a)
m, Int
_)) = k -> Map k (NonEmpty a) -> Maybe (k, NonEmpty a)
forall k v. Ord k => k -> Map k v -> Maybe (k, v)
Map.lookupGE k
k Map k (NonEmpty a)
m