{-
(c) The University of Glasgow 2006
(c) The AQUA Project, Glasgow University, 1994-1998

\section[UniqSet]{Specialised sets, for things with @Uniques@}

Based on @UniqFMs@ (as you would expect).

Basically, the things need to be in class @Uniquable@.
-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
{-# LANGUAGE DeriveDataTypeable #-}

module GHC.Types.Unique.Set (
        -- * Unique set type
        UniqSet,    -- type synonym for UniqFM a
        getUniqSet,
        pprUniqSet,

        -- ** Manipulating these sets
        emptyUniqSet,
        unitUniqSet,
        mkUniqSet,
        addOneToUniqSet, addListToUniqSet,
        delOneFromUniqSet, delOneFromUniqSet_Directly, delListFromUniqSet,
        delListFromUniqSet_Directly,
        unionUniqSets, unionManyUniqSets,
        minusUniqSet, uniqSetMinusUFM, uniqSetMinusUDFM,
        intersectUniqSets,
        disjointUniqSets,
        restrictUniqSetToUFM,
        uniqSetAny, uniqSetAll,
        elementOfUniqSet,
        elemUniqSet_Directly,
        filterUniqSet,
        filterUniqSet_Directly,
        sizeUniqSet,
        isEmptyUniqSet,
        lookupUniqSet,
        lookupUniqSet_Directly,
        partitionUniqSet,
        mapUniqSet,
        unsafeUFMToUniqSet,
        nonDetEltsUniqSet,
        nonDetKeysUniqSet,
        nonDetStrictFoldUniqSet,
    ) where

import GHC.Prelude

import GHC.Types.Unique.DFM
import GHC.Types.Unique.FM
import GHC.Types.Unique
import Data.Coerce
import GHC.Utils.Outputable
import Data.Data
import qualified Data.Semigroup as Semi

-- Note [UniqSet invariant]
-- ~~~~~~~~~~~~~~~~~~~~~~~~~
-- UniqSet has the following invariant:
--   The keys in the map are the uniques of the values
-- It means that to implement mapUniqSet you have to update
-- both the keys and the values.

newtype UniqSet a = UniqSet {forall a. UniqSet a -> UniqFM a a
getUniqSet' :: UniqFM a a}
                  deriving (Typeable (UniqSet a)
Typeable (UniqSet a) =>
(forall (c :: * -> *).
 (forall d b. Data d => c (d -> b) -> d -> c b)
 -> (forall g. g -> c g) -> UniqSet a -> c (UniqSet a))
-> (forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c (UniqSet a))
-> (UniqSet a -> Constr)
-> (UniqSet a -> DataType)
-> (forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c (UniqSet a)))
-> (forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e))
    -> Maybe (c (UniqSet a)))
-> ((forall b. Data b => b -> b) -> UniqSet a -> UniqSet a)
-> (forall r r'.
    (r -> r' -> r)
    -> r -> (forall d. Data d => d -> r') -> UniqSet a -> r)
-> (forall r r'.
    (r' -> r -> r)
    -> r -> (forall d. Data d => d -> r') -> UniqSet a -> r)
-> (forall u. (forall d. Data d => d -> u) -> UniqSet a -> [u])
-> (forall u.
    Int -> (forall d. Data d => d -> u) -> UniqSet a -> u)
-> (forall (m :: * -> *).
    Monad m =>
    (forall d. Data d => d -> m d) -> UniqSet a -> m (UniqSet a))
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> UniqSet a -> m (UniqSet a))
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> UniqSet a -> m (UniqSet a))
-> Data (UniqSet a)
UniqSet a -> Constr
UniqSet a -> DataType
(forall b. Data b => b -> b) -> UniqSet a -> UniqSet a
forall a. Data a => Typeable (UniqSet a)
forall a. Data a => UniqSet a -> Constr
forall a. Data a => UniqSet a -> DataType
forall a.
Data a =>
(forall b. Data b => b -> b) -> UniqSet a -> UniqSet a
forall a u.
Data a =>
Int -> (forall d. Data d => d -> u) -> UniqSet a -> u
forall a u.
Data a =>
(forall d. Data d => d -> u) -> UniqSet a -> [u]
forall a r r'.
Data a =>
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> UniqSet a -> r
forall a r r'.
Data a =>
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> UniqSet a -> r
forall a (m :: * -> *).
(Data a, Monad m) =>
(forall d. Data d => d -> m d) -> UniqSet a -> m (UniqSet a)
forall a (m :: * -> *).
(Data a, MonadPlus m) =>
(forall d. Data d => d -> m d) -> UniqSet a -> m (UniqSet a)
forall a (c :: * -> *).
Data a =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (UniqSet a)
forall a (c :: * -> *).
Data a =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> UniqSet a -> c (UniqSet a)
forall a (t :: * -> *) (c :: * -> *).
(Data a, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (UniqSet a))
forall a (t :: * -> * -> *) (c :: * -> *).
(Data a, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (UniqSet 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) -> UniqSet a -> u
forall u. (forall d. Data d => d -> u) -> UniqSet a -> [u]
forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> UniqSet a -> r
forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> UniqSet a -> r
forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> UniqSet a -> m (UniqSet a)
forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> UniqSet a -> m (UniqSet a)
forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (UniqSet a)
forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> UniqSet a -> c (UniqSet a)
forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c (UniqSet a))
forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (UniqSet a))
$cgfoldl :: forall a (c :: * -> *).
Data a =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> UniqSet a -> c (UniqSet a)
gfoldl :: forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> UniqSet a -> c (UniqSet a)
$cgunfold :: forall a (c :: * -> *).
Data a =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (UniqSet a)
gunfold :: forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (UniqSet a)
$ctoConstr :: forall a. Data a => UniqSet a -> Constr
toConstr :: UniqSet a -> Constr
$cdataTypeOf :: forall a. Data a => UniqSet a -> DataType
dataTypeOf :: UniqSet a -> DataType
$cdataCast1 :: forall a (t :: * -> *) (c :: * -> *).
(Data a, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (UniqSet a))
dataCast1 :: forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c (UniqSet a))
$cdataCast2 :: forall a (t :: * -> * -> *) (c :: * -> *).
(Data a, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (UniqSet a))
dataCast2 :: forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (UniqSet a))
$cgmapT :: forall a.
Data a =>
(forall b. Data b => b -> b) -> UniqSet a -> UniqSet a
gmapT :: (forall b. Data b => b -> b) -> UniqSet a -> UniqSet a
$cgmapQl :: forall a r r'.
Data a =>
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> UniqSet a -> r
gmapQl :: forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> UniqSet a -> r
$cgmapQr :: forall a r r'.
Data a =>
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> UniqSet a -> r
gmapQr :: forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> UniqSet a -> r
$cgmapQ :: forall a u.
Data a =>
(forall d. Data d => d -> u) -> UniqSet a -> [u]
gmapQ :: forall u. (forall d. Data d => d -> u) -> UniqSet a -> [u]
$cgmapQi :: forall a u.
Data a =>
Int -> (forall d. Data d => d -> u) -> UniqSet a -> u
gmapQi :: forall u. Int -> (forall d. Data d => d -> u) -> UniqSet a -> u
$cgmapM :: forall a (m :: * -> *).
(Data a, Monad m) =>
(forall d. Data d => d -> m d) -> UniqSet a -> m (UniqSet a)
gmapM :: forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> UniqSet a -> m (UniqSet a)
$cgmapMp :: forall a (m :: * -> *).
(Data a, MonadPlus m) =>
(forall d. Data d => d -> m d) -> UniqSet a -> m (UniqSet a)
gmapMp :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> UniqSet a -> m (UniqSet a)
$cgmapMo :: forall a (m :: * -> *).
(Data a, MonadPlus m) =>
(forall d. Data d => d -> m d) -> UniqSet a -> m (UniqSet a)
gmapMo :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> UniqSet a -> m (UniqSet a)
Data, NonEmpty (UniqSet a) -> UniqSet a
UniqSet a -> UniqSet a -> UniqSet a
(UniqSet a -> UniqSet a -> UniqSet a)
-> (NonEmpty (UniqSet a) -> UniqSet a)
-> (forall b. Integral b => b -> UniqSet a -> UniqSet a)
-> Semigroup (UniqSet a)
forall b. Integral b => b -> UniqSet a -> UniqSet a
forall a. NonEmpty (UniqSet a) -> UniqSet a
forall a. UniqSet a -> UniqSet a -> UniqSet a
forall a.
(a -> a -> a)
-> (NonEmpty a -> a)
-> (forall b. Integral b => b -> a -> a)
-> Semigroup a
forall a b. Integral b => b -> UniqSet a -> UniqSet a
$c<> :: forall a. UniqSet a -> UniqSet a -> UniqSet a
<> :: UniqSet a -> UniqSet a -> UniqSet a
$csconcat :: forall a. NonEmpty (UniqSet a) -> UniqSet a
sconcat :: NonEmpty (UniqSet a) -> UniqSet a
$cstimes :: forall a b. Integral b => b -> UniqSet a -> UniqSet a
stimes :: forall b. Integral b => b -> UniqSet a -> UniqSet a
Semi.Semigroup, Semigroup (UniqSet a)
UniqSet a
Semigroup (UniqSet a) =>
UniqSet a
-> (UniqSet a -> UniqSet a -> UniqSet a)
-> ([UniqSet a] -> UniqSet a)
-> Monoid (UniqSet a)
[UniqSet a] -> UniqSet a
UniqSet a -> UniqSet a -> UniqSet a
forall a. Semigroup (UniqSet a)
forall a. UniqSet a
forall a.
Semigroup a =>
a -> (a -> a -> a) -> ([a] -> a) -> Monoid a
forall a. [UniqSet a] -> UniqSet a
forall a. UniqSet a -> UniqSet a -> UniqSet a
$cmempty :: forall a. UniqSet a
mempty :: UniqSet a
$cmappend :: forall a. UniqSet a -> UniqSet a -> UniqSet a
mappend :: UniqSet a -> UniqSet a -> UniqSet a
$cmconcat :: forall a. [UniqSet a] -> UniqSet a
mconcat :: [UniqSet a] -> UniqSet a
Monoid)

emptyUniqSet :: UniqSet a
emptyUniqSet :: forall a. UniqSet a
emptyUniqSet = UniqFM a a -> UniqSet a
forall a. UniqFM a a -> UniqSet a
UniqSet UniqFM a a
forall key elt. UniqFM key elt
emptyUFM

unitUniqSet :: Uniquable a => a -> UniqSet a
unitUniqSet :: forall a. Uniquable a => a -> UniqSet a
unitUniqSet a
x = UniqFM a a -> UniqSet a
forall a. UniqFM a a -> UniqSet a
UniqSet (UniqFM a a -> UniqSet a) -> UniqFM a a -> UniqSet a
forall a b. (a -> b) -> a -> b
$ a -> a -> UniqFM a a
forall key elt. Uniquable key => key -> elt -> UniqFM key elt
unitUFM a
x a
x

mkUniqSet :: Uniquable a => [a]  -> UniqSet a
mkUniqSet :: forall a. Uniquable a => [a] -> UniqSet a
mkUniqSet = (UniqSet a -> a -> UniqSet a) -> UniqSet a -> [a] -> UniqSet a
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' UniqSet a -> a -> UniqSet a
forall a. Uniquable a => UniqSet a -> a -> UniqSet a
addOneToUniqSet UniqSet a
forall a. UniqSet a
emptyUniqSet

addOneToUniqSet :: Uniquable a => UniqSet a -> a -> UniqSet a
addOneToUniqSet :: forall a. Uniquable a => UniqSet a -> a -> UniqSet a
addOneToUniqSet (UniqSet UniqFM a a
set) a
x = UniqFM a a -> UniqSet a
forall a. UniqFM a a -> UniqSet a
UniqSet (UniqFM a a -> a -> a -> UniqFM a a
forall key elt.
Uniquable key =>
UniqFM key elt -> key -> elt -> UniqFM key elt
addToUFM UniqFM a a
set a
x a
x)

addListToUniqSet :: Uniquable a => UniqSet a -> [a] -> UniqSet a
addListToUniqSet :: forall a. Uniquable a => UniqSet a -> [a] -> UniqSet a
addListToUniqSet = (UniqSet a -> a -> UniqSet a) -> UniqSet a -> [a] -> UniqSet a
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' UniqSet a -> a -> UniqSet a
forall a. Uniquable a => UniqSet a -> a -> UniqSet a
addOneToUniqSet

delOneFromUniqSet :: Uniquable a => UniqSet a -> a -> UniqSet a
delOneFromUniqSet :: forall a. Uniquable a => UniqSet a -> a -> UniqSet a
delOneFromUniqSet (UniqSet UniqFM a a
s) a
a = UniqFM a a -> UniqSet a
forall a. UniqFM a a -> UniqSet a
UniqSet (UniqFM a a -> a -> UniqFM a a
forall key elt.
Uniquable key =>
UniqFM key elt -> key -> UniqFM key elt
delFromUFM UniqFM a a
s a
a)

delOneFromUniqSet_Directly :: UniqSet a -> Unique -> UniqSet a
delOneFromUniqSet_Directly :: forall a. UniqSet a -> Unique -> UniqSet a
delOneFromUniqSet_Directly (UniqSet UniqFM a a
s) Unique
u = UniqFM a a -> UniqSet a
forall a. UniqFM a a -> UniqSet a
UniqSet (UniqFM a a -> Unique -> UniqFM a a
forall key elt. UniqFM key elt -> Unique -> UniqFM key elt
delFromUFM_Directly UniqFM a a
s Unique
u)

delListFromUniqSet :: Uniquable a => UniqSet a -> [a] -> UniqSet a
delListFromUniqSet :: forall a. Uniquable a => UniqSet a -> [a] -> UniqSet a
delListFromUniqSet (UniqSet UniqFM a a
s) [a]
l = UniqFM a a -> UniqSet a
forall a. UniqFM a a -> UniqSet a
UniqSet (UniqFM a a -> [a] -> UniqFM a a
forall key elt.
Uniquable key =>
UniqFM key elt -> [key] -> UniqFM key elt
delListFromUFM UniqFM a a
s [a]
l)

delListFromUniqSet_Directly :: UniqSet a -> [Unique] -> UniqSet a
delListFromUniqSet_Directly :: forall a. UniqSet a -> [Unique] -> UniqSet a
delListFromUniqSet_Directly (UniqSet UniqFM a a
s) [Unique]
l =
    UniqFM a a -> UniqSet a
forall a. UniqFM a a -> UniqSet a
UniqSet (UniqFM a a -> [Unique] -> UniqFM a a
forall key elt. UniqFM key elt -> [Unique] -> UniqFM key elt
delListFromUFM_Directly UniqFM a a
s [Unique]
l)

unionUniqSets :: UniqSet a -> UniqSet a -> UniqSet a
unionUniqSets :: forall a. UniqSet a -> UniqSet a -> UniqSet a
unionUniqSets (UniqSet UniqFM a a
s) (UniqSet UniqFM a a
t) = UniqFM a a -> UniqSet a
forall a. UniqFM a a -> UniqSet a
UniqSet (UniqFM a a -> UniqFM a a -> UniqFM a a
forall key elt. UniqFM key elt -> UniqFM key elt -> UniqFM key elt
plusUFM UniqFM a a
s UniqFM a a
t)

unionManyUniqSets :: [UniqSet a] -> UniqSet a
unionManyUniqSets :: forall a. [UniqSet a] -> UniqSet a
unionManyUniqSets = (UniqSet a -> UniqSet a -> UniqSet a)
-> UniqSet a -> [UniqSet a] -> UniqSet a
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' ((UniqSet a -> UniqSet a -> UniqSet a)
-> UniqSet a -> UniqSet a -> UniqSet a
forall a b c. (a -> b -> c) -> b -> a -> c
flip UniqSet a -> UniqSet a -> UniqSet a
forall a. UniqSet a -> UniqSet a -> UniqSet a
unionUniqSets) UniqSet a
forall a. UniqSet a
emptyUniqSet

