-- (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 "GHC.Types.Unique.DFM" for explanation why we need it.
--
-- Basically, the things need to be in class 'Uniquable'.

{-# LANGUAGE DeriveDataTypeable #-}

module GHC.Types.Unique.DSet (
        -- * 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,
        nonDetStrictFoldUniqDSet,
        elementOfUniqDSet,
        filterUniqDSet,
        sizeUniqDSet,
        isEmptyUniqDSet,
        lookupUniqDSet,
        uniqDSetToList,
        partitionUniqDSet,
        mapUniqDSet, strictFoldUniqDSet, mapMUniqDSet
    ) where

import GHC.Prelude

import GHC.Utils.Outputable
import GHC.Types.Unique.DFM
import GHC.Types.Unique.Set
import GHC.Types.Unique

import Data.Coerce
import Data.Data

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

newtype UniqDSet a = UniqDSet {forall a. UniqDSet a -> UniqDFM a a
getUniqDSet' :: UniqDFM a a}
                   deriving (Typeable (UniqDSet a)
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 -> Constr
UniqDSet a -> DataType
(forall b. Data b => b -> b) -> UniqDSet a -> UniqDSet a
forall a. Data a => Typeable (UniqDSet a)
forall a. Data a => UniqDSet a -> Constr
forall a. Data a => UniqDSet a -> DataType
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))
$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)
gfoldl :: forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> UniqDSet a -> 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)
gunfold :: forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (UniqDSet a)
$ctoConstr :: forall a. Data a => UniqDSet a -> Constr
toConstr :: UniqDSet a -> Constr
$cdataTypeOf :: forall a. Data a => UniqDSet a -> DataType
dataTypeOf :: UniqDSet a -> DataType
$cdataCast1 :: forall a (t :: * -> *) (c :: * -> *).
(Data a, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (UniqDSet a))
dataCast1 :: forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> 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))
dataCast2 :: forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (UniqDSet a))
$cgmapT :: forall a.
Data a =>
(forall b. Data b => b -> b) -> UniqDSet a -> UniqDSet a
gmapT :: (forall b. Data b => b -> b) -> UniqDSet a -> UniqDSet a
$cgmapQl :: forall a r r'.
Data a =>
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> UniqDSet a -> r
gmapQl :: forall r r'.
(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
gmapQr :: forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> UniqDSet a -> r
$cgmapQ :: forall a u.
Data a =>
(forall d. Data d => d -> u) -> UniqDSet a -> [u]
gmapQ :: forall u. (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
gmapQi :: forall u. Int -> (forall d. Data d => d -> u) -> UniqDSet a -> u
$cgmapM :: forall a (m :: * -> *).
(Data a, Monad m) =>
(forall d. Data d => d -> m d) -> UniqDSet a -> m (UniqDSet a)
gmapM :: forall (m :: * -> *).
Monad m =>
(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)
gmapMp :: forall (m :: * -> *).
MonadPlus m =>
(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)
gmapMo :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> UniqDSet a -> m (UniqDSet a)
Data)

emptyUniqDSet :: UniqDSet a
emptyUniqDSet :: forall a. UniqDSet a
emptyUniqDSet = UniqDFM a a -> UniqDSet a
forall a. UniqDFM a a -> UniqDSet a
UniqDSet UniqDFM a a
forall {k} (key :: k) elt. UniqDFM key elt
emptyUDFM

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

mkUniqDSet :: Uniquable a => [a] -> UniqDSet a
mkUniqDSet :: forall a. Uniquable a => [a] -> UniqDSet a
mkUniqDSet = (UniqDSet a -> a -> UniqDSet a) -> UniqDSet a -> [a] -> UniqDSet a
forall b a. (b -> a -> b) -> b -> [a] -> b
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 :: forall a. Uniquable a => UniqDSet a -> a -> UniqDSet a
addOneToUniqDSet (UniqDSet UniqDFM a a
set) a
x = UniqDFM a a -> UniqDSet a
forall a. UniqDFM a a -> UniqDSet a
UniqDSet (UniqDFM a a -> a -> a -> UniqDFM a a
forall key elt.
Uniquable key =>
UniqDFM key elt -> key -> elt -> UniqDFM key elt
addToUDFM UniqDFM a a
set a
x a
x)

addListToUniqDSet :: Uniquable a => UniqDSet a -> [a] -> UniqDSet a
addListToUniqDSet :: forall a. Uniquable a => UniqDSet a -> [a] -> UniqDSet a
addListToUniqDSet = (UniqDSet a -> a -> UniqDSet a) -> UniqDSet a -> [a] -> UniqDSet a
forall b a. (b -> a -> b) -> b -> [a] -> b
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 :: forall a. Uniquable a => UniqDSet a -> a -> UniqDSet a
delOneFromUniqDSet (UniqDSet UniqDFM a a
s) = UniqDFM a a -> UniqDSet a
forall a. UniqDFM a a -> UniqDSet a
UniqDSet (UniqDFM a a -> UniqDSet a)
-> (a -> UniqDFM a a) -> a -> UniqDSet a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. UniqDFM a a -> a -> UniqDFM a a
forall key elt.
Uniquable key =>
UniqDFM key elt -> key -> UniqDFM key elt
delFromUDFM UniqDFM a a
s

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

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

unionManyUniqDSets :: [UniqDSet a] -> UniqDSet a
unionManyUniqDSets :: forall a. [UniqDSet a] -> UniqDSet a
unionManyUniqDSets []     = UniqDSet a
forall a. UniqDSet a
emptyUniqDSet
unionManyUniqDSets (UniqDSet a
x:[UniqDSet a]
xs) = (UniqDSet a -> UniqDSet a -> UniqDSet a)
-> UniqDSet a -> [UniqDSet a] -> UniqDSet a
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' UniqDSet a -> UniqDSet a -> UniqDSet a
forall a. UniqDSet a -> UniqDSet a -> UniqDSet a
unionUniqDSets UniqDSet a
x [UniqDSet a]
xs

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

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

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

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

-- See Note [Deterministic UniqFM] to learn about nondeterminism.
-- If you use this please provide a justification why it doesn't introduce
-- nondeterminism.
nonDetStrictFoldUniqDSet :: (a -> b -> b) -> b -> UniqDSet a -> b
nonDetStrictFoldUniqDSet :: forall a b. (a -> b -> b) -> b -> UniqDSet a -> b
nonDetStrictFoldUniqDSet a -> b -> b
f b
acc (UniqDSet UniqDFM a a
s) = (a -> b -> b) -> b -> UniqDFM a a -> b
forall {k} elt a (key :: k).
(elt -> a -> a) -> a -> UniqDFM key elt -> a
nonDetStrictFoldUDFM a -> b -> b
f b
acc UniqDFM a a
s

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

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

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

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

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

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

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

-- See Note [UniqSet invariant] in GHC.Types.Unique.Set
mapUniqDSet :: Uniquable b => (a -> b) -> UniqDSet a -> UniqDSet b
mapUniqDSet :: forall b a. Uniquable b => (a -> b) -> UniqDSet a -> UniqDSet b
mapUniqDSet a -> b
f (UniqDSet UniqDFM a a
m) = UniqDFM b b -> UniqDSet b
forall a. UniqDFM a a -> UniqDSet a
UniqDSet (UniqDFM b b -> UniqDSet b) -> UniqDFM b b -> UniqDSet b
forall a b. (a -> b) -> a -> b
$ UniqDFM a b -> UniqDFM b b
forall {k1} {k2} (key1 :: k1) elt (key2 :: k2).
UniqDFM key1 elt -> UniqDFM key2 elt
unsafeCastUDFMKey (UniqDFM a b -> UniqDFM b b) -> UniqDFM a b -> UniqDFM b b
forall a b. (a -> b) -> a -> b
$ (a -> b) -> UniqDFM a a -> UniqDFM a b
forall {k} elt1 elt2 (key :: k).
(elt1 -> elt2) -> UniqDFM key elt1 -> UniqDFM key elt2
mapUDFM a -> b
f UniqDFM a a
m
  -- Simply apply `f` to each element, retaining all the structure unchanged.
  -- The identification of keys and elements prevents a derived Functor
  -- instance, but `unsafeCastUDFMKey` makes it possible to apply the strict
  -- mapping from DFM.

-- | Like 'mapUniqDSet' but for 'mapM'. Assumes the function we are mapping
-- over the 'UniqDSet' does not modify uniques, as per
-- Note [UniqSet invariant] in GHC.Types.Unique.Set.
mapMUniqDSet :: (Monad m, Uniquable b) => (a -> m b) -> UniqDSet a -> m (UniqDSet b)
mapMUniqDSet :: forall (m :: * -> *) b a.
(Monad m, Uniquable b) =>
(a -> m b) -> UniqDSet a -> m (UniqDSet b)
mapMUniqDSet a -> m b
f (UniqDSet UniqDFM a a
m) = UniqDFM b b -> UniqDSet b
forall a. UniqDFM a a -> UniqDSet a
UniqDSet (UniqDFM b b -> UniqDSet b)
-> (UniqDFM a b -> UniqDFM b b) -> UniqDFM a b -> UniqDSet b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. UniqDFM a b -> UniqDFM b b
forall {k1} {k2} (key1 :: k1) elt (key2 :: k2).
UniqDFM key1 elt -> UniqDFM key2 elt
unsafeCastUDFMKey (UniqDFM a b -> UniqDSet b) -> m (UniqDFM a b) -> m (UniqDSet b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (a -> m b) -> UniqDFM a a -> m (UniqDFM a b)
forall {k} (m :: * -> *) elt1 elt2 (key :: k).
Monad m =>
(elt1 -> m elt2) -> UniqDFM key elt1 -> m (UniqDFM key elt2)
mapMUDFM a -> m b
f UniqDFM a a
m
{-# INLINEABLE mapMUniqDSet #-}

strictFoldUniqDSet :: (a -> r -> r) -> r -> UniqDSet a -> r
strictFoldUniqDSet :: forall a b. (a -> b -> b) -> b -> UniqDSet a -> b
strictFoldUniqDSet a -> r -> r
k r
r UniqDSet a
s = (r -> a -> r) -> r -> [a] -> r
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\ !r
r a
e -> a -> r -> r
k a
e r
r) r
r ([a] -> r) -> [a] -> r
forall a b. (a -> b) -> a -> b
$
                           UniqDSet a -> [a]
forall a. UniqDSet a -> [a]
uniqDSetToList UniqDSet a
s

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

getUniqDSet :: UniqDSet a -> UniqDFM a a
getUniqDSet :: forall a. UniqDSet a -> UniqDFM a a
getUniqDSet = UniqDSet a -> UniqDFM a a
forall a. UniqDSet a -> UniqDFM a 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 :: forall a. (a -> SDoc) -> UniqDSet a -> SDoc
pprUniqDSet a -> SDoc
f = SDoc -> SDoc
forall doc. IsLine doc => doc -> doc
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