compiler/utils/UniqSet.lhs

   1 %
   2 % (c) The University of Glasgow 2006
   3 % (c) The AQUA Project, Glasgow University, 1994-1998
   4 %
   5 \section[UniqSet]{Specialised sets, for things with @Uniques@}
   6
   7 Based on @UniqFMs@ (as you would expect).
   8
   9 Basically, the things need to be in class @Uniquable@.
  10
  11 \begin{code}
  12 module UniqSet (
  13         -- * Unique set type
  14         UniqSet,    -- type synonym for UniqFM a
  15
  16         -- ** Manipulating these sets
  17         emptyUniqSet,
  18         unitUniqSet,
  19         mkUniqSet,
  20         addOneToUniqSet, addOneToUniqSet_C, addListToUniqSet,
  21         delOneFromUniqSet, delOneFromUniqSet_Directly, delListFromUniqSet,
  22         unionUniqSets, unionManyUniqSets,
  23         minusUniqSet,
  24         intersectUniqSets,
  25         foldUniqSet,
  26         mapUniqSet,
  27         elementOfUniqSet,
  28         elemUniqSet_Directly,
  29         filterUniqSet,
  30         sizeUniqSet,
  31         isEmptyUniqSet,
  32         lookupUniqSet,
  33         uniqSetToList,
  34     ) where
  35
  36 import UniqFM
  37 import Unique
  38
  39 \end{code}
  40
  41 %************************************************************************
  42 %*                                                                      *
  43 \subsection{The signature of the module}
  44 %*                                                                      *
  45 %************************************************************************
  46
  47 \begin{code}
  48 emptyUniqSet :: UniqSet a
  49 unitUniqSet :: Uniquable a => a -> UniqSet a
  50 mkUniqSet :: Uniquable a => [a]  -> UniqSet a
  51
  52 addOneToUniqSet :: Uniquable a => UniqSet a -> a -> UniqSet a
  53 addOneToUniqSet_C :: Uniquable a => (a -> a -> a) -> UniqSet a -> a -> UniqSet a
  54 addListToUniqSet :: Uniquable a => UniqSet a -> [a] -> UniqSet a
  55
  56 delOneFromUniqSet :: Uniquable a => UniqSet a -> a -> UniqSet a
  57 delOneFromUniqSet_Directly :: Uniquable a => UniqSet a -> Unique -> UniqSet a
  58 delListFromUniqSet :: Uniquable a => UniqSet a -> [a] -> UniqSet a
  59
  60 unionUniqSets :: UniqSet a -> UniqSet a -> UniqSet a
  61 unionManyUniqSets :: [UniqSet a] -> UniqSet a
  62 minusUniqSet  :: UniqSet a -> UniqSet a -> UniqSet a
  63 intersectUniqSets :: UniqSet a -> UniqSet a -> UniqSet a
  64
  65 foldUniqSet :: (a -> b -> b) -> b -> UniqSet a -> b
  66 mapUniqSet :: (a -> b) -> UniqSet a -> UniqSet b
  67 elementOfUniqSet :: Uniquable a => a -> UniqSet a -> Bool
  68 elemUniqSet_Directly :: Unique -> UniqSet a -> Bool
  69 filterUniqSet :: (a -> Bool) -> UniqSet a -> UniqSet a
  70
  71 sizeUniqSet :: UniqSet a -> Int
  72 isEmptyUniqSet :: UniqSet a -> Bool
  73 lookupUniqSet :: Uniquable a => UniqSet a -> a -> Maybe a
  74 uniqSetToList :: UniqSet a -> [a]
  75 \end{code}
  76 %************************************************************************
  77 %*                                                                      *
  78 \subsection{Implementation using ``UniqFM''}
  79 %*                                                                      *
  80 %************************************************************************
  81
  82 \begin{code}
  83
  84 type UniqSet a = UniqFM a
  85
  86 emptyUniqSet = emptyUFM
  87 unitUniqSet x = unitUFM x x
  88 mkUniqSet = foldl addOneToUniqSet emptyUniqSet
  89
  90 addOneToUniqSet set x = addToUFM set x x
  91 addOneToUniqSet_C f set x = addToUFM_C f set x x
  92 addListToUniqSet = foldl addOneToUniqSet
  93
  94 delOneFromUniqSet = delFromUFM
  95 delOneFromUniqSet_Directly = delFromUFM_Directly
  96 delListFromUniqSet = delListFromUFM
  97
  98 unionUniqSets = plusUFM
  99 unionManyUniqSets [] = emptyUniqSet
 100 unionManyUniqSets sets = foldr1 unionUniqSets sets
 101 minusUniqSet = minusUFM
 102 intersectUniqSets = intersectUFM
 103
 104 foldUniqSet = foldUFM
 105 mapUniqSet = mapUFM
 106 elementOfUniqSet = elemUFM
 107 elemUniqSet_Directly = elemUFM_Directly
 108 filterUniqSet = filterUFM
 109
 110 sizeUniqSet = sizeUFM
 111 isEmptyUniqSet = isNullUFM
 112 lookupUniqSet = lookupUFM
 113 uniqSetToList = eltsUFM
 114
 115 \end{code}