Add unsafe versions of accum/update operations
[darcs-mirrors/vector.git] / Data / Vector / Primitive.hs
1 {-# LANGUAGE FlexibleInstances, MultiParamTypeClasses, TypeFamilies #-}
2
3 -- |
4 -- Module : Data.Vector.Primitive
5 -- Copyright : (c) Roman Leshchinskiy 2008-2009
6 -- License : BSD-style
7 --
8 -- Maintainer : Roman Leshchinskiy <rl@cse.unsw.edu.au>
9 -- Stability : experimental
10 -- Portability : non-portable
11 --
12 -- Unboxed vectors of primitive types.
13 --
14
15 module Data.Vector.Primitive (
16 Vector, MVector(..), Prim,
17
18 -- * Length information
19 length, null,
20
21 -- * Construction
22 empty, singleton, cons, snoc, replicate, (++), copy,
23
24 -- * Accessing individual elements
25 (!), head, last,
26
27 -- * Subvectors
28 slice, init, tail, take, drop,
29 unsafeSlice,
30
31 -- * Permutations
32 accum, accumulate_, (//), update_, backpermute, reverse,
33
34 -- * Mapping
35 map, concatMap,
36
37 -- * Zipping and unzipping
38 zipWith, zipWith3,
39
40 -- * Filtering
41 filter, takeWhile, dropWhile,
42
43 -- * Searching
44 elem, notElem, find, findIndex,
45
46 -- * Folding
47 foldl, foldl1, foldl', foldl1', foldr, foldr1,
48
49 -- * Specialised folds
50 sum, product, maximum, minimum,
51
52 -- * Unfolding
53 unfoldr,
54
55 -- * Scans
56 prescanl, prescanl',
57 postscanl, postscanl',
58 scanl, scanl', scanl1, scanl1',
59
60 -- * Enumeration
61 enumFromTo, enumFromThenTo,
62
63 -- * Conversion to/from lists
64 toList, fromList,
65
66 -- * Unsafe operations
67 unsafeIndex,
68 unsafeAccum, unsafeAccumulate_,
69 unsafeUpd, unsafeUpdate_
70 ) where
71
72 import qualified Data.Vector.Generic as G
73 import Data.Vector.Primitive.Mutable ( MVector(..) )
74 import Data.Primitive.ByteArray
75 import Data.Primitive ( Prim )
76
77 import Control.Monad ( liftM )
78
79 import Prelude hiding ( length, null,
80 replicate, (++),
81 head, last,
82 init, tail, take, drop, reverse,
83 map, concatMap,
84 zipWith, zipWith3, zip, zip3, unzip, unzip3,
85 filter, takeWhile, dropWhile,
86 elem, notElem,
87 foldl, foldl1, foldr, foldr1,
88 sum, product, minimum, maximum,
89 scanl, scanl1,
90 enumFromTo, enumFromThenTo )
91
92 import qualified Prelude
93
94 -- | Unboxed vectors of primitive types
95 data Vector a = Vector {-# UNPACK #-} !Int
96 {-# UNPACK #-} !Int
97 {-# UNPACK #-} !ByteArray
98
99 instance (Show a, Prim a) => Show (Vector a) where
100 show = (Prelude.++ " :: Data.Vector.Primitive.Vector") . ("fromList " Prelude.++) . show . toList
101
102 type instance G.Mutable Vector = MVector
103
104 instance Prim a => G.Vector Vector a where
105 {-# INLINE unsafeFreeze #-}
106 unsafeFreeze (MVector i n marr)
107 = Vector i n `liftM` unsafeFreezeByteArray marr
108
109 {-# INLINE basicLength #-}
110 basicLength (Vector _ n _) = n
111
112 {-# INLINE basicUnsafeSlice #-}
113 basicUnsafeSlice (Vector i _ arr) j n = Vector (i+j) n arr
114
115 {-# INLINE basicUnsafeIndexM #-}
116 basicUnsafeIndexM (Vector i _ arr) j = return (indexByteArray arr (i+j))
117
118 instance (Prim a, Eq a) => Eq (Vector a) where
119 {-# INLINE (==) #-}
120 (==) = G.eq
121
122 instance (Prim a, Ord a) => Ord (Vector a) where
123 {-# INLINE compare #-}
124 compare = G.cmp
125
126 -- Length
127 -- ------
128
129 length :: Prim a => Vector a -> Int
130 {-# INLINE length #-}
131 length = G.length
132
133 null :: Prim a => Vector a -> Bool
134 {-# INLINE null #-}
135 null = G.null
136
137 -- Construction
138 -- ------------
139
140 -- | Empty vector
141 empty :: Prim a => Vector a
142 {-# INLINE empty #-}
143 empty = G.empty
144
145 -- | Vector with exaclty one element
146 singleton :: Prim a => a -> Vector a
147 {-# INLINE singleton #-}
148 singleton = G.singleton
149
150 -- | Vector of the given length with the given value in each position
151 replicate :: Prim a => Int -> a -> Vector a
152 {-# INLINE replicate #-}
153 replicate = G.replicate
154
155 -- | Prepend an element
156 cons :: Prim a => a -> Vector a -> Vector a
157 {-# INLINE cons #-}
158 cons = G.cons
159
160 -- | Append an element
161 snoc :: Prim a => Vector a -> a -> Vector a
162 {-# INLINE snoc #-}
163 snoc = G.snoc
164
165 infixr 5 ++
166 -- | Concatenate two vectors
167 (++) :: Prim a => Vector a -> Vector a -> Vector a
168 {-# INLINE (++) #-}
169 (++) = (G.++)
170
171 -- | Create a copy of a vector. Useful when dealing with slices.
172 copy :: Prim a => Vector a -> Vector a
173 {-# INLINE copy #-}
174 copy = G.copy
175
176 -- Accessing individual elements
177 -- -----------------------------
178
179 -- | Indexing
180 (!) :: Prim a => Vector a -> Int -> a
181 {-# INLINE (!) #-}
182 (!) = (G.!)
183
184 -- | Unsafe indexing without bounds checks
185 unsafeIndex :: Prim a => Vector a -> Int -> a
186 {-# INLINE unsafeIndex #-}
187 unsafeIndex = G.unsafeIndex
188
189 -- | First element
190 head :: Prim a => Vector a -> a
191 {-# INLINE head #-}
192 head = G.head
193
194 -- | Last element
195 last :: Prim a => Vector a -> a
196 {-# INLINE last #-}
197 last = G.last
198
199 -- Subarrays
200 -- ---------
201
202 -- | Yield a part of the vector without copying it. Safer version of
203 -- 'basicUnsafeSlice'.
204 slice :: Prim a => Vector a -> Int -- ^ starting index
205 -> Int -- ^ length
206 -> Vector a
207 {-# INLINE slice #-}
208 slice = G.slice
209
210 -- | Unsafely yield a part of the vector without copying it and without
211 -- performing bounds checks.
212 unsafeSlice :: Prim a => Vector a -> Int -- ^ starting index
213 -> Int -- ^ length
214 -> Vector a
215 {-# INLINE unsafeSlice #-}
216 unsafeSlice = G.unsafeSlice
217
218 -- | Yield all but the last element without copying.
219 init :: Prim a => Vector a -> Vector a
220 {-# INLINE init #-}
221 init = G.init
222
223 -- | All but the first element (without copying).
224 tail :: Prim a => Vector a -> Vector a
225 {-# INLINE tail #-}
226 tail = G.tail
227
228 -- | Yield the first @n@ elements without copying.
229 take :: Prim a => Int -> Vector a -> Vector a
230 {-# INLINE take #-}
231 take = G.take
232
233 -- | Yield all but the first @n@ elements without copying.
234 drop :: Prim a => Int -> Vector a -> Vector a
235 {-# INLINE drop #-}
236 drop = G.drop
237
238 -- Permutations
239 -- ------------
240
241 unsafeAccum :: Prim a => (a -> b -> a) -> Vector a -> [(Int,b)] -> Vector a
242 {-# INLINE unsafeAccum #-}
243 unsafeAccum = G.unsafeAccum
244
245 unsafeAccumulate_ :: (Prim a, Prim b) =>
246 (a -> b -> a) -> Vector a -> Vector Int -> Vector b -> Vector a
247 {-# INLINE unsafeAccumulate_ #-}
248 unsafeAccumulate_ = G.unsafeAccumulate_
249
250 accum :: Prim a => (a -> b -> a) -> Vector a -> [(Int,b)] -> Vector a
251 {-# INLINE accum #-}
252 accum = G.accum
253
254 accumulate_ :: (Prim a, Prim b) =>
255 (a -> b -> a) -> Vector a -> Vector Int -> Vector b -> Vector a
256 {-# INLINE accumulate_ #-}
257 accumulate_ = G.accumulate_
258
259 unsafeUpd :: Prim a => Vector a -> [(Int, a)] -> Vector a
260 {-# INLINE unsafeUpd #-}
261 unsafeUpd = G.unsafeUpd
262
263 unsafeUpdate_ :: Prim a => Vector a -> Vector Int -> Vector a -> Vector a
264 {-# INLINE unsafeUpdate_ #-}
265 unsafeUpdate_ = G.unsafeUpdate_
266
267 (//) :: Prim a => Vector a -> [(Int, a)] -> Vector a
268 {-# INLINE (//) #-}
269 (//) = (G.//)
270
271 update_ :: Prim a => Vector a -> Vector Int -> Vector a -> Vector a
272 {-# INLINE update_ #-}
273 update_ = G.update_
274
275 backpermute :: Prim a => Vector a -> Vector Int -> Vector a
276 {-# INLINE backpermute #-}
277 backpermute = G.backpermute
278
279 reverse :: Prim a => Vector a -> Vector a
280 {-# INLINE reverse #-}
281 reverse = G.reverse
282
283 -- Mapping
284 -- -------
285
286 -- | Map a function over a vector
287 map :: (Prim a, Prim b) => (a -> b) -> Vector a -> Vector b
288 {-# INLINE map #-}
289 map = G.map
290
291 concatMap :: (Prim a, Prim b) => (a -> Vector b) -> Vector a -> Vector b
292 {-# INLINE concatMap #-}
293 concatMap = G.concatMap
294
295 -- Zipping/unzipping
296 -- -----------------
297
298 -- | Zip two vectors with the given function.
299 zipWith :: (Prim a, Prim b, Prim c)
300 => (a -> b -> c) -> Vector a -> Vector b -> Vector c
301 {-# INLINE zipWith #-}
302 zipWith = G.zipWith
303
304 -- | Zip three vectors with the given function.
305 zipWith3 :: (Prim a, Prim b, Prim c, Prim d)
306 => (a -> b -> c -> d) -> Vector a -> Vector b -> Vector c -> Vector d
307 {-# INLINE zipWith3 #-}
308 zipWith3 = G.zipWith3
309
310 -- Filtering
311 -- ---------
312
313 -- | Drop elements which do not satisfy the predicate
314 filter :: Prim a => (a -> Bool) -> Vector a -> Vector a
315 {-# INLINE filter #-}
316 filter = G.filter
317
318 -- | Yield the longest prefix of elements satisfying the predicate.
319 takeWhile :: Prim a => (a -> Bool) -> Vector a -> Vector a
320 {-# INLINE takeWhile #-}
321 takeWhile = G.takeWhile
322
323 -- | Drop the longest prefix of elements that satisfy the predicate.
324 dropWhile :: Prim a => (a -> Bool) -> Vector a -> Vector a
325 {-# INLINE dropWhile #-}
326 dropWhile = G.dropWhile
327
328 -- Searching
329 -- ---------
330
331 infix 4 `elem`
332 -- | Check whether the vector contains an element
333 elem :: (Prim a, Eq a) => a -> Vector a -> Bool
334 {-# INLINE elem #-}
335 elem = G.elem
336
337 infix 4 `notElem`
338 -- | Inverse of `elem`
339 notElem :: (Prim a, Eq a) => a -> Vector a -> Bool
340 {-# INLINE notElem #-}
341 notElem = G.notElem
342
343 -- | Yield 'Just' the first element matching the predicate or 'Nothing' if no
344 -- such element exists.
345 find :: Prim a => (a -> Bool) -> Vector a -> Maybe a
346 {-# INLINE find #-}
347 find = G.find
348
349 -- | Yield 'Just' the index of the first element matching the predicate or
350 -- 'Nothing' if no such element exists.
351 findIndex :: Prim a => (a -> Bool) -> Vector a -> Maybe Int
352 {-# INLINE findIndex #-}
353 findIndex = G.findIndex
354
355 -- Folding
356 -- -------
357
358 -- | Left fold
359 foldl :: Prim b => (a -> b -> a) -> a -> Vector b -> a
360 {-# INLINE foldl #-}
361 foldl = G.foldl
362
363 -- | Lefgt fold on non-empty vectors
364 foldl1 :: Prim a => (a -> a -> a) -> Vector a -> a
365 {-# INLINE foldl1 #-}
366 foldl1 = G.foldl1
367
368 -- | Left fold with strict accumulator
369 foldl' :: Prim b => (a -> b -> a) -> a -> Vector b -> a
370 {-# INLINE foldl' #-}
371 foldl' = G.foldl'
372
373 -- | Left fold on non-empty vectors with strict accumulator
374 foldl1' :: Prim a => (a -> a -> a) -> Vector a -> a
375 {-# INLINE foldl1' #-}
376 foldl1' = G.foldl1'
377
378 -- | Right fold
379 foldr :: Prim a => (a -> b -> b) -> b -> Vector a -> b
380 {-# INLINE foldr #-}
381 foldr = G.foldr
382
383 -- | Right fold on non-empty vectors
384 foldr1 :: Prim a => (a -> a -> a) -> Vector a -> a
385 {-# INLINE foldr1 #-}
386 foldr1 = G.foldr1
387
388 -- Specialised folds
389 -- -----------------
390
391 sum :: (Prim a, Num a) => Vector a -> a
392 {-# INLINE sum #-}
393 sum = G.sum
394
395 product :: (Prim a, Num a) => Vector a -> a
396 {-# INLINE product #-}
397 product = G.product
398
399 maximum :: (Prim a, Ord a) => Vector a -> a
400 {-# INLINE maximum #-}
401 maximum = G.maximum
402
403 minimum :: (Prim a, Ord a) => Vector a -> a
404 {-# INLINE minimum #-}
405 minimum = G.minimum
406
407 -- Unfolding
408 -- ---------
409
410 unfoldr :: Prim a => (b -> Maybe (a, b)) -> b -> Vector a
411 {-# INLINE unfoldr #-}
412 unfoldr = G.unfoldr
413
414 -- Scans
415 -- -----
416
417 -- | Prefix scan
418 prescanl :: (Prim a, Prim b) => (a -> b -> a) -> a -> Vector b -> Vector a
419 {-# INLINE prescanl #-}
420 prescanl = G.prescanl
421
422 -- | Prefix scan with strict accumulator
423 prescanl' :: (Prim a, Prim b) => (a -> b -> a) -> a -> Vector b -> Vector a
424 {-# INLINE prescanl' #-}
425 prescanl' = G.prescanl'
426
427 -- | Suffix scan
428 postscanl :: (Prim a, Prim b) => (a -> b -> a) -> a -> Vector b -> Vector a
429 {-# INLINE postscanl #-}
430 postscanl = G.postscanl
431
432 -- | Suffix scan with strict accumulator
433 postscanl' :: (Prim a, Prim b) => (a -> b -> a) -> a -> Vector b -> Vector a
434 {-# INLINE postscanl' #-}
435 postscanl' = G.postscanl'
436
437 -- | Haskell-style scan
438 scanl :: (Prim a, Prim b) => (a -> b -> a) -> a -> Vector b -> Vector a
439 {-# INLINE scanl #-}
440 scanl = G.scanl
441
442 -- | Haskell-style scan with strict accumulator
443 scanl' :: (Prim a, Prim b) => (a -> b -> a) -> a -> Vector b -> Vector a
444 {-# INLINE scanl' #-}
445 scanl' = G.scanl'
446
447 -- | Scan over a non-empty 'Vector'
448 scanl1 :: Prim a => (a -> a -> a) -> Vector a -> Vector a
449 {-# INLINE scanl1 #-}
450 scanl1 = G.scanl1
451
452 -- | Scan over a non-empty 'Vector' with a strict accumulator
453 scanl1' :: Prim a => (a -> a -> a) -> Vector a -> Vector a
454 {-# INLINE scanl1' #-}
455 scanl1' = G.scanl1'
456
457 -- Enumeration
458 -- -----------
459
460 enumFromTo :: (Prim a, Enum a) => a -> a -> Vector a
461 {-# INLINE enumFromTo #-}
462 enumFromTo = G.enumFromTo
463
464 enumFromThenTo :: (Prim a, Enum a) => a -> a -> a -> Vector a
465 {-# INLINE enumFromThenTo #-}
466 enumFromThenTo = G.enumFromThenTo
467
468 -- Conversion to/from lists
469 -- ------------------------
470
471 -- | Convert a vector to a list
472 toList :: Prim a => Vector a -> [a]
473 {-# INLINE toList #-}
474 toList = G.toList
475
476 -- | Convert a list to a vector
477 fromList :: Prim a => [a] -> Vector a
478 {-# INLINE fromList #-}
479 fromList = G.fromList
480