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


UniqFM: Specialised finite maps, for things with @Uniques@.

Basically, the things need to be in class @Uniquable@, and we use the
@getUnique@ method to grab their @Uniques@.

(A similar thing to @UniqSet@, as opposed to @Set@.)

The interface is based on @FiniteMap@s, but the implementation uses
@Data.IntMap@, which is both maintained and faster than the past
implementation (see commit log).

The @UniqFM@ interface maps directly to Data.IntMap, only
``Data.IntMap.union'' is left-biased and ``plusUFM'' right-biased
and ``addToUFM\_C'' and ``Data.IntMap.insertWith'' differ in the order
of arguments of combining function.
-}

{-# LANGUAGE DeriveDataTypeable #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
{-# OPTIONS_GHC -Wall #-}

module UniqFM (
        -- * Unique-keyed mappings
        UniqFM,           -- abstract type
        NonDetUniqFM(..), -- wrapper for opting into nondeterminism

        -- ** Manipulating those mappings
        emptyUFM,
        unitUFM,
        unitDirectlyUFM,
        listToUFM,
        listToUFM_Directly,
        listToUFM_C,
        addToUFM,addToUFM_C,addToUFM_Acc,
        addListToUFM,addListToUFM_C,
        addToUFM_Directly,
        addListToUFM_Directly,
        adjustUFM, alterUFM,
        adjustUFM_Directly,
        delFromUFM,
        delFromUFM_Directly,
        delListFromUFM,
        delListFromUFM_Directly,
        plusUFM,
        plusUFM_C,
        plusUFM_CD,
        plusMaybeUFM_C,
        plusUFMList,
        minusUFM,
        intersectUFM,
        intersectUFM_C,
        disjointUFM,
        equalKeysUFM,
        nonDetFoldUFM, foldUFM, nonDetFoldUFM_Directly,
        anyUFM, allUFM, seqEltsUFM,
        mapUFM, mapUFM_Directly,
        elemUFM, elemUFM_Directly,
        filterUFM, filterUFM_Directly, partitionUFM,
        sizeUFM,
        isNullUFM,
        lookupUFM, lookupUFM_Directly,
        lookupWithDefaultUFM, lookupWithDefaultUFM_Directly,
        nonDetEltsUFM, eltsUFM, nonDetKeysUFM,
        ufmToSet_Directly,
        nonDetUFMToList, ufmToIntMap,
        pprUniqFM, pprUFM, pprUFMWithKeys, pluralUFM
    ) where

import GhcPrelude

import Unique           ( Uniquable(..), Unique, getKey )
import Outputable

import qualified Data.IntMap as M
import qualified Data.IntSet as S
import Data.Data
import qualified Data.Semigroup as Semi
import Data.Functor.Classes (Eq1 (..))


newtype UniqFM ele = UFM (M.IntMap ele)
  deriving (Typeable (UniqFM ele)
DataType
Constr
Typeable (UniqFM ele)
-> (forall (c :: * -> *).
    (forall d b. Data d => c (d -> b) -> d -> c b)
    -> (forall g. g -> c g) -> UniqFM ele -> c (UniqFM ele))
-> (forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c (UniqFM ele))
-> (UniqFM ele -> Constr)
-> (UniqFM ele -> DataType)
-> (forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c (UniqFM ele)))
-> (forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e))
    -> Maybe (c (UniqFM ele)))
