{-|
Module      : Z.Data.Vector.Base
Description : Fast boxed and unboxed vector
Copyright   : (c) Dong Han, 2017-2019
              (c) Tao He, 2018-2019
License     : BSD
Maintainer  : winterland1989@gmail.com
Stability   : experimental
Portability : non-portable

This module provides unified vector interface. Conceptually a vector is simply a slice of an array, for example this is the definition of boxed vector:

@
data Vector a = Vector !(SmallArray a)   !Int    !Int
                     -- payload           offset  length
@

The 'Vec' class unified different type of vectors, and this module provide operation over 'Vec' instances, with all the internal structures. Be careful on modifying internal slices, otherwise segmentation fault await.

-}

module Z.Data.Vector.Base (
  -- * The Vec typeclass
    Vec(..)
  , pattern Vec
  , arrVec
  , indexMaybe
  -- * Boxed and unboxed vector type
  , Vector(..)
  , PrimVector(..)
  -- ** Word8 vector
  , Bytes, packASCII
  -- * Creating utilities
  , create, create', creating, creating', createN, createN2
  , empty, singleton, copy
  -- * Conversion between list
  , pack, packN, packN', packR, packRN, packRN'
  , unpack, unpackR
  -- * Basic interface
  , null
  , length
  , append
  , map, map', imap', traverse, traverseWithIndex, traverse_, traverseWithIndex_
  , mapM, mapM_, forM, forM_
  , foldl', ifoldl', foldl1', foldl1Maybe'
  , foldr', ifoldr', foldr1', foldr1Maybe'
  , shuffle, permutations
    -- ** Special folds
  , concat, concatR, concatMap
  , maximum, minimum, maximumMaybe, minimumMaybe
  , sum
  , count, countBytes
  , product, product'
  , all, any
  -- * Building vector
  -- ** Accumulating maps
  , mapAccumL
  , mapAccumR
  -- ** Generating and unfolding vector
  , replicate
  , replicateM
  , cycleN
  , unfoldr
  , unfoldrN
  -- * Searching by equality
  , elem, notElem, elemIndex
  -- * Misc
  , IPair(..), mapIPair', fromIPair, toIPair
  , defaultInitSize
  , chunkOverhead
  , defaultChunkSize
  , smallChunkSize
  , VectorException(..)
  , errorEmptyVector
  , errorOutRange
  , castVector
  , replicatePM
  , traverseWithIndexPM
  -- * C FFI
  , c_strcmp
  , c_memchr
  , c_memrchr
  , c_strlen
  , c_ascii_validate_addr
  , c_fnv_hash_addr
  , c_fnv_hash_ba
 ) where

import           Control.DeepSeq
import           Control.Exception
import qualified Control.Monad             as M
import           Control.Monad.Primitive
import           Control.Monad.ST
import           Data.Bits
import qualified Data.CaseInsensitive      as CI
import           Data.Char                 (ord)
import qualified Data.Foldable             as F
import           Data.Functor.Classes      (Eq1 (..))
import           Data.Hashable             (Hashable (..))
import           Data.Hashable.Lifted      (Hashable1 (..), hashWithSalt1)
import           Data.Kind                 (Type)
import qualified Data.List                 as List
import           Data.List.NonEmpty        (NonEmpty ((:|)))
import           Data.Maybe
import           Data.Primitive            hiding (copyPtrToMutablePrimArray)
import           Data.Semigroup            (Semigroup (..))
import qualified Data.Traversable          as T
import           Foreign.C
import           GHC.Exts
import           GHC.Stack
import           GHC.Word
import           Prelude                   hiding (all, any, concat, concatMap,
                                            elem, foldl, foldl1, foldr, foldr1,
                                            length, map, mapM, mapM_, maximum,
                                            minimum, notElem, null, product,
                                            replicate, sum, traverse)
import           System.IO.Unsafe          (unsafeDupablePerformIO)
import           System.Random.Stateful    (StatefulGen)
import           Test.QuickCheck.Arbitrary (Arbitrary (..), CoArbitrary (..))
import           Test.QuickCheck.Gen       (chooseInt)
import           Text.Read                 (Read (..))

import           Z.Data.Array
import           Z.Data.ASCII              (toLower)

-- | Typeclass for box and unboxed vectors, which are created by slicing arrays.
--
-- Instead of providing a generalized vector with polymorphric array field, we use this typeclass
-- so that instances use concrete array type can unpack their array payload.
--
-- Vector types, e.g. 'Vector','PrimVector'... are obivious instances, with O(1) 'toArr' and
-- 'fromArr', which convert slices to (array, offset, length) tuple back and forth.
--
-- Array types can also be instances of this class, e.g. 'Array', 'PrimArray'..., in this case
-- 'toArr' will always return offset 0 and whole array length, and 'fromArr' is O(n) 'copyArr'.
class (Arr (IArray v) a) => Vec v a where
    -- | Vector's immutable array type
    type IArray v :: Type -> Type
    -- | Get underline array and slice range(offset and length).
    toArr :: v a -> (IArray v a, Int, Int)
    -- | Create a vector by slicing an array(with offset and length).
    fromArr :: IArray v a -> Int -> Int -> v a

