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