minusUniqSet  :: UniqSet a -> UniqSet a -> UniqSet a
minusUniqSet :: forall a. UniqSet a -> UniqSet a -> UniqSet a
minusUniqSet (UniqSet UniqFM a a
s) (UniqSet UniqFM a a
t) = UniqFM a a -> UniqSet a
forall a. UniqFM a a -> UniqSet a
UniqSet (UniqFM a a -> UniqFM a a -> UniqFM a a
forall key elt1 elt2.
UniqFM key elt1 -> UniqFM key elt2 -> UniqFM key elt1
minusUFM UniqFM a a
s UniqFM a a
t)

intersectUniqSets :: UniqSet a -> UniqSet a -> UniqSet a
intersectUniqSets :: forall a. UniqSet a -> UniqSet a -> UniqSet a
intersectUniqSets (UniqSet UniqFM a a
s) (UniqSet UniqFM a a
t) = UniqFM a a -> UniqSet a
forall a. UniqFM a a -> UniqSet a
UniqSet (UniqFM a a -> UniqFM a a -> UniqFM a a
forall key elt1 elt2.
UniqFM key elt1 -> UniqFM key elt2 -> UniqFM key elt1
intersectUFM UniqFM a a
s UniqFM a a
t)

disjointUniqSets :: UniqSet a -> UniqSet a -> Bool
disjointUniqSets :: forall a. UniqSet a -> UniqSet a -> Bool
disjointUniqSets (UniqSet UniqFM a a
s) (UniqSet UniqFM a a
t) = UniqFM a a -> UniqFM a a -> Bool
forall key elt1 elt2. UniqFM key elt1 -> UniqFM key elt2 -> Bool
disjointUFM UniqFM a a
s UniqFM a a
t

