Add uniqSetAny and uniqSetAll and use them
[ghc.git] / compiler / utils / UniqSet.hs
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
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, uniqSetAny, uniqSetAll,
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 {-
41 ************************************************************************
42 * *
43 \subsection{The signature of the module}
44 * *
45 ************************************************************************
46 -}
47
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 :: 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 partitionUniqSet :: (a -> Bool) -> UniqSet a -> (UniqSet a, UniqSet a)
71
72 sizeUniqSet :: UniqSet a -> Int
73 isEmptyUniqSet :: UniqSet a -> Bool
74 lookupUniqSet :: Uniquable a => UniqSet b -> a -> Maybe b
75 uniqSetToList :: UniqSet a -> [a]
76
77 {-
78 ************************************************************************
79 * *
80 \subsection{Implementation using ``UniqFM''}
81 * *
82 ************************************************************************
83 -}
84
85 type UniqSet a = UniqFM a
86
87 emptyUniqSet = emptyUFM
88 unitUniqSet x = unitUFM x x
89 mkUniqSet = foldl addOneToUniqSet emptyUniqSet
90
91 addOneToUniqSet set x = addToUFM set x x
92 addOneToUniqSet_C f set x = addToUFM_C f set x x
93 addListToUniqSet = foldl addOneToUniqSet
94
95 delOneFromUniqSet = delFromUFM
96 delOneFromUniqSet_Directly = delFromUFM_Directly
97 delListFromUniqSet = delListFromUFM
98
99 unionUniqSets = plusUFM
100 unionManyUniqSets [] = emptyUniqSet
101 unionManyUniqSets sets = foldr1 unionUniqSets sets
102 minusUniqSet = minusUFM
103 intersectUniqSets = intersectUFM
104
105 foldUniqSet = foldUFM
106 mapUniqSet = mapUFM
107 elementOfUniqSet = elemUFM
108 elemUniqSet_Directly = elemUFM_Directly
109 filterUniqSet = filterUFM
110 partitionUniqSet = partitionUFM
111
112 sizeUniqSet = sizeUFM
113 isEmptyUniqSet = isNullUFM
114 lookupUniqSet = lookupUFM
115 uniqSetToList = eltsUFM
116
117 uniqSetAny :: (a -> Bool) -> UniqSet a -> Bool
118 uniqSetAny = anyUFM
119
120 uniqSetAll :: (a -> Bool) -> UniqSet a -> Bool
121 uniqSetAll = allUFM