-> ((forall b. Data b => b -> b) -> UniqFM ele -> UniqFM ele)
-> (forall r r'.
    (r -> r' -> r)
    -> r -> (forall d. Data d => d -> r') -> UniqFM ele -> r)
-> (forall r r'.
    (r' -> r -> r)
    -> r -> (forall d. Data d => d -> r') -> UniqFM ele -> r)
-> (forall u. (forall d. Data d => d -> u) -> UniqFM ele -> [u])
-> (forall u.
    Int -> (forall d. Data d => d -> u) -> UniqFM ele -> u)
-> (forall (m :: * -> *).
    Monad m =>
    (forall d. Data d => d -> m d) -> UniqFM ele -> m (UniqFM ele))
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> UniqFM ele -> m (UniqFM ele))
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> UniqFM ele -> m (UniqFM ele))
-> Data (UniqFM ele)
UniqFM ele -> DataType
UniqFM ele -> Constr
(forall d. Data d => c (t d)) -> Maybe (c (UniqFM ele))
(forall b. Data b => b -> b) -> UniqFM ele -> UniqFM ele
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> UniqFM ele -> c (UniqFM ele)
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (UniqFM ele)
forall ele. Data ele => Typeable (UniqFM ele)
forall ele. Data ele => UniqFM ele -> DataType
forall ele. Data ele => UniqFM ele -> Constr
forall ele.
Data ele =>
(forall b. Data b => b -> b) -> UniqFM ele -> UniqFM ele
forall ele u.
Data ele =>
Int -> (forall d. Data d => d -> u) -> UniqFM ele -> u
forall ele u.
Data ele =>
(forall d. Data d => d -> u) -> UniqFM ele -> [u]
forall ele r r'.
Data ele =>
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> UniqFM ele -> r
forall ele r r'.
Data ele =>
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> UniqFM ele -> r
forall ele (m :: * -> *).
(Data ele, Monad m) =>
(forall d. Data d => d -> m d) -> UniqFM ele -> m (UniqFM ele)
forall ele (m :: * -> *).
(Data ele, MonadPlus m) =>
(forall d. Data d => d -> m d) -> UniqFM ele -> m (UniqFM ele)
forall ele (c :: * -> *).
Data ele =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (UniqFM ele)
forall ele (c :: * -> *).
Data ele =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> UniqFM ele -> c (UniqFM ele)
forall ele (t :: * -> *) (c :: * -> *).
(Data ele, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (UniqFM ele))
forall ele (t :: * -> * -> *) (c :: * -> *).
(Data ele, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (UniqFM ele))
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) -> UniqFM ele -> u
forall u. (forall d. Data d => d -> u) -> UniqFM ele -> [u]
forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> UniqFM ele -> r
forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> UniqFM ele -> r
forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> UniqFM ele -> m (UniqFM ele)
forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> UniqFM ele -> m (UniqFM ele)
forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (UniqFM ele)
forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> UniqFM ele -> c (UniqFM ele)
forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c (UniqFM ele))
forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (UniqFM ele))
$cUFM :: Constr
$tUniqFM :: DataType
gmapMo :: (forall d. Data d => d -> m d) -> UniqFM ele -> m (UniqFM ele)
$cgmapMo :: forall ele (m :: * -> *).
(Data ele, MonadPlus m) =>
(forall d. Data d => d -> m d) -> UniqFM ele -> m (UniqFM ele)
gmapMp :: (forall d. Data d => d -> m d) -> UniqFM ele -> m (UniqFM ele)
$cgmapMp :: forall ele (m :: * -> *).
(Data ele, MonadPlus m) =>
(forall d. Data d => d -> m d) -> UniqFM ele -> m (UniqFM ele)
gmapM :: (forall d. Data d => d -> m d) -> UniqFM ele -> m (UniqFM ele)
$cgmapM :: forall ele (m :: * -> *).
(Data ele, Monad m) =>
(forall d. Data d => d -> m d) -> UniqFM ele -> m (UniqFM ele)
gmapQi :: Int -> (forall d. Data d => d -> u) -> UniqFM ele -> u
$cgmapQi :: forall ele u.
Data ele =>
Int -> (forall d. Data d => d -> u) -> UniqFM ele -> u
gmapQ :: (forall d. Data d => d -> u) -> UniqFM ele -> [u]
$cgmapQ :: forall ele u.
Data ele =>
(forall d. Data d => d -> u) -> UniqFM ele -> [u]
gmapQr :: (r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> UniqFM ele -> r
$cgmapQr :: forall ele r r'.
Data ele =>
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> UniqFM ele -> r
gmapQl :: (r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> UniqFM ele -> r
$cgmapQl :: forall ele r r'.
Data ele =>
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> UniqFM ele -> r
gmapT :: (forall b. Data b => b -> b) -> UniqFM ele -> UniqFM ele
$cgmapT :: forall ele.
Data ele =>
(forall b. Data b => b -> b) -> UniqFM ele -> UniqFM ele
dataCast2 :: (forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (UniqFM ele))
$cdataCast2 :: forall ele (t :: * -> * -> *) (c :: * -> *).
(Data ele, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (UniqFM ele))
dataCast1 :: (forall d. Data d => c (t d)) -> Maybe (c (UniqFM ele))
$cdataCast1 :: forall ele (t :: * -> *) (c :: * -> *).
(Data ele, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (UniqFM ele))
dataTypeOf :: UniqFM ele -> DataType
$cdataTypeOf :: forall ele. Data ele => UniqFM ele -> DataType
toConstr :: UniqFM ele -> Constr
$ctoConstr :: forall ele. Data ele => UniqFM ele -> Constr
gunfold :: (forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (UniqFM ele)
$cgunfold :: forall ele (c :: * -> *).
Data ele =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (UniqFM ele)
gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> UniqFM ele -> c (UniqFM ele)
$cgfoldl :: forall ele (c :: * -> *).
Data ele =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> UniqFM ele -> c (UniqFM ele)
$cp1Data :: forall ele. Data ele => Typeable (UniqFM ele)
Data, UniqFM ele -> UniqFM ele -> Bool
(UniqFM ele -> UniqFM ele -> Bool)
-> (UniqFM ele -> UniqFM ele -> Bool) -> Eq (UniqFM ele)
forall ele. Eq ele => UniqFM ele -> UniqFM ele -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: UniqFM ele -> UniqFM ele -> Bool
$c/= :: forall ele. Eq ele => UniqFM ele -> UniqFM ele -> Bool
== :: UniqFM ele -> UniqFM ele -> Bool
$c== :: forall ele. Eq ele => UniqFM ele -> UniqFM ele -> Bool
Eq, a -> UniqFM b -> UniqFM a
(a -> b) -> UniqFM a -> UniqFM b
(forall a b. (a -> b) -> UniqFM a -> UniqFM b)
-> (forall a b. a -> UniqFM b -> UniqFM a) -> Functor UniqFM
forall a b. a -> UniqFM b -> UniqFM a
forall a b. (a -> b) -> UniqFM a -> UniqFM b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
<$ :: a -> UniqFM b -> UniqFM a
$c<$ :: forall a b. a -> UniqFM b -> UniqFM a
fmap :: (a -> b) -> UniqFM a -> UniqFM b
$cfmap :: forall a b. (a -> b) -> UniqFM a -> UniqFM b
Functor)
  -- Nondeterministic Foldable and Traversable instances are accessible through
  -- use of the 'NonDetUniqFM' wrapper.
  -- See Note [Deterministic UniqFM] in UniqDFM to learn about determinism.

emptyUFM :: UniqFM elt
emptyUFM :: UniqFM elt
emptyUFM = IntMap elt -> UniqFM elt
forall ele. IntMap ele -> UniqFM ele
UFM IntMap elt
forall a. IntMap a
M.empty

isNullUFM :: UniqFM elt -> Bool
isNullUFM :: UniqFM elt -> Bool
isNullUFM (UFM IntMap elt
m) = IntMap elt -> Bool
forall a. IntMap a -> Bool
M.null IntMap elt
m

unitUFM :: Uniquable key => key -> elt -> UniqFM elt
unitUFM :: key -> elt -> UniqFM elt
unitUFM key
k elt
v = IntMap elt -> UniqFM elt
forall ele. IntMap ele -> UniqFM ele
UFM (Int -> elt -> IntMap elt
forall a. Int -> a -> IntMap a
M.singleton (Unique -> Int
getKey (Unique -> Int) -> Unique -> Int
forall a b. (a -> b) -> a -> b
$ key -> Unique
forall a. Uniquable a => a -> Unique
getUnique key
k) elt
v)

-- when you've got the Unique already
unitDirectlyUFM :: Unique -> elt -> UniqFM elt
unitDirectlyUFM :: Unique -> elt -> UniqFM elt
unitDirectlyUFM Unique
u elt
v = IntMap elt -> UniqFM elt
forall ele. IntMap ele -> UniqFM ele
UFM (Int -> elt -> IntMap elt
forall a. Int -> a -> IntMap a
M.singleton (Unique -> Int
getKey Unique
u) elt
v)

listToUFM :: Uniquable key => [(key,elt)] -> UniqFM elt
listToUFM :: [(key, elt)] -> UniqFM elt
listToUFM = (UniqFM elt -> (key, elt) -> UniqFM elt)
-> UniqFM elt -> [(key, elt)] -> UniqFM elt
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\UniqFM elt
m (key
k, elt
v) -> UniqFM elt -> key -> elt -> UniqFM elt
forall key elt.
Uniquable key =>
UniqFM elt -> key -> elt -> UniqFM elt
addToUFM UniqFM elt
m key
k elt
v) UniqFM elt
forall elt. UniqFM elt
emptyUFM

listToUFM_Directly :: [(Unique, elt)] -> UniqFM elt
listToUFM_Directly :: [(Unique, elt)] -> UniqFM elt
listToUFM_Directly = (UniqFM elt -> (Unique, elt) -> UniqFM elt)
-> UniqFM elt -> [(Unique, elt)] -> UniqFM elt
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\UniqFM elt
m (Unique
u, elt
v) -> UniqFM elt -> Unique -> elt -> UniqFM elt
forall elt. UniqFM elt -> Unique -> elt -> UniqFM elt
addToUFM_Directly UniqFM elt
m Unique
u elt
v) UniqFM elt
forall elt. UniqFM elt
emptyUFM

listToUFM_C
  :: Uniquable key
  => (elt -> elt -> elt)
  -> [(key, elt)]
  -> UniqFM elt
listToUFM_C :: (elt -> elt -> elt) -> [(key, elt)] -> UniqFM elt
listToUFM_C elt -> elt -> elt
f = (UniqFM elt -> (key, elt) -> UniqFM elt)
-> UniqFM elt -> [(key, elt)] -> UniqFM elt
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\UniqFM elt
m (key
k, elt
v) -> (elt -> elt -> elt) -> UniqFM elt -> key -> elt -> UniqFM elt
forall key elt.
Uniquable key =>
(elt -> elt -> elt) -> UniqFM elt -> key -> elt -> UniqFM elt
addToUFM_C elt -> elt -> elt
f UniqFM elt
m key
k elt
v) UniqFM elt
forall elt. UniqFM elt
emptyUFM