restrictUniqSetToUFM :: UniqSet key -> UniqFM key b -> UniqSet key
restrictUniqSetToUFM :: forall key b. UniqSet key -> UniqFM key b -> UniqSet key
restrictUniqSetToUFM (UniqSet UniqFM key key
s) UniqFM key b
m = UniqFM key key -> UniqSet key
forall a. UniqFM a a -> UniqSet a
UniqSet (UniqFM key key -> UniqFM key b -> UniqFM key key
forall key elt1 elt2.
UniqFM key elt1 -> UniqFM key elt2 -> UniqFM key elt1
intersectUFM UniqFM key key
s UniqFM key b
m)

uniqSetMinusUFM :: UniqSet key -> UniqFM key b -> UniqSet key
uniqSetMinusUFM :: forall key b. UniqSet key -> UniqFM key b -> UniqSet key
uniqSetMinusUFM (UniqSet UniqFM key key
s) UniqFM key b
t = UniqFM key key -> UniqSet key
forall a. UniqFM a a -> UniqSet a
UniqSet (UniqFM key key -> UniqFM key b -> UniqFM key key
forall key elt1 elt2.
UniqFM key elt1 -> UniqFM key elt2 -> UniqFM key elt1
minusUFM UniqFM key key
s UniqFM key b
t)

