-- (c) Bartosz Nitka, Facebook, 2015

-- |
-- Specialised deterministic sets, for things with @Uniques@
--
-- Based on 'UniqDFM's (as you would expect).
-- See Note [Deterministic UniqFM] in UniqDFM for explanation why we need it.
--
-- Basically, the things need to be in class 'Uniquable'.

{-# LANGUAGE GeneralizedNewtypeDeriving #-}
{-# LANGUAGE DeriveDataTypeable #-}

module UniqDSet (
        -- * Unique set type
        UniqDSet,    -- type synonym for UniqFM a
        getUniqDSet,
        pprUniqDSet,

        -- ** Manipulating these sets
        delOneFromUniqDSet, delListFromUniqDSet,
        emptyUniqDSet,
        unitUniqDSet,
        mkUniqDSet,
        addOneToUniqDSet, addListToUniqDSet,
        unionUniqDSets, unionManyUniqDSets,
        minusUniqDSet, uniqDSetMinusUniqSet,
        intersectUniqDSets, uniqDSetIntersectUniqSet,
        foldUniqDSet,
        elementOfUniqDSet,
        filterUniqDSet,
        sizeUniqDSet,
        isEmptyUniqDSet,
        lookupUniqDSet,
        uniqDSetToList,
        partitionUniqDSet,
        mapUniqDSet
    ) where

import GhcPrelude

import Outputable
import UniqDFM
import UniqSet
import Unique

import Data.Coerce
import Data.Data
import qualified Data.Semigroup as Semi

-- See Note [UniqSet invariant] in UniqSet.hs for why we want a newtype here.
-- Beyond preserving invariants, we may also want to 'override' typeclass
-- instances.

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

emptyUniqDSet :: UniqDSet a
emptyUniqDSet :: UniqDSet a
emptyUniqDSet = UniqDFM a -> UniqDSet a
forall a. UniqDFM a -> UniqDSet a
UniqDSet UniqDFM a
forall elt. UniqDFM elt
emptyUDFM

unitUniqDSet :: Uniquable a => a -> UniqDSet a
unitUniqDSet :: a -> UniqDSet a
unitUniqDSet a
x = UniqDFM a -> UniqDSet a
forall a. UniqDFM a -> UniqDSet a
UniqDSet (a -> a -> UniqDFM a
forall key elt. Uniquable key => key -> elt -> UniqDFM elt
unitUDFM a
x a
x)

mkUniqDSet :: Uniquable a => [a] -> UniqDSet a
mkUniqDSet :: [a] -> UniqDSet a
mkUniqDSet = (UniqDSet a -> a -> UniqDSet a) -> UniqDSet a -> [a] -> UniqDSet a
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' UniqDSet a -> a -> UniqDSet a
forall a. Uniquable a => UniqDSet a -> a -> UniqDSet a
addOneToUniqDSet UniqDSet a
forall a. UniqDSet a
emptyUniqDSet

-- The new element always goes to the right of existing ones.
addOneToUniqDSet :: Uniquable a => UniqDSet a -> a -> UniqDSet a
addOneToUniqDSet :: UniqDSet a -> a -> UniqDSet a
addOneToUniqDSet (UniqDSet UniqDFM a
set) a
x = UniqDFM a -> UniqDSet a
forall a. UniqDFM a -> UniqDSet a
UniqDSet (UniqDFM a -> a -> a -> UniqDFM a
forall key elt.
Uniquable key =>
UniqDFM elt -> key -> elt -> UniqDFM elt
addToUDFM UniqDFM a
set a
x a
x)

addListToUniqDSet :: Uniquable a => UniqDSet a -> [a] -> UniqDSet a
addListToUniqDSet :: UniqDSet a -> [a] -> UniqDSet a
addListToUniqDSet = (UniqDSet a -> a -> UniqDSet a) -> UniqDSet a -> [a] -> UniqDSet a
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' UniqDSet a -> a -> UniqDSet a
forall a. Uniquable a => UniqDSet a -> a -> UniqDSet a
addOneToUniqDSet

delOneFromUniqDSet :: Uniquable a => UniqDSet a -> a -> UniqDSet a
delOneFromUniqDSet :: UniqDSet a -> a -> UniqDSet a
delOneFromUniqDSet (UniqDSet UniqDFM a
s) = UniqDFM a -> UniqDSet a
forall a. UniqDFM a -> UniqDSet a
UniqDSet (UniqDFM a -> UniqDSet a) -> (a -> UniqDFM a) -> a -> UniqDSet a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. UniqDFM a -> a -> UniqDFM a
forall key elt. Uniquable key => UniqDFM elt -> key -> UniqDFM elt
delFromUDFM UniqDFM a
s

delListFromUniqDSet :: Uniquable a => UniqDSet a -> [a] -> UniqDSet a
delListFromUniqDSet :: UniqDSet a -> [a] -> UniqDSet a
delListFromUniqDSet (UniqDSet UniqDFM a
s) = UniqDFM a -> UniqDSet a
forall a. UniqDFM a -> UniqDSet a
UniqDSet (UniqDFM a -> UniqDSet a)
-> ([a] -> UniqDFM a) -> [a] -> UniqDSet a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. UniqDFM a -> [a] -> UniqDFM a
forall key elt.
Uniquable key =>
UniqDFM elt -> [key] -> UniqDFM elt
delListFromUDFM UniqDFM a
s

unionUniqDSets :: UniqDSet a -> UniqDSet a -> UniqDSet a
unionUniqDSets :: UniqDSet a -> UniqDSet a -> UniqDSet a
unionUniqDSets (UniqDSet UniqDFM a
s) (UniqDSet UniqDFM a
t) = UniqDFM a -> UniqDSet a
forall a. UniqDFM a -> UniqDSet a
UniqDSet (UniqDFM a -> UniqDFM a -> UniqDFM a
forall elt. UniqDFM elt -> UniqDFM elt -> UniqDFM elt
plusUDFM UniqDFM a
s UniqDFM a
t)

unionManyUniqDSets :: [UniqDSet a] -> UniqDSet a
unionManyUniqDSets :: [UniqDSet a] -> UniqDSet a
unionManyUniqDSets [] = UniqDSet a
forall a. UniqDSet a
emptyUniqDSet
unionManyUniqDSets [UniqDSet a]
sets = (UniqDSet a -> UniqDSet a -> UniqDSet a)
-> [UniqDSet a] -> UniqDSet a
forall (t :: * -> *) a. Foldable t => (a -> a -> a) -> t a -> a
foldr1 UniqDSet a -> UniqDSet a -> UniqDSet a
forall a. UniqDSet a -> UniqDSet a -> UniqDSet a
unionUniqDSets [UniqDSet a]
sets

minusUniqDSet :: UniqDSet a -> UniqDSet a -> UniqDSet a
minusUniqDSet :: UniqDSet a -> UniqDSet a -> UniqDSet a
minusUniqDSet (UniqDSet UniqDFM a
s) (UniqDSet UniqDFM a
t) = UniqDFM a -> UniqDSet a
forall a. UniqDFM a -> UniqDSet a
UniqDSet (UniqDFM a -> UniqDFM a -> UniqDFM a
forall elt1 elt2. UniqDFM elt1 -> UniqDFM elt2 -> UniqDFM elt1
minusUDFM UniqDFM a
s UniqDFM a
t)

uniqDSetMinusUniqSet :: UniqDSet a -> UniqSet b -> UniqDSet a
uniqDSetMinusUniqSet :: UniqDSet a -> UniqSet b -> UniqDSet a
uniqDSetMinusUniqSet UniqDSet a
xs UniqSet b
ys
  = UniqDFM a -> UniqDSet a
forall a. UniqDFM a -> UniqDSet a
UniqDSet (UniqDFM a -> UniqFM b -> UniqDFM a
forall elt1 elt2. UniqDFM elt1 -> UniqFM elt2 -> UniqDFM elt1
udfmMinusUFM (UniqDSet a -> UniqDFM a
forall a. UniqDSet a -> UniqDFM a
getUniqDSet UniqDSet a
xs) (UniqSet b -> UniqFM b
forall a. UniqSet a -> UniqFM a
getUniqSet UniqSet b
ys))

intersectUniqDSets :: UniqDSet a -> UniqDSet a -> UniqDSet a
intersectUniqDSets :: UniqDSet a -> UniqDSet a -> UniqDSet a
intersectUniqDSets (UniqDSet UniqDFM a
s) (UniqDSet UniqDFM a
t) = UniqDFM a -> UniqDSet a
forall a. UniqDFM a -> UniqDSet a
UniqDSet (UniqDFM a -> UniqDFM a -> UniqDFM a
forall elt. UniqDFM elt -> UniqDFM elt -> UniqDFM elt
intersectUDFM UniqDFM a
s UniqDFM a
t)

uniqDSetIntersectUniqSet :: UniqDSet a -> UniqSet b -> UniqDSet a
uniqDSetIntersectUniqSet :: UniqDSet a -> UniqSet b -> UniqDSet a
uniqDSetIntersectUniqSet UniqDSet a
xs UniqSet b
ys
  = UniqDFM a -> UniqDSet a
forall a. UniqDFM a -> UniqDSet a
UniqDSet (UniqDFM a -> UniqFM b -> UniqDFM a
forall elt1 elt2. UniqDFM elt1 -> UniqFM elt2 -> UniqDFM elt1
udfmIntersectUFM (UniqDSet a -> UniqDFM a
forall a. UniqDSet a -> UniqDFM a
getUniqDSet UniqDSet a
xs) (UniqSet b -> UniqFM b
forall a. UniqSet a -> UniqFM a
getUniqSet UniqSet b
ys))

foldUniqDSet :: (a -> b -> b) -> b -> UniqDSet a -> b
foldUniqDSet :: (a -> b -> b) -> b -> UniqDSet a -> b
foldUniqDSet a -> b -> b
c b
n (UniqDSet UniqDFM a
s) = (a -> b -> b) -> b -> UniqDFM a -> b
forall elt a. (elt -> a -> a) -> a -> UniqDFM elt -> a
foldUDFM a -> b -> b
c b
n UniqDFM a
s

elementOfUniqDSet :: Uniquable a => a -> UniqDSet a -> Bool
elementOfUniqDSet :: a -> UniqDSet a -> Bool
elementOfUniqDSet a
k = a -> UniqDFM a -> Bool
forall key elt. Uniquable key => key -> UniqDFM elt -> Bool
elemUDFM a
k (UniqDFM a -> Bool)
-> (UniqDSet a -> UniqDFM a) -> UniqDSet a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. UniqDSet a -> UniqDFM a
forall a. UniqDSet a -> UniqDFM a
getUniqDSet

filterUniqDSet :: (a -> Bool) -> UniqDSet a -> UniqDSet a
filterUniqDSet :: (a -> Bool) -> UniqDSet a -> UniqDSet a
filterUniqDSet a -> Bool
p (UniqDSet UniqDFM a
s) = UniqDFM a -> UniqDSet a
forall a. UniqDFM a -> UniqDSet a
UniqDSet ((a -> Bool) -> UniqDFM a -> UniqDFM a
forall elt. (elt -> Bool) -> UniqDFM elt -> UniqDFM elt
filterUDFM a -> Bool
p UniqDFM a
s)

sizeUniqDSet :: UniqDSet a -> Int
sizeUniqDSet :: UniqDSet a -> Int
sizeUniqDSet = UniqDFM a -> Int
forall elt. UniqDFM elt -> Int
sizeUDFM (UniqDFM a -> Int)
-> (UniqDSet a -> UniqDFM a) -> UniqDSet a -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. UniqDSet a -> UniqDFM a
forall a. UniqDSet a -> UniqDFM a
getUniqDSet

isEmptyUniqDSet :: UniqDSet a -> Bool
isEmptyUniqDSet :: UniqDSet a -> Bool
isEmptyUniqDSet = UniqDFM a -> Bool
forall elt. UniqDFM elt -> Bool
isNullUDFM (UniqDFM a -> Bool)
-> (UniqDSet a -> UniqDFM a) -> UniqDSet a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. UniqDSet a -> UniqDFM a
forall a. UniqDSet a -> UniqDFM a
getUniqDSet

lookupUniqDSet :: Uniquable a => UniqDSet a -> a -> Maybe a
lookupUniqDSet :: UniqDSet a -> a -> Maybe a
lookupUniqDSet = UniqDFM a -> a -> Maybe a
forall key elt. Uniquable key => UniqDFM elt -> key -> Maybe elt
lookupUDFM (UniqDFM a -> a -> Maybe a)
-> (UniqDSet a -> UniqDFM a) -> UniqDSet a -> a -> Maybe a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. UniqDSet a -> UniqDFM a
forall a. UniqDSet a -> UniqDFM a
getUniqDSet

uniqDSetToList :: UniqDSet a -> [a]
uniqDSetToList :: UniqDSet a -> [a]
uniqDSetToList = UniqDFM a -> [a]
forall elt. UniqDFM elt -> [elt]
eltsUDFM (UniqDFM a -> [a])
-> (UniqDSet a -> UniqDFM a) -> UniqDSet a -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. UniqDSet a -> UniqDFM a
forall a. UniqDSet a -> UniqDFM a
getUniqDSet

partitionUniqDSet :: (a -> Bool) -> UniqDSet a -> (UniqDSet a, UniqDSet a)
partitionUniqDSet :: (a -> Bool) -> UniqDSet a -> (UniqDSet a, UniqDSet a)
partitionUniqDSet a -> Bool
p = (UniqDFM a, UniqDFM a) -> (UniqDSet a, UniqDSet a)
coerce ((UniqDFM a, UniqDFM a) -> (UniqDSet a, UniqDSet a))
-> (UniqDSet a -> (UniqDFM a, UniqDFM a))
-> UniqDSet a
-> (UniqDSet a, UniqDSet a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Bool) -> UniqDFM a -> (UniqDFM a, UniqDFM a)
forall elt.
(elt -> Bool) -> UniqDFM elt -> (UniqDFM elt, UniqDFM elt)
partitionUDFM a -> Bool
p (UniqDFM a -> (UniqDFM a, UniqDFM a))
-> (UniqDSet a -> UniqDFM a)
-> UniqDSet a
-> (UniqDFM a, UniqDFM a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. UniqDSet a -> UniqDFM a
forall a. UniqDSet a -> UniqDFM a
getUniqDSet

-- See Note [UniqSet invariant] in UniqSet.hs
mapUniqDSet :: Uniquable b => (a -> b) -> UniqDSet a -> UniqDSet b
mapUniqDSet :: (a -> b) -> UniqDSet a -> UniqDSet b
mapUniqDSet a -> b
f = [b] -> UniqDSet b
forall a. Uniquable a => [a] -> UniqDSet a
mkUniqDSet ([b] -> UniqDSet b)
-> (UniqDSet a -> [b]) -> UniqDSet a -> UniqDSet 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]) -> (UniqDSet a -> [a]) -> UniqDSet a -> [b]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. UniqDSet a -> [a]
forall a. UniqDSet a -> [a]
uniqDSetToList

-- Two 'UniqDSet's are considered equal if they contain the same
-- uniques.
instance Eq (UniqDSet a) where
  UniqDSet UniqDFM a
a == :: UniqDSet a -> UniqDSet a -> Bool
== UniqDSet UniqDFM a
b = UniqDFM a -> UniqDFM a -> Bool
forall a b. UniqDFM a -> UniqDFM b -> Bool
equalKeysUDFM UniqDFM a
a UniqDFM a
b

getUniqDSet :: UniqDSet a -> UniqDFM a
getUniqDSet :: UniqDSet a -> UniqDFM a
getUniqDSet = UniqDSet a -> UniqDFM a
forall a. UniqDSet a -> UniqDFM a
getUniqDSet'

instance Outputable a => Outputable (UniqDSet a) where
  ppr :: UniqDSet a -> SDoc
ppr = (a -> SDoc) -> UniqDSet a -> SDoc
forall a. (a -> SDoc) -> UniqDSet a -> SDoc
pprUniqDSet a -> SDoc
forall a. Outputable a => a -> SDoc
ppr

pprUniqDSet :: (a -> SDoc) -> UniqDSet a -> SDoc
pprUniqDSet :: (a -> SDoc) -> UniqDSet a -> SDoc
pprUniqDSet a -> SDoc
f = SDoc -> SDoc
braces (SDoc -> SDoc) -> (UniqDSet a -> SDoc) -> UniqDSet 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) -> (UniqDSet a -> [a]) -> UniqDSet a -> SDoc
forall b c a. (b -> c) -> (a -> b) -> a -> c
. UniqDSet a -> [a]
forall a. UniqDSet a -> [a]
uniqDSetToList