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