addToUFM :: Uniquable key => UniqFM elt -> key -> elt  -> UniqFM elt
addToUFM :: UniqFM elt -> key -> elt -> UniqFM elt
addToUFM (UFM IntMap elt
m) key
k elt
v = IntMap elt -> UniqFM elt
forall ele. IntMap ele -> UniqFM ele
UFM (Int -> elt -> IntMap elt -> IntMap elt
forall a. Int -> a -> IntMap a -> IntMap a
M.insert (Unique -> Int
getKey (Unique -> Int) -> Unique -> Int
forall a b. (a -> b) -> a -> b
$ key -> Unique
forall a. Uniquable a => a -> Unique
getUnique key
k) elt
v IntMap elt
m)

addListToUFM :: Uniquable key => UniqFM elt -> [(key,elt)] -> UniqFM elt
addListToUFM :: UniqFM elt -> [(key, elt)] -> UniqFM elt
addListToUFM = (UniqFM elt -> (key, elt) -> UniqFM elt)
-> UniqFM elt -> [(key, elt)] -> UniqFM elt
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\UniqFM elt
m (key
k, elt
v) -> UniqFM elt -> key -> elt -> UniqFM elt
forall key elt.
Uniquable key =>
UniqFM elt -> key -> elt -> UniqFM elt
addToUFM UniqFM elt
m key
k elt
v)

addListToUFM_Directly :: UniqFM elt -> [(Unique,elt)] -> UniqFM elt
addListToUFM_Directly :: UniqFM elt -> [(Unique, elt)] -> UniqFM elt
addListToUFM_Directly = (UniqFM elt -> (Unique, elt) -> UniqFM elt)
-> UniqFM elt -> [(Unique, elt)] -> UniqFM elt
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\UniqFM elt
m (Unique
k, elt
v) -> UniqFM elt -> Unique -> elt -> UniqFM elt
forall elt. UniqFM elt -> Unique -> elt -> UniqFM elt
addToUFM_Directly UniqFM elt
m Unique
k elt
v)

addToUFM_Directly :: UniqFM elt -> Unique -> elt -> UniqFM elt
addToUFM_Directly :: UniqFM elt -> Unique -> elt -> UniqFM elt
addToUFM_Directly (UFM IntMap elt
m) Unique
u elt
v = IntMap elt -> UniqFM elt
forall ele. IntMap ele -> UniqFM ele
UFM (Int -> elt -> IntMap elt -> IntMap elt
forall a. Int -> a -> IntMap a -> IntMap a
M.insert (Unique -> Int
getKey Unique
u) elt
v IntMap elt
m)

addToUFM_C
  :: Uniquable key
  => (elt -> elt -> elt)  -- old -> new -> result
  -> UniqFM elt           -- old
  -> key -> elt           -- new
  -> UniqFM elt           -- result
-- Arguments of combining function of M.insertWith and addToUFM_C are flipped.
addToUFM_C :: (elt -> elt -> elt) -> UniqFM elt -> key -> elt -> UniqFM elt
addToUFM_C elt -> elt -> elt
f (UFM IntMap elt
m) key
k elt
v =
  IntMap elt -> UniqFM elt
forall ele. IntMap ele -> UniqFM ele
UFM ((elt -> elt -> elt) -> Int -> elt -> IntMap elt -> IntMap elt
forall a. (a -> a -> a) -> Int -> a -> IntMap a -> IntMap a
M.insertWith ((elt -> elt -> elt) -> elt -> elt -> elt
forall a b c. (a -> b -> c) -> b -> a -> c
flip elt -> elt -> elt
f) (Unique -> Int
getKey (Unique -> Int) -> Unique -> Int
forall a b. (a -> b) -> a -> b
$ key -> Unique
forall a. Uniquable a => a -> Unique
getUnique key
k) elt
v IntMap elt
m)

addToUFM_Acc
  :: Uniquable key
  => (elt -> elts -> elts)  -- Add to existing
  -> (elt -> elts)          -- New element
  -> UniqFM elts            -- old
  -> key -> elt             -- new
  -> UniqFM elts            -- result
addToUFM_Acc :: (elt -> elts -> elts)
-> (elt -> elts) -> UniqFM elts -> key -> elt -> UniqFM elts
addToUFM_Acc elt -> elts -> elts
exi elt -> elts
new (UFM IntMap elts
m) key
k elt
v =
  IntMap elts -> UniqFM elts
forall ele. IntMap ele -> UniqFM ele
UFM ((elts -> elts -> elts) -> Int -> elts -> IntMap elts -> IntMap elts
forall a. (a -> a -> a) -> Int -> a -> IntMap a -> IntMap a
M.insertWith (\elts
_new elts
old -> elt -> elts -> elts
exi elt
v elts
old) (Unique -> Int
getKey (Unique -> Int) -> Unique -> Int
forall a b. (a -> b) -> a -> b
$ key -> Unique
forall a. Uniquable a => a -> Unique
getUnique key
k) (elt -> elts
new elt
v) IntMap elts
m)

alterUFM
  :: Uniquable key
  => (Maybe elt -> Maybe elt)  -- How to adjust
  -> UniqFM elt                -- old
  -> key                       -- new
  -> UniqFM elt                -- result
alterUFM :: (Maybe elt -> Maybe elt) -> UniqFM elt -> key -> UniqFM elt
alterUFM Maybe elt -> Maybe elt
f (UFM IntMap elt
m) key
k = IntMap elt -> UniqFM elt
forall ele. IntMap ele -> UniqFM ele
UFM ((Maybe elt -> Maybe elt) -> Int -> IntMap elt -> IntMap elt
forall a. (Maybe a -> Maybe a) -> Int -> IntMap a -> IntMap a
M.alter Maybe elt -> Maybe elt
f (Unique -> Int
getKey (Unique -> Int) -> Unique -> Int
forall a b. (a -> b) -> a -> b
$ key -> Unique
forall a. Uniquable a => a -> Unique
getUnique key
k) IntMap elt
m)

addListToUFM_C
  :: Uniquable key
  => (elt -> elt -> elt)
  -> UniqFM elt -> [(key,elt)]
  -> UniqFM elt
