utils: detabify/dewhitespace GraphPpr
[ghc.git] / 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         partitionUniqSet
35     ) where
36
37 import UniqFM
38 import Unique
39
40 \end{code}
41
42 %************************************************************************
43 %*                                                                      *
44 \subsection{The signature of the module}
45 %*                                                                      *
46 %************************************************************************
47
48 \begin{code}
49 emptyUniqSet :: UniqSet a
50 unitUniqSet :: Uniquable a => a -> UniqSet a
51 mkUniqSet :: Uniquable a => [a]  -> UniqSet a
52
53 addOneToUniqSet :: Uniquable a => UniqSet a -> a -> UniqSet a
54 addOneToUniqSet_C :: Uniquable a => (a -> a -> a) -> UniqSet a -> a -> UniqSet a
55 addListToUniqSet :: Uniquable a => UniqSet a -> [a] -> UniqSet a
56
57 delOneFromUniqSet :: Uniquable a => UniqSet a -> a -> UniqSet a
58 delOneFromUniqSet_Directly :: Uniquable a => UniqSet a -> Unique -> UniqSet a
59 delListFromUniqSet :: Uniquable a => UniqSet a -> [a] -> UniqSet a
60
61 unionUniqSets :: UniqSet a -> UniqSet a -> UniqSet a
62 unionManyUniqSets :: [UniqSet a] -> UniqSet a
63 minusUniqSet  :: UniqSet a -> UniqSet a -> UniqSet a
64 intersectUniqSets :: UniqSet a -> UniqSet a -> UniqSet a
65
66 foldUniqSet :: (a -> b -> b) -> b -> UniqSet a -> b
67 mapUniqSet :: (a -> b) -> UniqSet a -> UniqSet b
68 elementOfUniqSet :: Uniquable a => a -> UniqSet a -> Bool
69 elemUniqSet_Directly :: Unique -> UniqSet a -> Bool
70 filterUniqSet :: (a -> Bool) -> UniqSet a -> UniqSet a
71 partitionUniqSet :: (a -> Bool) -> UniqSet a -> (UniqSet a, UniqSet a)
72
73 sizeUniqSet :: UniqSet a -> Int
74 isEmptyUniqSet :: UniqSet a -> Bool
75 lookupUniqSet :: Uniquable a => UniqSet a -> a -> Maybe a
76 uniqSetToList :: UniqSet a -> [a]
77 \end{code}
78
79 %************************************************************************
80 %*                                                                      *
81 \subsection{Implementation using ``UniqFM''}
82 %*                                                                      *
83 %************************************************************************
84
85 \begin{code}
86
87 type UniqSet a = UniqFM a
88
89 emptyUniqSet = emptyUFM
90 unitUniqSet x = unitUFM x x
91 mkUniqSet = foldl addOneToUniqSet emptyUniqSet
92
93 addOneToUniqSet set x = addToUFM set x x
94 addOneToUniqSet_C f set x = addToUFM_C f set x x
95 addListToUniqSet = foldl addOneToUniqSet
96
97 delOneFromUniqSet = delFromUFM
98 delOneFromUniqSet_Directly = delFromUFM_Directly
99 delListFromUniqSet = delListFromUFM
100
101 unionUniqSets = plusUFM
102 unionManyUniqSets [] = emptyUniqSet
103 unionManyUniqSets sets = foldr1 unionUniqSets sets
104 minusUniqSet = minusUFM
105 intersectUniqSets = intersectUFM
106
107 foldUniqSet = foldUFM
108 mapUniqSet = mapUFM
109 elementOfUniqSet = elemUFM
110 elemUniqSet_Directly = elemUFM_Directly
111 filterUniqSet = filterUFM
112 partitionUniqSet = partitionUFM
113
114 sizeUniqSet = sizeUFM
115 isEmptyUniqSet = isNullUFM
116 lookupUniqSet = lookupUFM
117 uniqSetToList = eltsUFM
118
119 \end{code}