{-# LANGUAGE RoleAnnotations #-}
{-# LANGUAGE TupleSections #-}
{-# LANGUAGE DeriveDataTypeable #-}
{-# LANGUAGE DeriveFunctor #-}
{-# OPTIONS_GHC -Wall #-}

-- Like 'UniqFM', these are maps for keys which are Uniquable.
-- Unlike 'UniqFM', these maps also remember their keys, which
-- makes them a much better drop in replacement for 'Data.Map.Map'.
--
-- Key preservation is right-biased.
module GHC.Types.Unique.Map (
    UniqMap(..),
    emptyUniqMap,
    isNullUniqMap,
    unitUniqMap,
    listToUniqMap,
    listToUniqMap_C,
    addToUniqMap,
    addListToUniqMap,
    addToUniqMap_C,
    addToUniqMap_Acc,
    addToUniqMap_L,
    alterUniqMap,
    addListToUniqMap_C,
    adjustUniqMap,
    delFromUniqMap,
    delListFromUniqMap,
    plusUniqMap,
    plusUniqMap_C,
    plusMaybeUniqMap_C,
    plusUniqMapList,
    minusUniqMap,
    intersectUniqMap,
    intersectUniqMap_C,
    disjointUniqMap,
    mapUniqMap,
    filterUniqMap,
    partitionUniqMap,
    sizeUniqMap,
    elemUniqMap,
    lookupUniqMap,
    lookupWithDefaultUniqMap,
    anyUniqMap,
    allUniqMap,
    nonDetEltsUniqMap,
    nonDetFoldUniqMap
    -- Non-deterministic functions omitted
) where

import GHC.Prelude

import GHC.Types.Unique.FM

import GHC.Types.Unique
import GHC.Utils.Outputable

import Data.Semigroup as Semi ( Semigroup(..) )
import Data.Coerce
import Data.Maybe
import Data.Data
import Control.DeepSeq

-- | Maps indexed by 'Uniquable' keys
newtype UniqMap k a = UniqMap { forall k a. UniqMap k a -> UniqFM k (k, a)
getUniqMap :: UniqFM k (k, a) }
    deriving (Typeable (UniqMap k a)
Typeable (UniqMap k a) =>
(forall (c :: * -> *).
 (forall d b. Data d => c (d -> b) -> d -> c b)
 -> (forall g. g -> c g) -> UniqMap k a -> c (UniqMap k a))
-> (forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c (UniqMap k a))
-> (UniqMap k a -> Constr)
-> (UniqMap k a -> DataType)
-> (forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c (UniqMap k a)))
-> (forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e))
    -> Maybe (c (UniqMap k a)))
-> ((forall b. Data b => b -> b) -> UniqMap k a -> UniqMap k a)
-> (forall r r'.
    (r -> r' -> r)
    -> r -> (forall d. Data d => d -> r') -> UniqMap k a -> r)
-> (forall r r'.
    (r' -> r -> r)
    -> r -> (forall d. Data d => d -> r') -> UniqMap k a -> r)
-> (forall u. (forall d. Data d => d -> u) -> UniqMap k a -> [u])
-> (forall u.
    Int -> (forall d. Data d => d -> u) -> UniqMap k a -> u)
-> (forall (m :: * -> *).
    Monad m =>
    (forall d. Data d => d -> m d) -> UniqMap k a -> m (UniqMap k a))
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> UniqMap k a -> m (UniqMap k a))
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> UniqMap k a -> m (UniqMap k a))
-> Data (UniqMap k a)
UniqMap k a -> Constr
UniqMap k a -> DataType
(forall b. Data b => b -> b) -> UniqMap k a -> UniqMap 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) -> UniqMap k a -> u
forall u. (forall d. Data d => d -> u) -> UniqMap k a -> [u]
forall k a. (Data k, Data a) => Typeable (UniqMap k a)
forall k a. (Data k, Data a) => UniqMap k a -> Constr
forall k a. (Data k, Data a) => UniqMap k a -> DataType
forall k a.
(Data k, Data a) =>
(forall b. Data b => b -> b) -> UniqMap k a -> UniqMap k a
forall k a u.
(Data k, Data a) =>
Int -> (forall d. Data d => d -> u) -> UniqMap k a -> u
forall k a u.
(Data k, Data a) =>
(forall d. Data d => d -> u) -> UniqMap k a -> [u]
forall k a r r'.
(Data k, Data a) =>
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> UniqMap k a -> r
forall k a r r'.
(Data k, Data a) =>
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> UniqMap k a -> r
forall k a (m :: * -> *).
(Data k, Data a, Monad m) =>
(forall d. Data d => d -> m d) -> UniqMap k a -> m (UniqMap k a)
forall k a (m :: * -> *).
(Data k, Data a, MonadPlus m) =>
(forall d. Data d => d -> m d) -> UniqMap k a -> m (UniqMap k a)
forall k a (c :: * -> *).
(Data k, Data a) =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (UniqMap k a)
forall k a (c :: * -> *).
(Data k, Data a) =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> UniqMap k a -> c (UniqMap k a)
forall k a (t :: * -> *) (c :: * -> *).
(Data k, Data a, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (UniqMap k a))
forall k a (t :: * -> * -> *) (c :: * -> *).
(Data k, Data a, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (UniqMap k a))
forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> UniqMap k a -> r
forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> UniqMap k a -> r
forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> UniqMap k a -> m (UniqMap k a)
forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> UniqMap k a -> m (UniqMap k a)
forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (UniqMap k a)
forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> UniqMap k a -> c (UniqMap k a)
forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c (UniqMap k a))
forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (UniqMap k a))
$cgfoldl :: forall k a (c :: * -> *).
(Data k, Data a) =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> UniqMap k a -> c (UniqMap k a)
gfoldl :: forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> UniqMap k a -> c (UniqMap k a)
$cgunfold :: forall k a (c :: * -> *).
(Data k, Data a) =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (UniqMap k a)
gunfold :: forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (UniqMap k a)
$ctoConstr :: forall k a. (Data k, Data a) => UniqMap k a -> Constr
toConstr :: UniqMap k a -> Constr
$cdataTypeOf :: forall k a. (Data k, Data a) => UniqMap k a -> DataType
dataTypeOf :: UniqMap k a -> DataType
$cdataCast1 :: forall k a (t :: * -> *) (c :: * -> *).
(Data k, Data a, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (UniqMap k a))
dataCast1 :: forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c (UniqMap k a))
$cdataCast2 :: forall k a (t :: * -> * -> *) (c :: * -> *).
(Data k, Data a, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (UniqMap k a))
dataCast2 :: forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (UniqMap k a))
$cgmapT :: forall k a.
(Data k, Data a) =>
(forall b. Data b => b -> b) -> UniqMap k a -> UniqMap k a
gmapT :: (forall b. Data b => b -> b) -> UniqMap k a -> UniqMap k a
$cgmapQl :: forall k a r r'.
(Data k, Data a) =>
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> UniqMap k a -> r
gmapQl :: forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> UniqMap k a -> r
$cgmapQr :: forall k a r r'.
(Data k, Data a) =>
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> UniqMap k a -> r
gmapQr :: forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> UniqMap k a -> r
$cgmapQ :: forall k a u.
(Data k, Data a) =>
(forall d. Data d => d -> u) -> UniqMap k a -> [u]
gmapQ :: forall u. (forall d. Data d => d -> u) -> UniqMap k a -> [u]
$cgmapQi :: forall k a u.
(Data k, Data a) =>
Int -> (forall d. Data d => d -> u) -> UniqMap k a -> u
gmapQi :: forall u. Int -> (forall d. Data d => d -> u) -> UniqMap k a -> u
$cgmapM :: forall k a (m :: * -> *).
(Data k, Data a, Monad m) =>
(forall d. Data d => d -> m d) -> UniqMap k a -> m (UniqMap k a)
gmapM :: forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> UniqMap k a -> m (UniqMap k a)
$cgmapMp :: forall k a (m :: * -> *).
(Data k, Data a, MonadPlus m) =>
(forall d. Data d => d -> m d) -> UniqMap k a -> m (UniqMap k a)
gmapMp :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> UniqMap k a -> m (UniqMap k a)
$cgmapMo :: forall k a (m :: * -> *).
(Data k, Data a, MonadPlus m) =>
(forall d. Data d => d -> m d) -> UniqMap k a -> m (UniqMap k a)
gmapMo :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> UniqMap k a -> m (UniqMap k a)
Data, UniqMap k a -> UniqMap k a -> Bool
(UniqMap k a -> UniqMap k a -> Bool)
-> (UniqMap k a -> UniqMap k a -> Bool) -> Eq (UniqMap k a)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall k a. (Eq k, Eq a) => UniqMap k a -> UniqMap k a -> Bool
$c== :: forall k a. (Eq k, Eq a) => UniqMap k a -> UniqMap k a -> Bool
== :: UniqMap k a -> UniqMap k a -> Bool
$c/= :: forall k a. (Eq k, Eq a) => UniqMap k a -> UniqMap k a -> Bool
/= :: UniqMap k a -> UniqMap k a -> Bool
Eq, (forall a b. (a -> b) -> UniqMap k a -> UniqMap k b)
-> (forall a b. a -> UniqMap k b -> UniqMap k a)
-> Functor (UniqMap k)
forall a b. a -> UniqMap k b -> UniqMap k a
forall a b. (a -> b) -> UniqMap k a -> UniqMap k b
forall k a b. a -> UniqMap k b -> UniqMap k a
forall k a b. (a -> b) -> UniqMap k a -> UniqMap k b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
$cfmap :: forall k a b. (a -> b) -> UniqMap k a -> UniqMap k b
fmap :: forall a b. (a -> b) -> UniqMap k a -> UniqMap k b
$c<$ :: forall k a b. a -> UniqMap k b -> UniqMap k a
<$ :: forall a b. a -> UniqMap k b -> UniqMap k a
Functor)
type role UniqMap nominal representational

instance Semigroup (UniqMap k a) where
  <> :: UniqMap k a -> UniqMap k a -> UniqMap k a
(<>) = UniqMap k a -> UniqMap k a -> UniqMap k a
forall k a. UniqMap k a -> UniqMap k a -> UniqMap k a
plusUniqMap

instance Monoid (UniqMap k a) where
    mempty :: UniqMap k a
mempty = UniqMap k a
forall k a. UniqMap k a
emptyUniqMap
    mappend :: UniqMap k a -> UniqMap k a -> UniqMap k a
mappend = UniqMap k a -> UniqMap k a -> UniqMap k a
forall a. Semigroup a => a -> a -> a
(Semi.<>)

instance (Outputable k, Outputable a) => Outputable (UniqMap k a) where
    ppr :: UniqMap k a -> SDoc
ppr (UniqMap UniqFM k (k, a)
m) =
        SDoc -> SDoc
forall doc. IsLine doc => doc -> doc
brackets (SDoc -> SDoc) -> SDoc -> SDoc
forall a b. (a -> b) -> a -> b
$ [SDoc] -> SDoc
forall doc. IsLine doc => [doc] -> doc
fsep ([SDoc] -> SDoc) -> [SDoc] -> SDoc
forall a b. (a -> b) -> a -> b
$ SDoc -> [SDoc] -> [SDoc]
forall doc. IsLine doc => doc -> [doc] -> [doc]
punctuate SDoc
forall doc. IsLine doc => doc
comma ([SDoc] -> [SDoc]) -> [SDoc] -> [SDoc]
forall a b. (a -> b) -> a -> b
$
        [ k -> SDoc
forall a. Outputable a => a -> SDoc
ppr k
k SDoc -> SDoc -> SDoc
forall doc. IsLine doc => doc -> doc -> doc
<+> String -> SDoc
forall doc. IsLine doc => String -> doc
text String
"->" SDoc -> SDoc -> SDoc
forall doc. IsLine doc => doc -> doc -> doc
<+> a -> SDoc
forall a. Outputable a => a -> SDoc
ppr a
v
        | (k
k, a
v) <- UniqFM k (k, a) -> [(k, a)]
forall key elt. UniqFM key elt -> [elt]
nonDetEltsUFM UniqFM k (k, a)
m ]

instance (NFData k, NFData a) => NFData (UniqMap k a) where
  rnf :: UniqMap k a -> ()
rnf (UniqMap UniqFM k (k, a)
fm) = ((k, a) -> ()) -> UniqFM k (k, a) -> ()
forall elt key. (elt -> ()) -> UniqFM key elt -> ()
seqEltsUFM (k, a) -> ()
forall a. NFData a => a -> ()
rnf UniqFM k (k, a)
fm

liftC :: (a -> a -> a) -> (k, a) -> (k, a) -> (k, a)
liftC :: forall a k. (a -> a -> a) -> (k, a) -> (k, a) -> (k, a)
liftC a -> a -> a
f (k
_, a
v) (k
k', a
v') = (k
k', a -> a -> a
f a
v a
v')

emptyUniqMap :: UniqMap k a
emptyUniqMap :: forall k a. UniqMap k a
emptyUniqMap = UniqFM k (k, a) -> UniqMap k a
forall k a. UniqFM k (k, a) -> UniqMap k a
UniqMap UniqFM k (k, a)
forall key elt. UniqFM key elt
emptyUFM

isNullUniqMap :: UniqMap k a -> Bool
isNullUniqMap :: forall k a. UniqMap k a -> Bool
isNullUniqMap (UniqMap UniqFM k (k, a)
m) = UniqFM k (k, a) -> Bool
forall key elt. UniqFM key elt -> Bool
isNullUFM UniqFM k (k, a)
m

unitUniqMap :: Uniquable k => k -> a -> UniqMap k a
unitUniqMap :: forall k a. Uniquable k => k -> a -> UniqMap k a
unitUniqMap k
k a
v = UniqFM k (k, a) -> UniqMap k a
forall k a. UniqFM k (k, a) -> UniqMap k a
UniqMap (k -> (k, a) -> UniqFM k (k, a)
forall key elt. Uniquable key => key -> elt -> UniqFM key elt
unitUFM k
k (k
k, a
v))

listToUniqMap :: Uniquable k => [(k,a)] -> UniqMap k a
listToUniqMap :: forall k a. Uniquable k => [(k, a)] -> UniqMap k a
listToUniqMap [(k, a)]
kvs = UniqFM k (k, a) -> UniqMap k a
forall k a. UniqFM k (k, a) -> UniqMap k a
UniqMap ([(k, (k, a))] -> UniqFM k (k, a)
forall key elt. Uniquable key => [(key, elt)] -> UniqFM key elt
listToUFM [ (k
k,(k
k,a
v)) | (k
k,a
v) <- [(k, a)]
kvs])

listToUniqMap_C :: Uniquable k => (a -> a -> a) -> [(k,a)] -> UniqMap k a
listToUniqMap_C :: forall k a. Uniquable k => (a -> a -> a) -> [(k, a)] -> UniqMap k a
listToUniqMap_C a -> a -> a
f [(k, a)]
kvs = UniqFM k (k, a) -> UniqMap k a
forall k a. UniqFM k (k, a) -> UniqMap k a
UniqMap (UniqFM k (k, a) -> UniqMap k a) -> UniqFM k (k, a) -> UniqMap k a
forall a b. (a -> b) -> a -> b
$
    ((k, a) -> (k, a) -> (k, a)) -> [(k, (k, a))] -> UniqFM k (k, a)
forall key elt.
Uniquable key =>
(elt -> elt -> elt) -> [(key, elt)] -> UniqFM key elt
listToUFM_C ((a -> a -> a) -> (k, a) -> (k, a) -> (k, a)
forall a k. (a -> a -> a) -> (k, a) -> (k, a) -> (k, a)
liftC a -> a -> a
f) [ (k
k,(k
k,a
v)) | (k
k,a
v) <- [(k, a)]
kvs]

addToUniqMap :: Uniquable k => UniqMap k a -> k -> a -> UniqMap k a
addToUniqMap :: forall k a. Uniquable k => UniqMap k a -> k -> a -> UniqMap k a
addToUniqMap (UniqMap UniqFM k (k, a)
m) k
k a
v = UniqFM k (k, a) -> UniqMap k a
forall k a. UniqFM k (k, a) -> UniqMap k a
UniqMap (UniqFM k (k, a) -> UniqMap k a) -> UniqFM k (k, a) -> UniqMap k a
forall a b. (a -> b) -> a -> b
$ UniqFM k (k, a) -> k -> (k, a) -> UniqFM k (k, a)
forall key elt.
Uniquable key =>
UniqFM key elt -> key -> elt -> UniqFM key elt
addToUFM UniqFM k (k, a)
m k
k (k
k, a
v)

addListToUniqMap :: Uniquable k => UniqMap k a -> [(k,a)] -> UniqMap k a
addListToUniqMap :: forall k a. Uniquable k => UniqMap k a -> [(k, a)] -> UniqMap k a
addListToUniqMap (UniqMap UniqFM k (k, a)
m) [(k, a)]
kvs = UniqFM k (k, a) -> UniqMap k a
forall k a. UniqFM k (k, a) -> UniqMap k a
UniqMap (UniqFM k (k, a) -> UniqMap k a) -> UniqFM k (k, a) -> UniqMap k a
forall a b. (a -> b) -> a -> b
$
    UniqFM k (k, a) -> [(k, (k, a))] -> UniqFM k (k, a)
forall key elt.
Uniquable key =>
UniqFM key elt -> [(key, elt)] -> UniqFM key elt
addListToUFM UniqFM k (k, a)
m [(k
k,(k
k,a
v)) | (k
k,a
v) <- [(k, a)]
kvs]

addToUniqMap_C :: Uniquable k
               => (a -> a -> a)
               -> UniqMap k a
               -> k
               -> a
               -> UniqMap k a
addToUniqMap_C :: forall k a.
Uniquable k =>
(a -> a -> a) -> UniqMap k a -> k -> a -> UniqMap k a
addToUniqMap_C a -> a -> a
f (UniqMap UniqFM k (k, a)
m) k
k a
v = UniqFM k (k, a) -> UniqMap k a
forall k a. UniqFM k (k, a) -> UniqMap k a
UniqMap (UniqFM k (k, a) -> UniqMap k a) -> UniqFM k (k, a) -> UniqMap k a
forall a b. (a -> b) -> a -> b
$
    ((k, a) -> (k, a) -> (k, a))
-> UniqFM k (k, a) -> k -> (k, a) -> UniqFM k (k, a)
forall key elt.
Uniquable key =>
(elt -> elt -> elt)
-> UniqFM key elt -> key -> elt -> UniqFM key elt
addToUFM_C ((a -> a -> a) -> (k, a) -> (k, a) -> (k, a)
forall a k. (a -> a -> a) -> (k, a) -> (k, a) -> (k, a)
liftC a -> a -> a
f) UniqFM k (k, a)
m k
k (k
k, a
v)

addToUniqMap_Acc :: Uniquable k
                 => (b -> a -> a)
                 -> (b -> a)
                 -> UniqMap k a
                 -> k
                 -> b
                 -> UniqMap k a
addToUniqMap_Acc :: forall k b a.
Uniquable k =>
(b -> a -> a) -> (b -> a) -> UniqMap k a -> k -> b -> UniqMap k a
addToUniqMap_Acc b -> a -> a
exi b -> a
new (UniqMap UniqFM k (k, a)
m) k
k0 b
v0 = UniqFM k (k, a) -> UniqMap k a
forall k a. UniqFM k (k, a) -> UniqMap k a
UniqMap (UniqFM k (k, a) -> UniqMap k a) -> UniqFM k (k, a) -> UniqMap k a
forall a b. (a -> b) -> a -> b
$
    (b -> (k, a) -> (k, a))
-> (b -> (k, a)) -> UniqFM k (k, a) -> k -> b -> UniqFM k (k, a)
forall key elt elts.
Uniquable key =>
(elt -> elts -> elts)
-> (elt -> elts)
-> UniqFM key elts
-> key
-> elt
-> UniqFM key elts
addToUFM_Acc (\b
b (k
k, a
v) -> (k
k, b -> a -> a
exi b
b a
v))
                 (\b
b -> (k
k0, b -> a
new b
b))
                 UniqFM k (k, a)
m k
k0 b
v0

-- | Add an element, returns previous lookup result and new map. If
-- old element doesn't exist, add the passed element directly,
-- otherwise compute the element to add using the passed function.
addToUniqMap_L :: Uniquable k
               => (k -> a -> a -> a) -- key,old,new
               -> k
               -> a -- new
               -> UniqMap k a
               -> (Maybe a, UniqMap k a)
addToUniqMap_L :: forall k a.
Uniquable k =>
(k -> a -> a -> a)
-> k -> a -> UniqMap k a -> (Maybe a, UniqMap k a)
addToUniqMap_L k -> a -> a -> a
f k
k a
v (UniqMap UniqFM k (k, a)
m) = case (k -> (k, a) -> (k, a) -> (k, a))
-> k
-> (k, a)
-> UniqFM k (k, a)
-> (Maybe (k, a), UniqFM k (k, a))
forall key elt.
Uniquable key =>
(key -> elt -> elt -> elt)
-> key -> elt -> UniqFM key elt -> (Maybe elt, UniqFM key elt)
addToUFM_L
  (\k
_k (k
_, a
_o) (k
_, a
_n) -> (k
_k, k -> a -> a -> a
f k
_k a
_o a
_n))
  k
k
  (k
k, a
v)
  UniqFM k (k, a)
m of
  (Maybe (k, a)
_maybe, UniqFM k (k, a)
_ufm) -> ((k, a) -> a
forall a b. (a, b) -> b
snd ((k, a) -> a) -> Maybe (k, a) -> Maybe a
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Maybe (k, a)
_maybe, UniqFM k (k, a) -> UniqMap k a
forall k a. UniqFM k (k, a) -> UniqMap k a
UniqMap UniqFM k (k, a)
_ufm)

alterUniqMap :: Uniquable k
             => (Maybe a -> Maybe a)
             -> UniqMap k a
             -> k
             -> UniqMap k a
alterUniqMap :: forall k a.
Uniquable k =>
(Maybe a -> Maybe a) -> UniqMap k a -> k -> UniqMap k a
alterUniqMap Maybe a -> Maybe a
f (UniqMap UniqFM k (k, a)
m) k
k = UniqFM k (k, a) -> UniqMap k a
forall k a. UniqFM k (k, a) -> UniqMap k a
UniqMap (UniqFM k (k, a) -> UniqMap k a) -> UniqFM k (k, a) -> UniqMap k a
forall a b. (a -> b) -> a -> b
$
    (Maybe (k, a) -> Maybe (k, a))
-> UniqFM k (k, a) -> k -> UniqFM k (k, a)
forall key elt.
Uniquable key =>
(Maybe elt -> Maybe elt) -> UniqFM key elt -> key -> UniqFM key elt
alterUFM ((a -> (k, a)) -> Maybe a -> Maybe (k, a)
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (k
k,) (Maybe a -> Maybe (k, a))
-> (Maybe (k, a) -> Maybe a) -> Maybe (k, a) -> Maybe (k, a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Maybe a -> Maybe a
f (Maybe a -> Maybe a)
-> (Maybe (k, a) -> Maybe a) -> Maybe (k, a) -> Maybe a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((k, a) -> a) -> Maybe (k, a) -> Maybe a
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (k, a) -> a
forall a b. (a, b) -> b
snd) UniqFM k (k, a)
m k
k

addListToUniqMap_C
    :: Uniquable k
    => (a -> a -> a)
    -> UniqMap k a
    -> [(k, a)]
    -> UniqMap k a
addListToUniqMap_C :: forall k a.
Uniquable k =>
(a -> a -> a) -> UniqMap k a -> [(k, a)] -> UniqMap k a
addListToUniqMap_C a -> a -> a
f (UniqMap UniqFM k (k, a)
m) [(k, a)]
kvs = UniqFM k (k, a) -> UniqMap k a
forall k a. UniqFM k (k, a) -> UniqMap k a
UniqMap (UniqFM k (k, a) -> UniqMap k a) -> UniqFM k (k, a) -> UniqMap k a
forall a b. (a -> b) -> a -> b
$
    ((k, a) -> (k, a) -> (k, a))
-> UniqFM k (k, a) -> [(k, (k, a))] -> UniqFM k (k, a)
forall key elt.
Uniquable key =>
(elt -> elt -> elt)
-> UniqFM key elt -> [(key, elt)] -> UniqFM key elt
addListToUFM_C ((a -> a -> a) -> (k, a) -> (k, a) -> (k, a)
forall a k. (a -> a -> a) -> (k, a) -> (k, a) -> (k, a)
liftC a -> a -> a
f) UniqFM k (k, a)
m
        [(k
k,(k
k,a
v)) | (k
k,a
v) <- [(k, a)]
kvs]

adjustUniqMap
    :: Uniquable k
    => (a -> a)
    -> UniqMap k a
    -> k
    -> UniqMap k a
adjustUniqMap :: forall k a.
Uniquable k =>
(a -> a) -> UniqMap k a -> k -> UniqMap k a
adjustUniqMap a -> a
f (UniqMap UniqFM k (k, a)
m) k
k = UniqFM k (k, a) -> UniqMap k a
forall k a. UniqFM k (k, a) -> UniqMap k a
UniqMap (UniqFM k (k, a) -> UniqMap k a) -> UniqFM k (k, a) -> UniqMap k a
forall a b. (a -> b) -> a -> b
$
    ((k, a) -> (k, a)) -> UniqFM k (k, a) -> k -> UniqFM k (k, a)
forall key elt.
Uniquable key =>
(elt -> elt) -> UniqFM key elt -> key -> UniqFM key elt
adjustUFM (\(k
_,a
v) -> (k
k,a -> a
f a
v)) UniqFM k (k, a)
m k
k

delFromUniqMap :: Uniquable k => UniqMap k a -> k -> UniqMap k a
delFromUniqMap :: forall k a. Uniquable k => UniqMap k a -> k -> UniqMap k a
delFromUniqMap (UniqMap UniqFM k (k, a)
m) k
k = UniqFM k (k, a) -> UniqMap k a
forall k a. UniqFM k (k, a) -> UniqMap k a
UniqMap (UniqFM k (k, a) -> UniqMap k a) -> UniqFM k (k, a) -> UniqMap k a
forall a b. (a -> b) -> a -> b
$ UniqFM k (k, a) -> k -> UniqFM k (k, a)
forall key elt.
Uniquable key =>
UniqFM key elt -> key -> UniqFM key elt
delFromUFM UniqFM k (k, a)
m k
k

delListFromUniqMap :: Uniquable k => UniqMap k a -> [k] -> UniqMap k a
delListFromUniqMap :: forall k a. Uniquable k => UniqMap k a -> [k] -> UniqMap k a
delListFromUniqMap (UniqMap UniqFM k (k, a)
m) [k]
ks = UniqFM k (k, a) -> UniqMap k a
forall k a. UniqFM k (k, a) -> UniqMap k a
UniqMap (UniqFM k (k, a) -> UniqMap k a) -> UniqFM k (k, a) -> UniqMap k a
forall a b. (a -> b) -> a -> b
$ UniqFM k (k, a) -> [k] -> UniqFM k (k, a)
forall key elt.
Uniquable key =>
UniqFM key elt -> [key] -> UniqFM key elt
delListFromUFM UniqFM k (k, a)
m [k]
ks

plusUniqMap :: UniqMap k a -> UniqMap k a -> UniqMap k a
plusUniqMap :: forall k a. UniqMap k a -> UniqMap k a -> UniqMap k a
plusUniqMap (UniqMap UniqFM k (k, a)
m1) (UniqMap UniqFM k (k, a)
m2) = UniqFM k (k, a) -> UniqMap k a
forall k a. UniqFM k (k, a) -> UniqMap k a
UniqMap (UniqFM k (k, a) -> UniqMap k a) -> UniqFM k (k, a) -> UniqMap k a
forall a b. (a -> b) -> a -> b
$ UniqFM k (k, a) -> UniqFM k (k, a) -> UniqFM k (k, a)
forall key elt. UniqFM key elt -> UniqFM key elt -> UniqFM key elt
plusUFM UniqFM k (k, a)
m1 UniqFM k (k, a)
m2

plusUniqMap_C :: (a -> a -> a) -> UniqMap k a -> UniqMap k a -> UniqMap k a
plusUniqMap_C :: forall a k.
(a -> a -> a) -> UniqMap k a -> UniqMap k a -> UniqMap k a
plusUniqMap_C a -> a -> a
f (UniqMap UniqFM k (k, a)
m1) (UniqMap UniqFM k (k, a)
m2) = UniqFM k (k, a) -> UniqMap k a
forall k a. UniqFM k (k, a) -> UniqMap k a
UniqMap (UniqFM k (k, a) -> UniqMap k a) -> UniqFM k (k, a) -> UniqMap k a
forall a b. (a -> b) -> a -> b
$
    ((k, a) -> (k, a) -> (k, a))
-> UniqFM k (k, a) -> UniqFM k (k, a) -> UniqFM k (k, a)
forall elt key.
(elt -> elt -> elt)
-> UniqFM key elt -> UniqFM key elt -> UniqFM key elt
plusUFM_C ((a -> a -> a) -> (k, a) -> (k, a) -> (k, a)
forall a k. (a -> a -> a) -> (k, a) -> (k, a) -> (k, a)
liftC a -> a -> a
f) UniqFM k (k, a)
m1 UniqFM k (k, a)
m2

plusMaybeUniqMap_C :: (a -> a -> Maybe a) -> UniqMap k a -> UniqMap k a -> UniqMap k a
plusMaybeUniqMap_C :: forall a k.
(a -> a -> Maybe a) -> UniqMap k a -> UniqMap k a -> UniqMap k a
plusMaybeUniqMap_C a -> a -> Maybe a
f (UniqMap UniqFM k (k, a)
m1) (UniqMap UniqFM k (k, a)
m2) = UniqFM k (k, a) -> UniqMap k a
forall k a. UniqFM k (k, a) -> UniqMap k a
UniqMap (UniqFM k (k, a) -> UniqMap k a) -> UniqFM k (k, a) -> UniqMap k a
forall a b. (a -> b) -> a -> b
$
    ((k, a) -> (k, a) -> Maybe (k, a))
-> UniqFM k (k, a) -> UniqFM k (k, a) -> UniqFM k (k, a)
forall elt key.
(elt -> elt -> Maybe elt)
-> UniqFM key elt -> UniqFM key elt -> UniqFM key elt
plusMaybeUFM_C (\(k
_, a
v) (k
k', a
v') -> (a -> (k, a)) -> Maybe a -> Maybe (k, a)
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (k
k',) (a -> a -> Maybe a
f a
v a
v')) UniqFM k (k, a)
m1 UniqFM k (k, a)
m2

plusUniqMapList :: [UniqMap k a] -> UniqMap k a
plusUniqMapList :: forall k a. [UniqMap k a] -> UniqMap k a
plusUniqMapList [UniqMap k a]
xs = UniqFM k (k, a) -> UniqMap k a
forall k a. UniqFM k (k, a) -> UniqMap k a
UniqMap (UniqFM k (k, a) -> UniqMap k a) -> UniqFM k (k, a) -> UniqMap k a
forall a b. (a -> b) -> a -> b
$ [UniqFM k (k, a)] -> UniqFM k (k, a)
forall key elt. [UniqFM key elt] -> UniqFM key elt
plusUFMList ([UniqMap k a] -> [UniqFM k (k, a)]
forall a b. Coercible a b => a -> b
coerce [UniqMap k a]
xs)

minusUniqMap :: UniqMap k a -> UniqMap k b -> UniqMap k a
minusUniqMap :: forall k a b. UniqMap k a -> UniqMap k b -> UniqMap k a
minusUniqMap (UniqMap UniqFM k (k, a)
m1) (UniqMap UniqFM k (k, b)
m2) = UniqFM k (k, a) -> UniqMap k a
forall k a. UniqFM k (k, a) -> UniqMap k a
UniqMap (UniqFM k (k, a) -> UniqMap k a) -> UniqFM k (k, a) -> UniqMap k a
forall a b. (a -> b) -> a -> b
$ UniqFM k (k, a) -> UniqFM k (k, b) -> UniqFM k (k, a)
forall key elt1 elt2.
UniqFM key elt1 -> UniqFM key elt2 -> UniqFM key elt1
minusUFM UniqFM k (k, a)
m1 UniqFM k (k, b)
m2

intersectUniqMap :: UniqMap k a -> UniqMap k b -> UniqMap k a
intersectUniqMap :: forall k a b. UniqMap k a -> UniqMap k b -> UniqMap k a
intersectUniqMap (UniqMap UniqFM k (k, a)
m1) (UniqMap UniqFM k (k, b)
m2) = UniqFM k (k, a) -> UniqMap k a
forall k a. UniqFM k (k, a) -> UniqMap k a
UniqMap (UniqFM k (k, a) -> UniqMap k a) -> UniqFM k (k, a) -> UniqMap k a
forall a b. (a -> b) -> a -> b
$ UniqFM k (k, a) -> UniqFM k (k, b) -> UniqFM k (k, a)
forall key elt1 elt2.
UniqFM key elt1 -> UniqFM key elt2 -> UniqFM key elt1
intersectUFM UniqFM k (k, a)
m1 UniqFM k (k, b)
m2

-- | Intersection with a combining function.
intersectUniqMap_C :: (a -> b -> c) -> UniqMap k a -> UniqMap k b -> UniqMap k c
intersectUniqMap_C :: forall a b c k.
(a -> b -> c) -> UniqMap k a -> UniqMap k b -> UniqMap k c
intersectUniqMap_C a -> b -> c
f (UniqMap UniqFM k (k, a)
m1) (UniqMap UniqFM k (k, b)
m2) = UniqFM k (k, c) -> UniqMap k c
forall k a. UniqFM k (k, a) -> UniqMap k a
UniqMap (UniqFM k (k, c) -> UniqMap k c) -> UniqFM k (k, c) -> UniqMap k c
forall a b. (a -> b) -> a -> b
$ ((k, a) -> (k, b) -> (k, c))
-> UniqFM k (k, a) -> UniqFM k (k, b) -> UniqFM k (k, c)
forall elt1 elt2 elt3 key.
(elt1 -> elt2 -> elt3)
-> UniqFM key elt1 -> UniqFM key elt2 -> UniqFM key elt3
intersectUFM_C (\(k
k, a
a) (k
_, b
b) -> (k
k, a -> b -> c
f a
a b
b)) UniqFM k (k, a)
m1 UniqFM k (k, b)
m2

disjointUniqMap :: UniqMap k a -> UniqMap k b -> Bool
disjointUniqMap :: forall k a b. UniqMap k a -> UniqMap k b -> Bool
disjointUniqMap (UniqMap UniqFM k (k, a)
m1) (UniqMap UniqFM k (k, b)
m2) = UniqFM k (k, a) -> UniqFM k (k, b) -> Bool
forall key elt1 elt2. UniqFM key elt1 -> UniqFM key elt2 -> Bool
disjointUFM UniqFM k (k, a)
m1 UniqFM k (k, b)
m2

mapUniqMap :: (a -> b) -> UniqMap k a -> UniqMap k b
mapUniqMap :: forall a b k. (a -> b) -> UniqMap k a -> UniqMap k b
mapUniqMap a -> b
f (UniqMap UniqFM k (k, a)
m) = UniqFM k (k, b) -> UniqMap k b
forall k a. UniqFM k (k, a) -> UniqMap k a
UniqMap (UniqFM k (k, b) -> UniqMap k b) -> UniqFM k (k, b) -> UniqMap k b
forall a b. (a -> b) -> a -> b
$ ((k, a) -> (k, b)) -> UniqFM k (k, a) -> UniqFM k (k, b)
forall elt1 elt2 key.
(elt1 -> elt2) -> UniqFM key elt1 -> UniqFM key elt2
mapUFM ((a -> b) -> (k, a) -> (k, b)
forall a b. (a -> b) -> (k, a) -> (k, b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> b
f) UniqFM k (k, a)
m -- (,) k instance

filterUniqMap :: (a -> Bool) -> UniqMap k a -> UniqMap k a
filterUniqMap :: forall a k. (a -> Bool) -> UniqMap k a -> UniqMap k a
filterUniqMap a -> Bool
f (UniqMap UniqFM k (k, a)
m) = UniqFM k (k, a) -> UniqMap k a
forall k a. UniqFM k (k, a) -> UniqMap k a
UniqMap (UniqFM k (k, a) -> UniqMap k a) -> UniqFM k (k, a) -> UniqMap k a
forall a b. (a -> b) -> a -> b
$ ((k, a) -> Bool) -> UniqFM k (k, a) -> UniqFM k (k, a)
forall elt key. (elt -> Bool) -> UniqFM key elt -> UniqFM key elt
filterUFM (a -> Bool
f (a -> Bool) -> ((k, a) -> a) -> (k, a) -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k, a) -> a
forall a b. (a, b) -> b
snd) UniqFM k (k, a)
m

partitionUniqMap :: (a -> Bool) -> UniqMap k a -> (UniqMap k a, UniqMap k a)
partitionUniqMap :: forall a k.
(a -> Bool) -> UniqMap k a -> (UniqMap k a, UniqMap k a)
partitionUniqMap a -> Bool
f (UniqMap UniqFM k (k, a)
m) =
    (UniqFM k (k, a), UniqFM k (k, a)) -> (UniqMap k a, UniqMap k a)
forall a b. Coercible a b => a -> b
coerce ((UniqFM k (k, a), UniqFM k (k, a)) -> (UniqMap k a, UniqMap k a))
-> (UniqFM k (k, a), UniqFM k (k, a)) -> (UniqMap k a, UniqMap k a)
forall a b. (a -> b) -> a -> b
$ ((k, a) -> Bool)
-> UniqFM k (k, a) -> (UniqFM k (k, a), UniqFM k (k, a))
forall elt key.
(elt -> Bool) -> UniqFM key elt -> (UniqFM key elt, UniqFM key elt)
partitionUFM (a -> Bool
f (a -> Bool) -> ((k, a) -> a) -> (k, a) -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k, a) -> a
forall a b. (a, b) -> b
snd) UniqFM k (k, a)
m

sizeUniqMap :: UniqMap k a -> Int
sizeUniqMap :: forall k a. UniqMap k a -> Int
sizeUniqMap (UniqMap UniqFM k (k, a)
m) = UniqFM k (k, a) -> Int
forall key elt. UniqFM key elt -> Int
sizeUFM UniqFM k (k, a)
m

elemUniqMap :: Uniquable k => k -> UniqMap k a -> Bool
elemUniqMap :: forall k a. Uniquable k => k -> UniqMap k a -> Bool
elemUniqMap k
k (UniqMap UniqFM k (k, a)
m) = k -> UniqFM k (k, a) -> Bool
forall key elt. Uniquable key => key -> UniqFM key elt -> Bool
elemUFM k
k UniqFM k (k, a)
m

lookupUniqMap :: Uniquable k => UniqMap k a -> k -> Maybe a
lookupUniqMap :: forall k a. Uniquable k => UniqMap k a -> k -> Maybe a
lookupUniqMap (UniqMap UniqFM k (k, a)
m) k
k = ((k, a) -> a) -> Maybe (k, a) -> Maybe a
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (k, a) -> a
forall a b. (a, b) -> b
snd (UniqFM k (k, a) -> k -> Maybe (k, a)
forall key elt. Uniquable key => UniqFM key elt -> key -> Maybe elt
lookupUFM UniqFM k (k, a)
m k
k)

lookupWithDefaultUniqMap :: Uniquable k => UniqMap k a -> a -> k -> a
lookupWithDefaultUniqMap :: forall k a. Uniquable k => UniqMap k a -> a -> k -> a
lookupWithDefaultUniqMap (UniqMap UniqFM k (k, a)
m) a
a k
k = a -> Maybe a -> a
forall a. a -> Maybe a -> a
fromMaybe a
a (((k, a) -> a) -> Maybe (k, a) -> Maybe a
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (k, a) -> a
forall a b. (a, b) -> b
snd (UniqFM k (k, a) -> k -> Maybe (k, a)
forall key elt. Uniquable key => UniqFM key elt -> key -> Maybe elt
lookupUFM UniqFM k (k, a)
m k
k))

anyUniqMap :: (a -> Bool) -> UniqMap k a -> Bool
anyUniqMap :: forall a k. (a -> Bool) -> UniqMap k a -> Bool
anyUniqMap a -> Bool
f (UniqMap UniqFM k (k, a)
m) = ((k, a) -> Bool) -> UniqFM k (k, a) -> Bool
forall elt key. (elt -> Bool) -> UniqFM key elt -> Bool
anyUFM (a -> Bool
f (a -> Bool) -> ((k, a) -> a) -> (k, a) -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k, a) -> a
forall a b. (a, b) -> b
snd) UniqFM k (k, a)
m

allUniqMap :: (a -> Bool) -> UniqMap k a -> Bool
allUniqMap :: forall a k. (a -> Bool) -> UniqMap k a -> Bool
allUniqMap a -> Bool
f (UniqMap UniqFM k (k, a)
m) = ((k, a) -> Bool) -> UniqFM k (k, a) -> Bool
forall elt key. (elt -> Bool) -> UniqFM key elt -> Bool
allUFM (a -> Bool
f (a -> Bool) -> ((k, a) -> a) -> (k, a) -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k, a) -> a
forall a b. (a, b) -> b
snd) UniqFM k (k, a)
m

nonDetEltsUniqMap :: UniqMap k a -> [(k, a)]
nonDetEltsUniqMap :: forall k a. UniqMap k a -> [(k, a)]
nonDetEltsUniqMap (UniqMap UniqFM k (k, a)
m) = UniqFM k (k, a) -> [(k, a)]
forall key elt. UniqFM key elt -> [elt]
nonDetEltsUFM UniqFM k (k, a)
m

nonDetFoldUniqMap :: ((k, a) -> b -> b) -> b -> UniqMap k a -> b
nonDetFoldUniqMap :: forall k a b. ((k, a) -> b -> b) -> b -> UniqMap k a -> b
nonDetFoldUniqMap (k, a) -> b -> b
go b
z (UniqMap UniqFM k (k, a)
m) = ((k, a) -> b -> b) -> b -> UniqFM k (k, a) -> b
forall elt a key. (elt -> a -> a) -> a -> UniqFM key elt -> a
foldUFM (k, a) -> b -> b
go b
z UniqFM k (k, a)
m