addListToUFM_C :: (elt -> elt -> elt) -> UniqFM elt -> [(key, elt)] -> UniqFM elt
addListToUFM_C elt -> elt -> elt
f = (UniqFM elt -> (key, elt) -> UniqFM elt)
-> UniqFM elt -> [(key, elt)] -> UniqFM elt
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\UniqFM elt
m (key
k, elt
v) -> (elt -> elt -> elt) -> UniqFM elt -> key -> elt -> UniqFM elt
forall key elt.
Uniquable key =>
(elt -> elt -> elt) -> UniqFM elt -> key -> elt -> UniqFM elt
addToUFM_C elt -> elt -> elt
f UniqFM elt
m key
k elt
v)

adjustUFM :: Uniquable key => (elt -> elt) -> UniqFM elt -> key -> UniqFM elt
adjustUFM :: (elt -> elt) -> UniqFM elt -> key -> UniqFM elt
adjustUFM elt -> elt
f (UFM IntMap elt
m) key
k = IntMap elt -> UniqFM elt
forall ele. IntMap ele -> UniqFM ele
UFM ((elt -> elt) -> Int -> IntMap elt -> IntMap elt
forall a. (a -> a) -> Int -> IntMap a -> IntMap a
M.adjust elt -> elt
f (Unique -> Int
getKey (Unique -> Int) -> Unique -> Int
forall a b. (a -> b) -> a -> b
$ key -> Unique
forall a. Uniquable a => a -> Unique
getUnique key
k) IntMap elt
m)

adjustUFM_Directly :: (elt -> elt) -> UniqFM elt -> Unique -> UniqFM elt
adjustUFM_Directly :: (elt -> elt) -> UniqFM elt -> Unique -> UniqFM elt
adjustUFM_Directly elt -> elt
f (UFM IntMap elt
m) Unique
u = IntMap elt -> UniqFM elt
forall ele. IntMap ele -> UniqFM ele
UFM ((elt -> elt) -> Int -> IntMap elt -> IntMap elt
forall a. (a -> a) -> Int -> IntMap a -> IntMap a
M.adjust elt -> elt
f (Unique -> Int
getKey Unique
u) IntMap elt
m)

delFromUFM :: Uniquable key => UniqFM elt -> key    -> UniqFM elt
delFromUFM :: UniqFM elt -> key -> UniqFM elt
delFromUFM (UFM IntMap elt
m) key
k = IntMap elt -> UniqFM elt
forall ele. IntMap ele -> UniqFM ele
UFM (Int -> IntMap elt -> IntMap elt
forall a. Int -> IntMap a -> IntMap a
M.delete (Unique -> Int
getKey (Unique -> Int) -> Unique -> Int
forall a b. (a -> b) -> a -> b
$ key -> Unique
forall a. Uniquable a => a -> Unique
getUnique key
k) IntMap elt
m)

delListFromUFM :: Uniquable key => UniqFM elt -> [key] -> UniqFM elt
delListFromUFM :: UniqFM elt -> [key] -> UniqFM elt
delListFromUFM = (UniqFM elt -> key -> UniqFM elt)
-> UniqFM elt -> [key] -> UniqFM elt
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' UniqFM elt -> key -> UniqFM elt
forall key elt. Uniquable key => UniqFM elt -> key -> UniqFM elt
delFromUFM

delListFromUFM_Directly :: UniqFM elt -> [Unique] -> UniqFM elt
delListFromUFM_Directly :: UniqFM elt -> [Unique] -> UniqFM elt
delListFromUFM_Directly = (UniqFM elt -> Unique -> UniqFM elt)
-> UniqFM elt -> [Unique] -> UniqFM elt
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' UniqFM elt -> Unique -> UniqFM elt
forall elt. UniqFM elt -> Unique -> UniqFM elt
delFromUFM_Directly

delFromUFM_Directly :: UniqFM elt -> Unique -> UniqFM elt
delFromUFM_Directly :: UniqFM elt -> Unique -> UniqFM elt
delFromUFM_Directly (UFM IntMap elt
m) Unique
u = IntMap elt -> UniqFM elt
forall ele. IntMap ele -> UniqFM ele
UFM (Int -> IntMap elt -> IntMap elt
forall a. Int -> IntMap a -> IntMap a
M.delete (Unique -> Int
getKey Unique
u) IntMap elt
m)

-- Bindings in right argument shadow those in the left
plusUFM :: UniqFM elt -> UniqFM elt -> UniqFM elt
-- M.union is left-biased, plusUFM should be right-biased.
plusUFM :: UniqFM elt -> UniqFM elt -> UniqFM elt
plusUFM (UFM IntMap elt
x) (UFM IntMap elt
y) = IntMap elt -> UniqFM elt
forall ele. IntMap ele -> UniqFM ele
UFM (IntMap elt -> IntMap elt -> IntMap elt
forall a. IntMap a -> IntMap a -> IntMap a
M.union IntMap elt
y IntMap elt
x)
     -- Note (M.union y x), with arguments flipped
     -- M.union is left-biased, plusUFM should be right-biased.

plusUFM_C :: (elt -> elt -> elt) -> UniqFM elt -> UniqFM elt -> UniqFM elt
plusUFM_C :: (elt -> elt -> elt) -> UniqFM elt -> UniqFM elt -> UniqFM elt
plusUFM_C elt -> elt -> elt
f (UFM IntMap elt
x) (UFM IntMap elt
y) = IntMap elt -> UniqFM elt
forall ele. IntMap ele -> UniqFM ele
UFM ((elt -> elt -> elt) -> IntMap elt -> IntMap elt -> IntMap elt
forall a. (a -> a -> a) -> IntMap a -> IntMap a -> IntMap a
M.unionWith elt -> elt -> elt
f IntMap elt
x IntMap elt
y)

-- | `plusUFM_CD f m1 d1 m2 d2` merges the maps using `f` as the
-- combinding function and `d1` resp. `d2` as the default value if
-- there is no entry in `m1` reps. `m2`. The domain is the union of
-- the domains of `m1` and `m2`.
--
-- Representative example:
--
-- @
-- plusUFM_CD f {A: 1, B: 2} 23 {B: 3, C: 4} 42
--    == {A: f 1 42, B: f 2 3, C: f 23 4 }
-- @
plusUFM_CD
  :: (elt -> elt -> elt)
  -> UniqFM elt  -- map X
  -> elt         -- default for X
  -> UniqFM elt  -- map Y
  -> elt         -- default for Y
  -> UniqFM elt
plusUFM_CD :: (elt -> elt -> elt)
-> UniqFM elt -> elt -> UniqFM elt -> elt -> UniqFM elt
plusUFM_CD elt -> elt -> elt
f (UFM IntMap elt
xm) elt
dx (UFM IntMap elt
ym) elt
dy
  = IntMap elt -> UniqFM elt