uniqSetMinusUDFM :: UniqSet key -> UniqDFM key b -> UniqSet key
uniqSetMinusUDFM :: forall key b. UniqSet key -> UniqDFM key b -> UniqSet key
uniqSetMinusUDFM (UniqSet UniqFM key key
s) UniqDFM key b
t = UniqFM key key -> UniqSet key
forall a. UniqFM a a -> UniqSet a
UniqSet (UniqFM key key -> UniqDFM key b -> UniqFM key key
forall key elt1 elt2.
UniqFM key elt1 -> UniqDFM key elt2 -> UniqFM key elt1
ufmMinusUDFM UniqFM key key
s UniqDFM key b
t)

elementOfUniqSet :: Uniquable a => a -> UniqSet a -> Bool
elementOfUniqSet :: forall a. Uniquable a => a -> UniqSet a -> Bool
elementOfUniqSet a
a (UniqSet UniqFM a a
s) = a -> UniqFM a a -> Bool
forall key elt. Uniquable key => key -> UniqFM key elt -> Bool
elemUFM a
a UniqFM a a
s

elemUniqSet_Directly :: Unique -> UniqSet a -> Bool
elemUniqSet_Directly :: forall a. Unique -> UniqSet a -> Bool
elemUniqSet_Directly Unique
a (UniqSet UniqFM a a
s) = Unique -> UniqFM a a -> Bool
forall key elt. Unique -> UniqFM key elt -> Bool
elemUFM_Directly Unique
a UniqFM a a
s

