-- (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 GeneralizedNewtypeDeriving #-}
{-# 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
    ) 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
import qualified Data.Semigroup as Semi

-- 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 (UniqDSet a -> DataType
UniqDSet a -> Constr
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 (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))
gmapMo :: 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)
gmapMp :: forall (m :: * -> *).
MonadPlus 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)
gmapM :: forall (m :: * -> *).
Monad m =>
(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 :: forall u. 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 u. (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 :: 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
gmapQl :: forall r r'.
(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 (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(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 (t :: * -> *) (c :: * -> *).
Typeable t =>
(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 (c :: * -> *).
(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 (c :: * -> *).
(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)
Data, NonEmpty (UniqDSet a) -> UniqDSet a
UniqDSet a -> UniqDSet a -> 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 :: forall b. Integral b => 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, 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
Monoid)

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

unitUniqDSet :: Uniquable a => a -> UniqDSet a
unitUniqDSet :: forall a. Uniquable a => a -> UniqDSet a
unitUniqDSet a
x = forall a. UniqDFM a a -> UniqDSet a
UniqDSet (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 = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' forall a. Uniquable a => UniqDSet a -> a -> UniqDSet a
addOneToUniqDSet 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 = forall a. UniqDFM a a -> UniqDSet a
UniqDSet (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 = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' 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) = forall a. UniqDFM a a -> UniqDSet a
UniqDSet forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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) = forall a. UniqDFM a a -> UniqDSet a
UniqDSet forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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) = forall a. UniqDFM a a -> UniqDSet a
UniqDSet (forall key 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 []     = forall a. UniqDSet a
emptyUniqDSet
unionManyUniqDSets (UniqDSet a
x:[UniqDSet a]
xs) = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' 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) = forall a. UniqDFM a a -> UniqDSet a
UniqDSet (forall key 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
  = forall a. UniqDFM a a -> UniqDSet a
UniqDSet (forall key elt1 elt2.
UniqDFM key elt1 -> UniqFM key elt2 -> UniqDFM key elt1
udfmMinusUFM (forall a. UniqDSet a -> UniqDFM a a
getUniqDSet UniqDSet a
xs) (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) = forall a. UniqDFM a a -> UniqDSet a
UniqDSet (forall key 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
  = forall a. UniqDFM a a -> UniqDSet a
UniqDSet (forall key elt1 elt2.
UniqDFM key elt1 -> UniqFM key elt2 -> UniqDFM key elt1
udfmIntersectUFM (forall a. UniqDSet a -> UniqDFM a a
getUniqDSet UniqDSet a
xs) (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) = forall elt a key. (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 = forall key elt. Uniquable key => key -> UniqDFM key elt -> Bool
elemUDFM a
k forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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) = forall a. UniqDFM a a -> UniqDSet a
UniqDSet (forall elt key. (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 = forall key elt. UniqDFM key elt -> Int
sizeUDFM forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. UniqDSet a -> UniqDFM a a
getUniqDSet

isEmptyUniqDSet :: UniqDSet a -> Bool
isEmptyUniqDSet :: forall a. UniqDSet a -> Bool
isEmptyUniqDSet = forall key elt. UniqDFM key elt -> Bool
isNullUDFM forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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 = forall key elt.
Uniquable key =>
UniqDFM key elt -> key -> Maybe elt
lookupUDFM forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. UniqDSet a -> UniqDFM a a
getUniqDSet

uniqDSetToList :: UniqDSet a -> [a]
uniqDSetToList :: forall a. UniqDSet a -> [a]
uniqDSetToList = forall key elt. UniqDFM key elt -> [elt]
eltsUDFM forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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 = coerce :: forall a b. Coercible a b => a -> b
coerce forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall elt key.
(elt -> Bool)
-> UniqDFM key elt -> (UniqDFM key elt, UniqDFM key elt)
partitionUDFM a -> Bool
p forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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 = forall a. Uniquable a => [a] -> UniqDSet a
mkUniqDSet forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (a -> b) -> [a] -> [b]
map a -> b
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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
a == :: UniqDSet a -> UniqDSet a -> Bool
== UniqDSet UniqDFM a a
b = forall key 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 = forall a. UniqDSet a -> UniqDFM a a
getUniqDSet'

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