forall ele. IntMap ele -> UniqFM ele
UFM (IntMap elt -> UniqFM elt) -> IntMap elt -> UniqFM elt
forall a b. (a -> b) -> a -> b
$ (Int -> elt -> elt -> Maybe elt)
-> (IntMap elt -> IntMap elt)
-> (IntMap elt -> IntMap elt)
-> IntMap elt
-> IntMap elt
-> IntMap elt
forall a b c.
(Int -> a -> b -> Maybe c)
-> (IntMap a -> IntMap c)
-> (IntMap b -> IntMap c)
-> IntMap a
-> IntMap b
-> IntMap c
M.mergeWithKey
      (\Int
_ elt
x elt
y -> elt -> Maybe elt
forall a. a -> Maybe a
Just (elt
x elt -> elt -> elt
`f` elt
y))
      ((elt -> elt) -> IntMap elt -> IntMap elt
forall a b. (a -> b) -> IntMap a -> IntMap b
M.map (\elt
x -> elt
x elt -> elt -> elt
`f` elt
dy))
      ((elt -> elt) -> IntMap elt -> IntMap elt
forall a b. (a -> b) -> IntMap a -> IntMap b
M.map (\elt
y -> elt
dx elt -> elt -> elt
`f` elt
y))
      IntMap elt
xm IntMap elt
ym

plusMaybeUFM_C :: (elt -> elt -> Maybe elt)
               -> UniqFM elt -> UniqFM elt -> UniqFM elt
plusMaybeUFM_C :: (elt -> elt -> Maybe elt) -> UniqFM elt -> UniqFM elt -> UniqFM elt
plusMaybeUFM_C elt -> elt -> Maybe elt
f (UFM IntMap elt
xm) (UFM IntMap elt
ym)
    = IntMap elt -> UniqFM elt
forall ele. IntMap ele -> UniqFM ele
UFM (IntMap elt -> UniqFM elt) -> IntMap elt -> UniqFM elt
forall a b. (a -> b) -> a -> b
$ (Int -> elt -> elt -> Maybe elt)
-> (IntMap elt -> IntMap elt)
-> (IntMap elt -> IntMap elt)
-> IntMap elt
-> IntMap elt
-> IntMap elt
forall a b c.
(Int -> a -> b -> Maybe c)
-> (IntMap a -> IntMap c)
-> (IntMap b -> IntMap c)
-> IntMap a
-> IntMap b
-> IntMap c
M.mergeWithKey
        (\Int
_ elt
x elt
y -> elt
x elt -> elt -> Maybe elt
`f` elt
y)
        IntMap elt -> IntMap elt
forall a. a -> a
id
        IntMap elt -> IntMap elt
forall a. a -> a
id
        IntMap elt
xm IntMap elt
ym

plusUFMList :: [UniqFM elt] -> UniqFM elt
plusUFMList :: [UniqFM elt] -> UniqFM elt
plusUFMList = (UniqFM elt -> UniqFM elt -> UniqFM elt)
-> UniqFM elt -> [UniqFM elt] -> UniqFM elt
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' UniqFM elt -> UniqFM elt -> UniqFM elt
forall elt. UniqFM elt -> UniqFM elt -> UniqFM elt
plusUFM UniqFM elt
forall elt. UniqFM elt
emptyUFM

minusUFM :: UniqFM elt1 -> UniqFM elt2 -> UniqFM elt1
minusUFM :: UniqFM elt1 -> UniqFM elt2 -> UniqFM elt1
minusUFM (UFM IntMap elt1
x) (UFM IntMap elt2
y) = IntMap elt1 -> UniqFM elt1
forall ele. IntMap ele -> UniqFM ele
UFM (IntMap elt1 -> IntMap elt2 -> IntMap elt1
forall a b. IntMap a -> IntMap b -> IntMap a
M.difference IntMap elt1
x IntMap elt2
y)

intersectUFM :: UniqFM elt1 -> UniqFM elt2 -> UniqFM elt1
intersectUFM :: UniqFM elt1 -> UniqFM elt2 -> UniqFM elt1
intersectUFM (UFM IntMap elt1
x) (UFM IntMap elt2
y) = IntMap elt1 -> UniqFM elt1
forall ele. IntMap ele -> UniqFM ele
UFM (IntMap elt1 -> IntMap elt2 -> IntMap elt1
forall a b. IntMap a -> IntMap b -> IntMap a
M.intersection IntMap elt1
x IntMap elt2
y)

intersectUFM_C
  :: (elt1 -> elt2 -> elt3)
  -> UniqFM elt1
  -> UniqFM elt2
  -> UniqFM elt3
intersectUFM_C :: (elt1 -> elt2 -> elt3) -> UniqFM elt1 -> UniqFM elt2 -> UniqFM elt3
intersectUFM_C elt1 -> elt2 -> elt3
f (UFM IntMap elt1
x) (UFM IntMap elt2
y) = IntMap elt3 -> UniqFM elt3
forall ele. IntMap ele -> UniqFM ele
UFM ((elt1 -> elt2 -> elt3) -> IntMap elt1 -> IntMap elt2 -> IntMap elt3
forall a b c. (a -> b -> c) -> IntMap a -> IntMap b -> IntMap c
M.intersectionWith elt1 -> elt2 -> elt3
f IntMap elt1
x IntMap elt2
y)

disjointUFM :: UniqFM elt1 -> UniqFM elt2 -> Bool
disjointUFM :: UniqFM elt1 -> UniqFM elt2 -> Bool
disjointUFM (UFM IntMap elt1
x) (UFM IntMap elt2
y) = IntMap elt1 -> Bool
forall a. IntMap a -> Bool
M.null (IntMap elt1 -> IntMap elt2 -> IntMap elt1
forall a b. IntMap a -> IntMap b -> IntMap a
M.intersection IntMap elt1
x IntMap elt2
y)

foldUFM :: (elt -> a -> a) -> a -> UniqFM elt -> a
foldUFM :: (elt -> a -> a) -> a -> UniqFM elt -> a
foldUFM elt -> a -> a
k a
z (UFM IntMap elt
m) = (elt -> a -> a) -> a -> IntMap elt -> a
forall a b. (a -> b -> b) -> b -> IntMap a -> b
M.foldr elt -> a -> a
k a
z IntMap elt
m

mapUFM :: (elt1 -> elt2) -> UniqFM elt1 -> UniqFM elt2
mapUFM :: (elt1 -> elt2) -> UniqFM elt1 -> UniqFM elt2
mapUFM elt1 -> elt2
f (UFM IntMap elt1
m) = IntMap elt2 -> UniqFM elt2
forall ele. IntMap ele -> UniqFM ele
UFM ((elt1 -> elt2) -> IntMap elt1 -> IntMap elt2
forall a b. (a -> b) -> IntMap a -> IntMap b
M.map elt1 -> elt2
f IntMap elt1
m)

