Rename copy -> force
[darcs-mirrors/vector.git] / Data / Vector / Primitive.hs
index c19474c..8b4c6cd 100644 (file)
@@ -1,8 +1,8 @@
-{-# LANGUAGE FlexibleInstances, MultiParamTypeClasses, TypeFamilies #-}
+{-# LANGUAGE FlexibleInstances, MultiParamTypeClasses, TypeFamilies, ScopedTypeVariables #-}
 
 -- |
 -- Module      : Data.Vector.Primitive
--- Copyright   : (c) Roman Leshchinskiy 2008-2009
+-- Copyright   : (c) Roman Leshchinskiy 2008-2010
 -- License     : BSD-style
 --
 -- Maintainer  : Roman Leshchinskiy <rl@cse.unsw.edu.au>
@@ -19,7 +19,7 @@ module Data.Vector.Primitive (
   length, null,
 
   -- * Construction
-  empty, singleton, cons, snoc, replicate, generate, (++), copy,
+  empty, singleton, cons, snoc, replicate, generate, (++), force,
 
   -- * Accessing individual elements
   (!), head, last, indexM, headM, lastM,
@@ -45,14 +45,14 @@ module Data.Vector.Primitive (
 
   -- * Filtering
   filter, ifilter, takeWhile, dropWhile,
-  unstablePartition, span, break,
+  partition, unstablePartition, span, break,
 
   -- * Searching
   elem, notElem, find, findIndex, findIndices, elemIndex, elemIndices,
 
   -- * Folding
-  foldl, foldl1, foldl', foldl1', foldr, foldr1,
-  ifoldl, ifoldl', ifoldr,
+  foldl, foldl1, foldl', foldl1', foldr, foldr1, foldr', foldr1',
+  ifoldl, ifoldl', ifoldr, ifoldr',
 
   -- * Specialised folds
   all, any,
@@ -61,24 +61,28 @@ module Data.Vector.Primitive (
   minIndex, minIndexBy, maxIndex, maxIndexBy,
 
   -- * Unfolding
-  unfoldr,
+  unfoldr, unfoldrN,
 
   -- * Scans
   prescanl, prescanl',
   postscanl, postscanl',
   scanl, scanl', scanl1, scanl1',
+  prescanr, prescanr',
+  postscanr, postscanr',
+  scanr, scanr', scanr1, scanr1',
 
   -- * Enumeration
-  enumFromTo, enumFromThenTo,
+  enumFromN, enumFromStepN, enumFromTo, enumFromThenTo,
 
   -- * Conversion to/from lists
-  toList, fromList
+  toList, fromList, fromListN
 ) where
 
 import qualified Data.Vector.Generic           as G
 import           Data.Vector.Primitive.Mutable ( MVector(..) )
+import qualified Data.Vector.Fusion.Stream as Stream
 import           Data.Primitive.ByteArray
-import           Data.Primitive ( Prim )
+import           Data.Primitive ( Prim, sizeOf )
 
 import Control.Monad ( liftM )
 
@@ -92,19 +96,31 @@ import Prelude hiding ( length, null,
                         elem, notElem,
                         foldl, foldl1, foldr, foldr1,
                         all, any, sum, product, minimum, maximum,
-                        scanl, scanl1,
+                        scanl, scanl1, scanr, scanr1,
                         enumFromTo, enumFromThenTo )
 
 import qualified Prelude
 
+import Data.Typeable ( Typeable )
+import Data.Data     ( Data(..) )
+
 -- | Unboxed vectors of primitive types
 data Vector a = Vector {-# UNPACK #-} !Int
                        {-# UNPACK #-} !Int
                        {-# UNPACK #-} !ByteArray
+  deriving ( Typeable )
 
 instance (Show a, Prim a) => Show (Vector a) where
     show = (Prelude.++ " :: Data.Vector.Primitive.Vector") . ("fromList " Prelude.++) . show . toList
 
+instance (Data a, Prim a) => Data (Vector a) where
+  gfoldl       = G.gfoldl
+  toConstr _   = error "toConstr"
+  gunfold _ _  = error "gunfold"
+  dataTypeOf _ = G.mkType "Data.Vector.Primitive.Vector"
+  dataCast1    = G.dataCast
+
+
 type instance G.Mutable Vector = MVector
 
 instance Prim a => G.Vector Vector a where
@@ -121,16 +137,39 @@ instance Prim a => G.Vector Vector a where
   {-# INLINE basicUnsafeIndexM #-}
   basicUnsafeIndexM (Vector i _ arr) j = return (indexByteArray arr (i+j))
 
+  {-# INLINE basicUnsafeCopy #-}
+  basicUnsafeCopy (MVector i n dst) (Vector j _ src)
+    = memcpyByteArray' dst (i * sz) src (j * sz) (n * sz)
+    where
+      sz = sizeOf (undefined :: a)
+
   {-# INLINE elemseq #-}
   elemseq _ = seq
 
+-- See [HACKS:Eq and Ord instances]
 instance (Prim a, Eq a) => Eq (Vector a) where
   {-# INLINE (==) #-}
-  (==) = G.eq
+  xs == ys = Stream.eq (G.stream xs) (G.stream ys)
+
+  {-# INLINE (/=) #-}
+  xs /= ys = not (Stream.eq (G.stream xs) (G.stream ys))
 
+-- See [HACKS:Eq and Ord instances]
 instance (Prim a, Ord a) => Ord (Vector a) where
   {-# INLINE compare #-}
-  compare = G.cmp
+  compare xs ys = Stream.cmp (G.stream xs) (G.stream ys)
+
+  {-# INLINE (<) #-}
+  xs < ys = Stream.cmp (G.stream xs) (G.stream ys) == LT
+
+  {-# INLINE (<=) #-}
+  xs <= ys = Stream.cmp (G.stream xs) (G.stream ys) /= GT
+
+  {-# INLINE (>) #-}
+  xs > ys = Stream.cmp (G.stream xs) (G.stream ys) == GT
+
+  {-# INLINE (>=) #-}
+  xs >= ys = Stream.cmp (G.stream xs) (G.stream ys) /= LT
 
 -- Length
 -- ------
@@ -184,9 +223,9 @@ infixr 5 ++
 (++) = (G.++)
 
 -- | Create a copy of a vector. Useful when dealing with slices.
-copy :: Prim a => Vector a -> Vector a
-{-# INLINE copy #-}
-copy = G.copy
+force :: Prim a => Vector a -> Vector a
+{-# INLINE force #-}
+force = G.force
 
 -- Accessing individual elements
 -- -----------------------------
@@ -466,6 +505,14 @@ dropWhile :: Prim a => (a -> Bool) -> Vector a -> Vector a
 dropWhile = G.dropWhile
 
 -- | Split the vector in two parts, the first one containing those elements
+-- that satisfy the predicate and the second one those that don't. The
+-- relative order of the elements is preserved at the cost of a (sometimes)
+-- reduced performance compared to 'unstablePartition'.
+partition :: Prim a => (a -> Bool) -> Vector a -> (Vector a, Vector a)
+{-# INLINE partition #-}
+partition = G.partition
+
+-- | Split the vector in two parts, the first one containing those elements
 -- that satisfy the predicate and the second one those that don't. The order
 -- of the elements is not preserved.
 unstablePartition :: Prim a => (a -> Bool) -> Vector a -> (Vector a, Vector a)
@@ -560,6 +607,16 @@ foldr1 :: Prim a => (a -> a -> a) -> Vector a -> a
 {-# INLINE foldr1 #-}
 foldr1 = G.foldr1
 
+-- | Right fold with a strict accumulator
+foldr' :: Prim a => (a -> b -> b) -> b -> Vector a -> b
+{-# INLINE foldr' #-}
+foldr' = G.foldr'
+
+-- | Right fold on non-empty vectors with strict accumulator
+foldr1' :: Prim a => (a -> a -> a) -> Vector a -> a
+{-# INLINE foldr1' #-}
+foldr1' = G.foldr1'
+
 -- | Left fold (function applied to each element and its index)
 ifoldl :: Prim b => (a -> Int -> b -> a) -> a -> Vector b -> a
 {-# INLINE ifoldl #-}
@@ -576,6 +633,12 @@ ifoldr :: Prim a => (Int -> a -> b -> b) -> b -> Vector a -> b
 {-# INLINE ifoldr #-}
 ifoldr = G.ifoldr
 
+-- | Right fold with strict accumulator (function applied to each element and
+-- its index)
+ifoldr' :: Prim a => (Int -> a -> b -> b) -> b -> Vector a -> b
+{-# INLINE ifoldr' #-}
+ifoldr' = G.ifoldr'
+
 -- Specialised folds
 -- -----------------
 
@@ -630,10 +693,27 @@ minIndexBy = G.minIndexBy
 -- Unfolding
 -- ---------
 
+-- | The 'unfoldr' function is a \`dual\' to 'foldr': while 'foldr'
+-- reduces a vector to a summary value, 'unfoldr' builds a list from
+-- a seed value.  The function takes the element and returns 'Nothing'
+-- if it is done generating the vector or returns 'Just' @(a,b)@, in which
+-- case, @a@ is a prepended to the vector and @b@ is used as the next
+-- element in a recursive call.
+--
+-- A simple use of unfoldr:
+--
+-- > unfoldr (\b -> if b == 0 then Nothing else Just (b, b-1)) 10
+-- >  [10,9,8,7,6,5,4,3,2,1]
+--
 unfoldr :: Prim a => (b -> Maybe (a, b)) -> b -> Vector a
 {-# INLINE unfoldr #-}
 unfoldr = G.unfoldr
 
+-- | Unfold at most @n@ elements
+unfoldrN :: Prim a => Int -> (b -> Maybe (a, b)) -> b -> Vector a
+{-# INLINE unfoldrN #-}
+unfoldrN = G.unfoldrN
+
 -- Scans
 -- -----
 
@@ -677,13 +757,75 @@ scanl1' :: Prim a => (a -> a -> a) -> Vector a -> Vector a
 {-# INLINE scanl1' #-}
 scanl1' = G.scanl1'
 
+
+-- | Prefix right-to-left scan
+prescanr :: (Prim a, Prim b) => (a -> b -> b) -> b -> Vector a -> Vector b
+{-# INLINE prescanr #-}
+prescanr = G.prescanr
+
+-- | Prefix right-to-left scan with strict accumulator
+prescanr' :: (Prim a, Prim b) => (a -> b -> b) -> b -> Vector a -> Vector b
+{-# INLINE prescanr' #-}
+prescanr' = G.prescanr'
+
+-- | Suffix right-to-left scan
+postscanr :: (Prim a, Prim b) => (a -> b -> b) -> b -> Vector a -> Vector b
+{-# INLINE postscanr #-}
+postscanr = G.postscanr
+
+-- | Suffix right-to-left scan with strict accumulator
+postscanr' :: (Prim a, Prim b) => (a -> b -> b) -> b -> Vector a -> Vector b
+{-# INLINE postscanr' #-}
+postscanr' = G.postscanr'
+
+-- | Haskell-style right-to-left scan
+scanr :: (Prim a, Prim b) => (a -> b -> b) -> b -> Vector a -> Vector b
+{-# INLINE scanr #-}
+scanr = G.scanr
+
+-- | Haskell-style right-to-left scan with strict accumulator
+scanr' :: (Prim a, Prim b) => (a -> b -> b) -> b -> Vector a -> Vector b
+{-# INLINE scanr' #-}
+scanr' = G.scanr'
+
+-- | Right-to-left scan over a non-empty vector
+scanr1 :: Prim a => (a -> a -> a) -> Vector a -> Vector a
+{-# INLINE scanr1 #-}
+scanr1 = G.scanr1
+
+-- | Right-to-left scan over a non-empty vector with a strict accumulator
+scanr1' :: Prim a => (a -> a -> a) -> Vector a -> Vector a
+{-# INLINE scanr1' #-}
+scanr1' = G.scanr1'
+
 -- Enumeration
 -- -----------
 
+-- | Yield a vector of the given length containing the values @x@, @x+1@ etc.
+-- This operation is usually more efficient than 'enumFromTo'.
+enumFromN :: (Prim a, Num a) => a -> Int -> Vector a
+{-# INLINE enumFromN #-}
+enumFromN = G.enumFromN
+
+-- | Yield a vector of the given length containing the values @x@, @x+y@,
+-- @x+y+y@ etc. This operations is usually more efficient than
+-- 'enumFromThenTo'.
+enumFromStepN :: (Prim a, Num a) => a -> a -> Int -> Vector a
+{-# INLINE enumFromStepN #-}
+enumFromStepN = G.enumFromStepN
+
+-- | Enumerate values from @x@ to @y@.
+--
+-- /WARNING:/ This operation can be very inefficient. If at all possible, use
+-- 'enumFromN' instead.
 enumFromTo :: (Prim a, Enum a) => a -> a -> Vector a
 {-# INLINE enumFromTo #-}
 enumFromTo = G.enumFromTo
 
+-- | Enumerate values from @x@ to @y@ with a specific step @z@.
+--
+-- /WARNING:/ This operation can be very inefficient. If at all possible, use
+-- 'enumFromStepN' instead.
 enumFromThenTo :: (Prim a, Enum a) => a -> a -> a -> Vector a
 {-# INLINE enumFromThenTo #-}
 enumFromThenTo = G.enumFromThenTo
@@ -701,3 +843,10 @@ fromList :: Prim a => [a] -> Vector a
 {-# INLINE fromList #-}
 fromList = G.fromList
 
+-- | Convert the first @n@ elements of a list to a vector
+--
+-- > fromListN n xs = fromList (take n xs)
+fromListN :: Prim a => Int -> [a] -> Vector a
+{-# INLINE fromListN #-}
+fromListN = G.fromListN
+