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