Begin large refactoring of mutable vectors
[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, accumulate_, (//), update_, 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 Control.Monad.ST ( ST, runST )
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 = runST (do
106 MVector i n p <- (id :: ST s (MVector s a) -> ST s (MVector s a)) 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 accumulate_ :: (Storable a, Storable b) =>
248 (a -> b -> a) -> Vector a -> Vector Int -> Vector b -> Vector a
249 {-# INLINE accumulate_ #-}
250 accumulate_ = G.accumulate_
251
252 (//) :: Storable a => Vector a -> [(Int, a)] -> Vector a
253 {-# INLINE (//) #-}
254 (//) = (G.//)
255
256 update_ :: Storable a => Vector a -> Vector Int -> Vector a -> Vector a
257 {-# INLINE update_ #-}
258 update_ = G.update_
259
260 backpermute :: Storable a => Vector a -> Vector Int -> Vector a
261 {-# INLINE backpermute #-}
262 backpermute = G.backpermute
263
264 reverse :: Storable a => Vector a -> Vector a
265 {-# INLINE reverse #-}
266 reverse = G.reverse
267
268 -- Mapping
269 -- -------
270
271 -- | Map a function over a vector
272 map :: (Storable a, Storable b) => (a -> b) -> Vector a -> Vector b
273 {-# INLINE map #-}
274 map = G.map
275
276 concatMap :: (Storable a, Storable b) => (a -> Vector b) -> Vector a -> Vector b
277 {-# INLINE concatMap #-}
278 concatMap = G.concatMap
279
280 -- Zipping/unzipping
281 -- -----------------
282
283 -- | Zip two vectors with the given function.
284 zipWith :: (Storable a, Storable b, Storable c)
285 => (a -> b -> c) -> Vector a -> Vector b -> Vector c
286 {-# INLINE zipWith #-}
287 zipWith = G.zipWith
288
289 -- | Zip three vectors with the given function.
290 zipWith3 :: (Storable a, Storable b, Storable c, Storable d)
291 => (a -> b -> c -> d) -> Vector a -> Vector b -> Vector c -> Vector d
292 {-# INLINE zipWith3 #-}
293 zipWith3 = G.zipWith3
294
295 -- Filtering
296 -- ---------
297
298 -- | Drop elements which do not satisfy the predicate
299 filter :: Storable a => (a -> Bool) -> Vector a -> Vector a
300 {-# INLINE filter #-}
301 filter = G.filter
302
303 -- | Yield the longest prefix of elements satisfying the predicate.
304 takeWhile :: Storable a => (a -> Bool) -> Vector a -> Vector a
305 {-# INLINE takeWhile #-}
306 takeWhile = G.takeWhile
307
308 -- | Drop the longest prefix of elements that satisfy the predicate.
309 dropWhile :: Storable a => (a -> Bool) -> Vector a -> Vector a
310 {-# INLINE dropWhile #-}
311 dropWhile = G.dropWhile
312
313 -- Searching
314 -- ---------
315
316 infix 4 `elem`
317 -- | Check whether the vector contains an element
318 elem :: (Storable a, Eq a) => a -> Vector a -> Bool
319 {-# INLINE elem #-}
320 elem = G.elem
321
322 infix 4 `notElem`
323 -- | Inverse of `elem`
324 notElem :: (Storable a, Eq a) => a -> Vector a -> Bool
325 {-# INLINE notElem #-}
326 notElem = G.notElem
327
328 -- | Yield 'Just' the first element matching the predicate or 'Nothing' if no
329 -- such element exists.
330 find :: Storable a => (a -> Bool) -> Vector a -> Maybe a
331 {-# INLINE find #-}
332 find = G.find
333
334 -- | Yield 'Just' the index of the first element matching the predicate or
335 -- 'Nothing' if no such element exists.
336 findIndex :: Storable a => (a -> Bool) -> Vector a -> Maybe Int
337 {-# INLINE findIndex #-}
338 findIndex = G.findIndex
339
340 -- Folding
341 -- -------
342
343 -- | Left fold
344 foldl :: Storable b => (a -> b -> a) -> a -> Vector b -> a
345 {-# INLINE foldl #-}
346 foldl = G.foldl
347
348 -- | Lefgt fold on non-empty vectors
349 foldl1 :: Storable a => (a -> a -> a) -> Vector a -> a
350 {-# INLINE foldl1 #-}
351 foldl1 = G.foldl1
352
353 -- | Left fold with strict accumulator
354 foldl' :: Storable b => (a -> b -> a) -> a -> Vector b -> a
355 {-# INLINE foldl' #-}
356 foldl' = G.foldl'
357
358 -- | Left fold on non-empty vectors with strict accumulator
359 foldl1' :: Storable a => (a -> a -> a) -> Vector a -> a
360 {-# INLINE foldl1' #-}
361 foldl1' = G.foldl1'
362
363 -- | Right fold
364 foldr :: Storable a => (a -> b -> b) -> b -> Vector a -> b
365 {-# INLINE foldr #-}
366 foldr = G.foldr
367
368 -- | Right fold on non-empty vectors
369 foldr1 :: Storable a => (a -> a -> a) -> Vector a -> a
370 {-# INLINE foldr1 #-}
371 foldr1 = G.foldr1
372
373 -- Specialised folds
374 -- -----------------
375
376 and :: Vector Bool -> Bool
377 {-# INLINE and #-}
378 and = G.and
379
380 or :: Vector Bool -> Bool
381 {-# INLINE or #-}
382 or = G.or
383
384 sum :: (Storable a, Num a) => Vector a -> a
385 {-# INLINE sum #-}
386 sum = G.sum
387
388 product :: (Storable a, Num a) => Vector a -> a
389 {-# INLINE product #-}
390 product = G.product
391
392 maximum :: (Storable a, Ord a) => Vector a -> a
393 {-# INLINE maximum #-}
394 maximum = G.maximum
395
396 minimum :: (Storable a, Ord a) => Vector a -> a
397 {-# INLINE minimum #-}
398 minimum = G.minimum
399
400 -- Unfolding
401 -- ---------
402
403 unfoldr :: Storable a => (b -> Maybe (a, b)) -> b -> Vector a
404 {-# INLINE unfoldr #-}
405 unfoldr = G.unfoldr
406
407 -- Scans
408 -- -----
409
410 -- | Prefix scan
411 prescanl :: (Storable a, Storable b) => (a -> b -> a) -> a -> Vector b -> Vector a
412 {-# INLINE prescanl #-}
413 prescanl = G.prescanl
414
415 -- | Prefix scan with strict accumulator
416 prescanl' :: (Storable a, Storable b) => (a -> b -> a) -> a -> Vector b -> Vector a
417 {-# INLINE prescanl' #-}
418 prescanl' = G.prescanl'
419
420 -- | Suffix scan
421 postscanl :: (Storable a, Storable b) => (a -> b -> a) -> a -> Vector b -> Vector a
422 {-# INLINE postscanl #-}
423 postscanl = G.postscanl
424
425 -- | Suffix scan with strict accumulator
426 postscanl' :: (Storable a, Storable b) => (a -> b -> a) -> a -> Vector b -> Vector a
427 {-# INLINE postscanl' #-}
428 postscanl' = G.postscanl'
429
430 -- | Haskell-style scan
431 scanl :: (Storable a, Storable b) => (a -> b -> a) -> a -> Vector b -> Vector a
432 {-# INLINE scanl #-}
433 scanl = G.scanl
434
435 -- | Haskell-style scan with strict accumulator
436 scanl' :: (Storable a, Storable b) => (a -> b -> a) -> a -> Vector b -> Vector a
437 {-# INLINE scanl' #-}
438 scanl' = G.scanl'
439
440 -- | Scan over a non-empty 'Vector'
441 scanl1 :: Storable a => (a -> a -> a) -> Vector a -> Vector a
442 {-# INLINE scanl1 #-}
443 scanl1 = G.scanl1
444
445 -- | Scan over a non-empty 'Vector' with a strict accumulator
446 scanl1' :: Storable a => (a -> a -> a) -> Vector a -> Vector a
447 {-# INLINE scanl1' #-}
448 scanl1' = G.scanl1'
449
450 -- Enumeration
451 -- -----------
452
453 enumFromTo :: (Storable a, Enum a) => a -> a -> Vector a
454 {-# INLINE enumFromTo #-}
455 enumFromTo = G.enumFromTo
456
457 enumFromThenTo :: (Storable a, Enum a) => a -> a -> a -> Vector a
458 {-# INLINE enumFromThenTo #-}
459 enumFromThenTo = G.enumFromThenTo
460
461 -- Conversion to/from lists
462 -- ------------------------
463
464 -- | Convert a vector to a list
465 toList :: Storable a => Vector a -> [a]
466 {-# INLINE toList #-}
467 toList = G.toList
468
469 -- | Convert a list to a vector
470 fromList :: Storable a => [a] -> Vector a
471 {-# INLINE fromList #-}
472 fromList = G.fromList
473