-- | Change vector types based on same array type, e.g. construct a whole slice from an array.
arrVec :: (Vec v a, Vec u a, IArray v ~ IArray u) => v a -> u a
{-# INLINE arrVec #-}
arrVec :: forall (v :: * -> *) a (u :: * -> *).
(Vec v a, Vec u a, IArray v ~ IArray u) =>
v a -> u a
arrVec v a
bs = let (IArray v a
arr, Int
s, Int
l) = forall (v :: * -> *) a. Vec v a => v a -> (IArray v a, Int, Int)
toArr v a
bs in forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arr Int
s Int
l

instance Vec Array a where
    type IArray Array = Array
    {-# INLINE toArr #-}
    toArr :: Array a -> (IArray Array a, Int, Int)
toArr Array a
arr = (Array a
arr, Int
0, forall (arr :: * -> *) a. Arr arr a => arr a -> Int
sizeofArr Array a
arr)
    {-# INLINE fromArr #-}
    fromArr :: IArray Array a -> Int -> Int -> Array a
fromArr = forall (arr :: * -> *) a. Arr arr a => arr a -> Int -> Int -> arr a
fromArray

instance Vec SmallArray a where
    type IArray SmallArray = SmallArray
    {-# INLINE toArr #-}
    toArr :: SmallArray a -> (IArray SmallArray a, Int, Int)
toArr SmallArray a
arr = (SmallArray a
arr, Int
0, forall (arr :: * -> *) a. Arr arr a => arr a -> Int
sizeofArr SmallArray a
arr)
    {-# INLINE fromArr #-}
    fromArr :: IArray SmallArray a -> Int -> Int -> SmallArray a
fromArr = forall (arr :: * -> *) a. Arr arr a => arr a -> Int -> Int -> arr a
fromArray

instance Prim a => Vec PrimArray a where
    type IArray PrimArray = PrimArray
    {-# INLINE toArr #-}
    toArr :: PrimArray a -> (IArray PrimArray a, Int, Int)
toArr PrimArray a
arr = (PrimArray a
arr, Int
0, forall (arr :: * -> *) a. Arr arr a => arr a -> Int
sizeofArr PrimArray a
arr)
    {-# INLINE fromArr #-}
    fromArr :: IArray PrimArray a -> Int -> Int -> PrimArray a
fromArr = forall (arr :: * -> *) a. Arr arr a => arr a -> Int -> Int -> arr a
fromArray

instance PrimUnlifted a => Vec UnliftedArray a where
    type IArray UnliftedArray = UnliftedArray
    {-# INLINE toArr #-}
    toArr :: UnliftedArray a -> (IArray UnliftedArray a, Int, Int)
toArr UnliftedArray a
arr = (UnliftedArray a
arr, Int
0, forall (arr :: * -> *) a. Arr arr a => arr a -> Int
sizeofArr UnliftedArray a
arr)
    {-# INLINE fromArr #-}
    fromArr :: IArray UnliftedArray a -> Int -> Int -> UnliftedArray a
fromArr = forall (arr :: * -> *) a. Arr arr a => arr a -> Int -> Int -> arr a
fromArray

fromArray :: Arr arr a => arr a -> Int -> Int -> arr a
{-# INLINE fromArray #-}
fromArray :: forall (arr :: * -> *) a. Arr arr a => arr a -> Int -> Int -> arr a
fromArray arr a
arr Int
offset Int
len | Int
offset forall a. Eq a => a -> a -> Bool
== Int
0 Bool -> Bool -> Bool
&& forall (arr :: * -> *) a. Arr arr a => arr a -> Int
sizeofArr arr a
arr forall a. Eq a => a -> a -> Bool
== Int
len = arr a
arr
                         | Bool
otherwise = forall (arr :: * -> *) a.
(Arr arr a, HasCallStack) =>
arr a -> Int -> Int -> arr a
cloneArr arr a
arr Int
offset Int
len

-- | A pattern synonyms for matching the underline array, offset and length.
--
-- This is a bidirectional pattern synonyms, but very unsafe if not use properly.
-- Make sure your slice is within array's bounds!
pattern Vec :: Vec v a => IArray v a -> Int -> Int -> v a
pattern $bVec :: forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
$mVec :: forall {r} {v :: * -> *} {a}.
Vec v a =>
v a -> (IArray v a -> Int -> Int -> r) -> ((# #) -> r) -> r
Vec arr s l <- (toArr -> (arr,s,l)) where
        Vec IArray v a
arr Int
s Int
l = forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arr Int
s Int
l

-- | /O(1)/ Index vector's element.
--
-- Return 'Nothing' if index is out of bounds.
--
indexMaybe :: Vec v a => v a -> Int -> Maybe a
{-# INLINE indexMaybe #-}
indexMaybe :: forall (v :: * -> *) a. Vec v a => v a -> Int -> Maybe a
indexMaybe (Vec IArray v a
arr Int
s Int
l) Int
i | Int
i forall a. Ord a => a -> a -> Bool
< Int
0 Bool -> Bool -> Bool
|| Int
i forall a. Ord a => a -> a -> Bool
>= Int
l = forall a. Maybe a
Nothing
                           | Bool
otherwise       = IArray v a
arr forall (arr :: * -> *) a (m :: * -> *).
(Arr arr a, Monad m, HasCallStack) =>
arr a -> Int -> m a
`indexArrM` (Int
s forall a. Num a => a -> a -> a
+ Int
i)

--------------------------------------------------------------------------------
-- | Boxed vector
--
data Vector a = Vector
    {-# UNPACK #-} !(SmallArray a)  -- ^ payload
    {-# UNPACK #-} !Int             -- ^ offset
    {-# UNPACK #-} !Int             -- ^ length

instance Vec Vector a where
    type IArray Vector = SmallArray
    {-# INLINE toArr #-}
    toArr :: Vector a -> (IArray Vector a, Int, Int)
toArr (Vector SmallArray a
arr Int
s Int
l) = (SmallArray a
arr, Int
s, Int
l)
    {-# INLINE fromArr #-}
    fromArr :: IArray Vector a -> Int -> Int -> Vector a
fromArr = forall a. SmallArray a -> Int -> Int -> Vector a
Vector

instance IsList (Vector a) where
    type Item (Vector a) = a
    {-# INLINE fromList #-}
    fromList :: [Item (Vector a)] -> Vector a
fromList = forall (v :: * -> *) a. Vec v a => [a] -> v a
pack
    {-# INLINE toList #-}
    toList :: Vector a -> [Item (Vector a)]
toList = forall (v :: * -> *) a. Vec v a => v a -> [a]
unpack
    {-# INLINE fromListN #-}
    fromListN :: Int -> [Item (Vector a)] -> Vector a
fromListN = forall (v :: * -> *) a. Vec v a => Int -> [a] -> v a
packN

instance Eq a => Eq (Vector a) where
    {-# INLINE (==) #-}
    Vector a
v1 == :: Vector a -> Vector a -> Bool
== Vector a
v2 = forall a b. (a -> b -> Bool) -> Vector a -> Vector b -> Bool
eqVector forall a. Eq a => a -> a -> Bool
(==) Vector a
v1 Vector a
v2

instance Eq1 Vector where
    {-# INLINE liftEq #-}
    liftEq :: forall a b. (a -> b -> Bool) -> Vector a -> Vector b -> Bool
liftEq = forall a b. (a -> b -> Bool) -> Vector a -> Vector b -> Bool
eqVector

eqVector :: (a -> b -> Bool) -> Vector a -> Vector b -> Bool
{-# INLINE eqVector #-}
eqVector :: forall a b. (a -> b -> Bool) -> Vector a -> Vector b -> Bool
eqVector a -> b -> Bool
eq (Vector SmallArray a
baA Int
sA Int
lA) (Vector SmallArray b
baB Int
sB Int
lB)
    | SmallArray a
baA forall {a} {a}. SmallArray a -> SmallArray a -> Bool
`sameArr'` SmallArray b
baB =
        if Int
sA forall a. Eq a => a -> a -> Bool
== Int
sB then Int
lA forall a. Eq a => a -> a -> Bool
== Int
lB else Int
lA forall a. Eq a => a -> a -> Bool
== Int
lB Bool -> Bool -> Bool
&& Int -> Int -> Bool
go Int
sA Int
sB
    | Bool
otherwise = Int
lA forall a. Eq a => a -> a -> Bool
== Int
lB Bool -> Bool -> Bool
&& Int -> Int -> Bool
go Int
sA Int
sB
  where
    !endA :: Int
endA = Int
sA forall a. Num a => a -> a -> a
+ Int
lA
    go :: Int -> Int -> Bool
go !Int
i !Int
j
        | Int
i forall a. Ord a => a -> a -> Bool
>= Int
endA = Bool
True
        | Bool
otherwise =
            (forall a. SmallArray a -> Int -> a
indexSmallArray SmallArray a
baA Int
i a -> b -> Bool
`eq` forall a. SmallArray a -> Int -> a
indexSmallArray SmallArray b
baB Int
j) Bool -> Bool -> Bool
&& Int -> Int -> Bool
go (Int
iforall a. Num a => a -> a -> a
+Int
1) (Int
jforall a. Num a => a -> a -> a
+Int
1)
    -- The same implementation as 'sameArr' but with different type signature
    -- sameArr' :: arr a -> arr b -> Bool
    sameArr' :: SmallArray a -> SmallArray a -> Bool
sameArr' (SmallArray SmallArray# a
arr1#) (SmallArray SmallArray# a
arr2#) = Int# -> Bool
isTrue# (
        forall d a.
SmallMutableArray# d a -> SmallMutableArray# d a -> Int#
sameSmallMutableArray# (unsafeCoerce# :: forall a b. a -> b
unsafeCoerce# SmallArray# a
arr1#) (unsafeCoerce# :: forall a b. a -> b
unsafeCoerce# SmallArray# a
arr2#))

instance Ord a => Ord (Vector a) where
    {-# INLINE compare #-}
    compare :: Vector a -> Vector a -> Ordering
compare = forall a. Ord a => Vector a -> Vector a -> Ordering
compareVector

compareVector :: Ord a => Vector a -> Vector a -> Ordering
{-# INLINE compareVector #-}
compareVector :: forall a. Ord a => Vector a -> Vector a -> Ordering
compareVector (Vector SmallArray a
baA Int
sA Int
lA) (Vector SmallArray a
baB Int
sB Int
lB)
    | SmallArray a
baA forall (arr :: * -> *) a. Arr arr a => arr a -> arr a -> Bool
`sameArr` SmallArray a
baB = if Int
sA forall a. Eq a => a -> a -> Bool
== Int
sB then Int
lA forall a. Ord a => a -> a -> Ordering
`compare` Int
lB else Int -> Int -> Ordering
go Int
sA Int
sB
    | Bool
otherwise = Int -> Int -> Ordering
go Int
sA Int
sB
  where
    !endA :: Int
endA = Int
sA forall a. Num a => a -> a -> a
+ Int
lA
    !endB :: Int
endB = Int
sB forall a. Num a => a -> a -> a
+ Int
lB
    go :: Int -> Int -> Ordering
go !Int
i !Int
j | Int
i forall a. Ord a => a -> a -> Bool
>= Int
endA  = Int
lA forall a. Ord a => a -> a -> Ordering
`compare` Int
lB
             | Int
j forall a. Ord a => a -> a -> Bool
>= Int
endB  = Int
lA forall a. Ord a => a -> a -> Ordering
`compare` Int
lB
             | Bool
otherwise = let o :: Ordering
o = forall a. SmallArray a -> Int -> a
indexSmallArray SmallArray a
baA Int
i forall a. Ord a => a -> a -> Ordering
`compare` forall a. SmallArray a -> Int -> a
indexSmallArray SmallArray a
baB Int
j
                           in case Ordering
o of Ordering
EQ -> Int -> Int -> Ordering
go (Int
iforall a. Num a => a -> a -> a
+Int
1) (Int
jforall a. Num a => a -> a -> a
+Int
1)
                                        Ordering
x  -> Ordering
x

instance Semigroup (Vector a) where
    {-# INLINE (<>) #-}
    <> :: Vector a -> Vector a -> Vector a
(<>)    = forall (v :: * -> *) a. Vec v a => v a -> v a -> v a
append
    {-# INLINE sconcat #-}
    sconcat :: NonEmpty (Vector a) -> Vector a
sconcat (Vector a
b:|[Vector a]
bs) = forall (v :: * -> *) a. Vec v a => [v a] -> v a
concat (Vector a
bforall a. a -> [a] -> [a]
:[Vector a]
bs)
    {-# INLINE stimes #-}
    stimes :: forall b. Integral b => b -> Vector a -> Vector a
stimes  = forall (v :: * -> *) a x. (Vec v a, Integral x) => x -> v a -> v a
_cycleN

instance Monoid (Vector a) where
    {-# INLINE mempty #-}
    mempty :: Vector a
mempty  = forall (v :: * -> *) a. Vec v a => v a
empty
    {-# INLINE mappend #-}
    mappend :: Vector a -> Vector a -> Vector a
mappend = forall a. Semigroup a => a -> a -> a
(<>)
    {-# INLINE mconcat #-}
    mconcat :: [Vector a] -> Vector a
mconcat = forall (v :: * -> *) a. Vec v a => [v a] -> v a
concat

instance NFData a => NFData (Vector a) where
    {-# INLINE rnf #-}
    rnf :: Vector a -> ()
rnf (Vector SmallArray a
arr Int
s Int
l) = Int -> ()
go Int
s
      where
        !end :: Int
end = Int
sforall a. Num a => a -> a -> a
+Int
l
        go :: Int -> ()
go !Int
i | Int
i forall a. Ord a => a -> a -> Bool
< Int
end   = case forall (arr :: * -> *) a.
(Arr arr a, HasCallStack) =>
arr a -> Int -> (# a #)
indexArr' SmallArray a
arr Int
i of (# a
x #) -> a
x seq :: forall a b. a -> b -> b
`seq` Int -> ()
go (Int
iforall a. Num a => a -> a -> a
+Int
1)
              | Bool
otherwise = ()

instance (Show a) => Show (Vector a) where
    showsPrec :: Int -> Vector a -> ShowS
showsPrec Int
p Vector a
v = forall a. Show a => Int -> a -> ShowS
showsPrec Int
p (forall (v :: * -> *) a. Vec v a => v a -> [a]
unpack Vector a
v)

instance (Read a) => Read (Vector a) where
    readPrec :: ReadPrec (Vector a)
readPrec = forall (v :: * -> *) a. Vec v a => [a] -> v a
pack forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall a. Read a => ReadPrec a
readPrec

instance Functor Vector where
    {-# INLINE fmap #-}
    fmap :: forall a b. (a -> b) -> Vector a -> Vector b
fmap = forall (u :: * -> *) (v :: * -> *) a b.
(Vec u a, Vec v b) =>
(a -> b) -> u a -> v b
map

instance F.Foldable Vector where
    {-# INLINE foldr' #-}
    foldr' :: forall a b. (a -> b -> b) -> b -> Vector a -> b
foldr' = forall (v :: * -> *) a b. Vec v a => (a -> b -> b) -> b -> v a -> b
foldr'
    {-# INLINE foldr #-}
    foldr :: forall a b. (a -> b -> b) -> b -> Vector a -> b
foldr a -> b -> b
f b
acc = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
List.foldr a -> b -> b
f b
acc forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (v :: * -> *) a. Vec v a => v a -> [a]
unpack
    {-# INLINE foldl' #-}
    foldl' :: forall b a. (b -> a -> b) -> b -> Vector a -> b
foldl' = forall (v :: * -> *) a b. Vec v a => (b -> a -> b) -> b -> v a -> b
foldl'
    {-# INLINE foldl #-}
    foldl :: forall b a. (b -> a -> b) -> b -> Vector a -> b
foldl b -> a -> b
f b
acc = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
List.foldr (forall a b c. (a -> b -> c) -> b -> a -> c
flip b -> a -> b
f) b
acc forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (v :: * -> *) a. Vec v a => v a -> [a]
unpackR
    {-# INLINE toList #-}
    toList :: forall a. Vector a -> [a]
toList = forall (v :: * -> *) a. Vec v a => v a -> [a]
unpack
    {-# INLINE null #-}
    null :: forall a. Vector a -> Bool
null = forall (v :: * -> *) a. Vec v a => v a -> Bool
null
    {-# INLINE length #-}
    length :: forall a. Vector a -> Int
length = forall (v :: * -> *) a. Vec v a => v a -> Int
length
    {-# INLINE elem #-}
    elem :: forall a. Eq a => a -> Vector a -> Bool
elem = forall (v :: * -> *) a. (Vec v a, Eq a) => a -> v a -> Bool
elem
    {-# INLINE maximum #-}
    maximum :: forall a. Ord a => Vector a -> a
maximum = forall (v :: * -> *) a. (Vec v a, Ord a, HasCallStack) => v a -> a
maximum
    {-# INLINE minimum #-}
    minimum :: forall a. Ord a => Vector a -> a
minimum = forall (v :: * -> *) a. (Vec v a, Ord a, HasCallStack) => v a -> a
minimum
    {-# INLINE product #-}
    product :: forall a. Num a => Vector a -> a
product = forall (v :: * -> *) a. (Vec v a, Num a) => v a -> a
product
    {-# INLINE sum #-}
    sum :: forall a. Num a => Vector a -> a
sum = forall (v :: * -> *) a. (Vec v a, Num a) => v a -> a
sum

instance T.Traversable Vector where
    {-# INLINE traverse #-}
    traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Vector a -> f (Vector b)
traverse = forall (v :: * -> *) a (u :: * -> *) b (f :: * -> *).
(Vec v a, Vec u b, Applicative f) =>
(a -> f b) -> v a -> f (u b)
traverse

instance Arbitrary a => Arbitrary (Vector a) where
    arbitrary :: Gen (Vector a)
arbitrary = do
        [a]
vs <- forall a. Arbitrary a => Gen a
arbitrary
        let l :: Int
l = forall (t :: * -> *) a. Foldable t => t a -> Int
List.length [a]
vs
        Int
s <- (Int, Int) -> Gen Int
chooseInt (Int
0, Int
l)
        Int
l' <- (Int, Int) -> Gen Int
chooseInt (Int
0, Int
l forall a. Num a => a -> a -> a
- Int
s)
        forall (f :: * -> *) a. Applicative f => a -> f a
pure forall a b. (a -> b) -> a -> b
$ forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr (forall (v :: * -> *) a. Vec v a => [a] -> v a
pack [a]
vs) Int
s Int
l'
    shrink :: Vector a -> [Vector a]
shrink Vector a
v = forall (v :: * -> *) a. Vec v a => [a] -> v a
pack forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall a. Arbitrary a => a -> [a]
shrink (forall (v :: * -> *) a. Vec v a => v a -> [a]
unpack Vector a
v)

instance CoArbitrary a => CoArbitrary (Vector a) where
    coarbitrary :: forall b. Vector a -> Gen b -> Gen b
coarbitrary = forall a b. CoArbitrary a => a -> Gen b -> Gen b
coarbitrary forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (v :: * -> *) a. Vec v a => v a -> [a]
unpack

instance Hashable a => Hashable (Vector a) where
    {-# INLINE hashWithSalt #-}
    hashWithSalt :: Int -> Vector a -> Int
hashWithSalt = forall (f :: * -> *) a.
(Hashable1 f, Hashable a) =>
Int -> f a -> Int
hashWithSalt1

instance Hashable1 Vector where
    {-# INLINE liftHashWithSalt #-}
    liftHashWithSalt :: forall a. (Int -> a -> Int) -> Int -> Vector a -> Int
liftHashWithSalt Int -> a -> Int
h Int
salt0 (Vector SmallArray a
arr Int
s Int
l) = forall a. Hashable a => Int -> a -> Int
hashWithSalt (Int -> Int -> Int
go Int
salt0 Int
s) Int
l
      where
        !end :: Int
end = Int
s forall a. Num a => a -> a -> a
+ Int
l
        go :: Int -> Int -> Int
go !Int
salt !Int
i
            | Int
i forall a. Ord a => a -> a -> Bool
>= Int
end  = Int
salt
            | Bool
otherwise = Int -> Int -> Int
go (Int -> a -> Int
h Int
salt (forall (arr :: * -> *) a.
(Arr arr a, HasCallStack) =>
arr a -> Int -> a
indexArr SmallArray a
arr Int
i)) (Int
iforall a. Num a => a -> a -> a
+Int
1)

-- | Traverse vector and gather result in another vector.
--
-- There're rules to optimize the intermedia list away when @f@ is an instance of 'PrimMoand',
-- such as 'IO', 'ST' or 'Z.Data.Parser.Parser'.
traverse :: (Vec v a, Vec u b, Applicative f) => (a -> f b) -> v a -> f (u b)
{-# INLINE [1] traverse #-}
{-# RULES "traverse/IO" forall (f :: a -> IO b). traverse f = traverseWithIndexPM (const f) #-}
{-# RULES "traverse/ST" forall (f :: a -> ST s b). traverse f = traverseWithIndexPM (const f) #-}
traverse :: forall (v :: * -> *) a (u :: * -> *) b (f :: * -> *).
(Vec v a, Vec u b, Applicative f) =>
(a -> f b) -> v a -> f (u b)
traverse a -> f b
f v a
v = forall (v :: * -> *) a. Vec v a => Int -> [a] -> v a
packN (forall (v :: * -> *) a. Vec v a => v a -> Int
length v a
v) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
T.traverse a -> f b
f (forall (v :: * -> *) a. Vec v a => v a -> [a]
unpack v a
v)

-- | Traverse vector and gather result in another vector.
traverseWithIndex :: (Vec v a, Vec u b, Applicative f) => (Int -> a -> f b) -> v a -> f (u b)
{-# INLINE [1] traverseWithIndex #-}
{-# RULES "traverseWithIndex/IO" forall (f :: Int -> a -> IO b). traverseWithIndex f = traverseWithIndexPM f #-}
{-# RULES "traverseWithIndex/ST" forall (f :: Int -> a -> ST s b). traverseWithIndex f = traverseWithIndexPM f #-}
traverseWithIndex :: forall (v :: * -> *) a (u :: * -> *) b (f :: * -> *).
(Vec v a, Vec u b, Applicative f) =>
(Int -> a -> f b) -> v a -> f (u b)
traverseWithIndex Int -> a -> f b
f v a
v = forall (v :: * -> *) a. Vec v a => Int -> [a] -> v a
packN (forall (v :: * -> *) a. Vec v a => v a -> Int
length v a
v) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall (m :: * -> *) a b c.
Applicative m =>
(a -> b -> m c) -> [a] -> [b] -> m [c]
M.zipWithM Int -> a -> f b
f [Int
0..] (forall (v :: * -> *) a. Vec v a => v a -> [a]
unpack v a
v)

-- | 'PrimMonad' specialzied version of 'traverseWithIndex'.
--
-- You can add rules to rewrite 'traverse' and 'traverseWithIndex' to this function in your own 'PrimMonad' instance, e.g.
--
-- @
-- instance PrimMonad YourMonad where ...
--
-- {-# RULES "traverse\/YourMonad" forall (f :: a -> YourMonad b). traverse\' f = traverseWithIndexPM (const f) #-}
-- {-# RULES "traverseWithIndex\/YourMonad" forall (f :: Int -> a -> YourMonad b). traverseWithIndex f = traverseWithIndexPM f #-}
-- @
--
traverseWithIndexPM :: forall m v u a b. (PrimMonad m, Vec v a, Vec u b) => (Int -> a -> m b) -> v a -> m (u b)
{-# INLINE traverseWithIndexPM #-}
traverseWithIndexPM :: forall (m :: * -> *) (v :: * -> *) (u :: * -> *) a b.
(PrimMonad m, Vec v a, Vec u b) =>
(Int -> a -> m b) -> v a -> m (u b)
traverseWithIndexPM Int -> a -> m b
f (Vec IArray v a
arr Int
s Int
l)
    | Int
l forall a. Eq a => a -> a -> Bool
== Int
0    = forall (m :: * -> *) a. Monad m => a -> m a
return forall (v :: * -> *) a. Vec v a => v a
empty
    | Bool
otherwise = do
        !MArr (IArray u) (PrimState m) b
marr <- forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
Int -> m (MArr arr s a)
newArr Int
l
        IArray u b
ba <- MArr (IArray u) (PrimState m) b -> Int -> m (IArray u b)
go MArr (IArray u) (PrimState m) b
marr Int
0
        forall (m :: * -> *) a. Monad m => a -> m a
return forall a b. (a -> b) -> a -> b
$! forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray u b
ba Int
0 Int
l
  where
    go :: MArr (IArray u) (PrimState m) b -> Int -> m (IArray u b)
    go :: MArr (IArray u) (PrimState m) b -> Int -> m (IArray u b)
go MArr (IArray u) (PrimState m) b
marr !Int
i
        | Int
i forall a. Ord a => a -> a -> Bool
>= Int
l = forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> m (arr a)
unsafeFreezeArr MArr (IArray u) (PrimState m) b
marr
        | Bool
otherwise = do
            forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray u) (PrimState m) b
marr Int
i forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< Int -> a -> m b
f Int
i (forall (arr :: * -> *) a.
(Arr arr a, HasCallStack) =>
arr a -> Int -> a
indexArr IArray v a
arr (Int
iforall a. Num a => a -> a -> a
+Int
s))
            MArr (IArray u) (PrimState m) b -> Int -> m (IArray u b)
go MArr (IArray u) (PrimState m) b
marr (Int
iforall a. Num a => a -> a -> a
+Int
1)

-- | Traverse vector without gathering result.
traverse_ :: (Vec v a, Applicative f) => (a -> f b) -> v a -> f ()
{-# INLINE traverse_ #-}
traverse_ :: forall (v :: * -> *) a (f :: * -> *) b.
(Vec v a, Applicative f) =>
(a -> f b) -> v a -> f ()
traverse_ a -> f b
f (Vec IArray v a
arr Int
s Int
l) = Int -> f ()
go Int
s
  where
    end :: Int
end = Int
s forall a. Num a => a -> a -> a
+ Int
l
    go :: Int -> f ()
go !Int
i
        | Int
i forall a. Ord a => a -> a -> Bool
>= Int
end = forall (f :: * -> *) a. Applicative f => a -> f a
pure ()
        | Bool
otherwise = a -> f b
f (forall (arr :: * -> *) a.
(Arr arr a, HasCallStack) =>
arr a -> Int -> a
indexArr IArray v a
arr Int
i) forall (f :: * -> *) a b. Applicative f => f a -> f b -> f b
*> Int -> f ()
go (Int
iforall a. Num a => a -> a -> a
+Int
1)

-- | Traverse vector with index.
traverseWithIndex_ :: (Vec v a, Applicative f) => (Int -> a -> f b) -> v a -> f ()
{-# INLINE traverseWithIndex_ #-}
traverseWithIndex_ :: forall (v :: * -> *) a (f :: * -> *) b.
(Vec v a, Applicative f) =>
(Int -> a -> f b) -> v a -> f ()
traverseWithIndex_ Int -> a -> f b
f (Vec IArray v a
arr Int
s Int
l) = Int -> f ()
go Int
s
  where
    end :: Int
end = Int
s forall a. Num a => a -> a -> a
+ Int
l
    go :: Int -> f ()
go !Int
i
        | Int
i forall a. Ord a => a -> a -> Bool
>= Int
end = forall (f :: * -> *) a. Applicative f => a -> f a
pure ()
        | Bool
otherwise = Int -> a -> f b
f (Int
iforall a. Num a => a -> a -> a
-Int
s) (forall (arr :: * -> *) a.
(Arr arr a, HasCallStack) =>
arr a -> Int -> a
indexArr IArray v a
arr Int
i) forall (f :: * -> *) a b. Applicative f => f a -> f b -> f b
*> Int -> f ()
go (Int
iforall a. Num a => a -> a -> a
+Int
1)

-- | Alias for 'traverse'.
mapM ::  (Vec v a, Vec u b, Applicative f) => (a -> f b) -> v a -> f (u b)
{-# INLINE mapM #-}
mapM :: forall (v :: * -> *) a (u :: * -> *) b (f :: * -> *).
(Vec v a, Vec u b, Applicative f) =>
(a -> f b) -> v a -> f (u b)
mapM = forall (v :: * -> *) a (u :: * -> *) b (f :: * -> *).
(Vec v a, Vec u b, Applicative f) =>
(a -> f b) -> v a -> f (u b)
traverse

-- | Alias for 'traverse_'.
mapM_ ::  (Vec v a, Applicative f) => (a -> f b) -> v a -> f ()
{-# INLINE mapM_ #-}
mapM_ :: forall (v :: * -> *) a (f :: * -> *) b.
(Vec v a, Applicative f) =>
(a -> f b) -> v a -> f ()
mapM_ = forall (v :: * -> *) a (f :: * -> *) b.
(Vec v a, Applicative f) =>
(a -> f b) -> v a -> f ()
traverse_

-- | Flipped version of 'traverse'.
forM ::  (Vec v a, Vec u b, Applicative f) => v a -> (a -> f b) -> f (u b)
{-# INLINE forM #-}
forM :: forall (v :: * -> *) a (u :: * -> *) b (f :: * -> *).
(Vec v a, Vec u b, Applicative f) =>
v a -> (a -> f b) -> f (u b)
forM v a
v a -> f b
f = forall (v :: * -> *) a (u :: * -> *) b (f :: * -> *).
(Vec v a, Vec u b, Applicative f) =>
(a -> f b) -> v a -> f (u b)
traverse a -> f b
f v a
v

-- | Flipped version of 'traverse_'.
forM_ ::  (Vec v a, Applicative f) => v a -> (a -> f b) -> f ()
{-# INLINE forM_ #-}
forM_ :: forall (v :: * -> *) a (f :: * -> *) b.
(Vec v a, Applicative f) =>
v a -> (a -> f b) -> f ()
forM_ v a
v a -> f b
f = forall (v :: * -> *) a (f :: * -> *) b.
(Vec v a, Applicative f) =>
(a -> f b) -> v a -> f ()
traverse_ a -> f b
f v a
v


--------------------------------------------------------------------------------
-- | Primitive vector
--
data PrimVector a = PrimVector
    {-# UNPACK #-} !(PrimArray a)   -- ^ payload
    {-# UNPACK #-} !Int             -- ^ offset in elements of type a rather than in bytes
    {-# UNPACK #-} !Int             -- ^ length in elements of type a rather than in bytes

instance Prim a => Vec PrimVector a where
    type IArray PrimVector = PrimArray
    {-# INLINE toArr #-}
    toArr :: PrimVector a -> (IArray PrimVector a, Int, Int)
toArr (PrimVector PrimArray a
arr Int
s Int
l) = (PrimArray a
arr, Int
s, Int
l)
    {-# INLINE fromArr #-}
    fromArr :: IArray PrimVector a -> Int -> Int -> PrimVector a
fromArr = forall a. PrimArray a -> Int -> Int -> PrimVector a
PrimVector

instance (Prim a, Eq a) => Eq (PrimVector a) where
    {-# INLINE (==) #-}
    == :: PrimVector a -> PrimVector a -> Bool
(==) = forall a. Prim a => PrimVector a -> PrimVector a -> Bool
eqPrimVector

eqPrimVector :: forall a. Prim a => PrimVector a -> PrimVector a -> Bool
{-# INLINE eqPrimVector #-}
eqPrimVector :: forall a. Prim a => PrimVector a -> PrimVector a -> Bool
eqPrimVector (PrimVector (PrimArray ByteArray#
baA#) (I# Int#
sA#) Int
lA)
             (PrimVector (PrimArray ByteArray#
baB#) (I# Int#
sB#) Int
lB)
    = -- we use memcmp for all primitive vector, ghc emit code to test
      -- pointer equality so we don't have to do it manually here
      Int
lA forall a. Eq a => a -> a -> Bool
== Int
lB Bool -> Bool -> Bool
&&
        Int
0 forall a. Eq a => a -> a -> Bool
== Int# -> Int
I# (ByteArray# -> Int# -> ByteArray# -> Int# -> Int# -> Int#
compareByteArrays# ByteArray#
baA# (Int#
sA# Int# -> Int# -> Int#
*# Int#
siz#) ByteArray#
baB# (Int#
sB# Int# -> Int# -> Int#
*# Int#
siz#) Int#
n#)
  where
    !siz :: Int
siz@(I# Int#
siz#) = forall a. Prim a => a -> Int
sizeOf (forall a. HasCallStack => a
undefined :: a)
    !(I# Int#
n#) = Int
lAforall a. Num a => a -> a -> a
*Int
siz

instance (Prim a, Ord a) => Ord (PrimVector a) where
    {-# INLINE compare #-}
    compare :: PrimVector a -> PrimVector a -> Ordering
compare = forall a.
(Prim a, Ord a) =>
PrimVector a -> PrimVector a -> Ordering
comparePrimVector

comparePrimVector :: (Prim a, Ord a) => PrimVector a -> PrimVector a -> Ordering
{-# INLINE comparePrimVector #-}
comparePrimVector :: forall a.
(Prim a, Ord a) =>
PrimVector a -> PrimVector a -> Ordering
comparePrimVector (PrimVector PrimArray a
baA Int
sA Int
lA) (PrimVector PrimArray a
baB Int
sB Int
lB)
    | PrimArray a
baA forall (arr :: * -> *) a. Arr arr a => arr a -> arr a -> Bool
`sameArr` PrimArray a
baB = if Int
sA forall a. Eq a => a -> a -> Bool
== Int
sB then Int
lA forall a. Ord a => a -> a -> Ordering
`compare` Int
lB else Int -> Int -> Ordering
go Int
sA Int
sB
    | Bool
otherwise = Int -> Int -> Ordering
go Int
sA Int
sB
  where
    !endA :: Int
endA = Int
sA forall a. Num a => a -> a -> a
+ Int
lA
    !endB :: Int
endB = Int
sB forall a. Num a => a -> a -> a
+ Int
lB
    go :: Int -> Int -> Ordering
go !Int
i !Int
j | Int
i forall a. Ord a => a -> a -> Bool
>= Int
endA  = Int
lA forall a. Ord a => a -> a -> Ordering
`compare` Int
lB
             | Int
j forall a. Ord a => a -> a -> Bool
>= Int
endB  = Int
lA forall a. Ord a => a -> a -> Ordering
`compare` Int
lB
             | Bool
otherwise = let o :: Ordering
o = forall a. Prim a => PrimArray a -> Int -> a
indexPrimArray PrimArray a
baA Int
i forall a. Ord a => a -> a -> Ordering
`compare` forall a. Prim a => PrimArray a -> Int -> a
indexPrimArray PrimArray a
baB Int
j
                           in case Ordering
o of Ordering
EQ -> Int -> Int -> Ordering
go (Int
iforall a. Num a => a -> a -> a
+Int
1) (Int
jforall a. Num a => a -> a -> a
+Int
1)
                                        Ordering
x  -> Ordering
x

-- | This is an INCOHERENT instance, compare binary data using SIMD.
instance {-# INCOHERENT #-} Ord Bytes where
    {-# INLINE compare #-}
    compare :: Bytes -> Bytes -> Ordering
compare = Bytes -> Bytes -> Ordering
compareBytes

compareBytes :: PrimVector Word8 -> PrimVector Word8 -> Ordering
{-# INLINE compareBytes #-}
compareBytes :: Bytes -> Bytes -> Ordering
compareBytes (PrimVector (PrimArray ByteArray#
baA#) (I# Int#
sA#) Int
lA)
             (PrimVector (PrimArray ByteArray#
baB#) (I# Int#
sB#) Int
lB) =
    let !(I# Int#
n#) = forall a. Ord a => a -> a -> a
min Int
lA Int
lB
        r :: Int
r = Int# -> Int
I# (ByteArray# -> Int# -> ByteArray# -> Int# -> Int# -> Int#
compareByteArrays# ByteArray#
baA# Int#
sA# ByteArray#
baB# Int#
sB# Int#
n#)
    in case Int
r forall a. Ord a => a -> a -> Ordering
`compare` Int
0 of
        Ordering
EQ -> Int
lA forall a. Ord a => a -> a -> Ordering
`compare` Int
lB
        Ordering
x  -> Ordering
x

instance Prim a => Semigroup (PrimVector a) where
    {-# INLINE (<>) #-}
    <> :: PrimVector a -> PrimVector a -> PrimVector a
(<>)    = forall (v :: * -> *) a. Vec v a => v a -> v a -> v a
append
    {-# INLINE sconcat #-}
    sconcat :: NonEmpty (PrimVector a) -> PrimVector a
sconcat (PrimVector a
b:|[PrimVector a]
bs) = forall (v :: * -> *) a. Vec v a => [v a] -> v a
concat (PrimVector a
bforall a. a -> [a] -> [a]
:[PrimVector a]
bs)
    {-# INLINE stimes #-}
    stimes :: forall b. Integral b => b -> PrimVector a -> PrimVector a
stimes  = forall (v :: * -> *) a x. (Vec v a, Integral x) => x -> v a -> v a
_cycleN

instance Prim a => Monoid (PrimVector a) where
    {-# INLINE mempty #-}
    mempty :: PrimVector a
mempty  = forall (v :: * -> *) a. Vec v a => v a
empty
    {-# INLINE mappend #-}
    mappend :: PrimVector a -> PrimVector a -> PrimVector a
mappend = forall a. Semigroup a => a -> a -> a
(<>)
    {-# INLINE mconcat #-}
    mconcat :: [PrimVector a] -> PrimVector a
mconcat = forall (v :: * -> *) a. Vec v a => [v a] -> v a
concat

instance NFData (PrimVector a) where
    {-# INLINE rnf #-}
    rnf :: PrimVector a -> ()
rnf PrimVector{} = ()

instance (Prim a, Show a) => Show (PrimVector a) where
    showsPrec :: Int -> PrimVector a -> ShowS
showsPrec Int
p PrimVector a
v = forall a. Show a => Int -> a -> ShowS
showsPrec Int
p (forall (v :: * -> *) a. Vec v a => v a -> [a]
unpack PrimVector a
v)

instance (Prim a, Read a) => Read (PrimVector a) where
    readPrec :: ReadPrec (PrimVector a)
readPrec = forall (v :: * -> *) a. Vec v a => [a] -> v a
pack forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall a. Read a => ReadPrec a
readPrec

instance (Prim a, Arbitrary a) => Arbitrary (PrimVector a) where
    arbitrary :: Gen (PrimVector a)
arbitrary = do
        [a]
vs <- forall a. Arbitrary a => Gen a
arbitrary
        let l :: Int
l = forall (t :: * -> *) a. Foldable t => t a -> Int
List.length [a]
vs
        Int
s <- (Int, Int) -> Gen Int
chooseInt (Int
0, Int
l)
        Int
l' <- (Int, Int) -> Gen Int
chooseInt (Int
0, Int
l forall a. Num a => a -> a -> a
- Int
s)
        forall (f :: * -> *) a. Applicative f => a -> f a
pure forall a b. (a -> b) -> a -> b
$ forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr (forall (v :: * -> *) a. Vec v a => [a] -> v a
pack [a]
vs) Int
s Int
l'
    shrink :: PrimVector a -> [PrimVector a]
shrink PrimVector a
v = forall (v :: * -> *) a. Vec v a => [a] -> v a
pack forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall a. Arbitrary a => a -> [a]
shrink (forall (v :: * -> *) a. Vec v a => v a -> [a]
unpack PrimVector a
v)

instance (Prim a, CoArbitrary a) => CoArbitrary (PrimVector a) where
    coarbitrary :: forall b. PrimVector a -> Gen b -> Gen b
coarbitrary = forall a b. CoArbitrary a => a -> Gen b -> Gen b
coarbitrary forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (v :: * -> *) a. Vec v a => v a -> [a]
unpack

instance (Hashable a, Prim a) => Hashable (PrimVector a) where
    {-# INLINE hashWithSalt #-}
    hashWithSalt :: Int -> PrimVector a -> Int
hashWithSalt = forall a. (Hashable a, Prim a) => Int -> PrimVector a -> Int
hashWithSaltPrimVector

hashWithSaltPrimVector :: (Hashable a, Prim a) => Int -> PrimVector a -> Int
{-# INLINE hashWithSaltPrimVector #-}
hashWithSaltPrimVector :: forall a. (Hashable a, Prim a) => Int -> PrimVector a -> Int
hashWithSaltPrimVector Int
salt0 (PrimVector PrimArray a
arr Int
s Int
l) = Int -> Int -> Int
go Int
salt0 Int
s
  where
    -- we don't do a final hash with length to keep consistent with Bytes's instance
    !end :: Int
end = Int
s forall a. Num a => a -> a -> a
+ Int
l
    go :: Int -> Int -> Int
go !Int
salt !Int
i
        | Int
i forall a. Ord a => a -> a -> Bool
>= Int
end  = Int
salt
        | Bool
otherwise = Int -> Int -> Int
go (forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
salt (forall a. Prim a => PrimArray a -> Int -> a
indexPrimArray PrimArray a
arr Int
i)) (Int
iforall a. Num a => a -> a -> a
+Int
1)

-- | This is an INCOHERENT instance, hash binary data using FNV-1a
--
-- Note this is different from @Vector Word8@ or @[Word8]@ which use FNV-1.
instance {-# INCOHERENT #-} Hashable Bytes where
    {-# INLINE hashWithSalt #-}
    hashWithSalt :: Int -> Bytes -> Int
hashWithSalt = Int -> Bytes -> Int
hashWithSaltBytes

hashWithSaltBytes :: Int -> Bytes -> Int
{-# INLINE hashWithSaltBytes #-}
hashWithSaltBytes :: Int -> Bytes -> Int
hashWithSaltBytes Int
salt (PrimVector (PrimArray ByteArray#
ba#) Int
s Int
l) =
    forall a. IO a -> a
unsafeDupablePerformIO (ByteArray# -> Int -> Int -> Int -> IO Int
c_fnv_hash_ba ByteArray#
ba# Int
s Int
l Int
salt)

--------------------------------------------------------------------------------

-- | 'Bytes' is just primitive word8 vectors.
type Bytes = PrimVector Word8

-- | This instance use 'packASCII', which may silently chop bytes, use it with ASCII literals only.
instance a ~ Word8 => IsString (PrimVector a) where
    {-# INLINE fromString #-}
    fromString :: String -> PrimVector a
fromString = String -> Bytes
packASCII

instance Prim a => IsList (PrimVector a) where
    type Item (PrimVector a) = a
    {-# INLINE fromList #-}
    fromList :: [Item (PrimVector a)] -> PrimVector a
fromList = forall (v :: * -> *) a. Vec v a => [a] -> v a
pack
    {-# INLINE toList #-}
    toList :: PrimVector a -> [Item (PrimVector a)]
toList = forall (v :: * -> *) a. Vec v a => v a -> [a]
unpack
    {-# INLINE fromListN #-}
    fromListN :: Int -> [Item (PrimVector a)] -> PrimVector a
fromListN = forall (v :: * -> *) a. Vec v a => Int -> [a] -> v a
packN

-- | This instance assume ASCII encoded bytes
instance CI.FoldCase Bytes where
    {-# INLINE foldCase #-}
    foldCase :: Bytes -> Bytes
foldCase = forall (u :: * -> *) (v :: * -> *) a b.
(Vec u a, Vec v b) =>
(a -> b) -> u a -> v b
map Word8 -> Word8
toLower

-- | /O(n)/, pack an ASCII 'String', multi-bytes char WILL BE CHOPPED!
packASCII :: String -> Bytes
{-# INLINE CONLIKE [0] packASCII #-}
{-# RULES "packASCII/packASCIIAddr" forall addr . packASCII (unpackCString# addr) = packASCIIAddr addr #-}
packASCII :: String -> Bytes
packASCII = forall (v :: * -> *) a. Vec v a => [a] -> v a
pack forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (forall a b. (Integral a, Num b) => a -> b
fromIntegral forall b c a. (b -> c) -> (a -> b) -> a -> c
. Char -> Int
ord)

packASCIIAddr :: Addr# -> Bytes
{-# INLINE packASCIIAddr #-}
packASCIIAddr :: Addr# -> Bytes
packASCIIAddr Addr#
addr0# = Addr# -> Bytes
go Addr#
addr0#
  where
    len :: Int
len = forall a b. (Integral a, Num b) => a -> b
fromIntegral forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. IO a -> a
unsafeDupablePerformIO forall a b. (a -> b) -> a -> b
$ Addr# -> IO CSize
c_strlen Addr#
addr0#
    go :: Addr# -> Bytes
go Addr#
addr# = forall a. (forall s. ST s a) -> a
runST forall a b. (a -> b) -> a -> b
$ do
        MutablePrimArray s Word8
marr <- forall (m :: * -> *) a.
(PrimMonad m, Prim a) =>
Int -> m (MutablePrimArray (PrimState m) a)
newPrimArray Int
len
        forall (m :: * -> *) a.
(PrimMonad m, Prim a, HasCallStack) =>
MutablePrimArray (PrimState m) a -> Int -> Ptr a -> Int -> m ()
copyPtrToMutablePrimArray MutablePrimArray s Word8
marr Int
0 (forall a. Addr# -> Ptr a
Ptr Addr#
addr#) Int
len
        PrimArray Word8
arr <- forall (m :: * -> *) a.
PrimMonad m =>
MutablePrimArray (PrimState m) a -> m (PrimArray a)
unsafeFreezePrimArray MutablePrimArray s Word8
marr
        forall (m :: * -> *) a. Monad m => a -> m a
return (forall a. PrimArray a -> Int -> Int -> PrimVector a
PrimVector PrimArray Word8
arr Int
0 Int
len)


--------------------------------------------------------------------------------
-- Basic creating

-- | Create a vector with size N.
--
create :: Vec v a
       => Int                                   -- ^ length in elements of type @a@
       -> (forall s. MArr (IArray v) s a -> ST s ())   -- ^ initialization function
       -> v a
{-# INLINE create #-}
create :: forall (v :: * -> *) a.
Vec v a =>
Int -> (forall s. MArr (IArray v) s a -> ST s ()) -> v a
create Int
n forall s. MArr (IArray v) s a -> ST s ()
fill = forall a. HasCallStack => Bool -> a -> a
assert (Int
n forall a. Ord a => a -> a -> Bool
>= Int
0) forall a b. (a -> b) -> a -> b
$ forall a. (forall s. ST s a) -> a
runST (do
        MArr (IArray v) s a
marr <- forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
Int -> m (MArr arr s a)
newArr Int
n
        forall s. MArr (IArray v) s a -> ST s ()
fill MArr (IArray v) s a
marr
        IArray v a
ba <- forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> m (arr a)
unsafeFreezeArr MArr (IArray v) s a
marr
        forall (m :: * -> *) a. Monad m => a -> m a
return forall a b. (a -> b) -> a -> b
$! forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
ba Int
0 Int
n)

-- | Create a vector with a initial size N array (which may not be the final array).
--
create' :: Vec v a
        => Int
        -- ^ length in elements of type @a@
        -> (forall s. MArr (IArray v) s a -> ST s (IPair (MArr (IArray v) s a)))
        -- ^ initialization function return a result size and array, the result must start from index 0
        -> v a
{-# INLINE create' #-}
create' :: forall (v :: * -> *) a.
Vec v a =>
Int
-> (forall s.
    MArr (IArray v) s a -> ST s (IPair (MArr (IArray v) s a)))
-> v a
create' Int
n forall s. MArr (IArray v) s a -> ST s (IPair (MArr (IArray v) s a))
fill = forall a. HasCallStack => Bool -> a -> a
assert (Int
n forall a. Ord a => a -> a -> Bool
>= Int
0) forall a b. (a -> b) -> a -> b
$ forall a. (forall s. ST s a) -> a
runST (do
        MArr (IArray v) s a
marr <- forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
Int -> m (MArr arr s a)
newArr Int
n
        IPair Int
n' MArr (IArray v) s a
marr' <- forall s. MArr (IArray v) s a -> ST s (IPair (MArr (IArray v) s a))
fill MArr (IArray v) s a
marr
        forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> m ()
shrinkMutableArr MArr (IArray v) s a
marr' Int
n'
        IArray v a
ba <- forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> m (arr a)
unsafeFreezeArr MArr (IArray v) s a
marr'
        forall (m :: * -> *) a. Monad m => a -> m a
return forall a b. (a -> b) -> a -> b
$! forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
ba Int
0 Int
n')

-- | Create a vector with a initial size N array, return both the vector and
-- the monadic result during creating.
--
-- The result is not demanded strictly while the returned vector will be in normal form.
-- It this is not desired, use @return $!@ idiom in your initialization function.
creating :: Vec v a
         => Int  -- length in elements of type @a@
         -> (forall s. MArr (IArray v) s a -> ST s b)  -- ^ initialization function
         -> (b, v a)
{-# INLINE creating #-}
creating :: forall (v :: * -> *) a b.
Vec v a =>
Int -> (forall s. MArr (IArray v) s a -> ST s b) -> (b, v a)
creating Int
n forall s. MArr (IArray v) s a -> ST s b
fill = forall a. HasCallStack => Bool -> a -> a
assert (Int
n forall a. Ord a => a -> a -> Bool
>= Int
0) forall a b. (a -> b) -> a -> b
$ forall a. (forall s. ST s a) -> a
runST (do
        MArr (IArray v) s a
marr <- forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
Int -> m (MArr arr s a)
newArr Int
n
        b
b <- forall s. MArr (IArray v) s a -> ST s b
fill MArr (IArray v) s a
marr
        IArray v a
ba <- forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> m (arr a)
unsafeFreezeArr MArr (IArray v) s a
marr
        let !v :: v a
v = forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
ba Int
0 Int
n
        forall (m :: * -> *) a. Monad m => a -> m a
return (b
b, v a
v))

-- | Create a vector with a initial size N array (which may not be the final array),
-- return both the vector and the monadic result during creating.
--
-- The result is not demanded strictly while the returned vector will be in normal form.
-- It this is not desired, use @return $!@ idiom in your initialization function.
creating' :: Vec v a
         => Int  -- length in elements of type @a@
         -> (forall s. MArr (IArray v) s a -> ST s (b, (IPair (MArr (IArray v) s a))))  -- ^ initialization function
         -> (b, v a)
{-# INLINE creating' #-}
creating' :: forall (v :: * -> *) a b.
Vec v a =>
Int
-> (forall s.
    MArr (IArray v) s a -> ST s (b, IPair (MArr (IArray v) s a)))
-> (b, v a)
creating' Int
n forall s.
MArr (IArray v) s a -> ST s (b, IPair (MArr (IArray v) s a))
fill = forall a. HasCallStack => Bool -> a -> a
assert (Int
n forall a. Ord a => a -> a -> Bool
>= Int
0) forall a b. (a -> b) -> a -> b
$ forall a. (forall s. ST s a) -> a
runST (do
        MArr (IArray v) s a
marr <- forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
Int -> m (MArr arr s a)
newArr Int
n
        (b
b, IPair Int
n' MArr (IArray v) s a
marr') <- forall s.
MArr (IArray v) s a -> ST s (b, IPair (MArr (IArray v) s a))
fill MArr (IArray v) s a
marr
        forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> m ()
shrinkMutableArr MArr (IArray v) s a
marr' Int
n'
        IArray v a
ba <- forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> m (arr a)
unsafeFreezeArr MArr (IArray v) s a
marr'
        let !v :: v a
v = forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
ba Int
0 Int
n'
        forall (m :: * -> *) a. Monad m => a -> m a
return (b
b, v a
v))

-- | Create a vector up to a specific length.
--
-- If the initialization function return a length larger than initial size,
-- an 'IndexOutOfVectorRange' will be raised.
--
createN :: (Vec v a, HasCallStack)
        => Int                                  -- ^ length's upper bound
        -> (forall s. MArr (IArray v) s a -> ST s Int) -- ^ initialization function which return the actual length
        -> v a
{-# INLINE createN #-}
createN :: forall (v :: * -> *) a.
(Vec v a, HasCallStack) =>
Int -> (forall s. MArr (IArray v) s a -> ST s Int) -> v a
createN Int
n0 forall s. MArr (IArray v) s a -> ST s Int
fill = forall a. (forall s. ST s a) -> a
runST (do
        let n :: Int
n = forall a. Ord a => a -> a -> a
max Int
0 Int
n0
        MArr (IArray v) s a
marr <- forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
Int -> m (MArr arr s a)
newArr Int
n
        Int
l' <- forall s. MArr (IArray v) s a -> ST s Int
fill MArr (IArray v) s a
marr
        forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> m ()
shrinkMutableArr MArr (IArray v) s a
marr Int
l'
        IArray v a
ba <- forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> m (arr a)
unsafeFreezeArr MArr (IArray v) s a
marr
        if Int
l' forall a. Ord a => a -> a -> Bool
<= Int
n
        then forall (m :: * -> *) a. Monad m => a -> m a
return forall a b. (a -> b) -> a -> b
$! forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
ba Int
0 Int
l'
        else forall a. HasCallStack => Int -> a
errorOutRange Int
l')

-- | Create two vector up to a specific length.
--
-- If the initialization function return lengths larger than initial sizes,
-- an 'IndexOutOfVectorRange' will be raised.
--
createN2 :: (Vec v a, Vec u b, HasCallStack)
         => Int
         -> Int
         -> (forall s. MArr (IArray v) s a -> MArr (IArray u) s b -> ST s (Int,Int))
         -> (v a, u b)
{-# INLINE createN2 #-}
createN2 :: forall (v :: * -> *) a (u :: * -> *) b.
(Vec v a, Vec u b, HasCallStack) =>
Int
-> Int
-> (forall s.
    MArr (IArray v) s a -> MArr (IArray u) s b -> ST s (Int, Int))
-> (v a, u b)
createN2 Int
n0 Int
n1 forall s.
MArr (IArray v) s a -> MArr (IArray u) s b -> ST s (Int, Int)
fill = forall a. (forall s. ST s a) -> a
runST (do
        let n0' :: Int
n0' = forall a. Ord a => a -> a -> a
max Int
0 Int
n0
            n1' :: Int
n1' = forall a. Ord a => a -> a -> a
max Int
0 Int
n1
        MArr (IArray v) s a
mba0 <- forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
Int -> m (MArr arr s a)
newArr Int
n0'
        MArr (IArray u) s b
mba1 <- forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
Int -> m (MArr arr s a)
newArr Int
n1'
        (Int
l0, Int
l1) <- forall s.
MArr (IArray v) s a -> MArr (IArray u) s b -> ST s (Int, Int)
fill MArr (IArray v) s a
mba0 MArr (IArray u) s b
mba1
        forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> m ()
shrinkMutableArr MArr (IArray v) s a
mba0 Int
l0
        forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> m ()
shrinkMutableArr MArr (IArray u) s b
mba1 Int
l1
        IArray v a
ba0 <- forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> m (arr a)
unsafeFreezeArr MArr (IArray v) s a
mba0
        IArray u b
ba1 <- forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> m (arr a)
unsafeFreezeArr MArr (IArray u) s b
mba1
        if (Int
l0 forall a. Ord a => a -> a -> Bool
<= Int
n0)
        then if (Int
l1 forall a. Ord a => a -> a -> Bool
<= Int
n1)
            then let !v1 :: v a
v1 = forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
ba0 Int
0 Int
l0
                     !v2 :: u b
v2 = forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray u b
ba1 Int
0 Int
l1
                 in forall (m :: * -> *) a. Monad m => a -> m a
return (v a
v1, u b
v2)
            else forall a. HasCallStack => Int -> a
errorOutRange Int
l1
        else forall a. HasCallStack => Int -> a
errorOutRange Int
l0)

-- | /O(1)/. The empty vector.
--
empty :: Vec v a => v a
{-# NOINLINE empty #-}
empty :: forall (v :: * -> *) a. Vec v a => v a
empty = forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
Vec forall (arr :: * -> *) a. (Arr arr a, Arr arr a) => arr a
emptyArr Int
0 Int
0

-- | /O(1)/. Single element vector.
singleton :: Vec v a => a -> v a
{-# INLINE singleton #-}
singleton :: forall (v :: * -> *) a. Vec v a => a -> v a
singleton a
c = forall (v :: * -> *) a.
Vec v a =>
Int -> (forall s. MArr (IArray v) s a -> ST s ()) -> v a
create Int
1 (\ MArr (IArray v) s a
marr -> forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray v) s a
marr Int
0 a
c)

-- | /O(n)/. Copy a vector from slice.
--
copy :: Vec v a => v a -> v a
{-# INLINE copy #-}
copy :: forall (v :: * -> *) a. Vec v a => v a -> v a
copy (Vec IArray v a
ba Int
s Int
l) = forall (v :: * -> *) a.
Vec v a =>
Int -> (forall s. MArr (IArray v) s a -> ST s ()) -> v a
create Int
l (\ MArr (IArray v) s a
marr -> forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> arr a -> Int -> Int -> m ()
copyArr MArr (IArray v) s a
marr Int
0 IArray v a
ba Int
s Int
l)

--------------------------------------------------------------------------------
-- Conversion between list
--
-- | /O(n)/ Convert a list into a vector
--
-- Alias for @'packN' 'defaultInitSize'@.
--
pack :: Vec v a => [a] -> v a
{-# INLINE pack #-}
pack :: forall (v :: * -> *) a. Vec v a => [a] -> v a
pack = forall (v :: * -> *) a. Vec v a => Int -> [a] -> v a
packN Int
defaultInitSize

-- | /O(n)/ Convert a list into a vector with an approximate size.
--
-- If the list's length is large than the size given, we simply double the buffer size
-- and continue building.
--
-- This function is a /good consumer/ in the sense of build/foldr fusion.
--
packN :: forall v a. Vec v a => Int -> [a] -> v a
{-# INLINE [1] packN #-}
packN :: forall (v :: * -> *) a. Vec v a => Int -> [a] -> v a
packN Int
n0 = \ [a]
ws0 -> forall a. (forall s. ST s a) -> a
runST (do let n :: Int
n = forall a. Ord a => a -> a -> a
max Int
4 Int
n0
                              MArr (IArray v) s a
marr <- forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
Int -> m (MArr arr s a)
newArr Int
n
                              (IPair Int
i MArr (IArray v) s a
marr') <- forall (t :: * -> *) (m :: * -> *) b a.
(Foldable t, Monad m) =>
(b -> a -> m b) -> b -> t a -> m b
M.foldM forall s.
IPair (MArr (IArray v) s a)
-> a -> ST s (IPair (MArr (IArray v) s a))
go (forall a. Int -> a -> IPair a
IPair Int
0 MArr (IArray v) s a
marr) [a]
ws0
                              forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> m ()
shrinkMutableArr MArr (IArray v) s a
marr' Int
i
                              IArray v a
ba <- forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> m (arr a)
unsafeFreezeArr MArr (IArray v) s a
marr'
                              forall (m :: * -> *) a. Monad m => a -> m a
return forall a b. (a -> b) -> a -> b
$! forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
ba Int
0 Int
i)
  where
    -- It's critical that this function get specialized and unboxed
    -- Keep an eye on its core!
    go :: IPair (MArr (IArray v) s a) -> a -> ST s (IPair (MArr (IArray v) s a))
    go :: forall s.
IPair (MArr (IArray v) s a)
-> a -> ST s (IPair (MArr (IArray v) s a))
go (IPair Int
i MArr (IArray v) s a
marr) !a
x = do
        let i' :: Int
i' = Int
iforall a. Num a => a -> a -> a
+Int
1
        MArr (IArray v) s a
marr' <- forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> Int -> m (MArr arr s a)
doubleMutableArr MArr (IArray v) s a
marr Int
i'
        forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray v) s a
marr' Int
i a
x
        forall (m :: * -> *) a. Monad m => a -> m a
return (forall a. Int -> a -> IPair a
IPair Int
i' MArr (IArray v) s a
marr')


-- | A version of 'replicateM' which works on 'Vec', with specialized rules under 'PrimMonad'.
--
-- There're rules to optimize the intermedia list away when m is an instance of 'PrimMoand',
-- such as 'IO', 'ST' or 'Z.Data.Parser.Parser'.
replicateM :: (Applicative f, Vec v a) => Int -> f a -> f (v a)
{-# INLINE [1] replicateM #-}
{-# RULES "replicateM/IO" forall n (x :: IO a). replicateM n x = replicatePM n x #-}
{-# RULES "replicateM/ST" forall n (x :: ST s a). replicateM n x = replicatePM n x #-}
replicateM :: forall (f :: * -> *) (v :: * -> *) a.
(Applicative f, Vec v a) =>
Int -> f a -> f (v a)
replicateM Int
n f a
f = forall (v :: * -> *) a. Vec v a => Int -> [a] -> v a
packN Int
n forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall (m :: * -> *) a. Applicative m => Int -> m a -> m [a]
M.replicateM Int
n f a
f

-- | 'PrimMonad' specialzied version of 'replicateM'.
--
-- You can add rules to rewrite 'replicateM' to this function in your own 'PrimMonad' instance, e.g.
--
-- @
-- instance PrimMonad YourMonad where ...
--
-- {-# RULES "replicateM\/YourMonad" forall n (f :: YourMonad a). replicateM n f = replicatePM n f #-}
-- @
--
replicatePM :: (PrimMonad m, Vec v a) => Int -> m a -> m (v a)
{-# INLINE replicatePM #-}
replicatePM :: forall (m :: * -> *) (v :: * -> *) a.
(PrimMonad m, Vec v a) =>
Int -> m a -> m (v a)
replicatePM Int
n m a
f = do
    !MArr (IArray v) (PrimState m) a
marr <- forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
Int -> m (MArr arr s a)
newArr Int
n
    IArray v a
ba <- MArr (IArray v) (PrimState m) a -> Int -> m (IArray v a)
go MArr (IArray v) (PrimState m) a
marr Int
0
    forall (m :: * -> *) a. Monad m => a -> m a
return forall a b. (a -> b) -> a -> b
$! forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
ba Int
0 Int
n
  where
    go :: MArr (IArray v) (PrimState m) a -> Int -> m (IArray v a)
go MArr (IArray v) (PrimState m) a
marr !Int
i
        | Int
i forall a. Ord a => a -> a -> Bool
>= Int
n = forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> m (arr a)
unsafeFreezeArr MArr (IArray v) (PrimState m) a
marr
        | Bool
otherwise = do
            a
x <- m a
f
            forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray v) (PrimState m) a
marr Int
i a
x
            MArr (IArray v) (PrimState m) a -> Int -> m (IArray v a)
go MArr (IArray v) (PrimState m) a
marr (Int
iforall a. Num a => a -> a -> a
+Int
1)

-- | /O(n)/ Convert a list into a vector with given size.
--
-- If the list's length is large than the size given, we drop the rest elements.
--
-- This function is a /good consumer/ in the sense of build/foldr fusion.
--
packN' :: forall v a. Vec v a => Int -> [a] -> v a
{-# INLINE packN' #-}
packN' :: forall (v :: * -> *) a. Vec v a => Int -> [a] -> v a
packN' Int
n = \ [a]
ws0 -> forall a. (forall s. ST s a) -> a
runST (do MArr (IArray v) s a
marr <- forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
Int -> m (MArr arr s a)
newArr Int
n
                              (IPair Int
i MArr (IArray v) s a
marr') <- forall (t :: * -> *) (m :: * -> *) b a.
(Foldable t, Monad m) =>
(b -> a -> m b) -> b -> t a -> m b
M.foldM forall s.
IPair (MArr (IArray v) s a)
-> a -> ST s (IPair (MArr (IArray v) s a))
go (forall a. Int -> a -> IPair a
IPair Int
0 MArr (IArray v) s a
marr) [a]
ws0
                              forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> m ()
shrinkMutableArr MArr (IArray v) s a
marr' Int
i
                              IArray v a
ba <- forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> m (arr a)
unsafeFreezeArr MArr (IArray v) s a
marr'
                              forall (m :: * -> *) a. Monad m => a -> m a
return forall a b. (a -> b) -> a -> b
$! forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
ba Int
0 Int
i)
  where
    -- It's critical that this function get specialized and unboxed
    -- Keep an eye on its core!
    go :: IPair (MArr (IArray v) s a) -> a -> ST s (IPair (MArr (IArray v) s a))
    go :: forall s.
IPair (MArr (IArray v) s a)
-> a -> ST s (IPair (MArr (IArray v) s a))
go (IPair Int
i MArr (IArray v) s a
marr) !a
x = do
        if Int
i forall a. Ord a => a -> a -> Bool
< Int
n
        then do forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray v) s a
marr Int
i a
x
                forall (m :: * -> *) a. Monad m => a -> m a
return (forall a. Int -> a -> IPair a
IPair (Int
iforall a. Num a => a -> a -> a
+Int
1) MArr (IArray v) s a
marr)
        else forall (m :: * -> *) a. Monad m => a -> m a
return (forall a. Int -> a -> IPair a
IPair Int
i MArr (IArray v) s a
marr)

-- | /O(n)/ Alias for @'packRN' 'defaultInitSize'@.
--
packR :: Vec v a => [a] -> v a
{-# INLINE packR #-}
packR :: forall (v :: * -> *) a. Vec v a => [a] -> v a
packR = forall (v :: * -> *) a. Vec v a => Int -> [a] -> v a
packRN Int
defaultInitSize

-- | /O(n)/ 'packN' in reverse order.
--
-- This function is a /good consumer/ in the sense of build/foldr fusion.
--
packRN :: forall v a. Vec v a => Int -> [a] -> v a
{-# INLINE packRN #-}
packRN :: forall (v :: * -> *) a. Vec v a => Int -> [a] -> v a
packRN Int
n0 = \ [a]
ws0 -> forall a. (forall s. ST s a) -> a
runST (do let n :: Int
n = forall a. Ord a => a -> a -> a
max Int
4 Int
n0
                               MArr (IArray v) s a
marr <- forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
Int -> m (MArr arr s a)
newArr Int
n
                               (IPair Int
i MArr (IArray v) s a
marr') <- forall (t :: * -> *) (m :: * -> *) b a.
(Foldable t, Monad m) =>
(b -> a -> m b) -> b -> t a -> m b
M.foldM forall s.
IPair (MArr (IArray v) s a)
-> a -> ST s (IPair (MArr (IArray v) s a))
go (forall a. Int -> a -> IPair a
IPair (Int
nforall a. Num a => a -> a -> a
-Int
1) MArr (IArray v) s a
marr) [a]
ws0
                               IArray v a
ba <- forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> m (arr a)
unsafeFreezeArr MArr (IArray v) s a
marr'
                               let i' :: Int
i' = Int
i forall a. Num a => a -> a -> a
+ Int
1
                                   n' :: Int
n' = forall (arr :: * -> *) a. Arr arr a => arr a -> Int
sizeofArr IArray v a
ba
                               forall (m :: * -> *) a. Monad m => a -> m a
return forall a b. (a -> b) -> a -> b
$! forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
ba Int
i' (Int
n'forall a. Num a => a -> a -> a
-Int
i'))
  where
    go :: IPair (MArr (IArray v) s a) -> a -> ST s (IPair (MArr (IArray v) s a))
    go :: forall s.
IPair (MArr (IArray v) s a)
-> a -> ST s (IPair (MArr (IArray v) s a))
go (IPair Int
i MArr (IArray v) s a
marr) !a
x = do
        Int
n <- forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> m Int
sizeofMutableArr MArr (IArray v) s a
marr
        if Int
i forall a. Ord a => a -> a -> Bool
>= Int
0
        then do forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray v) s a
marr Int
i a
x
                forall (m :: * -> *) a. Monad m => a -> m a
return (forall a. Int -> a -> IPair a
IPair (Int
iforall a. Num a => a -> a -> a
-Int
1) MArr (IArray v) s a
marr)
        else do let !n' :: Int
n' = Int
n forall a. Bits a => a -> Int -> a
`unsafeShiftL` Int
1  -- double the buffer
                !MArr (IArray v) s a
marr' <- forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
Int -> m (MArr arr s a)
newArr Int
n'
                forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> MArr arr s a -> Int -> Int -> m ()
copyMutableArr MArr (IArray v) s a
marr' Int
n MArr (IArray v) s a
marr Int
0 Int
n
                forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray v) s a
marr' (Int
nforall a. Num a => a -> a -> a
-Int
1) a
x
                forall (m :: * -> *) a. Monad m => a -> m a
return (forall a. Int -> a -> IPair a
IPair (Int
nforall a. Num a => a -> a -> a
-Int
2) MArr (IArray v) s a
marr')

-- | /O(n)/ 'packN'' in reverse order.
--
-- >>> packRN' 3 [1,2,3,4,5]
-- >>> [3,2,1]
--
-- This function is a /good consumer/ in the sense of build/foldr fusion.
--
packRN' :: forall v a. Vec v a => Int -> [a] -> v a
{-# INLINE packRN' #-}
packRN' :: forall (v :: * -> *) a. Vec v a => Int -> [a] -> v a
packRN' Int
n = \ [a]
ws0 -> forall a. (forall s. ST s a) -> a
runST (do MArr (IArray v) s a
marr <- forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
Int -> m (MArr arr s a)
newArr Int
n
                               (IPair Int
i MArr (IArray v) s a
marr') <- forall (t :: * -> *) (m :: * -> *) b a.
(Foldable t, Monad m) =>
(b -> a -> m b) -> b -> t a -> m b
M.foldM forall s.
IPair (MArr (IArray v) s a)
-> a -> ST s (IPair (MArr (IArray v) s a))
go (forall a. Int -> a -> IPair a
IPair (Int
nforall a. Num a => a -> a -> a
-Int
1) MArr (IArray v) s a
marr) [a]
ws0
                               IArray v a
ba <- forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> m (arr a)
unsafeFreezeArr MArr (IArray v) s a
marr'
                               let i' :: Int
i' = Int
i forall a. Num a => a -> a -> a
+ Int
1
                                   n' :: Int
n' = forall (arr :: * -> *) a. Arr arr a => arr a -> Int
sizeofArr IArray v a
ba
                               forall (m :: * -> *) a. Monad m => a -> m a
return forall a b. (a -> b) -> a -> b
$! forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
ba Int
i' (Int
n'forall a. Num a => a -> a -> a
-Int
i'))
  where
    go :: IPair (MArr (IArray v) s a) -> a -> ST s (IPair (MArr (IArray v) s a))
    go :: forall s.
IPair (MArr (IArray v) s a)
-> a -> ST s (IPair (MArr (IArray v) s a))
go (IPair Int
i MArr (IArray v) s a
marr) !a
x = do
        if Int
i forall a. Ord a => a -> a -> Bool
>= Int
0
        then do forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray v) s a
marr Int
i a
x
                forall (m :: * -> *) a. Monad m => a -> m a
return (forall a. Int -> a -> IPair a
IPair (Int
iforall a. Num a => a -> a -> a
-Int
1) MArr (IArray v) s a
marr)
        else forall (m :: * -> *) a. Monad m => a -> m a
return (forall a. Int -> a -> IPair a
IPair Int
i MArr (IArray v) s a
marr)

-- | /O(n)/ Convert vector to a list.
--
-- Unpacking is done lazily. i.e. we will retain reference to the array until all element are consumed.
--
-- This function is a /good producer/ in the sense of build/foldr fusion.
unpack :: Vec v a => v a -> [a]
{-# INLINE [1] unpack #-}
unpack :: forall (v :: * -> *) a. Vec v a => v a -> [a]
unpack (Vec IArray v a
ba Int
s Int
l) = Int -> [a]
go Int
s
  where
    !end :: Int
end = Int
s forall a. Num a => a -> a -> a
+ Int
l
    go :: Int -> [a]
go !Int
idx
        | Int
idx forall a. Ord a => a -> a -> Bool
>= Int
end = []
        | Bool
otherwise = case forall (arr :: * -> *) a.
(Arr arr a, HasCallStack) =>
arr a -> Int -> (# a #)
indexArr' IArray v a
ba Int
idx of (# a
x #) -> a
x forall a. a -> [a] -> [a]
: Int -> [a]
go (Int
idxforall a. Num a => a -> a -> a
+Int
1)

unpackFB :: Vec v a => v a -> (a -> r -> r) -> r -> r
{-# INLINE [0] unpackFB #-}
unpackFB :: forall (v :: * -> *) a r. Vec v a => v a -> (a -> r -> r) -> r -> r
unpackFB (Vec IArray v a
ba Int
s Int
l) a -> r -> r
k r
z = Int -> r
go Int
s
  where
    !end :: Int
end = Int
s forall a. Num a => a -> a -> a
+ Int
l
    go :: Int -> r
go !Int
idx
        | Int
idx forall a. Ord a => a -> a -> Bool
>= Int
end = r
z
        | Bool
otherwise = case forall (arr :: * -> *) a.
(Arr arr a, HasCallStack) =>
arr a -> Int -> (# a #)
indexArr' IArray v a
ba Int
idx of (# a
x #) -> a
x a -> r -> r
`k` Int -> r
go (Int
idxforall a. Num a => a -> a -> a
+Int
1)

{-# RULES
"unpack" [~1] forall v . unpack v = build (\ k z -> unpackFB v k z)
"unpackFB" [1] forall v . unpackFB v (:) [] = unpack v
 #-}

-- | /O(n)/ Convert vector to a list in reverse order.
--
-- This function is a /good producer/ in the sense of build/foldr fusion.
unpackR :: Vec v a => v a -> [a]
{-# INLINE [1] unpackR #-}
unpackR :: forall (v :: * -> *) a. Vec v a => v a -> [a]
unpackR (Vec IArray v a
ba Int
s Int
l) = Int -> [a]
go (Int
s forall a. Num a => a -> a -> a
+ Int
l forall a. Num a => a -> a -> a
- Int
1)
  where
    go :: Int -> [a]
go !Int
idx
        | Int
idx forall a. Ord a => a -> a -> Bool
< Int
s = []
        | Bool
otherwise =
            case forall (arr :: * -> *) a.
(Arr arr a, HasCallStack) =>
arr a -> Int -> (# a #)
indexArr' IArray v a
ba Int
idx of (# a
x #) -> a
x forall a. a -> [a] -> [a]
: Int -> [a]
go (Int
idxforall a. Num a => a -> a -> a
-Int
1)

unpackRFB :: Vec v a => v a -> (a -> r -> r) -> r -> r
{-# INLINE [0] unpackRFB #-}
unpackRFB :: forall (v :: * -> *) a r. Vec v a => v a -> (a -> r -> r) -> r -> r
unpackRFB (Vec IArray v a
ba Int
s Int
l) a -> r -> r
k r
z = Int -> r
go (Int
s forall a. Num a => a -> a -> a
+ Int
l forall a. Num a => a -> a -> a
- Int
1)
  where
    go :: Int -> r
go !Int
idx
        | Int
idx forall a. Ord a => a -> a -> Bool
< Int
s = r
z
        | Bool
otherwise =
            case forall (arr :: * -> *) a.
(Arr arr a, HasCallStack) =>
arr a -> Int -> (# a #)
indexArr' IArray v a
ba Int
idx of (# a
x #) -> a
x a -> r -> r
`k` Int -> r
go (Int
idxforall a. Num a => a -> a -> a
-Int
1)

{-# RULES
"unpackR" [~1] forall v . unpackR v = build (\ k z -> unpackRFB v k z)
"unpackRFB" [1] forall v . unpackRFB v (:) [] = unpackR v
 #-}

--------------------------------------------------------------------------------
-- Basic interface
--
-- |  /O(1)/ The length of a vector.
length :: Vec v a => v a -> Int
{-# INLINE length #-}
length :: forall (v :: * -> *) a. Vec v a => v a -> Int
length (Vec IArray v a
_ Int
_ Int
l) = Int
l

-- | /O(1)/ Test whether a vector is empty.
null :: Vec v a => v a -> Bool
{-# INLINE null #-}
null :: forall (v :: * -> *) a. Vec v a => v a -> Bool
null v a
v = forall (v :: * -> *) a. Vec v a => v a -> Int
length v a
v forall a. Eq a => a -> a -> Bool
== Int
0

-- | /O(m+n)/
--
-- There's no need to guard empty vector because we guard them for you, so
-- appending empty vectors are no-ops.
append :: Vec v a => v a -> v a -> v a
{-# INLINE append #-}
append :: forall (v :: * -> *) a. Vec v a => v a -> v a -> v a
append (Vec IArray v a
_ Int
_ Int
0) v a
b                    = v a
b
append v a
a                (Vec IArray v a
_ Int
_ Int
0)     = v a
a
append (Vec IArray v a
baA Int
sA Int
lA) (Vec IArray v a
baB Int
sB Int
lB) = forall (v :: * -> *) a.
Vec v a =>
Int -> (forall s. MArr (IArray v) s a -> ST s ()) -> v a
create (Int
lAforall a. Num a => a -> a -> a
+Int
lB) forall a b. (a -> b) -> a -> b
$ \ MArr (IArray v) s a
marr -> do
    forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> arr a -> Int -> Int -> m ()
copyArr MArr (IArray v) s a
marr Int
0  IArray v a
baA Int
sA Int
lA
    forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> arr a -> Int -> Int -> m ()
copyArr MArr (IArray v) s a
marr Int
lA IArray v a
baB Int
sB Int
lB

--------------------------------------------------------------------------------

-- | Mapping between vectors (possiblely with two different vector types).
--
-- NOTE, the result vector contain thunks in lifted 'Vector' case, use 'map''
-- if that's not desired.
--
-- For 'PrimVector', 'map' and 'map'' are same, since 'PrimVector's never
-- store thunks.
map :: forall u v a b. (Vec u a, Vec v b) => (a -> b) -> u a -> v b
{-# INLINE map #-}
map :: forall (u :: * -> *) (v :: * -> *) a b.
(Vec u a, Vec v b) =>
(a -> b) -> u a -> v b
map a -> b
f (Vec IArray u a
arr Int
s Int
l) = forall (v :: * -> *) a.
Vec v a =>
Int -> (forall s. MArr (IArray v) s a -> ST s ()) -> v a
create Int
l (forall s. Int -> MArr (IArray v) s b -> ST s ()
go Int
0)
  where
    go :: Int -> MArr (IArray v) s b -> ST s ()
    go :: forall s. Int -> MArr (IArray v) s b -> ST s ()
go !Int
i !MArr (IArray v) s b
marr | Int
i forall a. Ord a => a -> a -> Bool
>= Int
l = forall (m :: * -> *) a. Monad m => a -> m a
return ()
                | Bool
otherwise = do
                    a
x <- forall (arr :: * -> *) a (m :: * -> *).
(Arr arr a, Monad m, HasCallStack) =>
arr a -> Int -> m a
indexArrM IArray u a
arr (Int
iforall a. Num a => a -> a -> a
+Int
s); forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray v) s b
marr Int
i (a -> b
f a
x);
                    forall s. Int -> MArr (IArray v) s b -> ST s ()
go (Int
iforall a. Num a => a -> a -> a
+Int
1) MArr (IArray v) s b
marr

-- | Mapping between vectors (possiblely with two different vector types).
--
-- This is the strict version map. Note that the 'Functor' instance of lifted
-- 'Vector' is defined with 'map' to statisfy laws, which this strict version
-- breaks (@map' id arrayContainsBottom /= arrayContainsBottom @).
map' :: forall u v a b. (Vec u a, Vec v b) => (a -> b) -> u a -> v b
{-# INLINE map' #-}
map' :: forall (u :: * -> *) (v :: * -> *) a b.
(Vec u a, Vec v b) =>
(a -> b) -> u a -> v b
map' a -> b
f (Vec IArray u a
arr Int
s Int
l) = forall (v :: * -> *) a.
Vec v a =>
Int -> (forall s. MArr (IArray v) s a -> ST s ()) -> v a
create Int
l (forall s. Int -> MArr (IArray v) s b -> ST s ()
go Int
0)
  where
    go :: Int -> MArr (IArray v) s b -> ST s ()
    go :: forall s. Int -> MArr (IArray v) s b -> ST s ()
go !Int
i !MArr (IArray v) s b
marr | Int
i forall a. Ord a => a -> a -> Bool
< Int
l = do
                    a
x <- forall (arr :: * -> *) a (m :: * -> *).
(Arr arr a, Monad m, HasCallStack) =>
arr a -> Int -> m a
indexArrM IArray u a
arr (Int
iforall a. Num a => a -> a -> a
+Int
s)
                    let !v :: b
v = a -> b
f a
x in forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray v) s b
marr Int
i b
v
                    forall s. Int -> MArr (IArray v) s b -> ST s ()
go (Int
iforall a. Num a => a -> a -> a
+Int
1) MArr (IArray v) s b
marr
               | Bool
otherwise = forall (m :: * -> *) a. Monad m => a -> m a
return ()

-- | Strict mapping with index.
--
imap' :: forall u v a b. (Vec u a, Vec v b) => (Int -> a -> b) -> u a -> v b
{-# INLINE imap' #-}
imap' :: forall (u :: * -> *) (v :: * -> *) a b.
(Vec u a, Vec v b) =>
(Int -> a -> b) -> u a -> v b
imap' Int -> a -> b
f (Vec IArray u a
arr Int
s Int
l) = forall (v :: * -> *) a.
Vec v a =>
Int -> (forall s. MArr (IArray v) s a -> ST s ()) -> v a
create Int
l (forall s. Int -> MArr (IArray v) s b -> ST s ()
go Int
0)
  where
    go :: Int -> MArr (IArray v) s b -> ST s ()
    go :: forall s. Int -> MArr (IArray v) s b -> ST s ()
go !Int
i !MArr (IArray v) s b
marr | Int
i forall a. Ord a => a -> a -> Bool
< Int
l = do
                    a
x <- forall (arr :: * -> *) a (m :: * -> *).
(Arr arr a, Monad m, HasCallStack) =>
arr a -> Int -> m a
indexArrM IArray u a
arr (Int
iforall a. Num a => a -> a -> a
+Int
s)
                    let !v :: b
v = Int -> a -> b
f Int
i a
x in forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray v) s b
marr Int
i b
v
                    forall s. Int -> MArr (IArray v) s b -> ST s ()
go (Int
iforall a. Num a => a -> a -> a
+Int
1) MArr (IArray v) s b
marr
               | Bool
otherwise = forall (m :: * -> *) a. Monad m => a -> m a
return ()

-- | Shuffle a vector using  <https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle Fisher-Yates> algorithm.
shuffle :: (StatefulGen g m, PrimMonad m, Vec v a) => g -> v a -> m (v a)
{-# INLINE shuffle #-}
shuffle :: forall g (m :: * -> *) (v :: * -> *) a.
(StatefulGen g m, PrimMonad m, Vec v a) =>
g -> v a -> m (v a)
shuffle g
g (Vec IArray v a
arr Int
s Int
l) = do
    MArr (IArray v) (PrimState m) a
marr <- forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
arr a -> Int -> Int -> m (MArr arr s a)
thawArr IArray v a
arr Int
s Int
l
    forall g (m :: * -> *) s (arr :: * -> *) a.
(StatefulGen g m, PrimMonad m, PrimState m ~ s, Arr arr a) =>
g -> MArr arr s a -> Int -> Int -> m ()
shuffleMutableArr g
g MArr (IArray v) (PrimState m) a
marr Int
0 Int
l
    IArray v a
arr' <- forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> m (arr a)
unsafeFreezeArr MArr (IArray v) (PrimState m) a
marr
    forall (f :: * -> *) a. Applicative f => a -> f a
pure forall a b. (a -> b) -> a -> b
$! forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arr' Int
0 Int
l

-- | Generate all permutation of a vector.
permutations :: forall v a. (Vec v a) => v a -> [v a]
{-# INLINE permutations #-}
permutations :: forall (v :: * -> *) a. Vec v a => v a -> [v a]
permutations v a
v = forall (v :: * -> *) a. Vec v a => Int -> [a] -> v a
packN (forall (v :: * -> *) a. Vec v a => v a -> Int
length v a
v) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall a. [a] -> [[a]]
List.permutations (forall (v :: * -> *) a. Vec v a => v a -> [a]
unpack v a
v)

--------------------------------------------------------------------------------
--
-- Strict folds
--

-- | Strict left to right fold.
foldl' :: Vec v a => (b -> a -> b) -> b -> v a -> b
{-# INLINE foldl' #-}
foldl' :: forall (v :: * -> *) a b. Vec v a => (b -> a -> b) -> b -> v a -> b
foldl' b -> a -> b
f b
z (Vec IArray v a
arr Int
s Int
l) = b -> Int -> b
go b
z Int
s
  where
    !end :: Int
end = Int
s forall a. Num a => a -> a -> a
+ Int
l
    -- tail recursive; traverses array left to right
    go :: b -> Int -> b
go !b
acc !Int
i | Int
i forall a. Ord a => a -> a -> Bool
< Int
end  = case forall (arr :: * -> *) a.
(Arr arr a, HasCallStack) =>
arr a -> Int -> (# a #)
indexArr' IArray v a
arr Int
i of
                                (# a
x #) -> b -> Int -> b
go (b -> a -> b
f b
acc a
x) (Int
i forall a. Num a => a -> a -> a
+ Int
1)
               | Bool
otherwise = b
acc

-- | Strict left to right fold with index.
ifoldl' :: Vec v a => (b -> Int ->  a -> b) -> b -> v a -> b
{-# INLINE ifoldl' #-}
ifoldl' :: forall (v :: * -> *) a b.
Vec v a =>
(b -> Int -> a -> b) -> b -> v a -> b
ifoldl' b -> Int -> a -> b
f b
z (Vec IArray v a
arr Int
s Int
l) = b -> Int -> b
go b
z Int
s
  where
    !end :: Int
end = Int
s forall a. Num a => a -> a -> a
+ Int
l
    go :: b -> Int -> b
go !b
acc !Int
i | Int
i forall a. Ord a => a -> a -> Bool
< Int
end  = case forall (arr :: * -> *) a.
(Arr arr a, HasCallStack) =>
arr a -> Int -> (# a #)
indexArr' IArray v a
arr Int
i of
                                (# a
x #) -> b -> Int -> b
go (b -> Int -> a -> b
f b
acc Int
i a
x) (Int
i forall a. Num a => a -> a -> a
+ Int
1)
               | Bool
otherwise = b
acc

-- | Strict left to right fold using first element as the initial value.
--
-- Throw 'EmptyVector' if vector is empty.
foldl1' :: forall v a. (Vec v a, HasCallStack) => (a -> a -> a) -> v a -> a
{-# INLINE foldl1' #-}
foldl1' :: forall (v :: * -> *) a.
(Vec v a, HasCallStack) =>
(a -> a -> a) -> v a -> a
foldl1' a -> a -> a
f (Vec IArray v a
arr Int
s Int
l)
    | Int
l forall a. Ord a => a -> a -> Bool
<= Int
0    = forall a. HasCallStack => a
errorEmptyVector
    | Bool
otherwise = case forall (arr :: * -> *) a.
(Arr arr a, HasCallStack) =>
arr a -> Int -> (# a #)
indexArr' IArray v a
arr Int
s of
                    (# a
x0 #) -> forall (v :: * -> *) a b. Vec v a => (b -> a -> b) -> b -> v a -> b
foldl' a -> a -> a
f a
x0 (forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arr (Int
sforall a. Num a => a -> a -> a
+Int
1) (Int
lforall a. Num a => a -> a -> a
-Int
1) :: v a)

-- | Strict left to right fold using first element as the initial value.
--   return 'Nothing' when vector is empty.
foldl1Maybe' :: forall v a. Vec v a => (a -> a -> a) -> v a -> Maybe a
{-# INLINE foldl1Maybe' #-}
foldl1Maybe' :: forall (v :: * -> *) a. Vec v a => (a -> a -> a) -> v a -> Maybe a
foldl1Maybe' a -> a -> a
f (Vec IArray v a
arr Int
s Int
l)
    | Int
l forall a. Ord a => a -> a -> Bool
<= Int
0    = forall a. Maybe a
Nothing
    | Bool
otherwise = case forall (arr :: * -> *) a.
(Arr arr a, HasCallStack) =>
arr a -> Int -> (# a #)
indexArr' IArray v a
arr Int
s of
                    (# a
x0 #) -> let !r :: a
r = forall (v :: * -> *) a b. Vec v a => (b -> a -> b) -> b -> v a -> b
foldl' a -> a -> a
f a
x0 (forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arr (Int
sforall a. Num a => a -> a -> a
+Int
1) (Int
lforall a. Num a => a -> a -> a
-Int
1) :: v a)
                                in forall a. a -> Maybe a
Just a
r

-- | Strict right to left fold
foldr' :: Vec v a => (a -> b -> b) -> b -> v a -> b
{-# INLINE foldr' #-}
foldr' :: forall (v :: * -> *) a b. Vec v a => (a -> b -> b) -> b -> v a -> b
foldr' a -> b -> b
f b
z (Vec IArray v a
arr Int
s Int
l) = b -> Int -> b
go b
z (Int
sforall a. Num a => a -> a -> a
+Int
lforall a. Num a => a -> a -> a
-Int
1)
  where
    -- tail recursive; traverses array right to left
    go :: b -> Int -> b
go !b
acc !Int
i | Int
i forall a. Ord a => a -> a -> Bool
>= Int
s    = case forall (arr :: * -> *) a.
(Arr arr a, HasCallStack) =>
arr a -> Int -> (# a #)
indexArr' IArray v a
arr Int
i of
                                (# a
x #) -> b -> Int -> b
go (a -> b -> b
f a
x b
acc) (Int
i forall a. Num a => a -> a -> a
- Int
1)
               | Bool
otherwise = b
acc

-- | Strict right to left fold with index
--
-- NOTE: the index is counting from 0, not backwards
ifoldr' :: Vec v a => (Int -> a -> b -> b) -> b -> v a -> b
{-# INLINE ifoldr' #-}
ifoldr' :: forall (v :: * -> *) a b.
Vec v a =>
(Int -> a -> b -> b) -> b -> v a -> b
ifoldr' Int -> a -> b -> b
f b
z (Vec IArray v a
arr Int
s Int
l) = b -> Int -> Int -> b
go b
z (Int
sforall a. Num a => a -> a -> a
+Int
lforall a. Num a => a -> a -> a
-Int
1) Int
0
  where
    go :: b -> Int -> Int -> b
go !b
acc !Int
i !Int
k | Int
i forall a. Ord a => a -> a -> Bool
>= Int
s    = case forall (arr :: * -> *) a.
(Arr arr a, HasCallStack) =>
arr a -> Int -> (# a #)
indexArr' IArray v a
arr Int
i of
                                    (# a
x #) -> b -> Int -> Int -> b
go (Int -> a -> b -> b
f Int
k a
x b
acc) (Int
i forall a. Num a => a -> a -> a
- Int
1) (Int
k forall a. Num a => a -> a -> a
+ Int
1)
                  | Bool
otherwise = b
acc

-- | Strict right to left fold using last element as the initial value.
--
-- Throw 'EmptyVector' if vector is empty.
foldr1' :: forall v a. (Vec v a, HasCallStack) => (a -> a -> a) -> v a -> a
{-# INLINE foldr1' #-}
foldr1' :: forall (v :: * -> *) a.
(Vec v a, HasCallStack) =>
(a -> a -> a) -> v a -> a
foldr1' a -> a -> a
f (Vec IArray v a
arr Int
s Int
l)
    | Int
l forall a. Ord a => a -> a -> Bool
<= Int
0 = forall a. HasCallStack => a
errorEmptyVector
    | Bool
otherwise = case forall (arr :: * -> *) a.
(Arr arr a, HasCallStack) =>
arr a -> Int -> (# a #)
indexArr' IArray v a
arr (Int
sforall a. Num a => a -> a -> a
+Int
lforall a. Num a => a -> a -> a
-Int
1) of
                    (# a
x0 #) -> forall (v :: * -> *) a b. Vec v a => (b -> a -> b) -> b -> v a -> b
foldl' a -> a -> a
f a
x0 (forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arr Int
s (Int
lforall a. Num a => a -> a -> a
-Int
1) :: v a)

-- | Strict right to left fold using last element as the initial value,
--   return 'Nothing' when vector is empty.
foldr1Maybe' :: forall v a. Vec v a => (a -> a -> a) -> v a -> Maybe a
{-# INLINE foldr1Maybe' #-}
foldr1Maybe' :: forall (v :: * -> *) a. Vec v a => (a -> a -> a) -> v a -> Maybe a
foldr1Maybe' a -> a -> a
f (Vec IArray v a
arr Int
s Int
l)
    | Int
l forall a. Ord a => a -> a -> Bool
<= Int
0 = forall a. Maybe a
Nothing
    | Bool
otherwise = case forall (arr :: * -> *) a.
(Arr arr a, HasCallStack) =>
arr a -> Int -> (# a #)
indexArr' IArray v a
arr (Int
sforall a. Num a => a -> a -> a
+Int
lforall a. Num a => a -> a -> a
-Int
1) of
                    (# a
x0 #) -> let !r :: a
r = forall (v :: * -> *) a b. Vec v a => (b -> a -> b) -> b -> v a -> b
foldl' a -> a -> a
f a
x0 (forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arr Int
s (Int
lforall a. Num a => a -> a -> a
-Int
1) :: v a)
                                in forall a. a -> Maybe a
Just a
r

--------------------------------------------------------------------------------
--
-- Special folds
--
-- | /O(n)/ Concatenate a list of vector.
--
-- Note: 'concat' have to force the entire list to filter out empty vector and calculate
-- the length for allocation.
concat :: forall v a . Vec v a => [v a] -> v a
{-# INLINABLE concat #-}
concat :: forall (v :: * -> *) a. Vec v a => [v a] -> v a
concat [v a
v] = v a
v  -- shortcut common case in Parser
concat [v a]
vs = case forall (v :: * -> *) a.
Vec v a =>
Int -> Int -> [v a] -> (Int, Int)
preConcat Int
0 Int
0 [v a]
vs of
    (Int
1, Int
_) -> let Just v a
v = forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Maybe a
List.find (Bool -> Bool
not forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (v :: * -> *) a. Vec v a => v a -> Bool
null) [v a]
vs in v a
v -- there must be a not null vector
    (Int
_, Int
l) -> forall (v :: * -> *) a.
Vec v a =>
Int -> (forall s. MArr (IArray v) s a -> ST s ()) -> v a
create Int
l (forall s. [v a] -> Int -> MArr (IArray v) s a -> ST s ()
go [v a]
vs Int
0)
  where
    go :: [v a] -> Int -> MArr (IArray v) s a -> ST s ()
    go :: forall s. [v a] -> Int -> MArr (IArray v) s a -> ST s ()
go [] !Int
_ !MArr (IArray v) s a
_                  = forall (m :: * -> *) a. Monad m => a -> m a
return ()
    go (Vec IArray v a
ba Int
s Int
l:[v a]
vs') !Int
i !MArr (IArray v) s a
marr = do forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
M.when (Int
l forall a. Eq a => a -> a -> Bool
/= Int
0) (forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> arr a -> Int -> Int -> m ()
copyArr MArr (IArray v) s a
marr Int
i IArray v a
ba Int
s Int
l)
                                      forall s. [v a] -> Int -> MArr (IArray v) s a -> ST s ()
go [v a]
vs' (Int
iforall a. Num a => a -> a -> a
+Int
l) MArr (IArray v) s a
marr

-- | /O(n)/ Concatenate a list of vector in reverse order, e.g. @concat ["hello, world"] == "worldhello"@
--
-- Note: 'concatR' have to force the entire list to filter out empty vector and calculate
-- the length for allocation.
concatR :: forall v a . Vec v a => [v a] -> v a
{-# INLINABLE concatR #-}
concatR :: forall (v :: * -> *) a. Vec v a => [v a] -> v a
concatR [v a
v] = v a
v  -- shortcut common case in Parser
concatR [v a]
vs = case forall (v :: * -> *) a.
Vec v a =>
Int -> Int -> [v a] -> (Int, Int)
preConcat Int
0 Int
0 [v a]
vs of
    (Int
1, Int
_) -> let Just v a
v = forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Maybe a
List.find (Bool -> Bool
not forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (v :: * -> *) a. Vec v a => v a -> Bool
null) [v a]
vs in v a
v -- there must be a not null vector
    (Int
_, Int
l) -> forall (v :: * -> *) a.
Vec v a =>
Int -> (forall s. MArr (IArray v) s a -> ST s ()) -> v a
create Int
l (forall s. [v a] -> Int -> MArr (IArray v) s a -> ST s ()
go [v a]
vs Int
l)
  where
    go :: [v a] -> Int -> MArr (IArray v) s a -> ST s ()
    go :: forall s. [v a] -> Int -> MArr (IArray v) s a -> ST s ()
go [] !Int
_ !MArr (IArray v) s a
_                  = forall (m :: * -> *) a. Monad m => a -> m a
return ()
    go (Vec IArray v a
ba Int
s Int
l:[v a]
vs') !Int
i !MArr (IArray v) s a
marr = do forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
M.when (Int
l forall a. Eq a => a -> a -> Bool
/= Int
0) (forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> arr a -> Int -> Int -> m ()
copyArr MArr (IArray v) s a
marr (Int
iforall a. Num a => a -> a -> a
-Int
l) IArray v a
ba Int
s Int
l)
                                      forall s. [v a] -> Int -> MArr (IArray v) s a -> ST s ()
go [v a]
vs' (Int
iforall a. Num a => a -> a -> a
-Int
l) MArr (IArray v) s a
marr

-- pre scan to decide if we really need to copy and calculate total length
-- we don't accumulate another result list, since it's rare to got empty
preConcat :: Vec v a => Int -> Int -> [v a] -> (Int, Int)
{-# INLINE preConcat #-}
preConcat :: forall (v :: * -> *) a.
Vec v a =>
Int -> Int -> [v a] -> (Int, Int)
preConcat !Int
nacc !Int
lacc [] = (Int
nacc, Int
lacc)
preConcat !Int
nacc !Int
lacc (Vec IArray v a
_ Int
_ Int
l:[v a]
vs')
    | Int
l forall a. Ord a => a -> a -> Bool
<= Int
0    = forall (v :: * -> *) a.
Vec v a =>
Int -> Int -> [v a] -> (Int, Int)
preConcat Int
nacc Int
lacc [v a]
vs'
    | Bool
otherwise = forall (v :: * -> *) a.
Vec v a =>
Int -> Int -> [v a] -> (Int, Int)
preConcat (Int
naccforall a. Num a => a -> a -> a
+Int
1) (Int
lforall a. Num a => a -> a -> a
+Int
lacc) [v a]
vs'


-- | Map a function over a vector and concatenate the results
concatMap :: Vec v a => (a -> v a) -> v a -> v a
{-# INLINE concatMap #-}
concatMap :: forall (v :: * -> *) a. Vec v a => (a -> v a) -> v a -> v a
concatMap a -> v a
f = forall (v :: * -> *) a. Vec v a => [v a] -> v a
concat forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (v :: * -> *) a b. Vec v a => (a -> b -> b) -> b -> v a -> b
foldr' ((:) forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> v a
f) []

-- | /O(n)/ 'maximum' returns the maximum value from a vector
--
-- It's defined with 'foldl1'', an 'EmptyVector' exception will be thrown
-- in the case of an empty vector.
maximum :: (Vec v a, Ord a, HasCallStack) => v a -> a
{-# INLINE maximum #-}
maximum :: forall (v :: * -> *) a. (Vec v a, Ord a, HasCallStack) => v a -> a
maximum = forall (v :: * -> *) a.
(Vec v a, HasCallStack) =>
(a -> a -> a) -> v a -> a
foldl1' forall a. Ord a => a -> a -> a
max

-- | /O(n)/ 'maximum' returns the maximum value from a vector,
--   return 'Nothing' in the case of an empty vector.
maximumMaybe :: (Vec v a, Ord a) => v a -> Maybe a
{-# INLINE maximumMaybe #-}
maximumMaybe :: forall (v :: * -> *) a. (Vec v a, Ord a) => v a -> Maybe a
maximumMaybe = forall (v :: * -> *) a. Vec v a => (a -> a -> a) -> v a -> Maybe a
foldl1Maybe' forall a. Ord a => a -> a -> a
max

-- | /O(n)/ 'minimum' returns the minimum value from a 'vector'
--
-- An 'EmptyVector' exception will be thrown in the case of an empty vector.
minimum :: (Vec v a, Ord a, HasCallStack) => v a -> a
{-# INLINE minimum #-}
minimum :: forall (v :: * -> *) a. (Vec v a, Ord a, HasCallStack) => v a -> a
minimum = forall (v :: * -> *) a.
(Vec v a, HasCallStack) =>
(a -> a -> a) -> v a -> a
foldl1' forall a. Ord a => a -> a -> a
min

-- | /O(n)/ 'minimum' returns the minimum value from a vector,
--   return 'Nothing' in the case of an empty vector.
minimumMaybe :: (Vec v a, Ord a) => v a -> Maybe a
{-# INLINE minimumMaybe #-}
minimumMaybe :: forall (v :: * -> *) a. (Vec v a, Ord a) => v a -> Maybe a
minimumMaybe = forall (v :: * -> *) a. Vec v a => (a -> a -> a) -> v a -> Maybe a
foldl1Maybe' forall a. Ord a => a -> a -> a
min

-- | /O(n)/ 'product' returns the product value from a vector
product :: (Vec v a, Num a) => v a -> a
{-# INLINE product #-}
product :: forall (v :: * -> *) a. (Vec v a, Num a) => v a -> a
product = forall (v :: * -> *) a b. Vec v a => (b -> a -> b) -> b -> v a -> b
foldl' forall a. Num a => a -> a -> a
(*) a
1

-- | /O(n)/ 'product' returns the product value from a vector
--
-- This function will shortcut on zero. Note this behavior change the semantics
-- for lifted vector: @product [1,0,undefined] /= product' [1,0,undefined]@.
product' :: (Vec v a, Num a, Eq a) => v a -> a
{-# INLINE product' #-}
product' :: forall (v :: * -> *) a. (Vec v a, Num a, Eq a) => v a -> a
product' (Vec IArray v a
arr Int
s Int
l) = a -> Int -> a
go a
1 Int
s
  where
    !end :: Int
end = Int
sforall a. Num a => a -> a -> a
+Int
l
    go :: a -> Int -> a
go !a
acc !Int
i | a
acc forall a. Eq a => a -> a -> Bool
== a
0  = a
0
               | Int
i forall a. Ord a => a -> a -> Bool
>= Int
end  = a
acc
               | Bool
otherwise = case forall (arr :: * -> *) a.
(Arr arr a, HasCallStack) =>
arr a -> Int -> (# a #)
indexArr' IArray v a
arr Int
i of
                                (# a
x #) -> a -> Int -> a
go (a
accforall a. Num a => a -> a -> a
*a
x) (Int
iforall a. Num a => a -> a -> a
+Int
1)

-- | /O(n)/ Applied to a predicate and a vector, 'any' determines
-- if any elements of the vector satisfy the predicate.
any :: Vec v a => (a -> Bool) -> v a -> Bool
{-# INLINE any #-}
any :: forall (v :: * -> *) a. Vec v a => (a -> Bool) -> v a -> Bool
any a -> Bool
f (Vec IArray v a
arr Int
s Int
l)
    | Int
l forall a. Ord a => a -> a -> Bool
<= Int
0    = Bool
False
    | Bool
otherwise = case forall (arr :: * -> *) a.
(Arr arr a, HasCallStack) =>
arr a -> Int -> (# a #)
indexArr' IArray v a
arr Int
s of
                    (# a
x0 #) -> Bool -> Int -> Bool
go (a -> Bool
f a
x0) (Int
sforall a. Num a => a -> a -> a
+Int
1)
  where
    !end :: Int
end = Int
sforall a. Num a => a -> a -> a
+Int
l
    go :: Bool -> Int -> Bool
go !Bool
acc !Int
i | Bool
acc       = Bool
True
               | Int
i forall a. Ord a => a -> a -> Bool
>= Int
end  = Bool
acc
               | Bool
otherwise = case forall (arr :: * -> *) a.
(Arr arr a, HasCallStack) =>
arr a -> Int -> (# a #)
indexArr' IArray v a
arr Int
i of
                                (# a
x #) -> Bool -> Int -> Bool
go (Bool
acc Bool -> Bool -> Bool
|| a -> Bool
f a
x) (Int
iforall a. Num a => a -> a -> a
+Int
1)

-- | /O(n)/ Applied to a predicate and a vector, 'all' determines
-- if all elements of the vector satisfy the predicate.
all :: Vec v a => (a -> Bool) -> v a -> Bool
{-# INLINE all #-}
all :: forall (v :: * -> *) a. Vec v a => (a -> Bool) -> v a -> Bool
all a -> Bool
f (Vec IArray v a
arr Int
s Int
l)
    | Int
l forall a. Ord a => a -> a -> Bool
<= Int
0    = Bool
True
    | Bool
otherwise = case forall (arr :: * -> *) a.
(Arr arr a, HasCallStack) =>
arr a -> Int -> (# a #)
indexArr' IArray v a
arr Int
s of
                    (# a
x0 #) -> Bool -> Int -> Bool
go (a -> Bool
f a
x0) (Int
sforall a. Num a => a -> a -> a
+Int
1)
  where
    !end :: Int
end = Int
sforall a. Num a => a -> a -> a
+Int
l
    go :: Bool -> Int -> Bool
go !Bool
acc !Int
i | Bool -> Bool
not Bool
acc   = Bool
False
               | Int
i forall a. Ord a => a -> a -> Bool
>= Int
end  = Bool
acc
               | Bool
otherwise = case forall (arr :: * -> *) a.
(Arr arr a, HasCallStack) =>
arr a -> Int -> (# a #)
indexArr' IArray v a
arr Int
i of
                                (# a
x #) -> Bool -> Int -> Bool
go (Bool
acc Bool -> Bool -> Bool
&& a -> Bool
f a
x) (Int
iforall a. Num a => a -> a -> a
+Int
1)

-- | /O(n)/ 'sum' returns the sum value from a 'vector'
sum :: (Vec v a, Num a) => v a -> a
{-# INLINE sum #-}
sum :: forall (v :: * -> *) a. (Vec v a, Num a) => v a -> a
sum = forall (v :: * -> *) a b. Vec v a => (b -> a -> b) -> b -> v a -> b
foldl' forall a. Num a => a -> a -> a
(+) a
0

-- | /O(n)/ 'count' returns count of an element from a 'vector'
count :: (Vec v a, Eq a) => a -> v a -> Int
{-# INLINE[1] count #-}
{-# RULES "count/Bytes" count = countBytes #-}
count :: forall (v :: * -> *) a. (Vec v a, Eq a) => a -> v a -> Int
count a
w = forall (v :: * -> *) a b. Vec v a => (b -> a -> b) -> b -> v a -> b
foldl' (\ Int
acc a
x -> if a
x forall a. Eq a => a -> a -> Bool
== a
w then Int
accforall a. Num a => a -> a -> a
+Int
1 else Int
acc) Int
0

countBytes :: Word8 -> Bytes -> Int
{-# INLINE countBytes #-}
countBytes :: Word8 -> Bytes -> Int
countBytes Word8
w8 (PrimVector (PrimArray ByteArray#
ba#) Int
s Int
l) =
    forall a. IO a -> a
unsafeDupablePerformIO (ByteArray# -> Int -> Int -> Word8 -> IO Int
c_count_ba ByteArray#
ba# Int
s Int
l Word8
w8)

--------------------------------------------------------------------------------
-- Accumulating maps

-- | The 'mapAccumL' function behaves like a combination of 'map' and
-- 'foldl'; it applies a function to each element of a vector,
-- passing an accumulating parameter from left to right, and returning a
-- final value of this accumulator together with the new list.
--
-- Note, this function will only force the result tuple, not the elements inside,
-- to prevent creating thunks during 'mapAccumL', `seq` your accumulator and result
-- with the result tuple.
--
mapAccumL :: forall u v a b c. (Vec u b, Vec v c) => (a -> b -> (a, c)) -> a -> u b -> (a, v c)
{-# INLINE mapAccumL #-}
mapAccumL :: forall (u :: * -> *) (v :: * -> *) a b c.
(Vec u b, Vec v c) =>
(a -> b -> (a, c)) -> a -> u b -> (a, v c)
mapAccumL a -> b -> (a, c)
f a
z (Vec IArray u b
ba Int
s Int
l)
    | Int
l forall a. Ord a => a -> a -> Bool
<= Int
0    = (a
z, forall (v :: * -> *) a. Vec v a => v a
empty)
    | Bool
otherwise = forall (v :: * -> *) a b.
Vec v a =>
Int -> (forall s. MArr (IArray v) s a -> ST s b) -> (b, v a)
creating Int
l (forall s. a -> Int -> MArr (IArray v) s c -> ST s a
go a
z Int
s)
  where
    !end :: Int
end = Int
s forall a. Num a => a -> a -> a
+ Int
l
    go :: a -> Int -> MArr (IArray v) s c -> ST s a
    go :: forall s. a -> Int -> MArr (IArray v) s c -> ST s a
go a
acc !Int
i !MArr (IArray v) s c
marr
        | Int
i forall a. Ord a => a -> a -> Bool
>= Int
end = forall (m :: * -> *) a. Monad m => a -> m a
return a
acc
        | Bool
otherwise = do
            b
x <- forall (arr :: * -> *) a (m :: * -> *).
(Arr arr a, Monad m, HasCallStack) =>
arr a -> Int -> m a
indexArrM IArray u b
ba Int
i
            let (a
acc', c
c) = a
acc a -> b -> (a, c)
`f` b
x
            forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray v) s c
marr (Int
iforall a. Num a => a -> a -> a
-Int
s) c
c
            forall s. a -> Int -> MArr (IArray v) s c -> ST s a
go a
acc' (Int
iforall a. Num a => a -> a -> a
+Int
1) MArr (IArray v) s c
marr

-- | The 'mapAccumR' function behaves like a combination of 'map' and
-- 'foldr'; it applies a function to each element of a vector,
-- passing an accumulating parameter from right to left, and returning a
-- final value of this accumulator together with the new vector.
--
-- The same strictness property with 'mapAccumL' applys to 'mapAccumR' too.
--
mapAccumR :: forall u v a b c. (Vec u b, Vec v c) => (a -> b -> (a, c)) -> a -> u b -> (a, v c)
{-# INLINE mapAccumR #-}
mapAccumR :: forall (u :: * -> *) (v :: * -> *) a b c.
(Vec u b, Vec v c) =>
(a -> b -> (a, c)) -> a -> u b -> (a, v c)
mapAccumR a -> b -> (a, c)
f a
z (Vec IArray u b
ba Int
s Int
l)
    | Int
l forall a. Ord a => a -> a -> Bool
<= Int
0    = (a
z, forall (v :: * -> *) a. Vec v a => v a
empty)
    | Bool
otherwise = forall (v :: * -> *) a b.
Vec v a =>
Int -> (forall s. MArr (IArray v) s a -> ST s b) -> (b, v a)
creating Int
l (forall s. a -> Int -> MArr (IArray v) s c -> ST s a
go a
z (Int
sforall a. Num a => a -> a -> a
+Int
lforall a. Num a => a -> a -> a
-Int
1))
  where
    go :: a -> Int ->  MArr (IArray v) s c -> ST s a
    go :: forall s. a -> Int -> MArr (IArray v) s c -> ST s a
go a
acc !Int
i !MArr (IArray v) s c
marr
        | Int
i forall a. Ord a => a -> a -> Bool
< Int
s     = forall (m :: * -> *) a. Monad m => a -> m a
return a
acc
        | Bool
otherwise = do
            b
x <- forall (arr :: * -> *) a (m :: * -> *).
(Arr arr a, Monad m, HasCallStack) =>
arr a -> Int -> m a
indexArrM IArray u b
ba Int
i
            let (a
acc', c
c) = a
acc a -> b -> (a, c)
`f` b
x
            forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray v) s c
marr (Int
iforall a. Num a => a -> a -> a
-Int
s) c
c
            forall s. a -> Int -> MArr (IArray v) s c -> ST s a
go a
acc' (Int
iforall a. Num a => a -> a -> a
-Int
1) MArr (IArray v) s c
marr

--------------------------------------------------------------------------------
--  Generating and unfolding vector.
--
-- | /O(n)/ 'replicate' @n x@ is a vector of length @n@ with @x@
-- the value of every element.
--
-- Note: 'replicate' will not force the element in boxed vector case.
replicate :: (Vec v a) => Int -> a -> v a
{-# INLINE replicate #-}
replicate :: forall (v :: * -> *) a. Vec v a => Int -> a -> v a
replicate Int
n a
x | Int
n forall a. Ord a => a -> a -> Bool
<= Int
0    = forall (v :: * -> *) a. Vec v a => v a
empty
              | Bool
otherwise = forall (v :: * -> *) a.
Vec v a =>
Int -> (forall s. MArr (IArray v) s a -> ST s ()) -> v a
create Int
n (\ MArr (IArray v) s a
marr -> forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> Int -> a -> m ()
setArr MArr (IArray v) s a
marr Int
0 Int
n a
x)

-- | /O(n*m)/ 'cycleN' a vector n times.
cycleN :: forall v a. Vec v a => Int -> v a -> v a
{-# INLINE cycleN #-}
cycleN :: forall (v :: * -> *) a. Vec v a => Int -> v a -> v a
cycleN = forall (v :: * -> *) a x. (Vec v a, Integral x) => x -> v a -> v a
_cycleN

-- | /O(n*m)/ 'cycleN''s polymorphic type version
_cycleN :: forall v a x. (Vec v a, Integral x) => x -> v a -> v a
{-# INLINE _cycleN #-}
_cycleN :: forall (v :: * -> *) a x. (Vec v a, Integral x) => x -> v a -> v a
_cycleN x
n (Vec IArray v a
arr Int
s Int
l)
    | Int
l forall a. Eq a => a -> a -> Bool
== Int
0    = forall (v :: * -> *) a. Vec v a => v a
empty
    | Bool
otherwise = forall (v :: * -> *) a.
Vec v a =>
Int -> (forall s. MArr (IArray v) s a -> ST s ()) -> v a
create Int
end (forall s. Int -> MArr (IArray v) s a -> ST s ()
go Int
0)
  where
    !end :: Int
end = forall a b. (Integral a, Num b) => a -> b
fromIntegral x
n forall a. Num a => a -> a -> a
* Int
l
    go :: Int -> MArr (IArray v) s a -> ST s ()
    go :: forall s. Int -> MArr (IArray v) s a -> ST s ()
go !Int
i !MArr (IArray v) s a
marr | Int
i forall a. Ord a => a -> a -> Bool
>= Int
end  = forall (m :: * -> *) a. Monad m => a -> m a
return ()
                | Bool
otherwise = forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> arr a -> Int -> Int -> m ()
copyArr MArr (IArray v) s a
marr Int
i IArray v a
arr Int
s Int
l forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> forall s. Int -> MArr (IArray v) s a -> ST s ()
go (Int
iforall a. Num a => a -> a -> a
+Int
l) MArr (IArray v) s a
marr

-- | /O(n)/, where /n/ is the length of the result.  The 'unfoldr'
-- function is analogous to the List \'unfoldr\'.  'unfoldr' builds a
-- vector from a seed value. The function takes the element and
-- returns 'Nothing' if it is done producing the vector or returns
-- 'Just' @(a,b)@, in which case, @a@ is the next byte in the string,
-- and @b@ is the seed value for further production.
--
-- Examples:
--
-- >    unfoldr (\x -> if x <= 5 then Just (x, x + 1) else Nothing) 0
-- > == pack [0, 1, 2, 3, 4, 5]
--
unfoldr :: Vec u b => (a -> Maybe (b, a)) -> a -> u b
{-# INLINE unfoldr #-}
unfoldr :: forall (u :: * -> *) b a.
Vec u b =>
(a -> Maybe (b, a)) -> a -> u b
unfoldr a -> Maybe (b, a)
f = forall (v :: * -> *) a. Vec v a => [a] -> v a
pack forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall b a. (b -> Maybe (a, b)) -> b -> [a]
List.unfoldr a -> Maybe (b, a)
f

-- | /O(n)/ Like 'unfoldr', 'unfoldrN' builds a vector from a seed
-- value.  However, the length of the result is limited by the first
-- argument to 'unfoldrN'.  This function is more efficient than 'unfoldr'
-- when the maximum length of the result is known.
--
-- The following equation relates 'unfoldrN' and 'unfoldr':
--
-- > fst (unfoldrN n f s) == take n (unfoldr f s)
--
unfoldrN :: forall v a b. Vec v b => Int -> (a -> Maybe (b, a)) -> a -> (v b, Maybe a)
{-# INLINE unfoldrN #-}
unfoldrN :: forall (v :: * -> *) a b.
Vec v b =>
Int -> (a -> Maybe (b, a)) -> a -> (v b, Maybe a)
unfoldrN Int
n a -> Maybe (b, a)
f
    | Int
n forall a. Ord a => a -> a -> Bool
< Int
0     = \ a
z -> (forall (v :: * -> *) a. Vec v a => v a
empty, forall a. a -> Maybe a
Just a
z)
    | Bool
otherwise = \ a
z ->
        let ((Maybe a
r, Int
len), Vec IArray v b
arr Int
_ Int
_) = forall (v :: * -> *) a b.
Vec v a =>
Int -> (forall s. MArr (IArray v) s a -> ST s b) -> (b, v a)
creating @v Int
n (forall s. a -> Int -> MArr (IArray v) s b -> ST s (Maybe a, Int)
go a
z Int
0)
        in (forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
Vec IArray v b
arr Int
0 Int
len, Maybe a
r)
  where
    go :: a -> Int -> MArr (IArray v) s b -> ST s (Maybe a, Int)
    go :: forall s. a -> Int -> MArr (IArray v) s b -> ST s (Maybe a, Int)
go !a
acc !Int
i !MArr (IArray v) s b
marr
      | Int
n forall a. Eq a => a -> a -> Bool
== Int
i    = forall (m :: * -> *) a. Monad m => a -> m a
return (forall a. a -> Maybe a
Just a
acc, Int
i)
      | Bool
otherwise = case a -> Maybe (b, a)
f a
acc of
          Maybe (b, a)
Nothing        -> forall (m :: * -> *) a. Monad m => a -> m a
return (forall a. Maybe a
Nothing, Int
i)
          Just (b
x, a
acc') -> do forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray v) s b
marr Int
i b
x
                               forall s. a -> Int -> MArr (IArray v) s b -> ST s (Maybe a, Int)
go a
acc' (Int
iforall a. Num a => a -> a -> a
+Int
1) MArr (IArray v) s b
marr

--------------------------------------------------------------------------------
-- Searching by equality

-- | /O(n)/ 'elem' test if given element is in given vector.
elem :: (Vec v a, Eq a) => a -> v a -> Bool
{-# INLINE elem #-}
elem :: forall (v :: * -> *) a. (Vec v a, Eq a) => a -> v a -> Bool
elem a
x = forall a. Maybe a -> Bool
isJust forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (v :: * -> *) a. (Vec v a, Eq a) => a -> v a -> Maybe Int
elemIndex a
x

-- | /O(n)/ 'not . elem'
notElem ::  (Vec v a, Eq a) => a -> v a -> Bool
{-# INLINE notElem #-}
notElem :: forall (v :: * -> *) a. (Vec v a, Eq a) => a -> v a -> Bool
notElem a
x = Bool -> Bool
not forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (v :: * -> *) a. (Vec v a, Eq a) => a -> v a -> Bool
elem a
x

-- | /O(n)/ The 'elemIndex' function returns the index of the first
-- element in the given vector which is equal to the query
-- element, or 'Nothing' if there is no such element.
elemIndex :: (Vec v a, Eq a) => a -> v a -> Maybe Int
{-# INLINE [1] elemIndex #-}
{-# RULES "elemIndex/Bytes" elemIndex = elemIndexBytes #-}
elemIndex :: forall (v :: * -> *) a. (Vec v a, Eq a) => a -> v a -> Maybe Int
elemIndex a
w (Vec IArray v a
arr Int
s Int
l) = Int -> Maybe Int
go Int
s
  where
    !end :: Int
end = Int
s forall a. Num a => a -> a -> a
+ Int
l
    go :: Int -> Maybe Int
go !Int
i
        | Int
i forall a. Ord a => a -> a -> Bool
>= Int
end = forall a. Maybe a
Nothing
        | a
x forall a. Eq a => a -> a -> Bool
== a
w   = let !i' :: Int
i' = Int
i forall a. Num a => a -> a -> a
- Int
s in forall a. a -> Maybe a
Just Int
i'
        | Bool
otherwise = Int -> Maybe Int
go (Int
iforall a. Num a => a -> a -> a
+Int
1)
        where (# a
x #) = forall (arr :: * -> *) a.
(Arr arr a, HasCallStack) =>
arr a -> Int -> (# a #)
indexArr' IArray v a
arr Int
i

-- | /O(n)/ Special 'elemIndex' for 'Bytes' using @memchr(3)@
--
-- On most platforms @memchr(3)@ is a highly optimized byte searching
-- function, thus we make a special binding for it.
--
-- A rewrite rule @elemIndex = elemIndexBytes@ is also included.
elemIndexBytes :: Word8 -> Bytes -> Maybe Int
{-# INLINE elemIndexBytes #-}
elemIndexBytes :: Word8 -> Bytes -> Maybe Int
elemIndexBytes Word8
w (PrimVector (PrimArray ByteArray#
ba#) Int
s Int
l) =
    case forall a b. (Integral a, Num b) => a -> b
fromIntegral (ByteArray# -> Int -> Word8 -> Int -> Int
c_memchr ByteArray#
ba# Int
s Word8
w Int
l) of
        -1 -> forall a. Maybe a
Nothing
        Int
r  -> forall a. a -> Maybe a
Just Int
r

--------------------------------------------------------------------------------

-- | Pair type to help GHC unpack in some loops, useful when write fast folds.
data IPair a = IPair { forall a. IPair a -> Int
ifst :: {-# UNPACK #-}!Int, forall a. IPair a -> a
isnd :: a } deriving (Int -> IPair a -> ShowS
forall a. Show a => Int -> IPair a -> ShowS
forall a. Show a => [IPair a] -> ShowS
forall a. Show a => IPair a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [IPair a] -> ShowS
$cshowList :: forall a. Show a => [IPair a] -> ShowS
show :: IPair a -> String
$cshow :: forall a. Show a => IPair a -> String
showsPrec :: Int -> IPair a -> ShowS
$cshowsPrec :: forall a. Show a => Int -> IPair a -> ShowS
Show, IPair a -> IPair a -> Bool
forall a. Eq a => IPair a -> IPair a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: IPair a -> IPair a -> Bool
$c/= :: forall a. Eq a => IPair a -> IPair a -> Bool
== :: IPair a -> IPair a -> Bool
$c== :: forall a. Eq a => IPair a -> IPair a -> Bool
Eq, IPair a -> IPair a -> Bool
IPair a -> IPair a -> Ordering
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall {a}. Ord a => Eq (IPair a)
forall a. Ord a => IPair a -> IPair a -> Bool
forall a. Ord a => IPair a -> IPair a -> Ordering
forall a. Ord a => IPair a -> IPair a -> IPair a
min :: IPair a -> IPair a -> IPair a
$cmin :: forall a. Ord a => IPair a -> IPair a -> IPair a
max :: IPair a -> IPair a -> IPair a
$cmax :: forall a. Ord a => IPair a -> IPair a -> IPair a
>= :: IPair a -> IPair a -> Bool
$c>= :: forall a. Ord a => IPair a -> IPair a -> Bool
> :: IPair a -> IPair a -> Bool
$c> :: forall a. Ord a => IPair a -> IPair a -> Bool
<= :: IPair a -> IPair a -> Bool
$c<= :: forall a. Ord a => IPair a -> IPair a -> Bool
< :: IPair a -> IPair a -> Bool
$c< :: forall a. Ord a => IPair a -> IPair a -> Bool
compare :: IPair a -> IPair a -> Ordering
$ccompare :: forall a. Ord a => IPair a -> IPair a -> Ordering
Ord)

instance (Arbitrary v) => Arbitrary (IPair v) where
    arbitrary :: Gen (IPair v)
arbitrary = forall a. (Int, a) -> IPair a
toIPair forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall a. Arbitrary a => Gen a
arbitrary
    shrink :: IPair v -> [IPair v]
shrink IPair v
v = forall a. (Int, a) -> IPair a
toIPair forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall a. Arbitrary a => a -> [a]
shrink (forall a. IPair a -> (Int, a)
fromIPair IPair v
v)

instance (CoArbitrary v) => CoArbitrary (IPair v) where
    coarbitrary :: forall b. IPair v -> Gen b -> Gen b
coarbitrary = forall a b. CoArbitrary a => a -> Gen b -> Gen b
coarbitrary forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. IPair a -> (Int, a)
fromIPair

instance Functor IPair where
    {-# INLINE fmap #-}
    fmap :: forall a b. (a -> b) -> IPair a -> IPair b
fmap a -> b
f (IPair Int
i a
v) = forall a. Int -> a -> IPair a
IPair Int
i (a -> b
f a
v)

instance NFData a => NFData (IPair a) where
    {-# INLINE rnf #-}
    rnf :: IPair a -> ()
rnf (IPair Int
_ a
a) = forall a. NFData a => a -> ()
rnf a
a

-- | Unlike 'Functor' instance, this mapping evaluate value inside 'IPair' strictly.
mapIPair' :: (a -> b) -> IPair a -> IPair b
{-# INLINE mapIPair' #-}
mapIPair' :: forall a b. (a -> b) -> IPair a -> IPair b
mapIPair' a -> b
f (IPair Int
i a
v) = let !v' :: b
v' = a -> b
f a
v in forall a. Int -> a -> IPair a
IPair Int
i b
v'

fromIPair :: IPair a -> (Int, a)
{-# INLINE fromIPair #-}
fromIPair :: forall a. IPair a -> (Int, a)
fromIPair (IPair Int
i a
v) = (Int
i, a
v)

toIPair :: (Int, a) -> IPair a
{-# INLINE toIPair #-}
toIPair :: forall a. (Int, a) -> IPair a
toIPair (Int
i, a
v) = forall a. Int -> a -> IPair a
IPair Int
i a
v

-- | The chunk size used for I\/O. Currently set to @16k - chunkOverhead@
defaultChunkSize :: Int
{-# INLINE defaultChunkSize #-}
defaultChunkSize :: Int
defaultChunkSize = Int
16 forall a. Num a => a -> a -> a
* Int
1024 forall a. Num a => a -> a -> a
- Int
chunkOverhead

-- | The recommended chunk size. Currently set to @4k - chunkOverhead@.
smallChunkSize :: Int
{-# INLINE smallChunkSize #-}
smallChunkSize :: Int
smallChunkSize = Int
4 forall a. Num a => a -> a -> a
* Int
1024 forall a. Num a => a -> a -> a
- Int
chunkOverhead

-- | The memory management overhead. Currently this is tuned for GHC only.
chunkOverhead :: Int
{-# INLINE chunkOverhead #-}
chunkOverhead :: Int
chunkOverhead = Int
2 forall a. Num a => a -> a -> a
* forall a. Prim a => a -> Int
sizeOf (forall a. HasCallStack => a
undefined :: Int)

-- | @defaultInitSize = 30@, used as initialize size when packing list of unknown size.
defaultInitSize :: Int
{-# INLINE defaultInitSize #-}
defaultInitSize :: Int
defaultInitSize = Int
30

-- | All exception can be throw by using 'Vec'.
data VectorException = IndexOutOfVectorRange {-# UNPACK #-} !Int CallStack
                     | EmptyVector CallStack
                    deriving Int -> VectorException -> ShowS
[VectorException] -> ShowS
VectorException -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [VectorException] -> ShowS
$cshowList :: [VectorException] -> ShowS
show :: VectorException -> String
$cshow :: VectorException -> String
showsPrec :: Int -> VectorException -> ShowS
$cshowsPrec :: Int -> VectorException -> ShowS
Show
instance Exception VectorException

errorEmptyVector :: HasCallStack => a
{-# INLINE errorEmptyVector #-}
errorEmptyVector :: forall a. HasCallStack => a
errorEmptyVector = forall a e. Exception e => e -> a
throw (CallStack -> VectorException
EmptyVector HasCallStack => CallStack
callStack)

errorOutRange :: HasCallStack => Int -> a
{-# INLINE errorOutRange #-}
errorOutRange :: forall a. HasCallStack => Int -> a
errorOutRange Int
i = forall a e. Exception e => e -> a
throw (Int -> CallStack -> VectorException
IndexOutOfVectorRange Int
i HasCallStack => CallStack
callStack)

-- | Cast between vectors
castVector :: (Vec v a, Cast a b) => v a -> v b
{-# INLINE castVector #-}
castVector :: forall (v :: * -> *) a b. (Vec v a, Cast a b) => v a -> v b
castVector = unsafeCoerce# :: forall a b. a -> b
unsafeCoerce#

--------------------------------------------------------------------------------

foreign import ccall unsafe "string.h strcmp"
    c_strcmp :: Addr# -> Addr# -> IO CInt

foreign import ccall unsafe "string.h strlen"
    c_strlen :: Addr# -> IO CSize

foreign import ccall unsafe "ascii_validate_addr"
    c_ascii_validate_addr :: Addr# -> Int -> IO Int

foreign import ccall unsafe "hs_fnv_hash_addr"
    c_fnv_hash_addr :: Addr# -> Int -> Int -> IO Int

foreign import ccall unsafe "hs_fnv_hash"
    c_fnv_hash_ba :: ByteArray# -> Int -> Int -> Int -> IO Int

-- HsInt hs_memchr(uint8_t *a, HsInt aoff, uint8_t b, HsInt n);
foreign import ccall unsafe "hs_memchr" c_memchr ::
    ByteArray# -> Int -> Word8 -> Int -> Int

-- HsInt hs_memrchr(uint8_t *a, HsInt aoff, uint8_t b, HsInt n);
foreign import ccall unsafe "hs_memrchr" c_memrchr ::
    ByteArray# -> Int -> Word8 -> Int -> Int

foreign import ccall unsafe "hs_count_ba" c_count_ba ::
    ByteArray# -> Int -> Int -> Word8 -> IO Int