filterUniqSet :: (a -> Bool) -> UniqSet a -> UniqSet a
filterUniqSet :: forall a. (a -> Bool) -> UniqSet a -> UniqSet a
filterUniqSet a -> Bool
p (UniqSet UniqFM a a
s) = UniqFM a a -> UniqSet a
forall a. UniqFM a a -> UniqSet a
UniqSet ((a -> Bool) -> UniqFM a a -> UniqFM a a
forall elt key. (elt -> Bool) -> UniqFM key elt -> UniqFM key elt
filterUFM a -> Bool
p UniqFM a a
s)

filterUniqSet_Directly :: (Unique -> elt -> Bool) -> UniqSet elt -> UniqSet elt
filterUniqSet_Directly :: forall elt. (Unique -> elt -> Bool) -> UniqSet elt -> UniqSet elt
filterUniqSet_Directly Unique -> elt -> Bool
f (UniqSet UniqFM elt elt
s) = UniqFM elt elt -> UniqSet elt
forall a. UniqFM a a -> UniqSet a
UniqSet ((Unique -> elt -> Bool) -> UniqFM elt elt -> UniqFM elt elt
forall elt key.
(Unique -> elt -> Bool) -> UniqFM key elt -> UniqFM key elt
filterUFM_Directly Unique -> elt -> Bool
f UniqFM elt elt
s)

