-- |
-- Module      : Basement.BoxedArray
-- License     : BSD-style
-- Maintainer  : Vincent Hanquez <vincent@snarc.org>
-- Stability   : experimental
-- Portability : portable
--
-- Simple boxed array abstraction
--
{-# LANGUAGE MagicHash #-}
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE UnboxedTuples #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FlexibleInstances #-}
module Basement.BoxedArray
    ( Array
    , MArray
    , empty
    , length
    , mutableLength
    , copy
    , unsafeCopyAtRO
    , thaw
    , new
    , create
    , unsafeFreeze
    , unsafeThaw
    , freeze
    , unsafeWrite
    , unsafeRead
    , unsafeIndex
    , write
    , read
    , index
    , singleton
    , replicate
    , null
    , take
    , drop
    , splitAt
    , revTake
    , revDrop
    , revSplitAt
    , splitOn
    , sub
    , intersperse
    , span
    , spanEnd
    , break
    , breakEnd
    , mapFromUnboxed
    , mapToUnboxed
    , cons
    , snoc
    , uncons
    , unsnoc
    -- , findIndex
    , sortBy
    , filter
    , reverse
    , elem
    , find
    , foldl'
    , foldr
    , foldl1'
    , foldr1
    , all
    , any
    , isPrefixOf
    , isSuffixOf
    , builderAppend
    , builderBuild
    , builderBuild_
    ) where

import           GHC.Prim
import           GHC.Types
import           GHC.ST
import           Data.Proxy
import           Basement.Numerical.Additive
import           Basement.Numerical.Subtractive
import           Basement.NonEmpty
import           Basement.Compat.Base
import qualified Basement.Alg.Class as Alg
import qualified Basement.Alg.Mutable as Alg
import           Basement.Compat.MonadTrans
import           Basement.Compat.Semigroup
import           Basement.Types.OffsetSize
import           Basement.PrimType
import           Basement.NormalForm
import           Basement.Monad
import           Basement.UArray.Base (UArray)
import qualified Basement.UArray.Base as UArray
import           Basement.Exception
import           Basement.MutableBuilder
import qualified Basement.Compat.ExtList as List

-- | Array of a
data Array a = Array {-# UNPACK #-} !(Offset a)
                     {-# UNPACK #-} !(CountOf a)
                                    (Array# a)
    deriving (Typeable)

instance Data ty => Data (Array ty) where
    dataTypeOf :: Array ty -> DataType
dataTypeOf _ = DataType
arrayType
    toConstr :: Array ty -> Constr
toConstr _   = [Char] -> Constr
forall a. HasCallStack => [Char] -> a
error "toConstr"
    gunfold :: (forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (Array ty)
gunfold _ _  = [Char] -> Constr -> c (Array ty)
forall a. HasCallStack => [Char] -> a
error "gunfold"

arrayType :: DataType
arrayType :: DataType
arrayType = [Char] -> DataType
mkNoRepType "Foundation.Array"

instance NormalForm a => NormalForm (Array a) where
    toNormalForm :: Array a -> ()
toNormalForm arr :: Array a
arr = Offset a -> ()
loop 0
      where
        !sz :: CountOf a
sz = Array a -> CountOf a
forall a. Array a -> CountOf a
length Array a
arr
        loop :: Offset a -> ()
loop !Offset a
i
            | Offset a
i Offset a -> CountOf a -> Bool
forall ty. Offset ty -> CountOf ty -> Bool
.==# CountOf a
sz = ()
            | Bool
otherwise = Array a -> Offset a -> a
forall ty. Array ty -> Offset ty -> ty
unsafeIndex Array a
arr Offset a
i a -> () -> ()
forall a b. a -> b -> b
`seq` Offset a -> ()
loop (Offset a
iOffset a -> Offset a -> Offset a
forall a. Additive a => a -> a -> a
+1)

-- | Mutable Array of a
data MArray a st = MArray {-# UNPACK #-} !(Offset a)
                          {-# UNPACK #-} !(CountOf a)
                                         (MutableArray# st a)
    deriving (Typeable)

instance Functor Array where
    fmap :: (a -> b) -> Array a -> Array b
fmap = (a -> b) -> Array a -> Array b
forall a b. (a -> b) -> Array a -> Array b
map

instance Semigroup (Array a) where
    <> :: Array a -> Array a -> Array a
(<>) = Array a -> Array a -> Array a
forall a. Array a -> Array a -> Array a
append
instance Monoid (Array a) where
    mempty :: Array a
mempty  = Array a
forall a. Array a
empty
    mappend :: Array a -> Array a -> Array a
mappend = Array a -> Array a -> Array a
forall a. Array a -> Array a -> Array a
append
    mconcat :: [Array a] -> Array a
mconcat = [Array a] -> Array a
forall a. [Array a] -> Array a
concat

instance Show a => Show (Array a) where
    show :: Array a -> [Char]
show v :: Array a
v = [a] -> [Char]
forall a. Show a => a -> [Char]
show (Array a -> [Item (Array a)]
forall l. IsList l => l -> [Item l]
toList Array a
v)

instance Eq a => Eq (Array a) where
    == :: Array a -> Array a -> Bool
(==) = Array a -> Array a -> Bool
forall a. Eq a => Array a -> Array a -> Bool
equal
instance Ord a => Ord (Array a) where
    compare :: Array a -> Array a -> Ordering
compare = Array a -> Array a -> Ordering
forall a. Ord a => Array a -> Array a -> Ordering
vCompare

instance IsList (Array ty) where
    type Item (Array ty) = ty
    fromList :: [Item (Array ty)] -> Array ty
fromList = [Item (Array ty)] -> Array ty
forall a. [a] -> Array a
vFromList
    fromListN :: Int -> [Item (Array ty)] -> Array ty
fromListN len :: Int
len = CountOf ty -> [ty] -> Array ty
forall a. CountOf a -> [a] -> Array a
vFromListN (Int -> CountOf ty
forall ty. Int -> CountOf ty
CountOf Int
len)
    toList :: Array ty -> [Item (Array ty)]
toList = Array ty -> [Item (Array ty)]
forall a. Array a -> [a]
vToList

-- | return the numbers of elements in a mutable array
mutableLength :: MArray ty st -> Int
mutableLength :: MArray ty st -> Int
mutableLength (MArray _ (CountOf len :: Int
len) _) = Int
len
{-# INLINE mutableLength #-}

-- | return the numbers of elements in a mutable array
mutableLengthSize :: MArray ty st -> CountOf ty
mutableLengthSize :: MArray ty st -> CountOf ty
mutableLengthSize (MArray _ size :: CountOf ty
size _) = CountOf ty
size
{-# INLINE mutableLengthSize #-}

-- | Return the element at a specific index from an array.
--
-- If the index @n is out of bounds, an error is raised.
index :: Array ty -> Offset ty -> ty
index :: Array ty -> Offset ty -> ty
index array :: Array ty
array n :: Offset ty
n
    | Offset ty -> CountOf ty -> Bool
forall ty. Offset ty -> CountOf ty -> Bool
isOutOfBound Offset ty
n CountOf ty
len = OutOfBoundOperation -> Offset ty -> CountOf ty -> ty
forall ty a. OutOfBoundOperation -> Offset ty -> CountOf ty -> a
outOfBound OutOfBoundOperation
OOB_Index Offset ty
n CountOf ty
len
    | Bool
otherwise          = Array ty -> Offset ty -> ty
forall ty. Array ty -> Offset ty -> ty
unsafeIndex Array ty
array Offset ty
n
  where len :: CountOf ty
len = Array ty -> CountOf ty
forall a. Array a -> CountOf a
length Array ty
array
{-# INLINE index #-}

-- | Return the element at a specific index from an array without bounds checking.
--
-- Reading from invalid memory can return unpredictable and invalid values.
-- use 'index' if unsure.
unsafeIndex :: Array ty -> Offset ty -> ty
unsafeIndex :: Array ty -> Offset ty -> ty
unsafeIndex (Array start :: Offset ty
start _ a :: Array# ty
a) ofs :: Offset ty
ofs = Array# ty -> Offset ty -> ty
forall ty. Array# ty -> Offset ty -> ty
primArrayIndex Array# ty
a (Offset ty
startOffset ty -> Offset ty -> Offset ty
forall a. Additive a => a -> a -> a
+Offset ty
ofs)
{-# INLINE unsafeIndex #-}

-- | read a cell in a mutable array.
--
-- If the index is out of bounds, an error is raised.
read :: PrimMonad prim => MArray ty (PrimState prim) -> Offset ty -> prim ty
read :: MArray ty (PrimState prim) -> Offset ty -> prim ty
read array :: MArray ty (PrimState prim)
array n :: Offset ty
n
    | Offset ty -> CountOf ty -> Bool
forall ty. Offset ty -> CountOf ty -> Bool
isOutOfBound Offset ty
n CountOf ty
len = OutOfBoundOperation -> Offset ty -> CountOf ty -> prim ty
forall (prim :: * -> *) ty a.
PrimMonad prim =>
OutOfBoundOperation -> Offset ty -> CountOf ty -> prim a
primOutOfBound OutOfBoundOperation
OOB_Read Offset ty
n CountOf ty
len
    | Bool
otherwise          = MArray ty (PrimState prim) -> Offset ty -> prim ty
forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> Offset ty -> prim ty
unsafeRead MArray ty (PrimState prim)
array Offset ty
n
  where len :: CountOf ty
len = MArray ty (PrimState prim) -> CountOf ty
forall ty st. MArray ty st -> CountOf ty
mutableLengthSize MArray ty (PrimState prim)
array
{-# INLINE read #-}

-- | read from a cell in a mutable array without bounds checking.
--
-- Reading from invalid memory can return unpredictable and invalid values.
-- use 'read' if unsure.
unsafeRead :: PrimMonad prim => MArray ty (PrimState prim) -> Offset ty -> prim ty
unsafeRead :: MArray ty (PrimState prim) -> Offset ty -> prim ty
unsafeRead (MArray start :: Offset ty
start _ ma :: MutableArray# (PrimState prim) ty
ma) i :: Offset ty
i = MutableArray# (PrimState prim) ty -> Offset ty -> prim ty
forall (prim :: * -> *) ty.
PrimMonad prim =>
MutableArray# (PrimState prim) ty -> Offset ty -> prim ty
primMutableArrayRead MutableArray# (PrimState prim) ty
ma (Offset ty
start Offset ty -> Offset ty -> Offset ty
forall a. Additive a => a -> a -> a
+ Offset ty
i)
{-# INLINE unsafeRead #-}

-- | Write to a cell in a mutable array.
--
-- If the index is out of bounds, an error is raised.
write :: PrimMonad prim => MArray ty (PrimState prim) -> Offset ty -> ty -> prim ()
write :: MArray ty (PrimState prim) -> Offset ty -> ty -> prim ()
write array :: MArray ty (PrimState prim)
array n :: Offset ty
n val :: ty
val
    | Offset ty -> CountOf ty -> Bool
forall ty. Offset ty -> CountOf ty -> Bool
isOutOfBound Offset ty
n CountOf ty
len = OutOfBoundOperation -> Offset ty -> CountOf ty -> prim ()
forall (prim :: * -> *) ty a.
PrimMonad prim =>
OutOfBoundOperation -> Offset ty -> CountOf ty -> prim a
primOutOfBound OutOfBoundOperation
OOB_Write Offset ty
n CountOf ty
len
    | Bool
otherwise          = MArray ty (PrimState prim) -> Offset ty -> ty -> prim ()
forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> Offset ty -> ty -> prim ()
unsafeWrite MArray ty (PrimState prim)
array Offset ty
n ty
val
  where len :: CountOf ty
len = MArray ty (PrimState prim) -> CountOf ty
forall ty st. MArray ty st -> CountOf ty
mutableLengthSize MArray ty (PrimState prim)
array
{-# INLINE write #-}

-- | write to a cell in a mutable array without bounds checking.
--
-- Writing with invalid bounds will corrupt memory and your program will
-- become unreliable. use 'write' if unsure.
unsafeWrite :: PrimMonad prim => MArray ty (PrimState prim) -> Offset ty -> ty -> prim ()
unsafeWrite :: MArray ty (PrimState prim) -> Offset ty -> ty -> prim ()
unsafeWrite (MArray start :: Offset ty
start _ ma :: MutableArray# (PrimState prim) ty
ma) ofs :: Offset ty
ofs v :: ty
v =
    MutableArray# (PrimState prim) ty -> Offset ty -> ty -> prim ()
forall (prim :: * -> *) ty.
PrimMonad prim =>
MutableArray# (PrimState prim) ty -> Offset ty -> ty -> prim ()
primMutableArrayWrite MutableArray# (PrimState prim) ty
ma (Offset ty
start Offset ty -> Offset ty -> Offset ty
forall a. Additive a => a -> a -> a
+ Offset ty
ofs) ty
v
{-# INLINE unsafeWrite #-}

-- | Freeze a mutable array into an array.
--
-- the MArray must not be changed after freezing.
unsafeFreeze :: PrimMonad prim => MArray ty (PrimState prim) -> prim (Array ty)
unsafeFreeze :: MArray ty (PrimState prim) -> prim (Array ty)
unsafeFreeze (MArray ofs :: Offset ty
ofs sz :: CountOf ty
sz ma :: MutableArray# (PrimState prim) ty
ma) = (State# (PrimState prim)
 -> (# State# (PrimState prim), Array ty #))
-> prim (Array ty)
forall (m :: * -> *) a.
PrimMonad m =>
(State# (PrimState m) -> (# State# (PrimState m), a #)) -> m a
primitive ((State# (PrimState prim)
  -> (# State# (PrimState prim), Array ty #))
 -> prim (Array ty))
-> (State# (PrimState prim)
    -> (# State# (PrimState prim), Array ty #))
-> prim (Array ty)
forall a b. (a -> b) -> a -> b
$ \s1 :: State# (PrimState prim)
s1 ->
    case MutableArray# (PrimState prim) ty
-> State# (PrimState prim)
-> (# State# (PrimState prim), Array# ty #)
forall d a.
MutableArray# d a -> State# d -> (# State# d, Array# a #)
unsafeFreezeArray# MutableArray# (PrimState prim) ty
ma State# (PrimState prim)
s1 of
        (# s2 :: State# (PrimState prim)
s2, a :: Array# ty
a #) -> (# State# (PrimState prim)
s2, Offset ty -> CountOf ty -> Array# ty -> Array ty
forall a. Offset a -> CountOf a -> Array# a -> Array a
Array Offset ty
ofs CountOf ty
sz Array# ty
a #)
{-# INLINE unsafeFreeze #-}

-- | Thaw an immutable array.
--
-- The Array must not be used after thawing.
unsafeThaw :: PrimMonad prim => Array ty -> prim (MArray ty (PrimState prim))
unsafeThaw :: Array ty -> prim (MArray ty (PrimState prim))
unsafeThaw (Array ofs :: Offset ty
ofs sz :: CountOf ty
sz a :: Array# ty
a) = (State# (PrimState prim)
 -> (# State# (PrimState prim), MArray ty (PrimState prim) #))
-> prim (MArray ty (PrimState prim))
forall (m :: * -> *) a.
PrimMonad m =>
(State# (PrimState m) -> (# State# (PrimState m), a #)) -> m a
primitive ((State# (PrimState prim)
  -> (# State# (PrimState prim), MArray ty (PrimState prim) #))
 -> prim (MArray ty (PrimState prim)))
-> (State# (PrimState prim)
    -> (# State# (PrimState prim), MArray ty (PrimState prim) #))
-> prim (MArray ty (PrimState prim))
forall a b. (a -> b) -> a -> b
$ \st :: State# (PrimState prim)
st -> (# State# (PrimState prim)
st, Offset ty
-> CountOf ty
-> MutableArray# (PrimState prim) ty
-> MArray ty (PrimState prim)
forall a st.
Offset a -> CountOf a -> MutableArray# st a -> MArray a st
MArray Offset ty
ofs CountOf ty
sz (Array# ty -> MutableArray# (PrimState prim) ty
unsafeCoerce# Array# ty
a) #)
{-# INLINE unsafeThaw #-}

-- | Thaw an array to a mutable array.
--
-- the array is not modified, instead a new mutable array is created
-- and every values is copied, before returning the mutable array.
thaw :: PrimMonad prim => Array ty -> prim (MArray ty (PrimState prim))
thaw :: Array ty -> prim (MArray ty (PrimState prim))
thaw array :: Array ty
array = do
    MArray ty (PrimState prim)
m <- CountOf ty -> prim (MArray ty (PrimState prim))
forall (prim :: * -> *) ty.
PrimMonad prim =>
CountOf ty -> prim (MArray ty (PrimState prim))
new (Array ty -> CountOf ty
forall a. Array a -> CountOf a
length Array ty
array)
    MArray ty (PrimState prim)
-> Offset ty -> Array ty -> Offset ty -> CountOf ty -> prim ()
forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim)
-> Offset ty -> Array ty -> Offset ty -> CountOf ty -> prim ()
unsafeCopyAtRO MArray ty (PrimState prim)
m (Int -> Offset ty
forall ty. Int -> Offset ty
Offset 0) Array ty
array (Int -> Offset ty
forall ty. Int -> Offset ty
Offset 0) (Array ty -> CountOf ty
forall a. Array a -> CountOf a
length Array ty
array)
    MArray ty (PrimState prim) -> prim (MArray ty (PrimState prim))
forall (f :: * -> *) a. Applicative f => a -> f a
pure MArray ty (PrimState prim)
m
{-# INLINE thaw #-}

freeze :: PrimMonad prim => MArray ty (PrimState prim) -> prim (Array ty)
freeze :: MArray ty (PrimState prim) -> prim (Array ty)
freeze marray :: MArray ty (PrimState prim)
marray = do
    MArray ty (PrimState prim)
m <- CountOf ty -> prim (MArray ty (PrimState prim))
forall (prim :: * -> *) ty.
PrimMonad prim =>
CountOf ty -> prim (MArray ty (PrimState prim))
new CountOf ty
sz
    MArray ty (PrimState prim)
-> Offset ty
-> MArray ty (PrimState prim)
-> Offset ty
-> CountOf ty
-> prim ()
forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim)
-> Offset ty
-> MArray ty (PrimState prim)
-> Offset ty
-> CountOf ty
-> prim ()
copyAt MArray ty (PrimState prim)
m (Int -> Offset ty
forall ty. Int -> Offset ty
Offset 0) MArray ty (PrimState prim)
marray (Int -> Offset ty
forall ty. Int -> Offset ty
Offset 0) CountOf ty
sz
    MArray ty (PrimState prim) -> prim (Array ty)
forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> prim (Array ty)
unsafeFreeze MArray ty (PrimState prim)
m
  where
    sz :: CountOf ty
sz = MArray ty (PrimState prim) -> CountOf ty
forall ty st. MArray ty st -> CountOf ty
mutableLengthSize MArray ty (PrimState prim)
marray

-- | Copy the element to a new element array
copy :: Array ty -> Array ty
copy :: Array ty -> Array ty
copy a :: Array ty
a = (forall s. ST s (Array ty)) -> Array ty
forall a. (forall s. ST s a) -> a
runST (Array ty -> ST s (MArray ty (PrimState (ST s)))
forall (prim :: * -> *) ty.
PrimMonad prim =>
Array ty -> prim (MArray ty (PrimState prim))
unsafeThaw Array ty
a ST s (MArray ty s)
-> (MArray ty s -> ST s (Array ty)) -> ST s (Array ty)
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= MArray ty s -> ST s (Array ty)
forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> prim (Array ty)
freeze)

-- | Copy a number of elements from an array to another array with offsets
copyAt :: PrimMonad prim
       => MArray ty (PrimState prim) -- ^ destination array
       -> Offset ty                  -- ^ offset at destination
       -> MArray ty (PrimState prim) -- ^ source array
       -> Offset ty                  -- ^ offset at source
       -> CountOf ty                 -- ^ number of elements to copy
       -> prim ()
copyAt :: MArray ty (PrimState prim)
-> Offset ty
-> MArray ty (PrimState prim)
-> Offset ty
-> CountOf ty
-> prim ()
copyAt dst :: MArray ty (PrimState prim)
dst od :: Offset ty
od src :: MArray ty (PrimState prim)
src os :: Offset ty
os n :: CountOf ty
n = Offset ty -> Offset ty -> prim ()
loop Offset ty
od Offset ty
os
  where -- !endIndex = os `offsetPlusE` n
        loop :: Offset ty -> Offset ty -> prim ()
loop d :: Offset ty
d s :: Offset ty
s
            | Offset ty
s Offset ty -> CountOf ty -> Bool
forall ty. Offset ty -> CountOf ty -> Bool
.==# CountOf ty
n  = () -> prim ()
forall (f :: * -> *) a. Applicative f => a -> f a
pure ()
            | Bool
otherwise = MArray ty (PrimState prim) -> Offset ty -> prim ty
forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> Offset ty -> prim ty
unsafeRead MArray ty (PrimState prim)
src Offset ty
s prim ty -> (ty -> prim ()) -> prim ()
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= MArray ty (PrimState prim) -> Offset ty -> ty -> prim ()
forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> Offset ty -> ty -> prim ()
unsafeWrite MArray ty (PrimState prim)
dst Offset ty
d prim () -> prim () -> prim ()
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> Offset ty -> Offset ty -> prim ()
loop (Offset ty
dOffset ty -> Offset ty -> Offset ty
forall a. Additive a => a -> a -> a
+1) (Offset ty
sOffset ty -> Offset ty -> Offset ty
forall a. Additive a => a -> a -> a
+1)

-- | Copy @n@ sequential elements from the specified offset in a source array
--   to the specified position in a destination array.
--
--   This function does not check bounds. Accessing invalid memory can return
--   unpredictable and invalid values.
unsafeCopyAtRO :: PrimMonad prim
               => MArray ty (PrimState prim) -- ^ destination array
               -> Offset ty                  -- ^ offset at destination
               -> Array ty                   -- ^ source array
               -> Offset ty                  -- ^ offset at source
               -> CountOf ty                    -- ^ number of elements to copy
               -> prim ()
unsafeCopyAtRO :: MArray ty (PrimState prim)
-> Offset ty -> Array ty -> Offset ty -> CountOf ty -> prim ()
unsafeCopyAtRO (MArray (Offset (I# dstart :: Int#
dstart)) _ da :: MutableArray# (PrimState prim) ty
da) (Offset (I# dofs :: Int#
dofs))
               (Array  (Offset (I# sstart :: Int#
sstart)) _ sa :: Array# ty
sa) (Offset (I# sofs :: Int#
sofs))
               (CountOf (I# n :: Int#
n)) =
    (State# (PrimState prim) -> (# State# (PrimState prim), () #))
-> prim ()
forall (m :: * -> *) a.
PrimMonad m =>
(State# (PrimState m) -> (# State# (PrimState m), a #)) -> m a
primitive ((State# (PrimState prim) -> (# State# (PrimState prim), () #))
 -> prim ())
-> (State# (PrimState prim) -> (# State# (PrimState prim), () #))
-> prim ()
forall a b. (a -> b) -> a -> b
$ \st :: State# (PrimState prim)
st ->
        (# Array# ty
-> Int#
-> MutableArray# (PrimState prim) ty
-> Int#
-> Int#
-> State# (PrimState prim)
-> State# (PrimState prim)
forall a d.
Array# a
-> Int#
-> MutableArray# d a
-> Int#
-> Int#
-> State# d
-> State# d
copyArray# Array# ty
sa (Int#
sstart Int# -> Int# -> Int#
+# Int#
sofs) MutableArray# (PrimState prim) ty
da (Int#
dstart Int# -> Int# -> Int#
+# Int#
dofs) Int#
n State# (PrimState prim)
st, () #)

-- | Allocate a new array with a fill function that has access to the elements of
--   the source array.
unsafeCopyFrom :: Array ty -- ^ Source array
               -> CountOf ty  -- ^ Length of the destination array
               -> (Array ty -> Offset ty -> MArray ty s -> ST s ())
               -- ^ Function called for each element in the source array
               -> ST s (Array ty) -- ^ Returns the filled new array
unsafeCopyFrom :: Array ty
-> CountOf ty
-> (Array ty -> Offset ty -> MArray ty s -> ST s ())
-> ST s (Array ty)
unsafeCopyFrom v' :: Array ty
v' newLen :: CountOf ty
newLen f :: Array ty -> Offset ty -> MArray ty s -> ST s ()
f = CountOf ty -> ST s (MArray ty (PrimState (ST s)))
forall (prim :: * -> *) ty.
PrimMonad prim =>
CountOf ty -> prim (MArray ty (PrimState prim))
new CountOf ty
newLen ST s (MArray ty s)
-> (MArray ty s -> ST s (MArray ty s)) -> ST s (MArray ty s)
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= Offset ty
-> (Array ty -> Offset ty -> MArray ty s -> ST s ())
-> MArray ty s
-> ST s (MArray ty s)
fill (Int -> Offset ty
forall ty. Int -> Offset ty
Offset 0) Array ty -> Offset ty -> MArray ty s -> ST s ()
f ST s (MArray ty s)
-> (MArray ty s -> ST s (Array ty)) -> ST s (Array ty)
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= MArray ty s -> ST s (Array ty)
forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> prim (Array ty)
unsafeFreeze
  where len :: CountOf ty
len = Array ty -> CountOf ty
forall a. Array a -> CountOf a
length Array ty
v'
        endIdx :: Offset ty
endIdx = Int -> Offset ty
forall ty. Int -> Offset ty
Offset 0 Offset ty -> CountOf ty -> Offset ty
forall ty. Offset ty -> CountOf ty -> Offset ty
`offsetPlusE` CountOf ty
len
        fill :: Offset ty
-> (Array ty -> Offset ty -> MArray ty s -> ST s ())
-> MArray ty s
-> ST s (MArray ty s)
fill i :: Offset ty
i f' :: Array ty -> Offset ty -> MArray ty s -> ST s ()
f' r' :: MArray ty s
r'
            | Offset ty
i Offset ty -> Offset ty -> Bool
forall a. Eq a => a -> a -> Bool
== Offset ty
endIdx = MArray ty s -> ST s (MArray ty s)
forall (f :: * -> *) a. Applicative f => a -> f a
pure MArray ty s
r'
            | Bool
otherwise   = do Array ty -> Offset ty -> MArray ty s -> ST s ()
f' Array ty
v' Offset ty
i MArray ty s
r'
                               Offset ty
-> (Array ty -> Offset ty -> MArray ty s -> ST s ())
-> MArray ty s
-> ST s (MArray ty s)
fill (Offset ty
i Offset ty -> Offset ty -> Offset ty
forall a. Additive a => a -> a -> a
+ Int -> Offset ty
forall ty. Int -> Offset ty
Offset 1) Array ty -> Offset ty -> MArray ty s -> ST s ()
f' MArray ty s
r'

-- | Create a new mutable array of size @n.
--
-- all the cells are uninitialized and could contains invalid values.
--
-- All mutable arrays are allocated on a 64 bits aligned addresses
-- and always contains a number of bytes multiples of 64 bits.
new :: PrimMonad prim => CountOf ty -> prim (MArray ty (PrimState prim))
new :: CountOf ty -> prim (MArray ty (PrimState prim))
new sz :: CountOf ty
sz@(CountOf (I# n :: Int#
n)) = (State# (PrimState prim)
 -> (# State# (PrimState prim), MArray ty (PrimState prim) #))
-> prim (MArray ty (PrimState prim))
forall (m :: * -> *) a.
PrimMonad m =>
(State# (PrimState m) -> (# State# (PrimState m), a #)) -> m a
primitive ((State# (PrimState prim)
  -> (# State# (PrimState prim), MArray ty (PrimState prim) #))
 -> prim (MArray ty (PrimState prim)))
-> (State# (PrimState prim)
    -> (# State# (PrimState prim), MArray ty (PrimState prim) #))
-> prim (MArray ty (PrimState prim))
forall a b. (a -> b) -> a -> b
$ \s1 :: State# (PrimState prim)
s1 ->
    case Int#
-> ty
-> State# (PrimState prim)
-> (# State# (PrimState prim), MutableArray# (PrimState prim) ty #)
forall a d.
Int# -> a -> State# d -> (# State# d, MutableArray# d a #)
newArray# Int#
n ([Char] -> ty
forall a. HasCallStack => [Char] -> a
error "vector: internal error uninitialized vector") State# (PrimState prim)
s1 of
        (# s2 :: State# (PrimState prim)
s2, ma :: MutableArray# (PrimState prim) ty
ma #) -> (# State# (PrimState prim)
s2, Offset ty
-> CountOf ty
-> MutableArray# (PrimState prim) ty
-> MArray ty (PrimState prim)
forall a st.
Offset a -> CountOf a -> MutableArray# st a -> MArray a st
MArray (Int -> Offset ty
forall ty. Int -> Offset ty
Offset 0) CountOf ty
sz MutableArray# (PrimState prim) ty
ma #)

-- | Create a new array of size @n by settings each cells through the
-- function @f.
create :: forall ty . CountOf ty -- ^ the size of the array
       -> (Offset ty -> ty)   -- ^ the function that set the value at the index
       -> Array ty            -- ^ the array created
create :: CountOf ty -> (Offset ty -> ty) -> Array ty
create n :: CountOf ty
n initializer :: Offset ty -> ty
initializer = (forall s. ST s (Array ty)) -> Array ty
forall a. (forall s. ST s a) -> a
runST (CountOf ty -> ST s (MArray ty (PrimState (ST s)))
forall (prim :: * -> *) ty.
PrimMonad prim =>
CountOf ty -> prim (MArray ty (PrimState prim))
new CountOf ty
n ST s (MArray ty s)
-> (MArray ty s -> ST s (Array ty)) -> ST s (Array ty)
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= (Offset ty -> ty)
-> MArray ty (PrimState (ST s)) -> ST s (Array ty)
forall (prim :: * -> *).
PrimMonad prim =>
(Offset ty -> ty) -> MArray ty (PrimState prim) -> prim (Array ty)
iter Offset ty -> ty
initializer)
  where
    iter :: PrimMonad prim => (Offset ty -> ty) -> MArray ty (PrimState prim) -> prim (Array ty)
    iter :: (Offset ty -> ty) -> MArray ty (PrimState prim) -> prim (Array ty)
iter f :: Offset ty -> ty
f ma :: MArray ty (PrimState prim)
ma = Offset ty -> prim (Array ty)
loop 0
      where
        loop :: Offset ty -> prim (Array ty)
loop s :: Offset ty
s
            | Offset ty
s Offset ty -> CountOf ty -> Bool
forall ty. Offset ty -> CountOf ty -> Bool
.==# CountOf ty
n  = MArray ty (PrimState prim) -> prim (Array ty)
forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> prim (Array ty)
unsafeFreeze MArray ty (PrimState prim)
ma
            | Bool
otherwise = MArray ty (PrimState prim) -> Offset ty -> ty -> prim ()
forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> Offset ty -> ty -> prim ()
unsafeWrite MArray ty (PrimState prim)
ma Offset ty
s (Offset ty -> ty
f Offset ty
s) prim () -> prim (Array ty) -> prim (Array ty)
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> Offset ty -> prim (Array ty)
loop (Offset ty
sOffset ty -> Offset ty -> Offset ty
forall a. Additive a => a -> a -> a
+1)
        {-# INLINE loop #-}
    {-# INLINE iter #-}

-----------------------------------------------------------------------
-- higher level collection implementation
-----------------------------------------------------------------------
equal :: Eq a => Array a -> Array a -> Bool
equal :: Array a -> Array a -> Bool
equal a :: Array a
a b :: Array a
b = (CountOf a
len CountOf a -> CountOf a -> Bool
forall a. Eq a => a -> a -> Bool
== Array a -> CountOf a
forall a. Array a -> CountOf a
length Array a
b) Bool -> Bool -> Bool
&& Offset a -> Bool
eachEqual 0
  where
    len :: CountOf a
len = Array a -> CountOf a
forall a. Array a -> CountOf a
length Array a
a
    eachEqual :: Offset a -> Bool
eachEqual !Offset a
i
        | Offset a
i Offset a -> CountOf a -> Bool
forall ty. Offset ty -> CountOf ty -> Bool
.==# CountOf a
len                         = Bool
True
        | Array a -> Offset a -> a
forall ty. Array ty -> Offset ty -> ty
unsafeIndex Array a
a Offset a
i a -> a -> Bool
forall a. Eq a => a -> a -> Bool
/= Array a -> Offset a -> a
forall ty. Array ty -> Offset ty -> ty
unsafeIndex Array a
b Offset a
i =