-- |
-- 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 #-}
{-# LANGUAGE TypeOperators #-}
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.Compat.Primitive
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 Array ty
_ = DataType
arrayType
    toConstr :: Array ty -> Constr
toConstr Array ty
_   = forall a. HasCallStack => [Char] -> a
error [Char]
"toConstr"
    gunfold :: forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (Array ty)
gunfold forall b r. Data b => c (b -> r) -> c r
_ forall r. r -> c r
_  = forall a. HasCallStack => [Char] -> a
error [Char]
"gunfold"

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

instance NormalForm a => NormalForm (Array a) where
    toNormalForm :: Array a -> ()
toNormalForm Array a
arr = Offset a -> ()
loop Offset a
0
      where
        !sz :: CountOf a
sz = forall a. Array a -> CountOf a
length Array a
arr
        loop :: Offset a -> ()
loop !Offset a
i
            | Offset a
i forall ty. Offset ty -> CountOf ty -> Bool
.==# CountOf a
sz = ()
            | Bool
otherwise = forall ty. Array ty -> Offset ty -> ty
unsafeIndex Array a
arr Offset a
i seq :: forall a b. a -> b -> b
`seq` Offset a -> ()
loop (Offset a
iforall a. Additive a => a -> a -> a
+Offset 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 :: forall a b. (a -> b) -> Array a -> Array b
fmap = forall a b. (a -> b) -> Array a -> Array b
map

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

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

instance Eq a => Eq (Array a) where
    == :: 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 = 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 = forall a. [a] -> Array a
vFromList
    fromListN :: Int -> [Item (Array ty)] -> Array ty
fromListN Int
len = forall a. CountOf a -> [a] -> Array a
vFromListN (forall ty. Int -> CountOf ty
CountOf Int
len)
    toList :: Array ty -> [Item (Array ty)]
toList = forall a. Array a -> [a]
vToList

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

-- | return the numbers of elements in a mutable array
mutableLengthSize :: MArray ty st -> CountOf ty
mutableLengthSize :: forall ty st. MArray ty st -> CountOf ty
mutableLengthSize (MArray Offset ty
_ CountOf ty
size MutableArray# st ty
_) = 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 :: forall ty. Array ty -> Offset ty -> ty
index Array ty
array Offset ty
n
    | forall ty. Offset ty -> CountOf ty -> Bool
isOutOfBound Offset ty
n CountOf ty
len = forall ty a. OutOfBoundOperation -> Offset ty -> CountOf ty -> a
outOfBound OutOfBoundOperation
OOB_Index Offset ty
n CountOf ty
len
    | Bool
otherwise          = forall ty. Array ty -> Offset ty -> ty
unsafeIndex Array ty
array Offset ty
n
  where len :: CountOf ty
len = 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 :: forall ty. Array ty -> Offset ty -> ty
unsafeIndex (Array Offset ty
start CountOf ty
_ Array# ty
a) Offset ty
ofs = forall ty. Array# ty -> Offset ty -> ty
primArrayIndex Array# ty
a (Offset ty
startforall 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 :: forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> Offset ty -> prim ty
read MArray ty (PrimState prim)
array Offset ty
n
    | forall ty. Offset ty -> CountOf ty -> Bool
isOutOfBound Offset ty
n CountOf ty
len = 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          = 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 = 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 :: forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> Offset ty -> prim ty
unsafeRead (MArray Offset ty
start CountOf ty
_ MutableArray# (PrimState prim) ty
ma) Offset ty
i = forall (prim :: * -> *) ty.
PrimMonad prim =>
MutableArray# (PrimState prim) ty -> Offset ty -> prim ty
primMutableArrayRead MutableArray# (PrimState prim) ty
ma (Offset ty
start 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 :: forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> Offset ty -> ty -> prim ()
write MArray ty (PrimState prim)
array Offset ty
n ty
val
    | forall ty. Offset ty -> CountOf ty -> Bool
isOutOfBound Offset ty
n CountOf ty
len = 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          = 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 = 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 :: forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> Offset ty -> ty -> prim ()
unsafeWrite (MArray Offset ty
start CountOf ty
_ MutableArray# (PrimState prim) ty
ma) Offset ty
ofs ty
v =
    forall (prim :: * -> *) ty.
PrimMonad prim =>
MutableArray# (PrimState prim) ty -> Offset ty -> ty -> prim ()
primMutableArrayWrite MutableArray# (PrimState prim) ty
ma (Offset ty
start 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 :: forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> prim (Array ty)
unsafeFreeze (MArray Offset ty
ofs CountOf ty
sz MutableArray# (PrimState prim) ty
ma) = forall (m :: * -> *) a.
PrimMonad m =>
(State# (PrimState m) -> (# State# (PrimState m), a #)) -> m a
primitive forall a b. (a -> b) -> a -> b
$ \State# (PrimState prim)
s1 ->
    case forall d a.
MutableArray# d a -> State# d -> (# State# d, Array# a #)
unsafeFreezeArray# MutableArray# (PrimState prim) ty
ma State# (PrimState prim)
s1 of
        (# State# (PrimState prim)
s2, Array# ty
a #) -> (# State# (PrimState prim)
s2, 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 :: forall (prim :: * -> *) ty.
PrimMonad prim =>
Array ty -> prim (MArray ty (PrimState prim))
unsafeThaw (Array Offset ty
ofs CountOf ty
sz Array# ty
a) = forall (m :: * -> *) a.
PrimMonad m =>
(State# (PrimState m) -> (# State# (PrimState m), a #)) -> m a
primitive forall a b. (a -> b) -> a -> b
$ \State# (PrimState prim)
st -> (# State# (PrimState prim)
st, forall a st.
Offset a -> CountOf a -> MutableArray# st a -> MArray a st
MArray Offset ty
ofs CountOf ty
sz (unsafeCoerce# :: forall a b. a -> b
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 :: forall (prim :: * -> *) ty.
PrimMonad prim =>
Array ty -> prim (MArray ty (PrimState prim))
thaw Array ty
array = do
    MArray ty (PrimState prim)
m <- forall (prim :: * -> *) ty.
PrimMonad prim =>
CountOf ty -> prim (MArray ty (PrimState prim))
new (forall a. Array a -> CountOf a
length Array ty
array)
    forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim)
-> Offset ty -> Array ty -> Offset ty -> CountOf ty -> prim ()
unsafeCopyAtRO MArray ty (PrimState prim)
m (forall ty. Int -> Offset ty
Offset Int
0) Array ty
array (forall ty. Int -> Offset ty
Offset Int
0) (forall a. Array a -> CountOf a
length Array ty
array)
    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 :: forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> prim (Array ty)
freeze MArray ty (PrimState prim)
marray = do
    MArray ty (PrimState prim)
m <- forall (prim :: * -> *) ty.
PrimMonad prim =>
CountOf ty -> prim (MArray ty (PrimState prim))
new CountOf ty
sz
    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 (forall ty. Int -> Offset ty
Offset Int
0) MArray ty (PrimState prim)
marray (forall ty. Int -> Offset ty
Offset Int
0) CountOf ty
sz
    forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> prim (Array ty)
unsafeFreeze MArray ty (PrimState prim)
m
  where
    sz :: CountOf ty
sz = 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 :: forall ty. Array ty -> Array ty
copy Array ty
a = forall a. (forall s. ST s a) -> a
runST (forall (prim :: * -> *) ty.
PrimMonad prim =>
Array ty -> prim (MArray ty (PrimState prim))
unsafeThaw Array ty
a forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= 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 :: 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)
dst Offset ty
od MArray ty (PrimState prim)
src Offset ty
os 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 Offset ty
d Offset ty
s
            | Offset ty
s forall ty. Offset ty -> CountOf ty -> Bool
.==# CountOf ty
n  = forall (f :: * -> *) a. Applicative f => a -> f a
pure ()
            | Bool
otherwise = forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> Offset ty -> prim ty
unsafeRead MArray ty (PrimState prim)
src Offset ty
s forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> Offset ty -> ty -> prim ()
unsafeWrite MArray ty (PrimState prim)
dst Offset ty
d forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> Offset ty -> Offset ty -> prim ()
loop (Offset ty
dforall a. Additive a => a -> a -> a
+Offset ty
1) (Offset ty
sforall a. Additive a => a -> a -> a
+Offset ty
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 :: forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim)
-> Offset ty -> Array ty -> Offset ty -> CountOf ty -> prim ()
unsafeCopyAtRO (MArray (Offset (I# Int#
dstart)) CountOf ty
_ MutableArray# (PrimState prim) ty
da) (Offset (I# Int#
dofs))
               (Array  (Offset (I# Int#
sstart)) CountOf ty
_ Array# ty
sa) (Offset (I# Int#
sofs))
               (CountOf (I# Int#
n)) =
    forall (m :: * -> *) a.
PrimMonad m =>
(State# (PrimState m) -> (# State# (PrimState m), a #)) -> m a
primitive forall a b. (a -> b) -> a -> b
$ \State# (PrimState prim)
st ->
        (# 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 :: forall ty s.
Array ty
-> CountOf ty
-> (Array ty -> Offset ty -> MArray ty s -> ST s ())
-> ST s (Array ty)
unsafeCopyFrom Array ty
v' CountOf ty
newLen Array ty -> Offset ty -> MArray ty s -> ST s ()
f = forall (prim :: * -> *) ty.
PrimMonad prim =>
CountOf ty -> prim (MArray ty (PrimState prim))
new CountOf ty
newLen 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 (forall ty. Int -> Offset ty
Offset Int
0) Array ty -> Offset ty -> MArray ty s -> ST s ()
f forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> prim (Array ty)
unsafeFreeze
  where len :: CountOf ty
len = forall a. Array a -> CountOf a
length Array ty
v'
        endIdx :: Offset ty
endIdx = forall ty. Int -> Offset ty
Offset Int
0 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 Offset ty
i Array ty -> Offset ty -> MArray ty s -> ST s ()
f' MArray ty s
r'
            | Offset ty
i forall a. Eq a => a -> a -> Bool
== Offset ty
endIdx = 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 forall a. Additive a => a -> a -> a
+ forall ty. Int -> Offset ty
Offset Int
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 :: forall (prim :: * -> *) ty.
PrimMonad prim =>
CountOf ty -> prim (MArray ty (PrimState prim))
new sz :: CountOf ty
sz@(CountOf (I# Int#
n)) = forall (m :: * -> *) a.
PrimMonad m =>
(State# (PrimState m) -> (# State# (PrimState m), a #)) -> m a
primitive forall a b. (a -> b) -> a -> b
$ \State# (PrimState prim)
s1 ->
    case forall a d.
Int# -> a -> State# d -> (# State# d, MutableArray# d a #)
newArray# Int#
n (forall a. HasCallStack => [Char] -> a
error [Char]
"vector: internal error uninitialized vector") State# (PrimState prim)
s1 of
        (# State# (PrimState prim)
s2, MutableArray# (PrimState prim) ty
ma #) -> (# State# (PrimState prim)
s2, forall a st.
Offset a -> CountOf a -> MutableArray# st a -> MArray a st
MArray (forall ty. Int -> Offset ty
Offset Int
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 :: forall ty. CountOf ty -> (Offset ty -> ty) -> Array ty
create CountOf ty
n Offset ty -> ty
initializer = forall a. (forall s. ST s a) -> a
runST (forall (prim :: * -> *) ty.
PrimMonad prim =>
CountOf ty -> prim (MArray ty (PrimState prim))
new CountOf ty
n forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= 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 :: forall (prim :: * -> *).
PrimMonad prim =>
(Offset ty -> ty) -> MArray ty (PrimState prim) -> prim (Array ty)
iter Offset ty -> ty
f MArray ty (PrimState prim)
ma = Offset ty -> prim (Array ty)
loop Offset ty
0
      where
        loop :: Offset ty -> prim (Array ty)
loop Offset ty
s
            | Offset ty
s forall ty. Offset ty -> CountOf ty -> Bool
.==# CountOf ty
n  = forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> prim (Array ty)
unsafeFreeze MArray ty (PrimState prim)
ma
            | Bool
otherwise = 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) forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> Offset ty -> prim (Array ty)
loop (Offset ty
sforall a. Additive a => a -> a -> a
+Offset ty
1)
        {-# INLINE loop #-}
    {-# INLINE iter #-}

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

vCompare :: Ord a => Array a -> Array a -> Ordering
vCompare :: forall a. Ord a => Array a -> Array a -> Ordering
vCompare Array a
a Array a
b = Offset a -> Ordering
loop Offset a
0
  where
    !la :: CountOf a
la = forall a. Array a -> CountOf a
length Array a
a
    !lb :: CountOf a
lb = forall a. Array a -> CountOf a
length Array a
b
    loop :: Offset a -> Ordering
loop Offset a
n
        | Offset a
n forall ty. Offset ty -> CountOf ty -> Bool
.==# CountOf a
la = if CountOf a
la forall a. Eq a => a -> a -> Bool
== CountOf a
lb then Ordering
EQ else Ordering
LT
        | Offset a
n forall ty. Offset ty -> CountOf ty -> Bool
.==# CountOf a
lb = Ordering
GT
        | Bool
otherwise =
            case forall ty. Array ty -> Offset ty -> ty
unsafeIndex Array a
a Offset a
n forall a. Ord a => a -> a -> Ordering
`compare` forall ty. Array ty -> Offset ty -> ty
unsafeIndex Array a
b Offset a
n of
                Ordering
EQ -> Offset a -> Ordering
loop (Offset a
nforall a. Additive a => a -> a -> a
+Offset a
1)
                Ordering
r  -> Ordering
r

empty :: Array a
empty :: forall a. Array a
empty = forall a. (forall s. ST s a) -> a
runST forall a b. (a -> b) -> a -> b
$ forall (m :: * -> *) a.
PrimMonad m =>
Int
-> (MutableArray# (PrimState m) a
    -> State# (PrimState m) -> State# (PrimState m))
-> m (Array a)
onNewArray Int
0 (\MutableArray# (PrimState (ST s)) a
_ State# (PrimState (ST s))
s -> State# (PrimState (ST s))
s)

length :: Array a -> CountOf a
length :: forall a. Array a -> CountOf a
length (Array Offset a
_ CountOf a
sz Array# a
_) = CountOf a
sz

vFromList :: [a] -> Array a
vFromList :: forall a. [a] -> Array a
vFromList [a]
l = forall a. (forall s. ST s a) -> a
runST (forall (prim :: * -> *) ty.
PrimMonad prim =>
CountOf ty -> prim (MArray ty (PrimState prim))
new CountOf a
len forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall {prim :: * -> *} {ty}.
PrimMonad prim =>
Offset ty -> [ty] -> MArray ty (PrimState prim) -> prim (Array ty)
loop Offset a
0 [a]
l)
  where
    len :: CountOf a
len = forall a. [a] -> CountOf a
List.length [a]
l
    loop :: Offset ty -> [ty] -> MArray ty (PrimState prim) -> prim (Array ty)
loop Offset ty
_ []     MArray ty (PrimState prim)
ma = forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> prim (Array ty)
unsafeFreeze MArray ty (PrimState prim)
ma
    loop Offset ty
i (ty
x:[ty]
xs) MArray ty (PrimState prim)
ma = forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> Offset ty -> ty -> prim ()
unsafeWrite MArray ty (PrimState prim)
ma Offset ty
i ty
x forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> Offset ty -> [ty] -> MArray ty (PrimState prim) -> prim (Array ty)
loop (Offset ty
iforall a. Additive a => a -> a -> a
+Offset ty
1) [ty]
xs MArray ty (PrimState prim)
ma

-- | just like vFromList but with a length hint.
--
-- The resulting array is guarantee to have been allocated to the length
-- specified, but the slice might point to the initialized cells only in
-- case the length is bigger than the list.
--
-- If the length is too small, then the list is truncated.
--
vFromListN :: forall a . CountOf a -> [a] -> Array a
vFromListN :: forall a. CountOf a -> [a] -> Array a
vFromListN CountOf a
len [a]
l = forall a. (forall s. ST s a) -> a
runST forall a b. (a -> b) -> a -> b
$ do
    MArray a s
ma <- forall (prim :: * -> *) ty.
PrimMonad prim =>
CountOf ty -> prim (MArray ty (PrimState prim))
new CountOf a
len
    CountOf a
sz <- forall s. Offset a -> [a] -> MArray a s -> ST s (CountOf a)
loop Offset a
0 [a]
l MArray a s
ma
    forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> CountOf ty -> prim (Array ty)
unsafeFreezeShrink MArray a s
ma CountOf a
sz
  where
    -- TODO rewrite without ma as parameter
    loop :: Offset a -> [a] -> MArray a s -> ST s (CountOf a)
    loop :: forall s. Offset a -> [a] -> MArray a s -> ST s (CountOf a)
loop Offset a
i []     MArray a s
_  = forall (m :: * -> *) a. Monad m => a -> m a
return (forall a. Offset a -> CountOf a
offsetAsSize Offset a
i)
    loop Offset a
i (a
x:[a]
xs) MArray a s
ma
        | Offset a
i forall ty. Offset ty -> CountOf ty -> Bool
.==# CountOf a
len = forall (m :: * -> *) a. Monad m => a -> m a
return (forall a. Offset a -> CountOf a
offsetAsSize Offset a
i)
        | Bool
otherwise  = forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> Offset ty -> ty -> prim ()
unsafeWrite MArray a s
ma Offset a
i a
x forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> forall s. Offset a -> [a] -> MArray a s -> ST s (CountOf a)
loop (Offset a
iforall a. Additive a => a -> a -> a
+Offset a
1) [a]
xs MArray a s
ma

vToList :: Array a -> [a]
vToList :: forall a. Array a -> [a]
vToList Array a
v
    | CountOf a
len forall a. Eq a => a -> a -> Bool
== CountOf a
0  = []
    | Bool
otherwise = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (forall ty. Array ty -> Offset ty -> ty
unsafeIndex Array a
v) [Offset a
0..forall a. CountOf a -> Offset a
sizeLastOffset CountOf a
len]
  where !len :: CountOf a
len = forall a. Array a -> CountOf a
length Array a
v

-- | Append 2 arrays together by creating a new bigger array
append :: Array ty -> Array ty -> Array ty
append :: forall a. Array a -> Array a -> Array a
append Array ty
a Array ty
b = forall a. (forall s. ST s a) -> a
runST forall a b. (a -> b) -> a -> b
$ do
    MArray ty s
r  <- forall (prim :: * -> *) ty.
PrimMonad prim =>
CountOf ty -> prim (MArray ty (PrimState prim))
new (CountOf ty
laforall a. Additive a => a -> a -> a
+CountOf ty
lb)
    forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim)
-> Offset ty -> Array ty -> Offset ty -> CountOf ty -> prim ()
unsafeCopyAtRO MArray ty s
r (forall ty. Int -> Offset ty
Offset Int
0) Array ty
a (forall ty. Int -> Offset ty
Offset Int
0) CountOf ty
la
    forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim)
-> Offset ty -> Array ty -> Offset ty -> CountOf ty -> prim ()
unsafeCopyAtRO MArray ty s
r (forall a. CountOf a -> Offset a
sizeAsOffset CountOf ty
la) Array ty
b (forall ty. Int -> Offset ty
Offset Int
0) CountOf ty
lb
    forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> prim (Array ty)
unsafeFreeze MArray ty s
r
  where la :: CountOf ty
la = forall a. Array a -> CountOf a
length Array ty
a
        lb :: CountOf ty
lb = forall a. Array a -> CountOf a
length Array ty
b

concat :: [Array ty] -> Array ty
concat :: forall a. [Array a] -> Array a
concat [Array ty]
l = forall a. (forall s. ST s a) -> a
runST forall a b. (a -> b) -> a -> b
$ do
    MArray ty s
r <- forall (prim :: * -> *) ty.
PrimMonad prim =>
CountOf ty -> prim (MArray ty (PrimState prim))
new (forall a. Monoid a => [a] -> a
mconcat forall a b. (a -> b) -> a -> b
$ forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a. Array a -> CountOf a
length [Array ty]
l)
    forall {f :: * -> *} {ty}.
PrimMonad f =>
MArray ty (PrimState f) -> Offset ty -> [Array ty] -> f ()
loop MArray ty s
r (forall ty. Int -> Offset ty
Offset Int
0) [Array ty]
l
    forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> prim (Array ty)
unsafeFreeze MArray ty s
r
  where loop :: MArray ty (PrimState f) -> Offset ty -> [Array ty] -> f ()
loop MArray ty (PrimState f)
_ Offset ty
_ []     = forall (f :: * -> *) a. Applicative f => a -> f a
pure ()
        loop MArray ty (PrimState f)
r Offset ty
i (Array ty
x:[Array ty]
xs) = do
            forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim)
-> Offset ty -> Array ty -> Offset ty -> CountOf ty -> prim ()
unsafeCopyAtRO MArray ty (PrimState f)
r Offset ty
i Array ty
x (forall ty. Int -> Offset ty
Offset Int
0) CountOf ty
lx
            MArray ty (PrimState f) -> Offset ty -> [Array ty] -> f ()
loop MArray ty (PrimState f)
r (Offset ty
i forall ty. Offset ty -> CountOf ty -> Offset ty
`offsetPlusE` CountOf ty
lx) [Array ty]
xs
          where lx :: CountOf ty
lx = forall a. Array a -> CountOf a
length Array ty
x

{-
modify :: PrimMonad m
       => Array a
       -> (MArray (PrimState m) a -> m ())
       -> m (Array a)
modify (Array a) f = primitive $ \st -> do
    case thawArray# a 0# (sizeofArray# a) st of
        (# st2, mv #) ->
            case internal_ (f $ MArray mv) st2 of
                st3 ->
                    case unsafeFreezeArray# mv st3 of
                        (# st4, a' #) -> (# st4, Array a' #)
-}

-----------------------------------------------------------------------
-- helpers

onNewArray :: PrimMonad m
           => Int
           -> (MutableArray# (PrimState m) a -> State# (PrimState m) -> State# (PrimState m))
           -> m (Array a)
onNewArray :: forall (m :: * -> *) a.
PrimMonad m =>
Int
-> (MutableArray# (PrimState m) a
    -> State# (PrimState m) -> State# (PrimState m))
-> m (Array a)
onNewArray len :: Int
len@(I# Int#
len#) MutableArray# (PrimState m) a
-> State# (PrimState m) -> State# (PrimState m)
f = forall (m :: * -> *) a.
PrimMonad m =>
(State# (PrimState m) -> (# State# (PrimState m), a #)) -> m a
primitive forall a b. (a -> b) -> a -> b
$ \State# (PrimState m)
st -> do
    case forall a d.
Int# -> a -> State# d -> (# State# d, MutableArray# d a #)
newArray# Int#
len# (forall a. HasCallStack => [Char] -> a
error [Char]
"onArray") State# (PrimState m)
st of { (# State# (PrimState m)
st2, MutableArray# (PrimState m) a
mv #) ->
    case MutableArray# (PrimState m) a
-> State# (PrimState m) -> State# (PrimState m)
f MutableArray# (PrimState m) a
mv State# (PrimState m)
st2                            of { State# (PrimState m)
st3           ->
    case forall d a.
MutableArray# d a -> State# d -> (# State# d, Array# a #)
unsafeFreezeArray# MutableArray# (PrimState m) a
mv State# (PrimState m)
st3           of { (# State# (PrimState m)
st4, Array# a
a #)  ->
        (# State# (PrimState m)
st4, forall a. Offset a -> CountOf a -> Array# a -> Array a
Array (forall ty. Int -> Offset ty
Offset Int
0) (forall ty. Int -> CountOf ty
CountOf Int
len) Array# a
a #) }}}

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


null :: Array ty -> Bool
null :: forall ty. Array ty -> Bool
null = forall a. Eq a => a -> a -> Bool
(==) CountOf ty
0 forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. forall a. Array a -> CountOf a
length

take :: CountOf ty -> Array ty -> Array ty
take :: forall ty. CountOf ty -> Array ty -> Array ty
take CountOf ty
nbElems a :: Array ty
a@(Array Offset ty
start CountOf ty
len Array# ty
arr)
    | CountOf ty
nbElems forall a. Ord a => a -> a -> Bool
<= CountOf ty
0 = forall a. Array a
empty
    | CountOf ty
n forall a. Eq a => a -> a -> Bool
== CountOf ty
len     = Array ty
a
    | Bool
otherwise    = forall a. Offset a -> CountOf a -> Array# a -> Array a
Array Offset ty
start CountOf ty
n Array# ty
arr
  where
    n :: CountOf ty
n = forall a. Ord a => a -> a -> a
min CountOf ty
nbElems CountOf ty
len

drop :: CountOf ty -> Array ty -> Array ty
drop :: forall ty. CountOf ty -> Array ty -> Array ty
drop CountOf ty
nbElems a :: Array ty
a@(Array Offset ty
start CountOf ty
len Array# ty
arr)
    | CountOf ty
nbElems forall a. Ord a => a -> a -> Bool
<= CountOf ty
0                               = Array ty
a
    | Just CountOf ty
nbTails <- CountOf ty
len forall a. Subtractive a => a -> a -> Difference a
- CountOf ty
nbElems, CountOf ty
nbTails forall a. Ord a => a -> a -> Bool
> CountOf ty
0 = forall a. Offset a -> CountOf a -> Array# a -> Array a
Array (Offset ty
start forall ty. Offset ty -> CountOf ty -> Offset ty
`offsetPlusE` CountOf ty
nbElems) CountOf ty
nbTails Array# ty
arr
    | Bool
otherwise                                  = forall a. Array a
empty

splitAt :: CountOf ty -> Array ty -> (Array ty, Array ty)
splitAt :: forall ty. CountOf ty -> Array ty -> (Array ty, Array ty)
splitAt CountOf ty
nbElems a :: Array ty
a@(Array Offset ty
start CountOf ty
len Array# ty
arr)
    | CountOf ty
nbElems forall a. Ord a => a -> a -> Bool
<= CountOf ty
0 = (forall a. Array a
empty, Array ty
a)
    | Just CountOf ty
nbTails <- CountOf ty
len forall a. Subtractive a => a -> a -> Difference a
- CountOf ty
nbElems, CountOf ty
nbTails forall a. Ord a => a -> a -> Bool
> CountOf ty
0 = ( forall a. Offset a -> CountOf a -> Array# a -> Array a
Array Offset ty
start                         CountOf ty
nbElems Array# ty
arr
                                                   , forall a. Offset a -> CountOf a -> Array# a -> Array a
Array (Offset ty
start forall ty. Offset ty -> CountOf ty -> Offset ty
`offsetPlusE` CountOf ty
nbElems) CountOf ty
nbTails Array# ty
arr)
    | Bool
otherwise = (Array ty
a, forall a. Array a
empty)

-- inverse a CountOf that is specified from the end (e.g. take n elements from the end)
countFromStart :: Array ty -> CountOf ty -> CountOf ty
countFromStart :: forall ty. Array ty -> CountOf ty -> CountOf ty
countFromStart Array ty
v sz :: CountOf ty
sz@(CountOf Int
sz')
    | CountOf ty
sz forall a. Ord a => a -> a -> Bool
>= CountOf ty
len = forall ty. Int -> CountOf ty
CountOf Int
0
    | Bool
otherwise = forall ty. Int -> CountOf ty
CountOf (Int
len' forall a. Subtractive a => a -> a -> Difference a
- Int
sz')
  where len :: CountOf ty
len@(CountOf Int
len') = forall a. Array a -> CountOf a
length Array ty
v

revTake :: CountOf ty -> Array ty -> Array ty
revTake :: forall ty. CountOf ty -> Array ty -> Array ty
revTake CountOf ty
n Array ty
v = forall ty. CountOf ty -> Array ty -> Array ty
drop (forall ty. Array ty -> CountOf ty -> CountOf ty
countFromStart Array ty
v CountOf ty
n) Array ty
v

revDrop :: CountOf ty -> Array ty -> Array ty
revDrop :: forall ty. CountOf ty -> Array ty -> Array ty
revDrop CountOf ty
n Array ty
v = forall ty. CountOf ty -> Array ty -> Array ty
take (forall ty. Array ty -> CountOf ty -> CountOf ty
countFromStart Array ty
v CountOf ty
n) Array ty
v

revSplitAt :: CountOf ty -> Array ty -> (Array ty, Array ty)
revSplitAt :: forall ty. CountOf ty -> Array ty -> (Array ty, Array ty)
revSplitAt CountOf ty
n Array ty
v = (forall ty. CountOf ty -> Array ty -> Array ty
drop CountOf ty
idx Array ty
v, forall ty. CountOf ty -> Array ty -> Array ty
take CountOf ty
idx Array ty
v) where idx :: CountOf ty
idx = forall ty. Array ty -> CountOf ty -> CountOf ty
countFromStart Array ty
v CountOf ty
n

splitOn ::  (ty -> Bool) -> Array ty -> [Array ty]
splitOn :: forall ty. (ty -> Bool) -> Array ty -> [Array ty]
splitOn ty -> Bool
predicate Array ty
vec
    | CountOf ty
len forall a. Eq a => a -> a -> Bool
== forall ty. Int -> CountOf ty
CountOf Int
0 = [forall a. Monoid a => a
mempty]
    | Bool
otherwise     = Offset ty -> Offset ty -> [Array ty]
loop (forall ty. Int -> Offset ty
Offset Int
0) (forall ty. Int -> Offset ty
Offset Int
0)
  where
    !len :: CountOf ty
len = forall a. Array a -> CountOf a
length Array ty
vec
    !endIdx :: Offset ty
endIdx = forall ty. Int -> Offset ty
Offset Int
0 forall ty. Offset ty -> CountOf ty -> Offset ty
`offsetPlusE` CountOf ty
len
    loop :: Offset ty -> Offset ty -> [Array ty]
loop Offset ty
prevIdx Offset ty
idx
        | Offset ty
idx forall a. Eq a => a -> a -> Bool
== Offset ty
endIdx = [forall ty. Array ty -> Offset ty -> Offset ty -> Array ty
sub Array ty
vec Offset ty
prevIdx Offset ty
idx]
        | Bool
otherwise     =
            let e :: ty
e = forall ty. Array ty -> Offset ty -> ty
unsafeIndex Array ty
vec Offset ty
idx
                idx' :: Offset ty
idx' = Offset ty
idx forall a. Additive a => a -> a -> a
+ Offset ty
1
             in if ty -> Bool
predicate ty
e
                    then forall ty. Array ty -> Offset ty -> Offset ty -> Array ty
sub Array ty
vec Offset ty
prevIdx Offset ty
idx forall a. a -> [a] -> [a]
: Offset ty -> Offset ty -> [Array ty]
loop Offset ty
idx' Offset ty
idx'
                    else Offset ty -> Offset ty -> [Array ty]
loop Offset ty
prevIdx Offset ty
idx'

sub :: Array ty -> Offset ty -> Offset ty -> Array ty
sub :: forall ty. Array ty -> Offset ty -> Offset ty -> Array ty
sub (Array Offset ty
start CountOf ty
len Array# ty
a) Offset ty
startIdx Offset ty
expectedEndIdx
    | Offset ty
startIdx forall a. Eq a => a -> a -> Bool
== Offset ty
endIdx           = forall a. Array a
empty
    | Bool
otherwise                    = forall a. Offset a -> CountOf a -> Array# a -> Array a
Array (Offset ty
start forall a. Additive a => a -> a -> a
+ Offset ty
startIdx) Difference (Offset ty)
newLen Array# ty
a
  where
    newLen :: Difference (Offset ty)
newLen = Offset ty
endIdx forall a. Subtractive a => a -> a -> Difference a
- Offset ty
startIdx
    endIdx :: Offset ty
endIdx = forall a. Ord a => a -> a -> a
min Offset ty
expectedEndIdx (forall a. CountOf a -> Offset a
sizeAsOffset CountOf ty
len)

break ::  (ty -> Bool) -> Array ty -> (Array ty, Array ty)
break :: forall ty. (ty -> Bool) -> Array ty -> (Array ty, Array ty)
break ty -> Bool
predicate Array ty
v = Offset ty -> (Array ty, Array ty)
findBreak Offset ty
0
  where
    !len :: CountOf ty
len = forall a. Array a -> CountOf a
length Array ty
v
    findBreak :: Offset ty -> (Array ty, Array ty)
findBreak Offset ty
i
        | Offset ty
i forall ty. Offset ty -> CountOf ty -> Bool
.==# CountOf ty
len  = (Array ty
v, forall a. Array a
empty)
        | Bool
otherwise   =
            if ty -> Bool
predicate (forall ty. Array ty -> Offset ty -> ty
unsafeIndex Array ty
v Offset ty
i)
                then forall ty. CountOf ty -> Array ty -> (Array ty, Array ty)
splitAt (forall a. Offset a -> CountOf a
offsetAsSize Offset ty
i) Array ty
v
                else Offset ty -> (Array ty, Array ty)
findBreak (Offset ty
iforall a. Additive a => a -> a -> a
+Offset ty
1)

breakEnd ::  (ty -> Bool) -> Array ty -> (Array ty, Array ty)
breakEnd :: forall ty. (ty -> Bool) -> Array ty -> (Array ty, Array ty)
breakEnd ty -> Bool
predicate Array ty
v = Offset ty -> (Array ty, Array ty)
findBreak (forall a. CountOf a -> Offset a
sizeAsOffset CountOf ty
len)
  where
    !len :: CountOf ty
len = forall a. Array a -> CountOf a
length Array ty
v
    findBreak :: Offset ty -> (Array ty, Array ty)
findBreak !Offset ty
i
        | Offset ty
i forall a. Eq a => a -> a -> Bool
== Offset ty
0      = (Array ty
v, forall a. Array a
empty)
        | ty -> Bool
predicate ty
e = forall ty. CountOf ty -> Array ty -> (Array ty, Array ty)
splitAt (forall a. Offset a -> CountOf a
offsetAsSize Offset ty
i) Array ty
v
        | Bool
otherwise   = Offset ty -> (Array ty, Array ty)
findBreak Offset ty
i'
      where
        e :: ty
e = forall ty. Array ty -> Offset ty -> ty
unsafeIndex Array ty
v Offset ty
i'
        i' :: Offset ty
i' = Offset ty
i forall a. Offset a -> Offset a -> Offset a
`offsetSub` Offset ty
1

intersperse :: ty -> Array ty -> Array ty
intersperse :: forall ty. ty -> Array ty -> Array ty
intersperse ty
sep Array ty
v = case CountOf ty
len forall a. Subtractive a => a -> a -> Difference a
- CountOf ty
1 of
    Maybe (CountOf ty)
Difference (CountOf ty)
Nothing -> Array ty
v
    Just CountOf ty
0 -> Array ty
v
    Just CountOf ty
more -> forall a. (forall s. ST s a) -> a
runST forall a b. (a -> b) -> a -> b
$ forall ty s.
Array ty
-> CountOf ty
-> (Array ty -> Offset ty -> MArray ty s -> ST s ())
-> ST s (Array ty)
unsafeCopyFrom Array ty
v (CountOf ty
len forall a. Additive a => a -> a -> a
+ CountOf ty
more) (forall ty s.
Offset ty -> ty -> Array ty -> Offset ty -> MArray ty s -> ST s ()
go (forall ty. Int -> Offset ty
Offset Int
0 forall ty. Offset ty -> CountOf ty -> Offset ty
`offsetPlusE` CountOf ty
more) ty
sep)
  where len :: CountOf ty
len = forall a. Array a -> CountOf a
length Array ty
v
        -- terminate 1 before the end

        go :: Offset ty -> ty -> Array ty -> Offset ty -> MArray ty s -> ST s ()
        go :: forall ty s.
Offset ty -> ty -> Array ty -> Offset ty -> MArray ty s -> ST s ()
go Offset ty
endI ty
sep' Array ty
oldV Offset ty
oldI MArray ty s
newV
            | Offset ty
oldI forall a. Eq a => a -> a -> Bool
== Offset ty
endI = forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> Offset ty -> ty -> prim ()
unsafeWrite MArray ty s
newV Offset ty
dst ty
e
            | Bool
otherwise    = do
                forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> Offset ty -> ty -> prim ()
unsafeWrite MArray ty s
newV Offset ty
dst ty
e
                forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> Offset ty -> ty -> prim ()
unsafeWrite MArray ty s
newV (Offset ty
dst forall a. Additive a => a -> a -> a
+ Offset ty
1) ty
sep'
          where
            e :: ty
e = forall ty. Array ty -> Offset ty -> ty
unsafeIndex Array ty
oldV Offset ty
oldI
            dst :: Offset ty
dst = Offset ty
oldI forall a. Additive a => a -> a -> a
+ Offset ty
oldI

span ::  (ty -> Bool) -> Array ty -> (Array ty, Array ty)
span :: forall ty. (ty -> Bool) -> Array ty -> (Array ty, Array ty)
span ty -> Bool
p = forall ty. (ty -> Bool) -> Array ty -> (Array ty, Array ty)
break (Bool -> Bool
not forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. ty -> Bool
p)

spanEnd ::  (ty -> Bool) -> Array ty -> (Array ty, Array ty)
spanEnd :: forall ty. (ty -> Bool) -> Array ty -> (Array ty, Array ty)
spanEnd ty -> Bool
p = forall ty. (ty -> Bool) -> Array ty -> (Array ty, Array ty)
breakEnd (Bool -> Bool
not forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. ty -> Bool
p)

map :: (a -> b) -> Array a -> Array b
map :: forall a b. (a -> b) -> Array a -> Array b
map a -> b
f Array a
a = forall ty. CountOf ty -> (Offset ty -> ty) -> Array ty
create (forall a b. Proxy (a -> b) -> CountOf a -> CountOf b
sizeCast forall {k} (t :: k). Proxy t
Proxy forall a b. (a -> b) -> a -> b
$ forall a. Array a -> CountOf a
length Array a
a) (\Offset b
i -> a -> b
f forall a b. (a -> b) -> a -> b
$ forall ty. Array ty -> Offset ty -> ty
unsafeIndex Array a
a (forall a b. Proxy (a -> b) -> Offset a -> Offset b
offsetCast forall {k} (t :: k). Proxy t
Proxy Offset b
i))

mapFromUnboxed :: PrimType a => (a -> b) -> UArray a -> Array b
mapFromUnboxed :: forall a b. PrimType a => (a -> b) -> UArray a -> Array b
mapFromUnboxed a -> b
f UArray a
arr = forall a. CountOf a -> [a] -> Array a
vFromListN (forall a b. Proxy (a -> b) -> CountOf a -> CountOf b
sizeCast forall {k} (t :: k). Proxy t
Proxy forall a b. (a -> b) -> a -> b
$ forall ty. UArray ty -> CountOf ty
UArray.length UArray a
arr) forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> b
f forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. forall l. IsList l => l -> [Item l]
toList forall a b. (a -> b) -> a -> b
$ UArray a
arr

mapToUnboxed :: PrimType b => (a -> b) -> Array a -> UArray b
mapToUnboxed :: forall b a. PrimType b => (a -> b) -> Array a -> UArray b
mapToUnboxed a -> b
f Array a
arr = forall ty. PrimType ty => CountOf ty -> [ty] -> UArray ty
UArray.vFromListN (forall a b. Proxy (a -> b) -> CountOf a -> CountOf b
sizeCast forall {k} (t :: k). Proxy t
Proxy forall a b. (a -> b) -> a -> b
$ forall a. Array a -> CountOf a
length Array a
arr) forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> b
f forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. forall l. IsList l => l -> [Item l]
toList forall a b. (a -> b) -> a -> b
$ Array a
arr

{-
mapIndex :: (Int -> a -> b) -> Array a -> Array b
mapIndex f a = create (length a) (\i -> f i $ unsafeIndex a i)
-}

singleton :: ty -> Array ty
singleton :: forall ty. ty -> Array ty
singleton ty
e = forall a. (forall s. ST s a) -> a
runST forall a b. (a -> b) -> a -> b
$ do
    MArray ty s
a <- forall (prim :: * -> *) ty.
PrimMonad prim =>
CountOf ty -> prim (MArray ty (PrimState prim))
new CountOf ty
1
    forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> Offset ty -> ty -> prim ()
unsafeWrite MArray ty s
a Offset ty
0 ty
e
    forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> prim (Array ty)
unsafeFreeze MArray ty s
a

replicate :: CountOf ty -> ty -> Array ty
replicate :: forall ty. CountOf ty -> ty -> Array ty
replicate CountOf ty
sz ty
ty = forall ty. CountOf ty -> (Offset ty -> ty) -> Array ty
create CountOf ty
sz (forall a b. a -> b -> a
const ty
ty)

cons :: ty -> Array ty -> Array ty
cons :: forall ty. ty -> Array ty -> Array ty
cons ty
e Array ty
vec
    | CountOf ty
len forall a. Eq a => a -> a -> Bool
== forall ty. Int -> CountOf ty
CountOf Int
0 = forall ty. ty -> Array ty
singleton ty
e
    | Bool
otherwise     = forall a. (forall s. ST s a) -> a
runST forall a b. (a -> b) -> a -> b
$ do
        MArray ty s
mv <- forall (prim :: * -> *) ty.
PrimMonad prim =>
CountOf ty -> prim (MArray ty (PrimState prim))
new (CountOf ty
len forall a. Additive a => a -> a -> a
+ forall ty. Int -> CountOf ty
CountOf Int
1)
        forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> Offset ty -> ty -> prim ()
unsafeWrite MArray ty s
mv Offset ty
0 ty
e
        forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim)
-> Offset ty -> Array ty -> Offset ty -> CountOf ty -> prim ()
unsafeCopyAtRO MArray ty s
mv (forall ty. Int -> Offset ty
Offset Int
1) Array ty
vec (forall ty. Int -> Offset ty
Offset Int
0) CountOf ty
len
        forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> prim (Array ty)
unsafeFreeze MArray ty s
mv
  where
    !len :: CountOf ty
len = forall a. Array a -> CountOf a
length Array ty
vec

snoc ::  Array ty -> ty -> Array ty
snoc :: forall ty. Array ty -> ty -> Array ty
snoc Array ty
vec ty
e
    | CountOf ty
len forall a. Eq a => a -> a -> Bool
== CountOf ty
0  = forall ty. ty -> Array ty
singleton ty
e
    | Bool
otherwise = forall a. (forall s. ST s a) -> a
runST forall a b. (a -> b) -> a -> b
$ do
        MArray ty s
mv <- forall (prim :: * -> *) ty.
PrimMonad prim =>
CountOf ty -> prim (MArray ty (PrimState prim))
new (CountOf ty
len forall a. Additive a => a -> a -> a
+ CountOf ty
1)
        forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim)
-> Offset ty -> Array ty -> Offset ty -> CountOf ty -> prim ()
unsafeCopyAtRO MArray ty s
mv Offset ty
0 Array ty
vec Offset ty
0 CountOf ty
len
        forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> Offset ty -> ty -> prim ()
unsafeWrite MArray ty s
mv (forall a. CountOf a -> Offset a
sizeAsOffset CountOf ty
len) ty
e
        forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> prim (Array ty)
unsafeFreeze MArray ty s
mv
  where
    !len :: CountOf ty
len = forall a. Array a -> CountOf a
length Array ty
vec

uncons :: Array ty -> Maybe (ty, Array ty)
uncons :: forall ty. Array ty -> Maybe (ty, Array ty)
uncons Array ty
vec
    | CountOf ty
len forall a. Eq a => a -> a -> Bool
== CountOf ty
0  = forall a. Maybe a
Nothing
    | Bool
otherwise = forall a. a -> Maybe a
Just (forall ty. Array ty -> Offset ty -> ty
unsafeIndex Array ty
vec Offset ty
0, forall ty. CountOf ty -> Array ty -> Array ty
drop CountOf ty
1 Array ty
vec)
  where
    !len :: CountOf ty
len = forall a. Array a -> CountOf a
length Array ty
vec

unsnoc :: Array ty -> Maybe (Array ty, ty)
unsnoc :: forall ty. Array ty -> Maybe (Array ty, ty)
unsnoc Array ty
vec = case CountOf ty
len forall a. Subtractive a => a -> a -> Difference a
- CountOf ty
1 of
    Maybe (CountOf ty)
Difference (CountOf ty)
Nothing -> forall a. Maybe a
Nothing
    Just CountOf ty
newLen -> forall a. a -> Maybe a
Just (forall ty. CountOf ty -> Array ty -> Array ty
take CountOf ty
newLen Array ty
vec, forall ty. Array ty -> Offset ty -> ty
unsafeIndex Array ty
vec (forall a. CountOf a -> Offset a
sizeLastOffset CountOf ty
len))
  where
    !len :: CountOf ty
len = forall a. Array a -> CountOf a
length Array ty
vec

elem :: Eq ty => ty -> Array ty -> Bool
elem :: forall ty. Eq ty => ty -> Array ty -> Bool
elem !ty
ty Array ty
arr = Offset ty -> Bool
loop Offset ty
0
  where
    !sz :: CountOf ty
sz = forall a. Array a -> CountOf a
length Array ty
arr
    loop :: Offset ty -> Bool
loop !Offset ty
i | Offset ty
i forall ty. Offset ty -> CountOf ty -> Bool
.==# CountOf ty
sz = Bool
False
            | ty
t forall a. Eq a => a -> a -> Bool
== ty
ty   = Bool
True
            | Bool
otherwise = Offset ty -> Bool
loop (Offset ty
iforall a. Additive a => a -> a -> a
+Offset ty
1)
      where t :: ty
t = forall ty. Array ty -> Offset ty -> ty
unsafeIndex Array ty
arr Offset ty
i

find :: (ty -> Bool) -> Array ty -> Maybe ty
find :: forall ty. (ty -> Bool) -> Array ty -> Maybe ty
find ty -> Bool
predicate Array ty
vec = Offset ty -> Maybe ty
loop Offset ty
0
  where
    !len :: CountOf ty
len = forall a. Array a -> CountOf a
length Array ty
vec
    loop :: Offset ty -> Maybe ty
loop Offset ty
i
        | Offset ty
i forall ty. Offset ty -> CountOf ty -> Bool
.==# CountOf ty
len = forall a. Maybe a
Nothing
        | Bool
otherwise  =
            let e :: ty
e = forall ty. Array ty -> Offset ty -> ty
unsafeIndex Array ty
vec Offset ty
i
             in if ty -> Bool
predicate ty
e then forall a. a -> Maybe a
Just ty
e else Offset ty -> Maybe ty
loop (Offset ty
iforall a. Additive a => a -> a -> a
+Offset ty
1)

instance (PrimMonad prim, st ~ PrimState prim) 
         => Alg.RandomAccess (MArray ty st) prim ty where
    read :: MArray ty st -> Offset ty -> prim ty
read (MArray Offset ty
_ CountOf ty
_ MutableArray# st ty
mba) = forall (prim :: * -> *) ty.
PrimMonad prim =>
MutableArray# (PrimState prim) ty -> Offset ty -> prim ty
primMutableArrayRead MutableArray# st ty
mba
    write :: MArray ty st -> Offset ty -> ty -> prim ()
write (MArray Offset ty
_ CountOf ty
_ MutableArray# st ty
mba) = forall (prim :: * -> *) ty.
PrimMonad prim =>
MutableArray# (PrimState prim) ty -> Offset ty -> ty -> prim ()
primMutableArrayWrite MutableArray# st ty
mba

sortBy :: forall ty . (ty -> ty -> Ordering) -> Array ty -> Array ty
sortBy :: forall ty. (ty -> ty -> Ordering) -> Array ty -> Array ty
sortBy ty -> ty -> Ordering
xford Array ty
vec
    | CountOf ty
len forall a. Eq a => a -> a -> Bool
== CountOf ty
0  = forall a. Array a
empty
    | Bool
otherwise = forall a. (forall s. ST s a) -> a
runST (forall (prim :: * -> *) ty.
PrimMonad prim =>
Array ty -> prim (MArray ty (PrimState prim))
thaw Array ty
vec forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall (prim :: * -> *).
PrimMonad prim =>
(ty -> ty -> Ordering)
-> MArray ty (PrimState prim) -> prim (Array ty)
doSort ty -> ty -> Ordering
xford)
  where
    len :: CountOf ty
len = forall a. Array a -> CountOf a
length Array ty
vec
    doSort :: PrimMonad prim => (ty -> ty -> Ordering) -> MArray ty (PrimState prim) -> prim (Array ty)
    doSort :: forall (prim :: * -> *).
PrimMonad prim =>
(ty -> ty -> Ordering)
-> MArray ty (PrimState prim) -> prim (Array ty)
doSort ty -> ty -> Ordering
ford MArray ty (PrimState prim)
ma = forall (prim :: * -> *) container ty.
(PrimMonad prim, RandomAccess container prim ty) =>
(ty -> ty -> Ordering)
-> Offset ty -> CountOf ty -> container -> prim ()
Alg.inplaceSortBy ty -> ty -> Ordering
ford Offset ty
0 CountOf ty
len MArray ty (PrimState prim)
ma forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> prim (Array ty)
unsafeFreeze MArray ty (PrimState prim)
ma

filter :: forall ty . (ty -> Bool) -> Array ty -> Array ty
filter :: forall ty. (ty -> Bool) -> Array ty -> Array ty
filter ty -> Bool
predicate Array ty
vec = forall a. (forall s. ST s a) -> a
runST (forall (prim :: * -> *) ty.
PrimMonad prim =>
CountOf ty -> prim (MArray ty (PrimState prim))
new CountOf ty
len forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall (prim :: * -> *).
PrimMonad prim =>
(ty -> Bool)
-> (Offset ty -> ty)
-> MArray ty (PrimState prim)
-> prim (Array ty)
copyFilterFreeze ty -> Bool
predicate (forall ty. Array ty -> Offset ty -> ty
unsafeIndex Array ty
vec))
  where
    !len :: CountOf ty
len = forall a. Array a -> CountOf a
length Array ty
vec
    copyFilterFreeze :: PrimMonad prim => (ty -> Bool) -> (Offset ty -> ty) -> MArray ty (PrimState prim) -> prim (Array ty)
    copyFilterFreeze :: forall (prim :: * -> *).
PrimMonad prim =>
(ty -> Bool)
-> (Offset ty -> ty)
-> MArray ty (PrimState prim)
-> prim (Array ty)
copyFilterFreeze ty -> Bool
predi Offset ty -> ty
getVec MArray ty (PrimState prim)
mvec = Offset ty -> Offset ty -> prim (Offset ty)
loop (forall ty. Int -> Offset ty
Offset Int
0) (forall ty. Int -> Offset ty
Offset Int
0) forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> Offset ty -> prim (Array ty)
freezeUntilIndex MArray ty (PrimState prim)
mvec
      where
        loop :: Offset ty -> Offset ty -> prim (Offset ty)
loop Offset ty
d Offset ty
s
            | Offset ty
s forall ty. Offset ty -> CountOf ty -> Bool
.==# CountOf ty
len  = forall (f :: * -> *) a. Applicative f => a -> f a
pure Offset ty
d
            | ty -> Bool
predi ty
v     = forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> Offset ty -> ty -> prim ()
unsafeWrite MArray ty (PrimState prim)
mvec Offset ty
d ty
v forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> Offset ty -> Offset ty -> prim (Offset ty)
loop (Offset ty
dforall a. Additive a => a -> a -> a
+Offset ty
1) (Offset ty
sforall a. Additive a => a -> a -> a
+Offset ty
1)
            | Bool
otherwise   = Offset ty -> Offset ty -> prim (Offset ty)
loop Offset ty
d (Offset ty
sforall a. Additive a => a -> a -> a
+Offset ty
1)
          where
            v :: ty
v = Offset ty -> ty
getVec Offset ty
s

freezeUntilIndex :: PrimMonad prim => MArray ty (PrimState prim) -> Offset ty -> prim (Array ty)
freezeUntilIndex :: forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> Offset ty -> prim (Array ty)
freezeUntilIndex MArray ty (PrimState prim)
mvec Offset ty
d = do
    MArray ty (PrimState prim)
m <- forall (prim :: * -> *) ty.
PrimMonad prim =>
CountOf ty -> prim (MArray ty (PrimState prim))
new (forall a. Offset a -> CountOf a
offsetAsSize Offset ty
d)
    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 (forall ty. Int -> Offset ty
Offset Int
0) MArray ty (PrimState prim)
mvec (forall ty. Int -> Offset ty
Offset Int
0) (forall a. Offset a -> CountOf a
offsetAsSize Offset ty
d)
    forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> prim (Array ty)
unsafeFreeze MArray ty (PrimState prim)
m

unsafeFreezeShrink :: PrimMonad prim => MArray ty (PrimState prim) -> CountOf ty -> prim (Array ty)
unsafeFreezeShrink :: forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> CountOf ty -> prim (Array ty)
unsafeFreezeShrink (MArray Offset ty
start CountOf ty
_ MutableArray# (PrimState prim) ty
ma) CountOf ty
n = forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> prim (Array ty)
unsafeFreeze (forall a st.
Offset a -> CountOf a -> MutableArray# st a -> MArray a st
MArray Offset ty
start CountOf ty
n MutableArray# (PrimState prim) ty
ma)

reverse :: Array ty -> Array ty
reverse :: forall ty. Array ty -> Array ty
reverse Array ty
a = forall ty. CountOf ty -> (Offset ty -> ty) -> Array ty
create CountOf ty
len Offset ty -> ty
toEnd
  where
    len :: CountOf ty
len@(CountOf Int
s) = forall a. Array a -> CountOf a
length Array ty
a
    toEnd :: Offset ty -> ty
toEnd (Offset Int
i) = forall ty. Array ty -> Offset ty -> ty
unsafeIndex Array ty
a (forall ty. Int -> Offset ty
Offset (Int
s forall a. Subtractive a => a -> a -> Difference a
- Int
1 forall a. Subtractive a => a -> a -> Difference a
- Int
i))

foldr :: (ty -> a -> a) -> a -> Array ty -> a
foldr :: forall ty a. (ty -> a -> a) -> a -> Array ty -> a
foldr ty -> a -> a
f a
initialAcc Array ty
vec = Offset ty -> a
loop Offset ty
0
  where
    len :: CountOf ty
len = forall a. Array a -> CountOf a
length Array ty
vec
    loop :: Offset ty -> a
loop !Offset ty
i
        | Offset ty
i forall ty. Offset ty -> CountOf ty -> Bool
.==# CountOf ty
len = a
initialAcc
        | Bool
otherwise  = forall ty. Array ty -> Offset ty -> ty
unsafeIndex Array ty
vec Offset ty
i ty -> a -> a
`f` Offset ty -> a
loop (Offset ty
iforall a. Additive a => a -> a -> a
+Offset ty
1)

foldl' :: (a -> ty -> a) -> a -> Array ty -> a
foldl' :: forall a ty. (a -> ty -> a) -> a -> Array ty -> a
foldl' a -> ty -> a
f a
initialAcc Array ty
vec = Offset ty -> a -> a
loop Offset ty
0 a
initialAcc
  where
    len :: CountOf ty
len = forall a. Array a -> CountOf a
length Array ty
vec
    loop :: Offset ty -> a -> a
loop !Offset ty
i !a
acc
        | Offset ty
i forall ty. Offset ty -> CountOf ty -> Bool
.==# CountOf ty
len = a
acc
        | Bool
otherwise  = Offset ty -> a -> a
loop (Offset ty
iforall a. Additive a => a -> a -> a
+Offset ty
1) (a -> ty -> a
f a
acc (forall ty. Array ty -> Offset ty -> ty
unsafeIndex Array ty
vec Offset ty
i))

foldl1' :: (ty -> ty -> ty) -> NonEmpty (Array ty) -> ty
foldl1' :: forall ty. (ty -> ty -> ty) -> NonEmpty (Array ty) -> ty
foldl1' ty -> ty -> ty
f NonEmpty (Array ty)
arr = let (Array ty
initialAcc, Array ty
rest) = forall ty. CountOf ty -> Array ty -> (Array ty, Array ty)
splitAt CountOf ty
1 forall a b. (a -> b) -> a -> b
$ forall a. NonEmpty a -> a
getNonEmpty NonEmpty (Array ty)
arr
               in forall a ty. (a -> ty -> a) -> a -> Array ty -> a
foldl' ty -> ty -> ty
f (forall ty. Array ty -> Offset ty -> ty
unsafeIndex Array ty
initialAcc Offset ty
0) Array ty
rest

foldr1 :: (ty -> ty -> ty) -> NonEmpty (Array ty) -> ty
foldr1 :: forall ty. (ty -> ty -> ty) -> NonEmpty (Array ty) -> ty
foldr1 ty -> ty -> ty
f NonEmpty (Array ty)
arr = let (Array ty
initialAcc, Array ty
rest) = forall ty. CountOf ty -> Array ty -> (Array ty, Array ty)
revSplitAt CountOf ty
1 forall a b. (a -> b) -> a -> b
$ forall a. NonEmpty a -> a
getNonEmpty NonEmpty (Array ty)
arr
               in forall ty a. (ty -> a -> a) -> a -> Array ty -> a
foldr ty -> ty -> ty
f (forall ty. Array ty -> Offset ty -> ty
unsafeIndex Array ty
initialAcc Offset ty
0) Array ty
rest

all :: (ty -> Bool) -> Array ty -> Bool
all :: forall ty. (ty -> Bool) -> Array ty -> Bool
all ty -> Bool
p Array ty
ba = Offset ty -> Bool
loop Offset ty
0
  where
    len :: CountOf ty
len = forall a. Array a -> CountOf a
length Array ty
ba
    loop :: Offset ty -> Bool
loop !Offset ty
i
      | Offset ty
i forall ty. Offset ty -> CountOf ty -> Bool
.==# CountOf ty
len = Bool
True
      | Bool -> Bool
not forall a b. (a -> b) -> a -> b
$ ty -> Bool
p (forall ty. Array ty -> Offset ty -> ty
unsafeIndex Array ty
ba Offset ty
i) = Bool
False
      | Bool
otherwise = Offset ty -> Bool
loop (Offset ty
i forall a. Additive a => a -> a -> a
+ Offset ty
1)

any :: (ty -> Bool) -> Array ty -> Bool
any :: forall ty. (ty -> Bool) -> Array ty -> Bool
any ty -> Bool
p Array ty
ba = Offset ty -> Bool
loop Offset ty
0
  where
    len :: CountOf ty
len = forall a. Array a -> CountOf a
length Array ty
ba
    loop :: Offset ty -> Bool
loop !Offset ty
i
      | Offset ty
i forall ty. Offset ty -> CountOf ty -> Bool
.==# CountOf ty
len = Bool
False
      | ty -> Bool
p (forall ty. Array ty -> Offset ty -> ty
unsafeIndex Array ty
ba Offset ty
i) = Bool
True
      | Bool
otherwise = Offset ty -> Bool
loop (Offset ty
i forall a. Additive a => a -> a -> a
+ Offset ty
1)

isPrefixOf :: Eq ty => Array ty -> Array ty -> Bool
isPrefixOf :: forall a. Eq a => Array a -> Array a -> Bool
isPrefixOf Array ty
pre Array ty
arr
    | CountOf ty
pLen forall a. Ord a => a -> a -> Bool
> CountOf ty
pArr = Bool
False
    | Bool
otherwise   = Array ty
pre forall a. Eq a => a -> a -> Bool
== forall ty. CountOf ty -> Array ty -> Array ty
take CountOf ty
pLen Array ty
arr
  where
    !pLen :: CountOf ty
pLen = forall a. Array a -> CountOf a
length Array ty
pre
    !pArr :: CountOf ty
pArr = forall a. Array a -> CountOf a
length Array ty
arr

isSuffixOf :: Eq ty => Array ty -> Array ty -> Bool
isSuffixOf :: forall a. Eq a => Array a -> Array a -> Bool
isSuffixOf Array ty
suffix Array ty
arr
    | CountOf ty
pLen forall a. Ord a => a -> a -> Bool
> CountOf ty
pArr = Bool
False
    | Bool
otherwise   = Array ty
suffix forall a. Eq a => a -> a -> Bool
== forall ty. CountOf ty -> Array ty -> Array ty
revTake CountOf ty
pLen Array ty
arr
  where
    !pLen :: CountOf ty
pLen = forall a. Array a -> CountOf a
length Array ty
suffix
    !pArr :: CountOf ty
pArr = forall a. Array a -> CountOf a
length Array ty
arr

builderAppend :: PrimMonad state => ty -> Builder (Array ty) (MArray ty) ty state err ()
builderAppend :: forall (state :: * -> *) ty err.
PrimMonad state =>
ty -> Builder (Array ty) (MArray ty) ty state err ()
builderAppend ty
v = forall collection (mutCollection :: * -> *) step (state :: * -> *)
       err a.
State
  (Offset step,
   BuildingState collection mutCollection step (PrimState state),
   Maybe err)
  state
  a
-> Builder collection mutCollection step state err a
Builder forall a b. (a -> b) -> a -> b
$ forall s (m :: * -> *) a. (s -> m (a, s)) -> State s m a
State forall a b. (a -> b) -> a -> b
$ \(Offset ty
i, BuildingState (Array ty) (MArray ty) ty (PrimState state)
st, Maybe err
e) ->
    if Offset ty
i forall ty. Offset ty -> CountOf ty -> Bool
.==# forall collection (mutCollection :: * -> *) step state.
BuildingState collection mutCollection step state -> CountOf step
chunkSize BuildingState (Array ty) (MArray ty) ty (PrimState state)
st
        then do
            Array ty
cur      <- forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> prim (Array ty)
unsafeFreeze (forall collection (mutCollection :: * -> *) step state.
BuildingState collection mutCollection step state
-> mutCollection state
curChunk BuildingState (Array ty) (MArray ty) ty (PrimState state)
st)
            MArray ty (PrimState state)
newChunk <- forall (prim :: * -> *) ty.
PrimMonad prim =>
CountOf ty -> prim (MArray ty (PrimState prim))
new (forall collection (mutCollection :: * -> *) step state.
BuildingState collection mutCollection step state -> CountOf step
chunkSize BuildingState (Array ty) (MArray ty) ty (PrimState state)
st)
            forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> Offset ty -> ty -> prim ()
unsafeWrite MArray ty (PrimState state)
newChunk Offset ty
0 ty
v
            forall (f :: * -> *) a. Applicative f => a -> f a
pure ((), (forall ty. Int -> Offset ty
Offset Int
1, BuildingState (Array ty) (MArray ty) ty (PrimState state)
st { prevChunks :: [Array ty]
prevChunks     = Array ty
cur forall a. a -> [a] -> [a]
: forall collection (mutCollection :: * -> *) step state.
BuildingState collection mutCollection step state -> [collection]
prevChunks BuildingState (Array ty) (MArray ty) ty (PrimState state)
st
                                      , prevChunksSize :: CountOf ty
prevChunksSize = forall collection (mutCollection :: * -> *) step state.
BuildingState collection mutCollection step state -> CountOf step
chunkSize BuildingState (Array ty) (MArray ty) ty (PrimState state)
st forall a. Additive a => a -> a -> a
+ forall collection (mutCollection :: * -> *) step state.
BuildingState collection mutCollection step state -> CountOf step
prevChunksSize BuildingState (Array ty) (MArray ty) ty (PrimState state)
st
                                      , curChunk :: MArray ty (PrimState state)
curChunk       = MArray ty (PrimState state)
newChunk
                                      }, Maybe err
e))
        else do
            forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> Offset ty -> ty -> prim ()
unsafeWrite (forall collection (mutCollection :: * -> *) step state.
BuildingState collection mutCollection step state
-> mutCollection state
curChunk BuildingState (Array ty) (MArray ty) ty (PrimState state)
st) Offset ty
i ty
v
            forall (f :: * -> *) a. Applicative f => a -> f a
pure ((), (Offset ty
iforall a. Additive a => a -> a -> a
+Offset ty
1, BuildingState (Array ty) (MArray ty) ty (PrimState state)
st, Maybe err
e))

builderBuild :: PrimMonad m => Int -> Builder (Array ty) (MArray ty) ty m err () -> m (Either err (Array ty))
builderBuild :: forall (m :: * -> *) ty err.
PrimMonad m =>
Int
-> Builder (Array ty) (MArray ty) ty m err ()
-> m (Either err (Array ty))
builderBuild Int
sizeChunksI Builder (Array ty) (MArray ty) ty m err ()
ab
    | Int
sizeChunksI forall a. Ord a => a -> a -> Bool
<= Int
0 = forall (m :: * -> *) ty err.
PrimMonad m =>
Int
-> Builder (Array ty) (MArray ty) ty m err ()
-> m (Either err (Array ty))
builderBuild Int
64 Builder (Array ty) (MArray ty) ty m err ()
ab
    | Bool
otherwise        = do
        MArray ty (PrimState m)
first      <- forall (prim :: * -> *) ty.
PrimMonad prim =>
CountOf ty -> prim (MArray ty (PrimState prim))
new CountOf ty
sizeChunks
        (Offset ty
i, BuildingState (Array ty) (MArray ty) ty (PrimState m)
st, Maybe err
e) <- forall a b. (a, b) -> b
snd forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall s (m :: * -> *) a. State s m a -> s -> m (a, s)
runState (forall collection (mutCollection :: * -> *) step (state :: * -> *)
       err a.
Builder collection mutCollection step state err a
-> State
     (Offset step,
      BuildingState collection mutCollection step (PrimState state),
      Maybe err)
     state
     a
runBuilder Builder (Array ty) (MArray ty) ty m err ()
ab) (forall ty. Int -> Offset ty
Offset Int
0, forall collection (mutCollection :: * -> *) step state.
[collection]
-> CountOf step
-> mutCollection state
-> CountOf step
-> BuildingState collection mutCollection step state
BuildingState [] (forall ty. Int -> CountOf ty
CountOf Int
0) MArray ty (PrimState m)
first CountOf ty
sizeChunks, forall a. Maybe a
Nothing)
        case Maybe err
e of
          Just err
err -> forall (f :: * -> *) a. Applicative f => a -> f a
pure (forall a b. a -> Either a b
Left err
err)
          Maybe err
Nothing -> do
            Array ty
cur <- forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> CountOf ty -> prim (Array ty)
unsafeFreezeShrink (forall collection (mutCollection :: * -> *) step state.
BuildingState collection mutCollection step state
-> mutCollection state
curChunk BuildingState (Array ty) (MArray ty) ty (PrimState m)
st) (forall a. Offset a -> CountOf a
offsetAsSize Offset ty
i)
            -- Build final array
            let totalSize :: CountOf ty
totalSize = forall collection (mutCollection :: * -> *) step state.
BuildingState collection mutCollection step state -> CountOf step
prevChunksSize BuildingState (Array ty) (MArray ty) ty (PrimState m)
st forall a. Additive a => a -> a -> a
+ forall a. Offset a -> CountOf a
offsetAsSize Offset ty
i
            Array ty
bytes <- forall (prim :: * -> *) ty.
PrimMonad prim =>
CountOf ty -> prim (MArray ty (PrimState prim))
new CountOf ty
totalSize forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall {f :: * -> *} {ty}.
PrimMonad f =>
CountOf ty
-> [Array ty]
-> MArray ty (PrimState f)
-> f (MArray ty (PrimState f))
fillFromEnd CountOf ty
totalSize (Array ty
cur forall a. a -> [a] -> [a]
: forall collection (mutCollection :: * -> *) step state.
BuildingState collection mutCollection step state -> [collection]
prevChunks BuildingState (Array ty) (MArray ty) ty (PrimState m)
st) forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> prim (Array ty)
unsafeFreeze
            forall (f :: * -> *) a. Applicative f => a -> f a
pure (forall a b. b -> Either a b
Right Array ty
bytes)
  where
    sizeChunks :: CountOf ty
sizeChunks = forall ty. Int -> CountOf ty
CountOf Int
sizeChunksI

    fillFromEnd :: CountOf ty
-> [Array ty]
-> MArray ty (PrimState f)
-> f (MArray ty (PrimState f))
fillFromEnd CountOf ty
_    []     MArray ty (PrimState f)
mua = forall (f :: * -> *) a. Applicative f => a -> f a
pure MArray ty (PrimState f)
mua
    fillFromEnd !CountOf ty
end (Array ty
x:[Array ty]
xs) MArray ty (PrimState f)
mua = do
        let sz :: CountOf ty
sz = forall a. Array a -> CountOf a
length Array ty
x
        let start :: CountOf ty
start = CountOf ty
end forall a. CountOf a -> CountOf a -> CountOf a
`sizeSub` CountOf ty
sz
        forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim)
-> Offset ty -> Array ty -> Offset ty -> CountOf ty -> prim ()
unsafeCopyAtRO MArray ty (PrimState f)
mua (forall a. CountOf a -> Offset a
sizeAsOffset CountOf ty
start) Array ty
x (forall ty. Int -> Offset ty
Offset Int
0) CountOf ty
sz
        CountOf ty
-> [Array ty]
-> MArray ty (PrimState f)
-> f (MArray ty (PrimState f))
fillFromEnd CountOf ty
start [Array ty]
xs MArray ty (PrimState f)
mua

builderBuild_ :: PrimMonad m => Int -> Builder (Array ty) (MArray ty) ty m () () -> m (Array ty)
builderBuild_ :: forall (m :: * -> *) ty.
PrimMonad m =>
Int -> Builder (Array ty) (MArray ty) ty m () () -> m (Array ty)
builderBuild_ Int
sizeChunksI Builder (Array ty) (MArray ty) ty m () ()
ab = forall a c b. (a -> c) -> (b -> c) -> Either a b -> c
either (\() -> forall a. [Char] -> a
internalError [Char]
"impossible output") forall {k} (cat :: k -> k -> *) (a :: k). Category cat => cat a a
id forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall (m :: * -> *) ty err.
PrimMonad m =>
Int
-> Builder (Array ty) (MArray ty) ty m err ()
-> m (Either err (Array ty))
builderBuild Int
sizeChunksI Builder (Array ty) (MArray ty) ty m () ()
ab