partitionUniqSet :: (a -> Bool) -> UniqSet a -> (UniqSet a, UniqSet a)
partitionUniqSet :: forall a. (a -> Bool) -> UniqSet a -> (UniqSet a, UniqSet a)
partitionUniqSet a -> Bool
p (UniqSet UniqFM a a
s) = (UniqFM a a, UniqFM a a) -> (UniqSet a, UniqSet a)
forall a b. Coercible a b => a -> b
coerce ((a -> Bool) -> UniqFM a a -> (UniqFM a a, UniqFM a a)
forall elt key.
(elt -> Bool) -> UniqFM key elt -> (UniqFM key elt, UniqFM key elt)
partitionUFM a -> Bool
p UniqFM a a
s)

uniqSetAny :: (a -> Bool) -> UniqSet a -> Bool
uniqSetAny :: forall a. (a -> Bool) -> UniqSet a -> Bool
uniqSetAny a -> Bool
p (UniqSet UniqFM a a
s) = (a -> Bool) -> UniqFM a a -> Bool
forall elt key. (elt -> Bool) -> UniqFM key elt -> Bool
anyUFM a -> Bool
p UniqFM a a
s

uniqSetAll :: (a -> Bool) -> UniqSet a -> Bool
uniqSetAll :: forall a. (a -> Bool) -> UniqSet a -> Bool
uniqSetAll a -> Bool
p (UniqSet UniqFM a a
s) = (a -> Bool) -> UniqFM a a -> Bool
forall elt key. (elt -> Bool) -> UniqFM key elt -> Bool
allUFM a -> Bool
p UniqFM a a
s