mapUFM_Directly :: (Unique -> elt1 -> elt2) -> UniqFM elt1 -> UniqFM elt2
mapUFM_Directly :: (Unique -> elt1 -> elt2) -> UniqFM elt1 -> UniqFM elt2
mapUFM_Directly Unique -> elt1 -> elt2
f (UFM IntMap elt1
m) = IntMap elt2 -> UniqFM elt2
forall ele. IntMap ele -> UniqFM ele
UFM ((Int -> elt1 -> elt2) -> IntMap elt1 -> IntMap elt2
forall a b. (Int -> a -> b) -> IntMap a -> IntMap b
M.mapWithKey (Unique -> elt1 -> elt2
f (Unique -> elt1 -> elt2) -> (Int -> Unique) -> Int -> elt1 -> elt2
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Unique
forall a. Uniquable a => a -> Unique
getUnique) IntMap elt1
m)

filterUFM :: (elt -> Bool) -> UniqFM elt -> UniqFM elt
filterUFM :: (elt -> Bool) -> UniqFM elt -> UniqFM elt
filterUFM elt -> Bool
p (UFM IntMap elt
m) = IntMap elt -> UniqFM elt
forall ele. IntMap ele -> UniqFM ele
UFM ((elt -> Bool) -> IntMap elt -> IntMap elt
forall a. (a -> Bool) -> IntMap a -> IntMap a
M.filter elt -> Bool
p IntMap elt
m)

filterUFM_Directly :: (Unique -> elt -> Bool) -> UniqFM elt -> UniqFM elt
filterUFM_Directly :: (Unique -> elt -> Bool) -> UniqFM elt -> UniqFM elt
filterUFM_Directly Unique -> elt -> Bool
p (UFM IntMap elt
m) = IntMap elt -> UniqFM elt
forall ele. IntMap ele -> UniqFM ele
UFM ((Int -> elt -> Bool) -> IntMap elt -> IntMap elt
forall a. (Int -> a -> Bool) -> IntMap a -> IntMap a
M.filterWithKey (Unique -> elt -> Bool
p (Unique -> elt -> Bool) -> (Int -> Unique) -> Int -> elt -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Unique
forall a. Uniquable a => a -> Unique
getUnique) IntMap elt
m)

partitionUFM :: (elt -> Bool) -> UniqFM elt -> (UniqFM elt, UniqFM elt)
partitionUFM :: (elt -> Bool) -> UniqFM elt -> (UniqFM elt, UniqFM elt)
partitionUFM elt -> Bool
p (UFM IntMap elt
m) =
  case (elt -> Bool) -> IntMap elt -> (IntMap elt, IntMap elt)
forall a. (a -> Bool) -> IntMap a -> (IntMap a, IntMap a)
M.partition elt -> Bool
p IntMap elt
m of
    (IntMap elt
left, IntMap elt
right) -> (IntMap elt -> UniqFM elt
forall ele. IntMap ele -> UniqFM ele
UFM IntMap elt
left, IntMap elt -> UniqFM elt
forall ele. IntMap ele -> UniqFM ele
UFM IntMap elt
right)

sizeUFM :: UniqFM elt -> Int
sizeUFM :: UniqFM elt -> Int
sizeUFM (UFM IntMap elt
m) = IntMap elt -> Int
forall a. IntMap a -> Int
M.size IntMap elt
m

elemUFM :: Uniquable key => key -> UniqFM elt -> Bool
elemUFM :: key -> UniqFM elt -> Bool
elemUFM key
k (UFM IntMap elt
m) = Int -> IntMap elt -> Bool
forall a. Int -> IntMap a -> Bool
M.member (Unique -> Int
getKey (Unique -> Int) -> Unique -> Int
forall a b. (a -> b) -> a -> b
$ key -> Unique
forall a. Uniquable a => a -> Unique
getUnique key
k) IntMap elt
m

elemUFM_Directly :: Unique -> UniqFM elt -> Bool
elemUFM_Directly :: Unique -> UniqFM elt -> Bool
elemUFM_Directly Unique
u (UFM IntMap elt
m) = Int -> IntMap elt -> Bool
forall a. Int -> IntMap a -> Bool
M.member (Unique -> Int
getKey Unique
u) IntMap elt
m

lookupUFM :: Uniquable key => UniqFM elt -> key -> Maybe elt
lookupUFM :: UniqFM elt -> key -> Maybe elt
lookupUFM (UFM IntMap elt
m) key
k = Int -> IntMap elt -> Maybe elt
forall a. Int -> IntMap a -> Maybe a
M.lookup (Unique -> Int
getKey (Unique -> Int) -> Unique -> Int
forall a b. (a -> b) -> a -> b
$ key -> Unique
forall a. Uniquable a => a -> Unique
getUnique key
k) IntMap elt
m

-- when you've got the Unique already
lookupUFM_Directly :: UniqFM elt -> Unique -> Maybe elt
lookupUFM_Directly :: UniqFM elt -> Unique -> Maybe elt
lookupUFM_Directly (UFM IntMap elt
m) Unique
u = Int -> IntMap elt -> Maybe elt
forall a. Int -> IntMap a -> Maybe a
M.lookup (Unique -> Int
getKey Unique
u) IntMap elt
m

lookupWithDefaultUFM :: Uniquable key => UniqFM elt -> elt -> key -> elt
lookupWithDefaultUFM :: UniqFM elt -> elt -> key -> elt
lookupWithDefaultUFM (UFM IntMap elt
m) elt
v key
k = elt -> Int -> IntMap elt -> elt
forall a. a -> Int -> IntMap a -> a
M.findWithDefault elt
v (Unique -> Int
getKey (Unique -> Int) -> Unique -> Int
forall a b. (a -> b) -> a -> b
$ key -> Unique
forall a. Uniquable a => a -> Unique
getUnique key
k) IntMap elt
m

lookupWithDefaultUFM_Directly :: UniqFM elt -> elt -> Unique -> elt
lookupWithDefaultUFM_Directly :: UniqFM elt -> elt -> Unique -> elt
lookupWithDefaultUFM_Directly (UFM IntMap elt
m) elt
v Unique
u = elt -> Int -> IntMap elt -> elt
forall a. a -> Int -> IntMap a -> a
M.findWithDefault elt
v (Unique -> Int
getKey Unique
u) IntMap elt
m

eltsUFM :: UniqFM elt -> [elt]
eltsUFM :: UniqFM elt -> [elt]
eltsUFM (UFM IntMap elt
m) = IntMap elt -> [elt]
forall a. IntMap a -> [a]
M.elems IntMap elt
m

ufmToSet_Directly :: UniqFM elt -> S.IntSet
ufmToSet_Directly :: UniqFM elt -> IntSet
ufmToSet_Directly (UFM IntMap elt
m) = IntMap elt -> IntSet
forall a. IntMap a -> IntSet
M.keysSet IntMap elt
m

