« back to all changes in this revision
Viewing changes to src/UU/DData/IntBag.hs
- browse files at revision 12
- compare with another revision
- download diff
- download tarball
- view history from revision 12
- Committer: Bazaar Package Importer
- Author(s): Joachim Breitner
- Date: 2011-06-04 00:54:17 UTC
- mfrom: (9.1.2 sid)
- Revision ID: james.westby@ubuntu.com-20110604005417-4uxlka1134z0ig1w
Tags: 0.9.13-1
New upstream release
- files removed:
- src/UU/DData
- files modified:
- debian/changelog
added
removed
src/UU/DData/IntBag.hs
1
--------------------------------------------------------------------------------
2
{-| Module : IntBag
3
Copyright : (c) Daan Leijen 2002
4
License : BSD-style
5
6
Maintainer : daan@cs.uu.nl
7
Stability : provisional
8
Portability : portable
9
10
An efficient implementation of bags of integers on top of the "IntMap" module.
11
12
Many operations have a worst-case complexity of /O(min(n,W))/. This means that the
13
operation can become linear in the number of elements with a maximum of /W/
14
-- the number of bits in an 'Int' (32 or 64). For more information, see
15
the references in the "IntMap" module.
16
-}
17
---------------------------------------------------------------------------------}
18
module UU.DData.IntBag (
19
-- * Bag type
20
IntBag -- instance Eq,Show
21
22
-- * Operators
23
, (\\)
24
25
-- *Query
26
, isEmpty
27
, size
28
, distinctSize
29
, member
30
, occur
31
32
, subset
33
, properSubset
34
35
-- * Construction
36
, empty
37
, single
38
, insert
39
, insertMany
40
, delete
41
, deleteAll
42
43
-- * Combine
44
, union
45
, difference
46
, intersection
47
, unions
48
49
-- * Filter
50
, filter
51
, partition
52
53
-- * Fold
54
, fold
55
, foldOccur
56
57
-- * Conversion
58
, elems
59
60
-- ** List
61
, toList
62
, fromList
63
64
-- ** Ordered list
65
, toAscList
66
, fromAscList
67
, fromDistinctAscList
68
69
-- ** Occurrence lists
70
, toOccurList
71
, toAscOccurList
72
, fromOccurList
73
, fromAscOccurList
74
75
-- ** IntMap
76
, toMap
77
, fromMap
78
, fromOccurMap
79
80
-- * Debugging
81
, showTree
82
, showTreeWith
83
) where
84
85
import Prelude hiding (map,filter)
86
import qualified Prelude (map,filter)
87
88
import qualified UU.DData.IntMap as M
89
90
{--------------------------------------------------------------------
91
Operators
92
--------------------------------------------------------------------}
93
infixl 9 \\ --
94
95
(\\) :: IntBag -> IntBag -> IntBag
96
b1 \\ b2 = difference b1 b2
97
98
{--------------------------------------------------------------------
99
IntBags are a simple wrapper around Maps, 'Map.Map'
100
--------------------------------------------------------------------}
101
newtype IntBag = IntBag (M.IntMap Int)
102
103
{--------------------------------------------------------------------
104
Query
105
--------------------------------------------------------------------}
106
isEmpty :: IntBag -> Bool
107
isEmpty (IntBag m)
108
= M.isEmpty m
109
110
distinctSize :: IntBag -> Int
111
distinctSize (IntBag m)
112
= M.size m
113
114
size :: IntBag -> Int
115
size b
116
= foldOccur (\x n m -> n+m) 0 b
117
118
member :: Int -> IntBag -> Bool
119
member x m
120
= (occur x m > 0)
121
122
occur :: Int -> IntBag -> Int
123
occur x (IntBag m)
124
= case M.lookup x m of
125
Nothing -> 0
126
Just n -> n
127
128
subset :: IntBag -> IntBag -> Bool
129
subset (IntBag m1) (IntBag m2)
130
= M.subsetBy (<=) m1 m2
131
132
properSubset :: IntBag -> IntBag -> Bool
133
properSubset b1 b2
134
= subset b1 b2 && (b1 /= b2)
135
136
{--------------------------------------------------------------------
137
Construction
138
--------------------------------------------------------------------}
139
empty :: IntBag
140
empty
141
= IntBag (M.empty)
142
143
single :: Int -> IntBag
144
single x
145
= IntBag (M.single x 0)
146
147
{--------------------------------------------------------------------
148
Insertion, Deletion
149
--------------------------------------------------------------------}
150
insert :: Int -> IntBag -> IntBag
151
insert x (IntBag m)
152
= IntBag (M.insertWith (+) x 1 m)
153
154
insertMany :: Int -> Int -> IntBag -> IntBag
155
insertMany x count (IntBag m)
156
= IntBag (M.insertWith (+) x count m)
157
158
delete :: Int -> IntBag -> IntBag
159
delete x (IntBag m)
160
= IntBag (M.updateWithKey f x m)
161
where
162
f x n | n > 0 = Just (n-1)
163
| otherwise = Nothing
164
165
deleteAll :: Int -> IntBag -> IntBag
166
deleteAll x (IntBag m)
167
= IntBag (M.delete x m)
168
169
{--------------------------------------------------------------------
170
Combine
171
--------------------------------------------------------------------}
172
--
173
union :: IntBag -> IntBag -> IntBag
174
union (IntBag t1) (IntBag t2)
175
= IntBag (M.unionWith (+) t1 t2)
176
177
--
178
intersection :: IntBag -> IntBag -> IntBag
179
intersection (IntBag t1) (IntBag t2)
180
= IntBag (M.intersectionWith min t1 t2)
181
182
--
183
difference :: IntBag -> IntBag -> IntBag
184
difference (IntBag t1) (IntBag t2)
185
= IntBag (M.differenceWithKey f t1 t2)
186
where
187
f x n m | n-m > 0 = Just (n-m)
188
| otherwise = Nothing
189
190
unions :: [IntBag] -> IntBag
191
unions bags
192
= IntBag (M.unions [m | IntBag m <- bags])
193
194
{--------------------------------------------------------------------
195
Filter and partition
196
--------------------------------------------------------------------}
197
filter :: (Int -> Bool) -> IntBag -> IntBag
198
filter p (IntBag m)
199
= IntBag (M.filterWithKey (\x n -> p x) m)
200
201
partition :: (Int -> Bool) -> IntBag -> (IntBag,IntBag)
202
partition p (IntBag m)
203
= (IntBag l,IntBag r)
204
where
205
(l,r) = M.partitionWithKey (\x n -> p x) m
206
207
{--------------------------------------------------------------------
208
Fold
209
--------------------------------------------------------------------}
210
fold :: (Int -> b -> b) -> b -> IntBag -> b
211
fold f z (IntBag m)
212
= M.foldWithKey apply z m
213
where
214
apply x n z | n > 0 = apply x (n-1) (f x z)
215
| otherwise = z
216
217
foldOccur :: (Int -> Int -> b -> b) -> b -> IntBag -> b
218
foldOccur f z (IntBag m)
219
= M.foldWithKey f z m
220
221
{--------------------------------------------------------------------
222
List variations
223
--------------------------------------------------------------------}
224
elems :: IntBag -> [Int]
225
elems s
226
= toList s
227
228
{--------------------------------------------------------------------
229
Lists
230
--------------------------------------------------------------------}
231
toList :: IntBag -> [Int]
232
toList s
233
= toAscList s
234
235
toAscList :: IntBag -> [Int]
236
toAscList (IntBag m)
237
= [y | (x,n) <- M.toAscList m, y <- replicate n x]
238
239
240
fromList :: [Int] -> IntBag
241
fromList xs
242
= IntBag (M.fromListWith (+) [(x,1) | x <- xs])
243
244
fromAscList :: [Int] -> IntBag
245
fromAscList xs
246
= IntBag (M.fromAscListWith (+) [(x,1) | x <- xs])
247
248
fromDistinctAscList :: [Int] -> IntBag
249
fromDistinctAscList xs
250
= IntBag (M.fromDistinctAscList [(x,1) | x <- xs])
251
252
toOccurList :: IntBag -> [(Int,Int)]
253
toOccurList b
254
= toAscOccurList b
255
256
toAscOccurList :: IntBag -> [(Int,Int)]
257
toAscOccurList (IntBag m)
258
= M.toAscList m
259
260
fromOccurList :: [(Int,Int)] -> IntBag
261
fromOccurList xs
262
= IntBag (M.fromListWith (+) (Prelude.filter (\(x,i) -> i > 0) xs))
263
264
fromAscOccurList :: [(Int,Int)] -> IntBag
265
fromAscOccurList xs
266
= IntBag (M.fromAscListWith (+) (Prelude.filter (\(x,i) -> i > 0) xs))
267
268
{--------------------------------------------------------------------
269
Maps
270
--------------------------------------------------------------------}
271
toMap :: IntBag -> M.IntMap Int
272
toMap (IntBag m)
273
= m
274
275
fromMap :: M.IntMap Int -> IntBag
276
fromMap m
277
= IntBag (M.filter (>0) m)
278
279
fromOccurMap :: M.IntMap Int -> IntBag
280
fromOccurMap m
281
= IntBag m
282
283
{--------------------------------------------------------------------
284
Eq, Ord
285
--------------------------------------------------------------------}
286
instance Eq (IntBag) where
287
(IntBag m1) == (IntBag m2) = (m1==m2)
288
(IntBag m1) /= (IntBag m2) = (m1/=m2)
289
290
{--------------------------------------------------------------------
291
Show
292
--------------------------------------------------------------------}
293
instance Show (IntBag) where
294
showsPrec d b = showSet (toAscList b)
295
296
showSet :: Show a => [a] -> ShowS
297
showSet []
298
= showString "{}"
299
showSet (x:xs)
300
= showChar '{' . shows x . showTail xs
301
where
302
showTail [] = showChar '}'
303
showTail (x:xs) = showChar ',' . shows x . showTail xs
304
305
306
{--------------------------------------------------------------------
307
Debugging
308
--------------------------------------------------------------------}
309
showTree :: IntBag -> String
310
showTree bag
311
= showTreeWith True False bag
312
313
showTreeWith :: Bool -> Bool -> IntBag -> String
314
showTreeWith hang wide (IntBag m)
315
= M.showTreeWith hang wide m
316
Loggerhead is a web-based interface for Breezy
Version: 2.0.1