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