2 % (c) The University of Glasgow 2006
3 % (c) The AQUA Project, Glasgow University, 1994-1998
6 UniqFM: Specialised finite maps, for things with @Uniques@.
8 Basically, the things need to be in class @Uniquable@, and we use the
9 @getUnique@ method to grab their @Uniques@.
11 (A similar thing to @UniqSet@, as opposed to @Set@.)
13 The interface is based on @FiniteMap@s, but the implementation uses
14 @Data.IntMap@, which is both maitained and faster than the past
15 implementation (see commit log).
17 The @UniqFM@ interface maps directly to Data.IntMap, only
18 ``Data.IntMap.union'' is left-biased and ``plusUFM'' right-biased
19 and ``addToUFM\_C'' and ``Data.IntMap.insertWith'' differ in the order
20 of arguments of combining function.
25 -- * Unique-keyed mappings
26 UniqFM, -- abstract type
28 -- ** Manipulating those mappings
35 addToUFM,addToUFM_C,addToUFM_Acc,
36 addListToUFM,addListToUFM_C,
38 addListToUFM_Directly,
47 foldUFM, foldUFM_Directly,
49 elemUFM, elemUFM_Directly,
50 filterUFM, filterUFM_Directly,
53 lookupUFM, lookupUFM_Directly,
54 lookupWithDefaultUFM, lookupWithDefaultUFM_Directly,
55 eltsUFM, keysUFM, splitUFM,
59 import Unique ( Uniquable(..), Unique, getKey )
62 import qualified Data.IntMap as M
65 %************************************************************************
67 \subsection{The signature of the module}
69 %************************************************************************
72 emptyUFM :: UniqFM elt
73 isNullUFM :: UniqFM elt -> Bool
74 unitUFM :: Uniquable key => key -> elt -> UniqFM elt
75 unitDirectlyUFM -- got the Unique already
76 :: Unique -> elt -> UniqFM elt
77 listToUFM :: Uniquable key => [(key,elt)] -> UniqFM elt
79 :: [(Unique, elt)] -> UniqFM elt
80 listToUFM_C :: Uniquable key => (elt -> elt -> elt)
84 addToUFM :: Uniquable key => UniqFM elt -> key -> elt -> UniqFM elt
85 addListToUFM :: Uniquable key => UniqFM elt -> [(key,elt)] -> UniqFM elt
86 addListToUFM_Directly :: UniqFM elt -> [(Unique,elt)] -> UniqFM elt
88 :: UniqFM elt -> Unique -> elt -> UniqFM elt
90 addToUFM_C :: Uniquable key => (elt -> elt -> elt) -- old -> new -> result
93 -> UniqFM elt -- result
95 addToUFM_Acc :: Uniquable key =>
96 (elt -> elts -> elts) -- Add to existing
97 -> (elt -> elts) -- New element
100 -> UniqFM elts -- result
102 addListToUFM_C :: Uniquable key => (elt -> elt -> elt)
103 -> UniqFM elt -> [(key,elt)]
106 delFromUFM :: Uniquable key => UniqFM elt -> key -> UniqFM elt
107 delListFromUFM :: Uniquable key => UniqFM elt -> [key] -> UniqFM elt
108 delFromUFM_Directly :: UniqFM elt -> Unique -> UniqFM elt
110 -- Bindings in right argument shadow those in the left
111 plusUFM :: UniqFM elt -> UniqFM elt -> UniqFM elt
113 plusUFM_C :: (elt -> elt -> elt)
114 -> UniqFM elt -> UniqFM elt -> UniqFM elt
116 minusUFM :: UniqFM elt1 -> UniqFM elt2 -> UniqFM elt1
118 intersectUFM :: UniqFM elt -> UniqFM elt -> UniqFM elt
119 intersectUFM_C :: (elt1 -> elt2 -> elt3)
120 -> UniqFM elt1 -> UniqFM elt2 -> UniqFM elt3
122 foldUFM :: (elt -> a -> a) -> a -> UniqFM elt -> a
123 foldUFM_Directly:: (Unique -> elt -> a -> a) -> a -> UniqFM elt -> a
124 mapUFM :: (elt1 -> elt2) -> UniqFM elt1 -> UniqFM elt2
125 filterUFM :: (elt -> Bool) -> UniqFM elt -> UniqFM elt
126 filterUFM_Directly :: (Unique -> elt -> Bool) -> UniqFM elt -> UniqFM elt
128 sizeUFM :: UniqFM elt -> Int
129 --hashUFM :: UniqFM elt -> Int
130 elemUFM :: Uniquable key => key -> UniqFM elt -> Bool
131 elemUFM_Directly:: Unique -> UniqFM elt -> Bool
133 splitUFM :: Uniquable key => UniqFM elt -> key -> (UniqFM elt, Maybe elt, UniqFM elt)
134 -- Splits a UFM into things less than, equal to, and greater than the key
135 lookupUFM :: Uniquable key => UniqFM elt -> key -> Maybe elt
136 lookupUFM_Directly -- when you've got the Unique already
137 :: UniqFM elt -> Unique -> Maybe elt
139 :: Uniquable key => UniqFM elt -> elt -> key -> elt
140 lookupWithDefaultUFM_Directly
141 :: UniqFM elt -> elt -> Unique -> elt
142 keysUFM :: UniqFM elt -> [Unique] -- Get the keys
143 eltsUFM :: UniqFM elt -> [elt]
144 ufmToList :: UniqFM elt -> [(Unique, elt)]
148 %************************************************************************
150 \subsection{Implementation using ``Data.IntMap''}
152 %************************************************************************
155 newtype UniqFM ele = UFM (M.IntMap ele)
157 emptyUFM = UFM M.empty
158 isNullUFM (UFM m) = M.null m
159 unitUFM k v = UFM (M.singleton (getKey $ getUnique k) v)
160 unitDirectlyUFM u v = UFM (M.singleton (getKey u) v)
161 listToUFM = foldl (\m (k, v) -> addToUFM m k v) emptyUFM
162 listToUFM_Directly = foldl (\m (u, v) -> addToUFM_Directly m u v) emptyUFM
163 listToUFM_C f = foldl (\m (k, v) -> addToUFM_C f m k v) emptyUFM
165 addToUFM (UFM m) k v = UFM (M.insert (getKey $ getUnique k) v m)
166 addListToUFM = foldl (\m (k, v) -> addToUFM m k v)
167 addListToUFM_Directly = foldl (\m (k, v) -> addToUFM_Directly m k v)
168 addToUFM_Directly (UFM m) u v = UFM (M.insert (getKey u) v m)
170 -- Arguments of combining function of M.insertWith and addToUFM_C are flipped.
171 addToUFM_C f (UFM m) k v =
172 UFM (M.insertWith (flip f) (getKey $ getUnique k) v m)
173 addToUFM_Acc exi new (UFM m) k v =
174 UFM (M.insertWith (\_new old -> exi v old) (getKey $ getUnique k) (new v) m)
175 addListToUFM_C f = foldl (\m (k, v) -> addToUFM_C f m k v)
177 delFromUFM (UFM m) k = UFM (M.delete (getKey $ getUnique k) m)
178 delListFromUFM = foldl delFromUFM
179 delFromUFM_Directly (UFM m) u = UFM (M.delete (getKey u) m)
181 -- M.union is left-biased, plusUFM should be right-biased.
182 plusUFM (UFM x) (UFM y) = UFM (M.union y x)
183 plusUFM_C f (UFM x) (UFM y) = UFM (M.unionWith f x y)
184 minusUFM (UFM x) (UFM y) = UFM (M.difference x y)
185 intersectUFM (UFM x) (UFM y) = UFM (M.intersection x y)
186 intersectUFM_C f (UFM x) (UFM y) = UFM (M.intersectionWith f x y)
188 foldUFM k z (UFM m) = M.fold k z m
189 foldUFM_Directly k z (UFM m) = M.foldWithKey (k . getUnique) z m
190 mapUFM f (UFM m) = UFM (M.map f m)
191 filterUFM p (UFM m) = UFM (M.filter p m)
192 filterUFM_Directly p (UFM m) = UFM (M.filterWithKey (p . getUnique) m)
194 sizeUFM (UFM m) = M.size m
195 elemUFM k (UFM m) = M.member (getKey $ getUnique k) m
196 elemUFM_Directly u (UFM m) = M.member (getKey u) m
198 splitUFM (UFM m) k = case M.splitLookup (getKey $ getUnique k) m of
199 (less, equal, greater) -> (UFM less, equal, UFM greater)
200 lookupUFM (UFM m) k = M.lookup (getKey $ getUnique k) m
201 lookupUFM_Directly (UFM m) u = M.lookup (getKey u) m
202 lookupWithDefaultUFM (UFM m) v k = M.findWithDefault v (getKey $ getUnique k) m
203 lookupWithDefaultUFM_Directly (UFM m) v u = M.findWithDefault v (getKey u) m
204 keysUFM (UFM m) = map getUnique $ M.keys m
205 eltsUFM (UFM m) = M.elems m
206 ufmToList (UFM m) = map (\(k, v) -> (getUnique k, v)) $ M.toList m
210 %************************************************************************
212 \subsection{Output-ery}
214 %************************************************************************
217 instance Outputable a => Outputable (UniqFM a) where
218 ppr ufm = ppr (ufmToList ufm)