{-
(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 UniqSet (
        -- * 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,
        intersectUniqSets,
        restrictUniqSetToUFM,
        uniqSetAny, uniqSetAll,
        elementOfUniqSet,
        elemUniqSet_Directly,
        filterUniqSet,
        filterUniqSet_Directly,
        sizeUniqSet,
        isEmptyUniqSet,
        lookupUniqSet,
        lookupUniqSet_Directly,
        partitionUniqSet,
        mapUniqSet,
        unsafeUFMToUniqSet,
        nonDetEltsUniqSet,
        nonDetKeysUniqSet,
        nonDetFoldUniqSet,
        nonDetFoldUniqSet_Directly
    ) where

import GhcPrelude

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

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

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

mkUniqSet :: Uniquable a => [a]  -> UniqSet a
mkUniqSet :: [a] -> UniqSet a
mkUniqSet = (UniqSet a -> a -> UniqSet a) -> UniqSet a -> [a] -> UniqSet a
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 :: UniqSet a -> a -> UniqSet a
addOneToUniqSet (UniqSet UniqFM a
set) a
x = UniqFM a -> UniqSet a
forall a. UniqFM a -> UniqSet a
UniqSet (UniqFM a -> a -> a -> UniqFM a
forall key elt.
Uniquable key =>
UniqFM elt -> key -> elt -> UniqFM elt
addToUFM UniqFM a
set a
x a
x)

addListToUniqSet :: Uniquable a => UniqSet a -> [a] -> UniqSet a
addListToUniqSet :: UniqSet a -> [a] -> UniqSet a
addListToUniqSet = (UniqSet a -> a -> UniqSet a) -> UniqSet a -> [a] -> UniqSet a
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 :: UniqSet a -> a -> UniqSet a
delOneFromUniqSet (UniqSet UniqFM a
s) a
a = UniqFM a -> UniqSet a
forall a. UniqFM a -> UniqSet a
UniqSet (UniqFM a -> a -> UniqFM a
forall key elt. Uniquable key => UniqFM elt -> key -> UniqFM elt
delFromUFM UniqFM a
s a
a)

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

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

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

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

unionManyUniqSets :: [UniqSet a] -> UniqSet a
unionManyUniqSets :: [UniqSet a] -> UniqSet a
unionManyUniqSets = (UniqSet a -> UniqSet a -> UniqSet a)
-> UniqSet a -> [UniqSet a] -> UniqSet a
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 :: UniqSet a -> UniqSet a -> UniqSet a
minusUniqSet (UniqSet UniqFM a
s) (UniqSet UniqFM a
t) = UniqFM a -> UniqSet a
forall a. UniqFM a -> UniqSet a
UniqSet (UniqFM a -> UniqFM a -> UniqFM a
forall elt1 elt2. UniqFM elt1 -> UniqFM elt2 -> UniqFM elt1
minusUFM UniqFM a
s UniqFM a
t)

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

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

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

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

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

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

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

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

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

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

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

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

lookupUniqSet :: Uniquable a => UniqSet b -> a -> Maybe b
lookupUniqSet :: UniqSet b -> a -> Maybe b
lookupUniqSet (UniqSet UniqFM b
s) a
k = UniqFM b -> a -> Maybe b
forall key elt. Uniquable key => UniqFM elt -> key -> Maybe elt
lookupUFM UniqFM b
s a
k

lookupUniqSet_Directly :: UniqSet a -> Unique -> Maybe a
lookupUniqSet_Directly :: UniqSet a -> Unique -> Maybe a
lookupUniqSet_Directly (UniqSet UniqFM a
s) Unique
k = UniqFM a -> Unique -> Maybe a
forall elt. UniqFM elt -> Unique -> Maybe elt
lookupUFM_Directly UniqFM 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 :: UniqSet elt -> [elt]
nonDetEltsUniqSet = UniqFM elt -> [elt]
forall elt. UniqFM elt -> [elt]
nonDetEltsUFM (UniqFM elt -> [elt])
-> (UniqSet elt -> UniqFM elt) -> UniqSet elt -> [elt]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. UniqSet elt -> UniqFM elt
forall a. UniqSet a -> UniqFM 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 :: UniqSet elt -> [Unique]
nonDetKeysUniqSet = UniqFM elt -> [Unique]
forall elt. UniqFM elt -> [Unique]
nonDetKeysUFM (UniqFM elt -> [Unique])
-> (UniqSet elt -> UniqFM elt) -> UniqSet elt -> [Unique]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. UniqSet elt -> UniqFM elt
forall a. UniqSet a -> UniqFM a
getUniqSet'

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

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

-- See Note [UniqSet invariant]
mapUniqSet :: Uniquable b => (a -> b) -> UniqSet a -> UniqSet b
mapUniqSet :: (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 == :: UniqSet a -> UniqSet a -> Bool
== UniqSet UniqFM a
b = UniqFM a -> UniqFM a -> Bool
forall a b. UniqFM a -> UniqFM b -> Bool
equalKeysUFM UniqFM a
a UniqFM a
b

getUniqSet :: UniqSet a -> UniqFM a
getUniqSet :: UniqSet a -> UniqFM a
getUniqSet = UniqSet a -> UniqFM a
forall a. UniqSet a -> UniqFM 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 -> UniqSet a
unsafeUFMToUniqSet :: UniqFM a -> UniqSet a
unsafeUFMToUniqSet = UniqFM a -> UniqSet a
forall a. UniqFM 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 :: (a -> SDoc) -> UniqSet a -> SDoc
pprUniqSet a -> SDoc
f = SDoc -> SDoc
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