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