sizeUniqSet :: UniqSet a -> Int
sizeUniqSet :: forall a. UniqSet a -> Int
sizeUniqSet (UniqSet UniqFM a a
s) = UniqFM a a -> Int
forall key elt. UniqFM key elt -> Int
sizeUFM UniqFM a a
s

isEmptyUniqSet :: UniqSet a -> Bool
isEmptyUniqSet :: forall a. UniqSet a -> Bool
isEmptyUniqSet (UniqSet UniqFM a a
s) = UniqFM a a -> Bool
forall key elt. UniqFM key elt -> Bool
isNullUFM UniqFM a a
s

-- | What's the point you might ask? We might have changed an object
-- without it's key changing. In which case this lookup makes sense.
lookupUniqSet :: Uniquable key => UniqSet key -> key -> Maybe key
lookupUniqSet :: forall key. Uniquable key => UniqSet key -> key -> Maybe key
lookupUniqSet (UniqSet UniqFM key key
s) key
k = UniqFM key key -> key -> Maybe key
forall key elt. Uniquable key => UniqFM key elt -> key -> Maybe elt
lookupUFM UniqFM key key
s key
k

lookupUniqSet_Directly :: UniqSet a -> Unique -> Maybe a
lookupUniqSet_Directly :: forall a. UniqSet a -> Unique -> Maybe a
lookupUniqSet_Directly (UniqSet UniqFM a a
s) Unique
k = UniqFM a a -> Unique -> Maybe a
forall key elt. UniqFM key elt -> Unique -> Maybe elt
lookupUFM_Directly UniqFM a a
s Unique
k

-- See Note [Deterministic UniqFM] to learn about nondeterminism.
-- If you use this please provide a justification why it doesn't introduce
-- nondeterminism.
nonDetEltsUniqSet :: UniqSet elt -> [elt]
nonDetEltsUniqSet :: forall elt. UniqSet elt -> [elt]
nonDetEltsUniqSet = UniqFM elt elt -> [elt]
forall key elt. UniqFM key elt -> [elt]
nonDetEltsUFM (UniqFM elt elt -> [elt])
-> (UniqSet elt -> UniqFM elt elt) -> UniqSet elt -> [elt]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. UniqSet elt -> UniqFM elt elt
forall a. UniqSet a -> UniqFM a a
getUniqSet'

-- See Note [Deterministic UniqFM] to learn about nondeterminism.
-- If you use this please provide a justification why it doesn't introduce
-- nondeterminism.
nonDetKeysUniqSet :: UniqSet elt -> [Unique]
nonDetKeysUniqSet :: forall elt. UniqSet elt -> [Unique]
nonDetKeysUniqSet = UniqFM elt elt -> [Unique]
forall key elt. UniqFM key elt -> [Unique]
nonDetKeysUFM (UniqFM elt elt -> [Unique])
-> (UniqSet elt -> UniqFM elt elt) -> UniqSet elt -> [Unique]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. UniqSet elt -> UniqFM elt elt
forall a. UniqSet a -> UniqFM a a
getUniqSet'

