Add lots of index-related collective operations
[darcs-mirrors/vector.git] / Data / Vector / Storable.hs
1 {-# LANGUAGE MultiParamTypeClasses, FlexibleInstances, TypeFamilies #-}
2
3 -- |
4 -- Module : Data.Vector.Storable
5 -- Copyright : (c) Roman Leshchinskiy 2009
6 -- License : BSD-style
7 --
8 -- Maintainer : Roman Leshchinskiy <rl@cse.unsw.edu.au>
9 -- Stability : experimental
10 -- Portability : non-portable
11 --
12 -- 'Storable'-based vectors.
13 --
14
15 module Data.Vector.Storable (
16 Vector, MVector(..), Storable,
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, imap, concatMap,
36
37 -- * Zipping and unzipping
38 zipWith, zipWith3, zipWith4, zipWith5, zipWith6,
39 izipWith, izipWith3, izipWith4, izipWith5, izipWith6,
40
41 -- * Filtering
42 filter, ifilter, takeWhile, dropWhile,
43
44 -- * Searching
45 elem, notElem, find, findIndex, minIndex, maxIndex,
46
47 -- * Folding
48 foldl, foldl1, foldl', foldl1', foldr, foldr1,
49 ifoldl, ifoldl', ifoldr,
50
51 -- * Specialised folds
52 and, or, sum, product, maximum, minimum,
53
54 -- * Unfolding
55 unfoldr,
56
57 -- * Scans
58 prescanl, prescanl',
59 postscanl, postscanl',
60 scanl, scanl', scanl1, scanl1',
61
62 -- * Enumeration
63 enumFromTo, enumFromThenTo,
64
65 -- * Conversion to/from lists
66 toList, fromList,
67
68 -- * Unsafe operations
69 unsafeIndex,
70 unsafeAccum, unsafeAccumulate_,
71 unsafeUpd, unsafeUpdate_
72 ) where
73
74 import qualified Data.Vector.Generic as G
75 import Data.Vector.Storable.Mutable ( MVector(..) )
76 import Data.Vector.Storable.Internal
77
78 import Foreign.Storable
79 import Foreign.ForeignPtr
80 -- import Foreign.Ptr
81 -- import Foreign.C.Types
82
83 import Control.Monad.ST ( ST, runST )
84
85 import Prelude hiding ( length, null,
86 replicate, (++),
87 head, last,
88 init, tail, take, drop, reverse,
89 map, concatMap,
90 zipWith, zipWith3, zip, zip3, unzip, unzip3,
91 filter, takeWhile, dropWhile,
92 elem, notElem,
93 foldl, foldl1, foldr, foldr1,
94 and, or, sum, product, minimum, maximum,
95 scanl, scanl1,
96 enumFromTo, enumFromThenTo )
97
98 import qualified Prelude
99
100 #include "vector.h"
101
102 -- | 'Storable'-based vectors
103 data Vector a = Vector {-# UNPACK #-} !Int
104 {-# UNPACK #-} !Int
105 {-# UNPACK #-} !(ForeignPtr a)
106
107 instance (Show a, Storable a) => Show (Vector a) where
108 show = (Prelude.++ " :: Data.Vector.Storable.Vector")
109 . ("fromList " Prelude.++)
110 . show
111 . toList
112
113 type instance G.Mutable Vector = MVector
114
115 instance Storable a => G.Vector Vector a where
116 {-# INLINE unsafeFreeze #-}
117 unsafeFreeze (MVector i n p) = return $ Vector i n p
118
119 {-# INLINE basicLength #-}
120 basicLength (Vector _ n _) = n
121
122 {-# INLINE basicUnsafeSlice #-}
123 basicUnsafeSlice (Vector i _ p) j n = Vector (i+j) n p
124
125 {-# INLINE basicUnsafeIndexM #-}
126 basicUnsafeIndexM (Vector i _ p) j = return
127 . inlinePerformIO
128 $ withForeignPtr p (`peekElemOff` (i+j))
129
130 {-# INLINE elemseq #-}
131 elemseq _ = seq
132
133 instance (Storable a, Eq a) => Eq (Vector a) where
134 {-# INLINE (==) #-}
135 (==) = G.eq
136
137 {-
138 eq_memcmp :: forall a. Storable a => Vector a -> Vector a -> Bool
139 {-# INLINE_STREAM eq_memcmp #-}
140 eq_memcmp (Vector i m p) (Vector j n q)
141 = m == n && inlinePerformIO
142 (withForeignPtr p $ \p' ->
143 withForeignPtr q $ \q' ->
144 return $
145 memcmp (p' `plusPtr` i) (q' `plusPtr` j)
146 (fromIntegral $ sizeOf (undefined :: a) * m) == 0)
147
148 foreign import ccall unsafe "string.h memcmp" memcmp
149 :: Ptr a -> Ptr a -> CSize -> CInt
150
151 {-# RULES
152
153 "(==) [Vector.Storable Int]"
154 G.eq = eq_memcmp :: Vector Int -> Vector Int -> Bool
155 #-}
156 -}
157
158 instance (Storable a, Ord a) => Ord (Vector a) where
159 {-# INLINE compare #-}
160 compare = G.cmp
161
162 -- Length
163 -- ------
164
165 length :: Storable a => Vector a -> Int
166 {-# INLINE length #-}
167 length = G.length
168
169 null :: Storable a => Vector a -> Bool
170 {-# INLINE null #-}
171 null = G.null
172
173 -- Construction
174 -- ------------
175
176 -- | Empty vector
177 empty :: Storable a => Vector a
178 {-# INLINE empty #-}
179 empty = G.empty
180
181 -- | Vector with exaclty one element
182 singleton :: Storable a => a -> Vector a
183 {-# INLINE singleton #-}
184 singleton = G.singleton
185
186 -- | Vector of the given length with the given value in each position
187 replicate :: Storable a => Int -> a -> Vector a
188 {-# INLINE replicate #-}
189 replicate = G.replicate
190
191 -- | Prepend an element
192 cons :: Storable a => a -> Vector a -> Vector a
193 {-# INLINE cons #-}
194 cons = G.cons
195
196 -- | Append an element
197 snoc :: Storable a => Vector a -> a -> Vector a
198 {-# INLINE snoc #-}
199 snoc = G.snoc
200
201 infixr 5 ++
202 -- | Concatenate two vectors
203 (++) :: Storable a => Vector a -> Vector a -> Vector a
204 {-# INLINE (++) #-}
205 (++) = (G.++)
206
207 -- | Create a copy of a vector. Useful when dealing with slices.
208 copy :: Storable a => Vector a -> Vector a
209 {-# INLINE copy #-}
210 copy = G.copy
211
212 -- Accessing individual elements
213 -- -----------------------------
214
215 -- | Indexing
216 (!) :: Storable a => Vector a -> Int -> a
217 {-# INLINE (!) #-}
218 (!) = (G.!)
219
220 -- | Unsafe indexing without bounds checks
221 unsafeIndex :: Storable a => Vector a -> Int -> a
222 {-# INLINE unsafeIndex #-}
223 unsafeIndex = G.unsafeIndex
224
225 -- | First element
226 head :: Storable a => Vector a -> a
227 {-# INLINE head #-}
228 head = G.head
229
230 -- | Last element
231 last :: Storable a => Vector a -> a
232 {-# INLINE last #-}
233 last = G.last
234
235 -- Subarrays
236 -- ---------
237
238 -- | Yield a part of the vector without copying it. Safer version of
239 -- 'basicUnsafeSlice'.
240 slice :: Storable a => Vector a -> Int -- ^ starting index
241 -> Int -- ^ length
242 -> Vector a
243 {-# INLINE slice #-}
244 slice = G.slice
245
246 -- | Unsafely yield a part of the vector without copying it and without
247 -- performing bounds checks.
248 unsafeSlice :: Storable a => Vector a -> Int -- ^ starting index
249 -> Int -- ^ length
250 -> Vector a
251 {-# INLINE unsafeSlice #-}
252 unsafeSlice = G.unsafeSlice
253
254 -- | Yield all but the last element without copying.
255 init :: Storable a => Vector a -> Vector a
256 {-# INLINE init #-}
257 init = G.init
258
259 -- | All but the first element (without copying).
260 tail :: Storable a => Vector a -> Vector a
261 {-# INLINE tail #-}
262 tail = G.tail
263
264 -- | Yield the first @n@ elements without copying.
265 take :: Storable a => Int -> Vector a -> Vector a
266 {-# INLINE take #-}
267 take = G.take
268
269 -- | Yield all but the first @n@ elements without copying.
270 drop :: Storable a => Int -> Vector a -> Vector a
271 {-# INLINE drop #-}
272 drop = G.drop
273
274 -- Permutations
275 -- ------------
276
277 unsafeAccum :: Storable a => (a -> b -> a) -> Vector a -> [(Int,b)] -> Vector a
278 {-# INLINE unsafeAccum #-}
279 unsafeAccum = G.unsafeAccum
280
281 unsafeAccumulate_ :: (Storable a, Storable b) =>
282 (a -> b -> a) -> Vector a -> Vector Int -> Vector b -> Vector a
283 {-# INLINE unsafeAccumulate_ #-}
284 unsafeAccumulate_ = G.unsafeAccumulate_
285
286 accum :: Storable a => (a -> b -> a) -> Vector a -> [(Int,b)] -> Vector a
287 {-# INLINE accum #-}
288 accum = G.accum
289
290 accumulate_ :: (Storable a, Storable b) =>
291 (a -> b -> a) -> Vector a -> Vector Int -> Vector b -> Vector a
292 {-# INLINE accumulate_ #-}
293 accumulate_ = G.accumulate_
294
295 unsafeUpd :: Storable a => Vector a -> [(Int, a)] -> Vector a
296 {-# INLINE unsafeUpd #-}
297 unsafeUpd = G.unsafeUpd
298
299 unsafeUpdate_ :: Storable a => Vector a -> Vector Int -> Vector a -> Vector a
300 {-# INLINE unsafeUpdate_ #-}
301 unsafeUpdate_ = G.unsafeUpdate_
302
303 (//) :: Storable a => Vector a -> [(Int, a)] -> Vector a
304 {-# INLINE (//) #-}
305 (//) = (G.//)
306
307 update_ :: Storable a => Vector a -> Vector Int -> Vector a -> Vector a
308 {-# INLINE update_ #-}
309 update_ = G.update_
310
311 backpermute :: Storable a => Vector a -> Vector Int -> Vector a
312 {-# INLINE backpermute #-}
313 backpermute = G.backpermute
314
315 reverse :: Storable a => Vector a -> Vector a
316 {-# INLINE reverse #-}
317 reverse = G.reverse
318
319 -- Mapping
320 -- -------
321
322 -- | Map a function over a vector
323 map :: (Storable a, Storable b) => (a -> b) -> Vector a -> Vector b
324 {-# INLINE map #-}
325 map = G.map
326
327 -- | Apply a function to every index/value pair
328 imap :: (Storable a, Storable b) => (Int -> a -> b) -> Vector a -> Vector b
329 {-# INLINE imap #-}
330 imap = G.imap
331
332 concatMap :: (Storable a, Storable b) => (a -> Vector b) -> Vector a -> Vector b
333 {-# INLINE concatMap #-}
334 concatMap = G.concatMap
335
336 -- Zipping/unzipping
337 -- -----------------
338
339 -- | Zip two vectors with the given function.
340 zipWith :: (Storable a, Storable b, Storable c)
341 => (a -> b -> c) -> Vector a -> Vector b -> Vector c
342 {-# INLINE zipWith #-}
343 zipWith = G.zipWith
344
345 -- | Zip three vectors with the given function.
346 zipWith3 :: (Storable a, Storable b, Storable c, Storable d)
347 => (a -> b -> c -> d) -> Vector a -> Vector b -> Vector c -> Vector d
348 {-# INLINE zipWith3 #-}
349 zipWith3 = G.zipWith3
350
351 zipWith4 :: (Storable a, Storable b, Storable c, Storable d, Storable e)
352 => (a -> b -> c -> d -> e)
353 -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e
354 {-# INLINE zipWith4 #-}
355 zipWith4 = G.zipWith4
356
357 zipWith5 :: (Storable a, Storable b, Storable c, Storable d, Storable e,
358 Storable f)
359 => (a -> b -> c -> d -> e -> f)
360 -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e
361 -> Vector f
362 {-# INLINE zipWith5 #-}
363 zipWith5 = G.zipWith5
364
365 zipWith6 :: (Storable a, Storable b, Storable c, Storable d, Storable e,
366 Storable f, Storable g)
367 => (a -> b -> c -> d -> e -> f -> g)
368 -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e
369 -> Vector f -> Vector g
370 {-# INLINE zipWith6 #-}
371 zipWith6 = G.zipWith6
372
373 -- | Zip two vectors and their indices with the given function.
374 izipWith :: (Storable a, Storable b, Storable c)
375 => (Int -> a -> b -> c) -> Vector a -> Vector b -> Vector c
376 {-# INLINE izipWith #-}
377 izipWith = G.izipWith
378
379 -- | Zip three vectors and their indices with the given function.
380 izipWith3 :: (Storable a, Storable b, Storable c, Storable d)
381 => (Int -> a -> b -> c -> d)
382 -> Vector a -> Vector b -> Vector c -> Vector d
383 {-# INLINE izipWith3 #-}
384 izipWith3 = G.izipWith3
385
386 izipWith4 :: (Storable a, Storable b, Storable c, Storable d, Storable e)
387 => (Int -> a -> b -> c -> d -> e)
388 -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e
389 {-# INLINE izipWith4 #-}
390 izipWith4 = G.izipWith4
391
392 izipWith5 :: (Storable a, Storable b, Storable c, Storable d, Storable e,
393 Storable f)
394 => (Int -> a -> b -> c -> d -> e -> f)
395 -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e
396 -> Vector f
397 {-# INLINE izipWith5 #-}
398 izipWith5 = G.izipWith5
399
400 izipWith6 :: (Storable a, Storable b, Storable c, Storable d, Storable e,
401 Storable f, Storable g)
402 => (Int -> a -> b -> c -> d -> e -> f -> g)
403 -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e
404 -> Vector f -> Vector g
405 {-# INLINE izipWith6 #-}
406 izipWith6 = G.izipWith6
407
408 -- Filtering
409 -- ---------
410
411 -- | Drop elements which do not satisfy the predicate
412 filter :: Storable a => (a -> Bool) -> Vector a -> Vector a
413 {-# INLINE filter #-}
414 filter = G.filter
415
416 -- | Drop elements that do not satisfy the predicate (applied to values and
417 -- their indices)
418 ifilter :: Storable a => (Int -> a -> Bool) -> Vector a -> Vector a
419 {-# INLINE ifilter #-}
420 ifilter = G.ifilter
421
422 -- | Yield the longest prefix of elements satisfying the predicate.
423 takeWhile :: Storable a => (a -> Bool) -> Vector a -> Vector a
424 {-# INLINE takeWhile #-}
425 takeWhile = G.takeWhile
426
427 -- | Drop the longest prefix of elements that satisfy the predicate.
428 dropWhile :: Storable a => (a -> Bool) -> Vector a -> Vector a
429 {-# INLINE dropWhile #-}
430 dropWhile = G.dropWhile
431
432 -- Searching
433 -- ---------
434
435 infix 4 `elem`
436 -- | Check whether the vector contains an element
437 elem :: (Storable a, Eq a) => a -> Vector a -> Bool
438 {-# INLINE elem #-}
439 elem = G.elem
440
441 infix 4 `notElem`
442 -- | Inverse of `elem`
443 notElem :: (Storable a, Eq a) => a -> Vector a -> Bool
444 {-# INLINE notElem #-}
445 notElem = G.notElem
446
447 -- | Yield 'Just' the first element matching the predicate or 'Nothing' if no
448 -- such element exists.
449 find :: Storable a => (a -> Bool) -> Vector a -> Maybe a
450 {-# INLINE find #-}
451 find = G.find
452
453 -- | Yield 'Just' the index of the first element matching the predicate or
454 -- 'Nothing' if no such element exists.
455 findIndex :: Storable a => (a -> Bool) -> Vector a -> Maybe Int
456 {-# INLINE findIndex #-}
457 findIndex = G.findIndex
458
459 -- Folding
460 -- -------
461
462 -- | Left fold
463 foldl :: Storable b => (a -> b -> a) -> a -> Vector b -> a
464 {-# INLINE foldl #-}
465 foldl = G.foldl
466
467 -- | Lefgt fold on non-empty vectors
468 foldl1 :: Storable a => (a -> a -> a) -> Vector a -> a
469 {-# INLINE foldl1 #-}
470 foldl1 = G.foldl1
471
472 -- | Left fold with strict accumulator
473 foldl' :: Storable b => (a -> b -> a) -> a -> Vector b -> a
474 {-# INLINE foldl' #-}
475 foldl' = G.foldl'
476
477 -- | Left fold on non-empty vectors with strict accumulator
478 foldl1' :: Storable a => (a -> a -> a) -> Vector a -> a
479 {-# INLINE foldl1' #-}
480 foldl1' = G.foldl1'
481
482 -- | Right fold
483 foldr :: Storable a => (a -> b -> b) -> b -> Vector a -> b
484 {-# INLINE foldr #-}
485 foldr = G.foldr
486
487 -- | Right fold on non-empty vectors
488 foldr1 :: Storable a => (a -> a -> a) -> Vector a -> a
489 {-# INLINE foldr1 #-}
490 foldr1 = G.foldr1
491
492 -- | Left fold (function applied to each element and its index)
493 ifoldl :: Storable b => (a -> Int -> b -> a) -> a -> Vector b -> a
494 {-# INLINE ifoldl #-}
495 ifoldl = G.ifoldl
496
497 -- | Left fold with strict accumulator (function applied to each element and
498 -- its index)
499 ifoldl' :: Storable b => (a -> Int -> b -> a) -> a -> Vector b -> a
500 {-# INLINE ifoldl' #-}
501 ifoldl' = G.ifoldl'
502
503 -- | Right fold (function applied to each element and its index)
504 ifoldr :: Storable a => (Int -> a -> b -> b) -> b -> Vector a -> b
505 {-# INLINE ifoldr #-}
506 ifoldr = G.ifoldr
507
508 -- Specialised folds
509 -- -----------------
510
511 and :: Vector Bool -> Bool
512 {-# INLINE and #-}
513 and = G.and
514
515 or :: Vector Bool -> Bool
516 {-# INLINE or #-}
517 or = G.or
518
519 sum :: (Storable a, Num a) => Vector a -> a
520 {-# INLINE sum #-}
521 sum = G.sum
522
523 product :: (Storable a, Num a) => Vector a -> a
524 {-# INLINE product #-}
525 product = G.product
526
527 maximum :: (Storable a, Ord a) => Vector a -> a
528 {-# INLINE maximum #-}
529 maximum = G.maximum
530
531 minimum :: (Storable a, Ord a) => Vector a -> a
532 {-# INLINE minimum #-}
533 minimum = G.minimum
534
535 minIndex :: (Storable a, Ord a) => Vector a -> Int
536 {-# INLINE minIndex #-}
537 minIndex = G.minIndex
538
539 maxIndex :: (Storable a, Ord a) => Vector a -> Int
540 {-# INLINE maxIndex #-}
541 maxIndex = G.maxIndex
542
543 -- Unfolding
544 -- ---------
545
546 unfoldr :: Storable a => (b -> Maybe (a, b)) -> b -> Vector a
547 {-# INLINE unfoldr #-}
548 unfoldr = G.unfoldr
549
550 -- Scans
551 -- -----
552
553 -- | Prefix scan
554 prescanl :: (Storable a, Storable b) => (a -> b -> a) -> a -> Vector b -> Vector a
555 {-# INLINE prescanl #-}
556 prescanl = G.prescanl
557
558 -- | Prefix scan with strict accumulator
559 prescanl' :: (Storable a, Storable b) => (a -> b -> a) -> a -> Vector b -> Vector a
560 {-# INLINE prescanl' #-}
561 prescanl' = G.prescanl'
562
563 -- | Suffix scan
564 postscanl :: (Storable a, Storable b) => (a -> b -> a) -> a -> Vector b -> Vector a
565 {-# INLINE postscanl #-}
566 postscanl = G.postscanl
567
568 -- | Suffix scan with strict accumulator
569 postscanl' :: (Storable a, Storable b) => (a -> b -> a) -> a -> Vector b -> Vector a
570 {-# INLINE postscanl' #-}
571 postscanl' = G.postscanl'
572
573 -- | Haskell-style scan
574 scanl :: (Storable a, Storable b) => (a -> b -> a) -> a -> Vector b -> Vector a
575 {-# INLINE scanl #-}
576 scanl = G.scanl
577
578 -- | Haskell-style scan with strict accumulator
579 scanl' :: (Storable a, Storable b) => (a -> b -> a) -> a -> Vector b -> Vector a
580 {-# INLINE scanl' #-}
581 scanl' = G.scanl'
582
583 -- | Scan over a non-empty 'Vector'
584 scanl1 :: Storable a => (a -> a -> a) -> Vector a -> Vector a
585 {-# INLINE scanl1 #-}
586 scanl1 = G.scanl1
587
588 -- | Scan over a non-empty 'Vector' with a strict accumulator
589 scanl1' :: Storable a => (a -> a -> a) -> Vector a -> Vector a
590 {-# INLINE scanl1' #-}
591 scanl1' = G.scanl1'
592
593 -- Enumeration
594 -- -----------
595
596 enumFromTo :: (Storable a, Enum a) => a -> a -> Vector a
597 {-# INLINE enumFromTo #-}
598 enumFromTo = G.enumFromTo
599
600 enumFromThenTo :: (Storable a, Enum a) => a -> a -> a -> Vector a
601 {-# INLINE enumFromThenTo #-}
602 enumFromThenTo = G.enumFromThenTo
603
604 -- Conversion to/from lists
605 -- ------------------------
606
607 -- | Convert a vector to a list
608 toList :: Storable a => Vector a -> [a]
609 {-# INLINE toList #-}
610 toList = G.toList
611
612 -- | Convert a list to a vector
613 fromList :: Storable a => [a] -> Vector a
614 {-# INLINE fromList #-}
615 fromList = G.fromList
616