anyUFM :: (elt -> Bool) -> UniqFM elt -> Bool
anyUFM :: (elt -> Bool) -> UniqFM elt -> Bool
anyUFM elt -> Bool
p (UFM IntMap elt
m) = (elt -> Bool -> Bool) -> Bool -> IntMap elt -> Bool
forall a b. (a -> b -> b) -> b -> IntMap a -> b
M.foldr (Bool -> Bool -> Bool
(||) (Bool -> Bool -> Bool) -> (elt -> Bool) -> elt -> Bool -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. elt -> Bool
p) Bool
False IntMap elt
m

allUFM :: (elt -> Bool) -> UniqFM elt -> Bool
allUFM :: (elt -> Bool) -> UniqFM elt -> Bool
allUFM elt -> Bool
p (UFM IntMap elt
m) = (elt -> Bool -> Bool) -> Bool -> IntMap elt -> Bool
forall a b. (a -> b -> b) -> b -> IntMap a -> b
M.foldr (Bool -> Bool -> Bool
(&&) (Bool -> Bool -> Bool) -> (elt -> Bool) -> elt -> Bool -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. elt -> Bool
p) Bool
True IntMap elt
m

seqEltsUFM :: ([elt] -> ()) -> UniqFM elt -> ()
seqEltsUFM :: ([elt] -> ()) -> UniqFM elt -> ()
seqEltsUFM [elt] -> ()
seqList = [elt] -> ()
seqList ([elt] -> ()) -> (UniqFM elt -> [elt]) -> UniqFM elt -> ()
forall b c a. (b -> c) -> (a -> b) -> a -> c
. UniqFM elt -> [elt]
forall elt. UniqFM elt -> [elt]
nonDetEltsUFM
  -- It's OK to use nonDetEltsUFM here because the type guarantees that
  -- the only interesting thing this function can do is to force the
  -- elements.

-- See Note [Deterministic UniqFM] to learn about nondeterminism.
-- If you use this please provide a justification why it doesn't introduce
-- nondeterminism.
nonDetEltsUFM :: UniqFM elt -> [elt]
nonDetEltsUFM :: UniqFM elt -> [elt]
nonDetEltsUFM (UFM IntMap elt
m) = IntMap elt -> [elt]
forall a. IntMap a -> [a]
M.elems IntMap elt
m

-- See Note [Deterministic UniqFM] to learn about nondeterminism.
-- If you use this please provide a justification why it doesn't introduce
-- nondeterminism.
nonDetKeysUFM :: UniqFM elt -> [Unique]
nonDetKeysUFM :: UniqFM elt -> [Unique]
nonDetKeysUFM (UFM IntMap elt
m) = (Int -> Unique) -> [Int] -> [Unique]
forall a b. (a -> b) -> [a] -> [b]
map Int -> Unique
forall a. Uniquable a => a -> Unique
getUnique ([Int] -> [Unique]) -> [Int] -> [Unique]
forall a b. (a -> b) -> a -> b
$ IntMap elt -> [Int]
forall a. IntMap a -> [Int]
M.keys IntMap elt
m

-- See Note [Deterministic UniqFM] to learn about nondeterminism.
-- If you use this please provide a justification why it doesn't introduce
-- nondeterminism.
nonDetFoldUFM :: (elt -> a -> a) -> a -> UniqFM elt -> a
nonDetFoldUFM :: (elt -> a -> a) -> a -> UniqFM elt -> a
nonDetFoldUFM elt -> a -> a
k a
z (UFM IntMap elt
m) = (elt -> a -> a) -> a -> IntMap elt -> a
forall a b. (a -> b -> b) -> b -> IntMap a -> b
M.foldr elt -> a -> a
k a
z IntMap elt
m

-- See Note [Deterministic UniqFM] to learn about nondeterminism.
-- If you use this please provide a justification why it doesn't introduce
-- nondeterminism.
nonDetFoldUFM_Directly:: (Unique -> elt -> a -> a) -> a -> UniqFM elt -> a
nonDetFoldUFM_Directly :: (Unique -> elt -> a -> a) -> a -> UniqFM elt -> a
nonDetFoldUFM_Directly Unique -> elt -> a -> a
k a
z (UFM IntMap elt
m) = (Int -> elt -> a -> a) -> a -> IntMap elt -> a
forall a b. (Int -> a -> b -> b) -> b -> IntMap a -> b
M.foldrWithKey (Unique -> elt -> a -> a
k (Unique -> elt -> a -> a)
-> (Int -> Unique) -> Int -> elt -> a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Unique
forall a. Uniquable a => a -> Unique
getUnique) a
z IntMap elt
m

-- See Note [Deterministic UniqFM] to learn about nondeterminism.
-- If you use this please provide a justification why it doesn't introduce
-- nondeterminism.
nonDetUFMToList :: UniqFM elt -> [(Unique, elt)]
nonDetUFMToList :: UniqFM elt -> [(Unique, elt)]
nonDetUFMToList (UFM IntMap elt
m) = ((Int, elt) -> (Unique, elt)) -> [(Int, elt)] -> [(Unique, elt)]
forall a b. (a -> b) -> [a] -> [b]
map (\(Int
k, elt
v) -> (Int -> Unique
forall a. Uniquable a => a -> Unique
getUnique Int
k, elt
v)) ([(Int, elt)] -> [(Unique, elt)])
-> [(Int, elt)] -> [(Unique, elt)]
forall a b. (a -> b) -> a -> b
$ IntMap elt -> [(Int, elt)]
forall a. IntMap a -> [(Int, a)]
M.toList IntMap elt
m

-- | A wrapper around 'UniqFM' with the sole purpose of informing call sites
-- that the provided 'Foldable' and 'Traversable' instances are
-- nondeterministic.
-- If you use this please provide a justification why it doesn't introduce
-- nondeterminism.
-- See Note [Deterministic UniqFM] in UniqDFM to learn about determinism.
newtype NonDetUniqFM ele = NonDetUniqFM { NonDetUniqFM ele -> UniqFM ele
getNonDet :: UniqFM ele }
  deriving (a -> NonDetUniqFM b -> NonDetUniqFM a
(a -> b) -> NonDetUniqFM a -> NonDetUniqFM b
(forall a b. (a -> b) -> NonDetUniqFM a -> NonDetUniqFM b)
-> (forall a b. a -> NonDetUniqFM b -> NonDetUniqFM a)
-> Functor NonDetUniqFM
forall a b. a -> NonDetUniqFM b -> NonDetUniqFM a
forall a b. (a -> b) -> NonDetUniqFM a -> NonDetUniqFM b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
<$ :: a -> NonDetUniqFM b -> NonDetUniqFM a
$c<$ :: forall a b. a -> NonDetUniqFM b -> NonDetUniqFM a
fmap :: (a -> b) -> NonDetUniqFM a -> NonDetUniqFM b
$cfmap :: forall a b. (a -> b) -> NonDetUniqFM a -> NonDetUniqFM b
Functor)