-- See Note [Deterministic UniqFM] to learn about nondeterminism.
-- If you use this please provide a justification why it doesn't introduce
-- nondeterminism.
nonDetStrictFoldUniqSet :: (elt -> a -> a) -> a -> UniqSet elt -> a
nonDetStrictFoldUniqSet :: forall elt a. (elt -> a -> a) -> a -> UniqSet elt -> a
nonDetStrictFoldUniqSet elt -> a -> a
c a
n (UniqSet UniqFM elt elt
s) = (elt -> a -> a) -> a -> UniqFM elt elt -> a
forall elt a key. (elt -> a -> a) -> a -> UniqFM key elt -> a
nonDetStrictFoldUFM elt -> a -> a
c a
n UniqFM elt elt
s

-- See Note [UniqSet invariant]
mapUniqSet :: Uniquable b => (a -> b) -> UniqSet a -> UniqSet b
mapUniqSet :: forall b a. Uniquable b => (a -> b) -> UniqSet a -> UniqSet b
mapUniqSet a -> b
f = [b] -> UniqSet b
forall a. Uniquable a => [a] -> UniqSet a
mkUniqSet ([b] -> UniqSet b) -> (UniqSet a -> [b]) -> UniqSet a -> UniqSet b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> b) -> [a] -> [b]
forall a b. (a -> b) -> [a] -> [b]
map a -> b
f ([a] -> [b]) -> (UniqSet a -> [a]) -> UniqSet a -> [b]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. UniqSet a -> [a]
forall elt. UniqSet elt -> [elt]
nonDetEltsUniqSet

-- Two 'UniqSet's are considered equal if they contain the same
-- uniques.
instance Eq (UniqSet a) where
  UniqSet UniqFM a a
a == :: UniqSet a -> UniqSet a -> Bool
== UniqSet UniqFM a a
b = UniqFM a a -> UniqFM a a -> Bool
forall key elt1 elt2. UniqFM key elt1 -> UniqFM key elt2 -> Bool
equalKeysUFM UniqFM a a
a UniqFM a a
b

getUniqSet :: UniqSet a -> UniqFM a a
getUniqSet :: forall a. UniqSet a -> UniqFM a a
getUniqSet = UniqSet a -> UniqFM a a
forall a. UniqSet a -> UniqFM a a
getUniqSet'

-- | 'unsafeUFMToUniqSet' converts a @'UniqFM' a@ into a @'UniqSet' a@
-- assuming, without checking, that it maps each 'Unique' to a value
-- that has that 'Unique'. See Note [UniqSet invariant].
unsafeUFMToUniqSet :: UniqFM  a a -> UniqSet a
unsafeUFMToUniqSet :: forall a. UniqFM a a -> UniqSet a
unsafeUFMToUniqSet = UniqFM a a -> UniqSet a
forall a. UniqFM a a -> UniqSet a
UniqSet

instance Outputable a => Outputable (UniqSet a) where
    ppr :: UniqSet a -> SDoc
ppr = (a -> SDoc) -> UniqSet a -> SDoc
forall a. (a -> SDoc) -> UniqSet a -> SDoc
pprUniqSet a -> SDoc
forall a. Outputable a => a -> SDoc
ppr

pprUniqSet :: (a -> SDoc) -> UniqSet a -> SDoc
-- It's OK to use nonDetUFMToList here because we only use it for
-- pretty-printing.
pprUniqSet :: forall a. (a -> SDoc) -> UniqSet a -> SDoc
pprUniqSet a -> SDoc
f = SDoc -> SDoc
forall doc. IsLine doc => doc -> doc
braces (SDoc -> SDoc) -> (UniqSet a -> SDoc) -> UniqSet a -> SDoc
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> SDoc) -> [a] -> SDoc
forall a. (a -> SDoc) -> [a] -> SDoc
pprWithCommas a -> SDoc
f ([a] -> SDoc) -> (UniqSet a -> [a]) -> UniqSet a -> SDoc
forall b c a. (b -> c) -> (a -> b) -> a -> c
. UniqSet a -> [a]
forall elt. UniqSet elt -> [elt]
nonDetEltsUniqSet