-- | Inherently nondeterministic.
-- If you use this please provide a justification why it doesn't introduce
-- nondeterminism.
-- See Note [Deterministic UniqFM] in UniqDFM to learn about determinism.
instance Foldable NonDetUniqFM where
  foldr :: (a -> b -> b) -> b -> NonDetUniqFM a -> b
foldr a -> b -> b
f b
z (NonDetUniqFM (UFM IntMap a
m)) = (a -> b -> b) -> b -> IntMap a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> b -> b
f b
z IntMap a
m

-- | Inherently nondeterministic.
-- If you use this please provide a justification why it doesn't introduce
-- nondeterminism.
-- See Note [Deterministic UniqFM] in UniqDFM to learn about determinism.
instance Traversable NonDetUniqFM where
  traverse :: (a -> f b) -> NonDetUniqFM a -> f (NonDetUniqFM b)
traverse a -> f b
f (NonDetUniqFM (UFM IntMap a
m)) = UniqFM b -> NonDetUniqFM b
forall ele. UniqFM ele -> NonDetUniqFM ele
NonDetUniqFM (UniqFM b -> NonDetUniqFM b)
-> (IntMap b -> UniqFM b) -> IntMap b -> NonDetUniqFM b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. IntMap b -> UniqFM b
forall ele. IntMap ele -> UniqFM ele
UFM (IntMap b -> NonDetUniqFM b) -> f (IntMap b) -> f (NonDetUniqFM b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (a -> f b) -> IntMap a -> f (IntMap b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse a -> f b
f IntMap a
m

ufmToIntMap :: UniqFM elt -> M.IntMap elt
ufmToIntMap :: UniqFM elt -> IntMap elt
ufmToIntMap (UFM IntMap elt
m) = IntMap elt
m

-- Determines whether two 'UniqFM's contain the same keys.
equalKeysUFM :: UniqFM a -> UniqFM b -> Bool
equalKeysUFM :: UniqFM a -> UniqFM b -> Bool
equalKeysUFM (UFM IntMap a
m1) (UFM IntMap b
m2) = (a -> b -> Bool) -> IntMap a -> IntMap b -> Bool
forall (f :: * -> *) a b.
Eq1 f =>
(a -> b -> Bool) -> f a -> f b -> Bool
liftEq (\a
_ b
_ -> Bool
True) IntMap a
m1 IntMap b
m2

-- Instances

instance Semi.Semigroup (UniqFM a) where
  <> :: UniqFM a -> UniqFM a -> UniqFM a
(<>) = UniqFM a -> UniqFM a -> UniqFM a
forall elt. UniqFM elt -> UniqFM elt -> UniqFM elt
plusUFM

instance Monoid (UniqFM a) where
    mempty :: UniqFM a
mempty = UniqFM a
forall elt. UniqFM elt
emptyUFM
    mappend :: UniqFM a -> UniqFM a -> UniqFM a
mappend = UniqFM a -> UniqFM a -> UniqFM a
forall a. Semigroup a => a -> a -> a
(Semi.<>)

-- Output-ery

instance Outputable a => Outputable (UniqFM a) where
    ppr :: UniqFM a -> SDoc
ppr UniqFM a
ufm = (a -> SDoc) -> UniqFM a -> SDoc
forall a. (a -> SDoc) -> UniqFM a -> SDoc
pprUniqFM a -> SDoc
forall a. Outputable a => a -> SDoc
ppr UniqFM a
ufm

pprUniqFM :: (a -> SDoc) -> UniqFM a -> SDoc
pprUniqFM :: (a -> SDoc) -> UniqFM a -> SDoc
pprUniqFM a -> SDoc
ppr_elt UniqFM a
ufm
  = SDoc -> SDoc
brackets (SDoc -> SDoc) -> SDoc -> SDoc
forall a b. (a -> b) -> a -> b
$ [SDoc] -> SDoc
fsep ([SDoc] -> SDoc) -> [SDoc] -> SDoc
forall a b. (a -> b) -> a -> b
$ SDoc -> [SDoc] -> [SDoc]
punctuate SDoc
comma ([SDoc] -> [SDoc]) -> [SDoc] -> [SDoc]
forall a b. (a -> b) -> a -> b
$
    [ Unique -> SDoc
forall a. Outputable a => a -> SDoc
ppr Unique
uq SDoc -> SDoc -> SDoc
<+> String -> SDoc
text String
":->" SDoc -> SDoc -> SDoc
<+> a -> SDoc
ppr_elt a
elt
    | (Unique
uq, a
elt) <- UniqFM a -> [(Unique, a)]
forall elt. UniqFM elt -> [(Unique, elt)]
nonDetUFMToList UniqFM a
ufm ]
  -- It's OK to use nonDetUFMToList here because we only use it for
  -- pretty-printing.

-- | Pretty-print a non-deterministic set.
-- The order of variables is non-deterministic and for pretty-printing that
-- shouldn't be a problem.
-- Having this function helps contain the non-determinism created with
-- nonDetEltsUFM.
pprUFM :: UniqFM a      -- ^ The things to be pretty printed
       -> ([a] -> SDoc) -- ^ The pretty printing function to use on the elements
       -> SDoc          -- ^ 'SDoc' where the things have been pretty
                        -- printed
pprUFM :: UniqFM a -> ([a] -> SDoc) -> SDoc
pprUFM UniqFM a
ufm [a] -> SDoc
pp = [a] -> SDoc
pp (UniqFM a -> [a]
forall elt. UniqFM elt -> [elt]
nonDetEltsUFM UniqFM a
ufm)

-- | Pretty-print a non-deterministic set.
-- The order of variables is non-deterministic and for pretty-printing that
-- shouldn't be a problem.
-- Having this function helps contain the non-determinism created with
-- nonDetUFMToList.
pprUFMWithKeys
       :: UniqFM a                -- ^ The things to be pretty printed
       -> ([(Unique, a)] -> SDoc) -- ^ The pretty printing function to use on the elements
       -> SDoc                    -- ^ 'SDoc' where the things have been pretty
                                  -- printed
pprUFMWithKeys :: UniqFM a -> ([(Unique, a)] -> SDoc) -> SDoc
pprUFMWithKeys UniqFM a
ufm [(Unique, a)] -> SDoc
pp = [(Unique, a)] -> SDoc
pp (UniqFM a -> [(Unique, a)]
forall elt. UniqFM elt -> [(Unique, elt)]
nonDetUFMToList UniqFM a
ufm)

-- | Determines the pluralisation suffix appropriate for the length of a set
-- in the same way that plural from Outputable does for lists.
pluralUFM :: UniqFM a -> SDoc
pluralUFM :: UniqFM a -> SDoc
pluralUFM UniqFM a
ufm
  | UniqFM a -> Int
forall elt. UniqFM elt -> Int
sizeUFM UniqFM a
ufm Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
1 = SDoc
empty
  | Bool
otherwise = Char -> SDoc
char Char
's'