-- |
-- 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
_   = [Char] -> Constr
forall a. HasCallStack => [Char] -> a
error [Char]
"toConstr"
    gunfold :: (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
_  = [Char] -> Constr -> c (Array ty)
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 = 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 -> () -> ()
`seq` Offset a -> ()
loop (Offset a
iOffset a -> Offset a -> Offset a
forall 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 :: (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
    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 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 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 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 :: 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 :: Array ty -> Offset ty -> ty
index Array ty
array 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 Offset ty
start CountOf ty
_ Array# ty
a) 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 MArray ty (PrimState prim)
array 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 Offset ty
start CountOf ty
_ MutableArray# (PrimState prim) ty
ma) 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 MArray ty (PrimState prim)
array Offset ty
n 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 Offset ty
start CountOf ty
_ MutableArray# (PrimState prim) ty
ma) Offset ty
ofs 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 Offset ty
ofs CountOf ty
sz 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
$ \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
        (# State# (PrimState prim)
s2, 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 Offset ty
ofs CountOf ty
sz 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
$ \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 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 Int
0) Array ty
array (Int -> Offset ty
forall ty. Int -> Offset ty
Offset Int
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 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 Int
0) MArray ty (PrimState prim)
marray (Int -> Offset ty
forall ty. Int -> Offset ty
Offset Int
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 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 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 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
+Offset ty
1) (Offset ty
sOffset ty -> Offset ty -> Offset ty
forall 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 :: 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)) =
    (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
$ \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 Array ty
v' CountOf ty
newLen 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 Int
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 Int
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 Offset ty
i Array ty -> Offset ty -> MArray ty s -> ST s ()
f' 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 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 :: CountOf ty -> prim (MArray ty (PrimState prim))
new sz :: CountOf ty
sz@(CountOf (I# 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
$ \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 [Char]
"vector: internal error uninitialized vector") State# (PrimState prim)
s1 of
        (# State# (PrimState prim)
s2, 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 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 :: CountOf ty -> (Offset ty -> ty) -> Array ty
create CountOf ty
n 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 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 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
+Offset ty
1)
        {-# INLINE loop #-}
    {-# INLINE iter #-}

-----------------------------------------------------------------------
-- higher level collection implementation
-----------------------------------------------------------------------
equal :: Eq a => Array a -> Array a -> Bool
equal :: Array a -> Array a -> Bool
equal Array a
a 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 Offset a
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 = Bool
False
        | Bool
otherwise                          = Offset a -> Bool
eachEqual (Offset a
iOffset a -> Offset a -> Offset a
forall a. Additive a => a -> a -> a
+Offset a
1)

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

empty :: Array a
empty :: Array a
empty = (forall s. ST s (Array a)) -> Array a
forall a. (forall s. ST s a) -> a
runST ((forall s. ST s (Array a)) -> Array a)
-> (forall s. ST s (Array a)) -> Array a
forall a b. (a -> b) -> a -> b
$ Int
-> (MutableArray# (PrimState (ST s)) a
    -> State# (PrimState (ST s)) -> State# (PrimState (ST s)))
-> ST s (Array a)
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 :: Array a -> CountOf a
length (Array Offset a
_ CountOf a
sz Array# a
_) = CountOf a
sz

vFromList :: [a] -> Array a
vFromList :: [a] -> Array a
vFromList [a]
l = (forall s. ST s (Array a)) -> Array a
forall a. (forall s. ST s a) -> a
runST (CountOf a -> ST s (MArray a (PrimState (ST s)))
forall (prim :: * -> *) ty.
PrimMonad prim =>
CountOf ty -> prim (MArray ty (PrimState prim))
new CountOf a
len ST s (MArray a s)
-> (MArray a s -> ST s (Array a)) -> ST s (Array a)
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= Offset a -> [a] -> MArray a (PrimState (ST s)) -> ST s (Array a)
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 = [a] -> CountOf a
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 = 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
    loop Offset ty
i (ty
x:[ty]
xs) MArray ty (PrimState prim)
ma = 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
i ty
x prim () -> prim (Array ty) -> prim (Array ty)
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
iOffset ty -> Offset ty -> Offset ty
forall 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 :: CountOf a -> [a] -> Array a
vFromListN CountOf a
len [a]
l = (forall s. ST s (Array a)) -> Array a
forall a. (forall s. ST s a) -> a
runST ((forall s. ST s (Array a)) -> Array a)
-> (forall s. ST s (Array a)) -> Array a
forall a b. (a -> b) -> a -> b
$ do
    MArray a s
ma <- CountOf a -> ST s (MArray a (PrimState (ST s)))
forall (prim :: * -> *) ty.
PrimMonad prim =>
CountOf ty -> prim (MArray ty (PrimState prim))
new CountOf a
len
    CountOf a
sz <- Offset a -> [a] -> MArray a s -> ST s (CountOf a)
forall s. Offset a -> [a] -> MArray a s -> ST s (CountOf a)
loop Offset a
0 [a]
l MArray a s
ma
    MArray a (PrimState (ST s)) -> CountOf a -> ST s (Array a)
forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> CountOf ty -> prim (Array ty)
unsafeFreezeShrink MArray a s
MArray a (PrimState (ST s))
ma CountOf a
sz
  where
    -- TODO rewrite without ma as parameter
    loop :: Offset a -> [a] -> MArray a s -> ST s (CountOf a)
    loop :: Offset a -> [a] -> MArray a s -> ST s (CountOf a)
loop Offset a
i []     MArray a s
_  = CountOf a -> ST s (CountOf a)
forall (m :: * -> *) a. Monad m => a -> m a
return (Offset a -> CountOf a
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 Offset a -> CountOf a -> Bool
forall ty. Offset ty -> CountOf ty -> Bool
.==# CountOf a
len = CountOf a -> ST s (CountOf a)
forall (m :: * -> *) a. Monad m => a -> m a
return (Offset a -> CountOf a
forall a. Offset a -> CountOf a
offsetAsSize Offset a
i)
        | Bool
otherwise  = MArray a (PrimState (ST s)) -> Offset a -> a -> ST s ()
forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> Offset ty -> ty -> prim ()
unsafeWrite MArray a s
MArray a (PrimState (ST s))
ma Offset a
i a
x ST s () -> ST s (CountOf a) -> ST s (CountOf a)
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> Offset a -> [a] -> MArray a s -> ST s (CountOf a)
forall s. Offset a -> [a] -> MArray a s -> ST s (CountOf a)
loop (Offset a
iOffset a -> Offset a -> Offset a
forall a. Additive a => a -> a -> a
+Offset a
1) [a]
xs MArray a s
ma

vToList :: Array a -> [a]
vToList :: Array a -> [a]
vToList Array a
v
    | CountOf a
len CountOf a -> CountOf a -> Bool
forall a. Eq a => a -> a -> Bool
== CountOf a
0  = []
    | Bool
otherwise = (Offset a -> a) -> [Offset a] -> [a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Array a -> Offset a -> a
forall ty. Array ty -> Offset ty -> ty
unsafeIndex Array a
v) [Offset a
0..CountOf a -> Offset a
forall a. CountOf a -> Offset a
sizeLastOffset CountOf a
len]
  where !len :: CountOf a
len = Array a -> CountOf a
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 :: Array ty -> Array ty -> Array ty
append Array ty
a Array ty
b = (forall s. ST s (Array ty)) -> Array ty
forall a. (forall s. ST s a) -> a
runST ((forall s. ST s (Array ty)) -> Array ty)
-> (forall s. ST s (Array ty)) -> Array ty
forall a b. (a -> b) -> a -> b
$ do
    MArray ty s
r  <- CountOf ty -> ST s (MArray ty (PrimState (ST s)))
forall (prim :: * -> *) ty.
PrimMonad prim =>
CountOf ty -> prim (MArray ty (PrimState prim))
new (CountOf ty
laCountOf ty -> CountOf ty -> CountOf ty
forall a. Additive a => a -> a -> a
+CountOf ty
lb)
    MArray ty (PrimState (ST s))
-> Offset ty -> Array ty -> Offset ty -> CountOf ty -> ST s ()
forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim)
-> Offset ty -> Array ty -> Offset ty -> CountOf ty -> prim ()
unsafeCopyAtRO MArray ty s
MArray ty (PrimState (ST s))
r (Int -> Offset ty
forall ty. Int -> Offset ty
Offset Int
0) Array ty
a (Int -> Offset ty
forall ty. Int -> Offset ty
Offset Int
0) CountOf ty
la
    MArray ty (PrimState (ST s))
-> Offset ty -> Array ty -> Offset ty -> CountOf ty -> ST s ()
forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim)
-> Offset ty -> Array ty -> Offset ty -> CountOf ty -> prim ()
unsafeCopyAtRO MArray ty s
MArray ty (PrimState (ST s))
r (CountOf ty -> Offset ty
forall a. CountOf a -> Offset a
sizeAsOffset CountOf ty
la) Array ty
b (Int -> Offset ty
forall ty. Int -> Offset ty
Offset Int
0) CountOf ty
lb
    MArray ty (PrimState (ST s)) -> ST s (Array ty)
forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> prim (Array ty)
unsafeFreeze MArray ty s
MArray ty (PrimState (ST s))
r
  where la :: CountOf ty
la = Array ty -> CountOf ty
forall a. Array a -> CountOf a
length Array ty
a
        lb :: CountOf ty
lb = Array ty -> CountOf ty
forall a. Array a -> CountOf a
length Array ty
b

concat :: [Array ty] -> Array ty
concat :: [Array ty] -> Array ty
concat [Array ty]
l = (forall s. ST s (Array ty)) -> Array ty
forall a. (forall s. ST s a) -> a
runST ((forall s. ST s (Array ty)) -> Array ty)
-> (forall s. ST s (Array ty)) -> Array ty
forall a b. (a -> b) -> a -> b
$ do
    MArray ty s
r <- CountOf ty -> ST s (MArray ty (PrimState (ST s)))
forall (prim :: * -> *) ty.
PrimMonad prim =>
CountOf ty -> prim (MArray ty (PrimState prim))
new ([CountOf ty] -> CountOf ty
forall a. Monoid a => [a] -> a
mconcat ([CountOf ty] -> CountOf ty) -> [CountOf ty] -> CountOf ty
forall a b. (a -> b) -> a -> b
$ (Array ty -> CountOf ty) -> [Array ty] -> [CountOf ty]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Array ty -> CountOf ty
forall a. Array a -> CountOf a
length [Array ty]
l)
    MArray ty (PrimState (ST s)) -> Offset ty -> [Array ty] -> ST s ()
forall (f :: * -> *) ty.
PrimMonad f =>
MArray ty (PrimState f) -> Offset ty -> [Array ty] -> f ()
loop MArray ty s
MArray ty (PrimState (ST s))
r (Int -> Offset ty
forall ty. Int -> Offset ty
Offset Int
0) [Array ty]
l
    MArray ty (PrimState (ST s)) -> ST s (Array ty)
forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> prim (Array ty)
unsafeFreeze MArray ty s
MArray ty (PrimState (ST s))
r
  where loop :: MArray ty (PrimState f) -> Offset ty -> [Array ty] -> f ()
loop MArray ty (PrimState f)
_ Offset ty
_ []     = () -> f ()
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
            MArray ty (PrimState f)
-> Offset ty -> Array ty -> Offset ty -> CountOf ty -> f ()
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 (Int -> Offset ty
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 Offset ty -> CountOf ty -> Offset ty
forall ty. Offset ty -> CountOf ty -> Offset ty
`offsetPlusE` CountOf ty
lx) [Array ty]
xs
          where lx :: CountOf ty
lx = Array ty -> CountOf ty
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 :: 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 = (State# (PrimState m) -> (# State# (PrimState m), Array a #))
-> m (Array a)
forall (m :: * -> *) a.
PrimMonad m =>
(State# (PrimState m) -> (# State# (PrimState m), a #)) -> m a
primitive ((State# (PrimState m) -> (# State# (PrimState m), Array a #))
 -> m (Array a))
-> (State# (PrimState m) -> (# State# (PrimState m), Array a #))
-> m (Array a)
forall a b. (a -> b) -> a -> b
$ \State# (PrimState m)
st -> do
    case Int#
-> a
-> State# (PrimState m)
-> (# State# (PrimState m), MutableArray# (PrimState m) a #)
forall a d.
Int# -> a -> State# d -> (# State# d, MutableArray# d a #)
newArray# Int#
len# ([Char] -> a
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 MutableArray# (PrimState m) a
-> State# (PrimState m) -> (# State# (PrimState m), Array# a #)
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, Offset a -> CountOf a -> Array# a -> Array a
forall a. Offset a -> CountOf a -> Array# a -> Array a
Array (Int -> Offset a
forall ty. Int -> Offset ty
Offset Int
0) (Int -> CountOf a
forall ty. Int -> CountOf ty
CountOf Int
len) Array# a
a #) }}}

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


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

take :: CountOf ty -> Array ty -> Array ty
take :: 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 CountOf ty -> CountOf ty -> Bool
forall a. Ord a => a -> a -> Bool
<= CountOf ty
0 = Array ty
forall a. Array a
empty
    | CountOf ty
n CountOf ty -> CountOf ty -> Bool
forall a. Eq a => a -> a -> Bool
== CountOf ty
len     = Array ty
a
    | Bool
otherwise    = Offset ty -> CountOf ty -> Array# ty -> Array ty
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 = CountOf ty -> CountOf ty -> CountOf ty
forall a. Ord a => a -> a -> a
min CountOf ty
nbElems CountOf ty
len

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

splitAt :: CountOf ty -> Array ty -> (Array ty, Array ty)
splitAt :: 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 CountOf ty -> CountOf ty -> Bool
forall a. Ord a => a -> a -> Bool
<= CountOf ty
0 = (Array ty
forall a. Array a
empty, Array ty
a)
    | Just nbTails <- CountOf ty
len CountOf ty -> CountOf ty -> Difference (CountOf ty)
forall a. Subtractive a => a -> a -> Difference a
- CountOf ty
nbElems, CountOf ty
nbTails CountOf ty -> CountOf ty -> Bool
forall a. Ord a => a -> a -> Bool
> CountOf ty
0 = ( Offset ty -> CountOf ty -> Array# ty -> Array ty
forall a. Offset a -> CountOf a -> Array# a -> Array a
Array Offset ty
start                         CountOf ty
nbElems Array# ty
arr
                                                   , Offset ty -> CountOf ty -> Array# ty -> Array ty
forall a. Offset a -> CountOf a -> Array# a -> Array a
Array (Offset ty
start Offset ty -> CountOf ty -> Offset ty
forall ty. Offset ty -> CountOf ty -> Offset ty
`offsetPlusE` CountOf ty
nbElems) CountOf ty
nbTails Array# ty
arr)
    | Bool
otherwise = (Array ty
a, Array ty
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 :: Array ty -> CountOf ty -> CountOf ty
countFromStart Array ty
v sz :: CountOf ty
sz@(CountOf Int
sz')
    | CountOf ty
sz CountOf ty -> CountOf ty -> Bool
forall a. Ord a => a -> a -> Bool
>= CountOf ty
len = Int -> CountOf ty
forall ty. Int -> CountOf ty
CountOf Int
0
    | Bool
otherwise = Int -> CountOf ty
forall ty. Int -> CountOf ty
CountOf (Int
len' Int -> Int -> Difference Int
forall a. Subtractive a => a -> a -> Difference a
- Int
sz')
  where len :: CountOf ty
len@(CountOf Int
len') = Array ty -> CountOf ty
forall a. Array a -> CountOf a
length Array ty
v

revTake :: CountOf ty -> Array ty -> Array ty
revTake :: CountOf ty -> Array ty -> Array ty
revTake CountOf ty
n Array ty
v = CountOf ty -> Array ty -> Array ty
forall ty. CountOf ty -> Array ty -> Array ty
drop (Array ty -> CountOf ty -> CountOf ty
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 :: CountOf ty -> Array ty -> Array ty
revDrop CountOf ty
n Array ty
v = CountOf ty -> Array ty -> Array ty
forall ty. CountOf ty -> Array ty -> Array ty
take (Array ty -> CountOf ty -> CountOf ty
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 :: CountOf ty -> Array ty -> (Array ty, Array ty)
revSplitAt CountOf ty
n Array ty
v = (CountOf ty -> Array ty -> Array ty
forall ty. CountOf ty -> Array ty -> Array ty
drop CountOf ty
idx Array ty
v, CountOf ty -> Array ty -> Array ty
forall ty. CountOf ty -> Array ty -> Array ty
take CountOf ty
idx Array ty
v) where idx :: CountOf ty
idx = Array ty -> CountOf ty -> CountOf ty
forall ty. Array ty -> CountOf ty -> CountOf ty
countFromStart Array ty
v CountOf ty
n

splitOn ::  (ty -> Bool) -> Array ty -> [Array ty]
splitOn :: (ty -> Bool) -> Array ty -> [Array ty]
splitOn ty -> Bool
predicate Array ty
vec
    | CountOf ty
len CountOf ty -> CountOf ty -> Bool
forall a. Eq a => a -> a -> Bool
== Int -> CountOf ty
forall ty. Int -> CountOf ty
CountOf Int
0 = [Array ty
forall a. Monoid a => a
mempty]
    | Bool
otherwise     = Offset ty -> Offset ty -> [Array ty]
loop (Int -> Offset ty
forall ty. Int -> Offset ty
Offset Int
0) (Int -> Offset ty
forall ty. Int -> Offset ty
Offset Int
0)
  where
    !len :: CountOf ty
len = Array ty -> CountOf ty
forall a. Array a -> CountOf a
length Array ty
vec
    !endIdx :: Offset ty
endIdx = Int -> Offset ty
forall ty. Int -> Offset ty
Offset Int
0 Offset ty -> CountOf ty -> Offset ty
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 Offset ty -> Offset ty -> Bool
forall a. Eq a => a -> a -> Bool
== Offset ty
endIdx = [Array ty -> Offset ty -> Offset ty -> Array ty
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 = Array ty -> Offset ty -> ty
forall ty. Array ty -> Offset ty -> ty
unsafeIndex Array ty
vec Offset ty
idx
                idx' :: Offset ty
idx' = Offset ty
idx Offset ty -> Offset ty -> Offset ty
forall a. Additive a => a -> a -> a
+ Offset ty
1
             in if ty -> Bool
predicate ty
e
                    then Array ty -> Offset ty -> Offset ty -> Array ty
forall ty. Array ty -> Offset ty -> Offset ty -> Array ty
sub Array ty
vec Offset ty
prevIdx Offset ty
idx Array ty -> [Array ty] -> [Array ty]
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 :: 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 Offset ty -> Offset ty -> Bool
forall a. Eq a => a -> a -> Bool
== Offset ty
endIdx           = Array ty
forall a. Array a
empty
    | Bool
otherwise                    = Offset ty -> CountOf ty -> Array# ty -> Array ty
forall a. Offset a -> CountOf a -> Array# a -> Array a
Array (Offset ty
start Offset ty -> Offset ty -> Offset ty
forall a. Additive a => a -> a -> a
+ Offset ty
startIdx) Difference (Offset ty)
CountOf ty
newLen Array# ty
a
  where
    newLen :: Difference (Offset ty)
newLen = Offset ty
endIdx Offset ty -> Offset ty -> Difference (Offset ty)
forall a. Subtractive a => a -> a -> Difference a
- Offset ty
startIdx
    endIdx :: Offset ty
endIdx = Offset ty -> Offset ty -> Offset ty
forall a. Ord a => a -> a -> a
min Offset ty
expectedEndIdx (CountOf ty -> Offset ty
forall a. CountOf a -> Offset a
sizeAsOffset CountOf ty
len)

break ::  (ty -> Bool) -> Array ty -> (Array ty, Array ty)
break :: (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 = Array ty -> CountOf ty
forall a. Array a -> CountOf a
length Array ty
v
    findBreak :: Offset ty -> (Array ty, Array ty)
findBreak Offset ty
i
        | Offset ty
i Offset ty -> CountOf ty -> Bool
forall ty. Offset ty -> CountOf ty -> Bool
.==# CountOf ty
len  = (Array ty
v, Array ty
forall a. Array a
empty)
        | Bool
otherwise   =
            if ty -> Bool
predicate (Array ty -> Offset ty -> ty
forall ty. Array ty -> Offset ty -> ty
unsafeIndex Array ty
v Offset ty
i)
                then CountOf ty -> Array ty -> (Array ty, Array ty)
forall ty. CountOf ty -> Array ty -> (Array ty, Array ty)
splitAt (Offset ty -> CountOf ty
forall a. Offset a -> CountOf a
offsetAsSize Offset ty
i) Array ty
v
                else Offset ty -> (Array ty, Array ty)
findBreak (Offset ty
iOffset ty -> Offset ty -> Offset ty
forall a. Additive a => a -> a -> a
+Offset ty
1)

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

intersperse :: ty -> Array ty -> Array ty
intersperse :: ty -> Array ty -> Array ty
intersperse ty
sep Array ty
v = case CountOf ty
len CountOf ty -> CountOf ty -> Difference (CountOf ty)
forall a. Subtractive a => a -> a -> Difference a
- CountOf ty
1 of
    Difference (CountOf ty)
Nothing -> Array ty
v
    Just 0 -> Array ty
v
    Just more -> (forall s. ST s (Array ty)) -> Array ty
forall a. (forall s. ST s a) -> a
runST ((forall s. ST s (Array ty)) -> Array ty)
-> (forall s. ST s (Array ty)) -> Array ty
forall a b. (a -> b) -> a -> b
$ Array ty
-> CountOf ty
-> (Array ty -> Offset ty -> MArray ty s -> ST s ())
-> ST s (Array ty)
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 CountOf ty -> CountOf ty -> CountOf ty
forall a. Additive a => a -> a -> a
+ CountOf ty
more) (Offset ty -> ty -> Array ty -> Offset ty -> MArray ty s -> ST s ()
forall ty s.
Offset ty -> ty -> Array ty -> Offset ty -> MArray ty s -> ST s ()
go (Int -> Offset ty
forall ty. Int -> Offset ty
Offset Int
0 Offset ty -> CountOf ty -> Offset ty
forall ty. Offset ty -> CountOf ty -> Offset ty
`offsetPlusE` CountOf ty
more) ty
sep)
  where len :: CountOf ty
len = Array ty -> CountOf ty
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 :: 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 Offset ty -> Offset ty -> Bool
forall a. Eq a => a -> a -> Bool
== Offset ty
endI = MArray ty (PrimState (ST s)) -> Offset ty -> ty -> ST s ()
forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> Offset ty -> ty -> prim ()
unsafeWrite MArray ty s
MArray ty (PrimState (ST s))
newV Offset ty
dst ty
e
            | Bool
otherwise    = do
                MArray ty (PrimState (ST s)) -> Offset ty -> ty -> ST s ()
forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> Offset ty -> ty -> prim ()
unsafeWrite MArray ty s
MArray ty (PrimState (ST s))
newV Offset ty
dst ty
e
                MArray ty (PrimState (ST s)) -> Offset ty -> ty -> ST s ()
forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> Offset ty -> ty -> prim ()
unsafeWrite MArray ty s
MArray ty (PrimState (ST s))
newV (Offset ty
dst Offset ty -> Offset ty -> Offset ty
forall a. Additive a => a -> a -> a
+ Offset ty
1) ty
sep'
          where
            e :: ty
e = Array ty -> Offset ty -> ty
forall ty. Array ty -> Offset ty -> ty
unsafeIndex Array ty
oldV Offset ty
oldI
            dst :: Offset ty
dst = Offset ty
oldI Offset ty -> Offset ty -> Offset ty
forall a. Additive a => a -> a -> a
+ Offset ty
oldI

span ::  (ty -> Bool) -> Array ty -> (Array ty, Array ty)
span :: (ty -> Bool) -> Array ty -> (Array ty, Array ty)
span ty -> Bool
p = (ty -> Bool) -> Array ty -> (Array ty, Array ty)
forall ty. (ty -> Bool) -> Array ty -> (Array ty, Array ty)
break (Bool -> Bool
not (Bool -> Bool) -> (ty -> Bool) -> ty -> Bool
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 :: (ty -> Bool) -> Array ty -> (Array ty, Array ty)
spanEnd ty -> Bool
p = (ty -> Bool) -> Array ty -> (Array ty, Array ty)
forall ty. (ty -> Bool) -> Array ty -> (Array ty, Array ty)
breakEnd (Bool -> Bool
not (Bool -> Bool) -> (ty -> Bool) -> ty -> Bool
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 :: (a -> b) -> Array a -> Array b
map a -> b
f Array a
a = CountOf b -> (Offset b -> b) -> Array b
forall ty. CountOf ty -> (Offset ty -> ty) -> Array ty
create (Proxy (a -> b) -> CountOf a -> CountOf b
forall a b. Proxy (a -> b) -> CountOf a -> CountOf b
sizeCast Proxy (a -> b)
forall k (t :: k). Proxy t
Proxy (CountOf a -> CountOf b) -> CountOf a -> CountOf b
forall a b. (a -> b) -> a -> b
$ Array a -> CountOf a
forall a. Array a -> CountOf a
length Array a
a) (\Offset b
i -> a -> b
f (a -> b) -> a -> b
forall a b. (a -> b) -> a -> b
$ Array a -> Offset a -> a
forall ty. Array ty -> Offset ty -> ty
unsafeIndex Array a
a (Proxy (b -> a) -> Offset b -> Offset a
forall a b. Proxy (a -> b) -> Offset a -> Offset b
offsetCast Proxy (b -> a)
forall k (t :: k). Proxy t
Proxy Offset b
i))

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

mapToUnboxed :: PrimType b => (a -> b) -> Array a -> UArray b
mapToUnboxed :: (a -> b) -> Array a -> UArray b
mapToUnboxed a -> b
f Array a
arr = CountOf b -> [b] -> UArray b
forall ty. PrimType ty => CountOf ty -> [ty] -> UArray ty
UArray.vFromListN (Proxy (a -> b) -> CountOf a -> CountOf b
forall a b. Proxy (a -> b) -> CountOf a -> CountOf b
sizeCast Proxy (a -> b)
forall k (t :: k). Proxy t
Proxy (CountOf a -> CountOf b) -> CountOf a -> CountOf b
forall a b. (a -> b) -> a -> b
$ Array a -> CountOf a
forall a. Array a -> CountOf a
length Array a
arr) ([b] -> UArray b) -> (Array a -> [b]) -> Array a -> UArray b
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. (a -> b) -> [a] -> [b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> b
f ([a] -> [b]) -> (Array a -> [a]) -> Array a -> [b]
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. Array a -> [a]
forall l. IsList l => l -> [Item l]
toList (Array a -> UArray b) -> Array a -> UArray b
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 :: ty -> Array ty
singleton ty
e = (forall s. ST s (Array ty)) -> Array ty
forall a. (forall s. ST s a) -> a
runST ((forall s. ST s (Array ty)) -> Array ty)
-> (forall s. ST s (Array ty)) -> Array ty
forall a b. (a -> b) -> a -> b
$ do
    MArray ty s
a <- CountOf ty -> ST s (MArray ty (PrimState (ST s)))
forall (prim :: * -> *) ty.
PrimMonad prim =>
CountOf ty -> prim (MArray ty (PrimState prim))
new CountOf ty
1
    MArray ty (PrimState (ST s)) -> Offset ty -> ty -> ST s ()
forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> Offset ty -> ty -> prim ()
unsafeWrite MArray ty s
MArray ty (PrimState (ST s))
a Offset ty
0 ty
e
    MArray ty (PrimState (ST s)) -> ST s (Array ty)
forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> prim (Array ty)
unsafeFreeze MArray ty s
MArray ty (PrimState (ST s))
a

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

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

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

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

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

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

find :: (ty -> Bool) -> Array ty -> Maybe ty
find :: (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 = Array ty -> CountOf ty
forall a. Array a -> CountOf a
length Array ty
vec
    loop :: Offset ty -> Maybe ty
loop Offset ty
i
        | Offset ty
i Offset ty -> CountOf ty -> Bool
forall ty. Offset ty -> CountOf ty -> Bool
.==# CountOf ty
len = Maybe ty
forall a. Maybe a
Nothing
        | Bool
otherwise  =
            let e :: ty
e = Array ty -> Offset ty -> ty
forall ty. Array ty -> Offset ty -> ty
unsafeIndex Array ty
vec Offset ty
i
             in if ty -> Bool
predicate ty
e then ty -> Maybe ty
forall a. a -> Maybe a
Just ty
e else Offset ty -> Maybe ty
loop (Offset ty
iOffset ty -> Offset ty -> Offset ty
forall 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) = MutableArray# (PrimState prim) ty -> Offset ty -> prim ty
forall (prim :: * -> *) ty.
PrimMonad prim =>
MutableArray# (PrimState prim) ty -> Offset ty -> prim ty
primMutableArrayRead MutableArray# st ty
MutableArray# (PrimState prim) ty
mba
    write :: MArray ty st -> Offset ty -> ty -> prim ()
write (MArray Offset ty
_ CountOf ty
_ MutableArray# st ty
mba) = MutableArray# (PrimState prim) ty -> Offset ty -> ty -> prim ()
forall (prim :: * -> *) ty.
PrimMonad prim =>
MutableArray# (PrimState prim) ty -> Offset ty -> ty -> prim ()
primMutableArrayWrite MutableArray# st ty
MutableArray# (PrimState prim) ty
mba

sortBy :: forall ty . (ty -> ty -> Ordering) -> Array ty -> Array ty
sortBy :: (ty -> ty -> Ordering) -> Array ty -> Array ty
sortBy ty -> ty -> Ordering
xford Array ty
vec
    | CountOf ty
len CountOf ty -> CountOf ty -> Bool
forall a. Eq a => a -> a -> Bool
== CountOf ty
0  = Array ty
forall a. Array a
empty
    | Bool
otherwise = (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))
thaw Array ty
vec 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
>>= (ty -> ty -> Ordering)
-> MArray ty (PrimState (ST s)) -> ST s (Array ty)
forall (prim :: * -> *).
PrimMonad prim =>
(ty -> ty -> Ordering)
-> MArray ty (PrimState prim) -> prim (Array ty)
doSort ty -> ty -> Ordering
xford)
  where
    len :: CountOf ty
len = Array ty -> CountOf ty
forall a. Array a -> CountOf a
length Array ty
vec
    doSort :: PrimMonad prim => (ty -> ty -> Ordering) -> MArray ty (PrimState prim) -> prim (Array ty)
    doSort :: (ty -> ty -> Ordering)
-> MArray ty (PrimState prim) -> prim (Array ty)
doSort ty -> ty -> Ordering
ford MArray ty (PrimState prim)
ma = (ty -> ty -> Ordering)
-> Offset ty -> CountOf ty -> MArray ty (PrimState prim) -> prim ()
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 prim () -> prim (Array ty) -> prim (Array ty)
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> 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

filter :: forall ty . (ty -> Bool) -> Array ty -> Array ty
filter :: (ty -> Bool) -> Array ty -> Array ty
filter ty -> Bool
predicate Array ty
vec = (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
len 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
>>= (ty -> Bool)
-> (Offset ty -> ty)
-> MArray ty (PrimState (ST s))
-> ST s (Array ty)
forall (prim :: * -> *).
PrimMonad prim =>
(ty -> Bool)
-> (Offset ty -> ty)
-> MArray ty (PrimState prim)
-> prim (Array ty)
copyFilterFreeze ty -> Bool
predicate (Array ty -> Offset ty -> ty
forall ty. Array ty -> Offset ty -> ty
unsafeIndex Array ty
vec))
  where
    !len :: CountOf ty
len = Array ty -> CountOf ty
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 :: (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 (Int -> Offset ty
forall ty. Int -> Offset ty
Offset Int
0) (Int -> Offset ty
forall ty. Int -> Offset ty
Offset Int
0) prim (Offset ty)
-> (Offset ty -> prim (Array ty)) -> prim (Array ty)
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= MArray ty (PrimState prim) -> Offset ty -> prim (Array ty)
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 Offset ty -> CountOf ty -> Bool
forall ty. Offset ty -> CountOf ty -> Bool
.==# CountOf ty
len  = Offset ty -> prim (Offset ty)
forall (f :: * -> *) a. Applicative f => a -> f a
pure Offset ty
d
            | ty -> Bool
predi ty
v     = 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)
mvec Offset ty
d ty
v prim () -> prim (Offset ty) -> prim (Offset ty)
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> Offset ty -> Offset ty -> prim (Offset ty)
loop (Offset ty
dOffset ty -> Offset ty -> Offset ty
forall a. Additive a => a -> a -> a
+Offset ty
1) (Offset ty
sOffset ty -> Offset ty -> Offset ty
forall a. Additive a => a -> a -> a
+Offset ty
1)
            | Bool
otherwise   = Offset ty -> Offset ty -> prim (Offset ty)
loop Offset ty
d (Offset ty
sOffset ty -> Offset ty -> Offset ty
forall 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 :: MArray ty (PrimState prim) -> Offset ty -> prim (Array ty)
freezeUntilIndex MArray ty (PrimState prim)
mvec Offset ty
d = 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 (Offset ty -> CountOf ty
forall a. Offset a -> CountOf a
offsetAsSize Offset ty
d)
    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 Int
0) MArray ty (PrimState prim)
mvec (Int -> Offset ty
forall ty. Int -> Offset ty
Offset Int
0) (Offset ty -> CountOf ty
forall a. Offset a -> CountOf a
offsetAsSize Offset ty
d)
    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

unsafeFreezeShrink :: PrimMonad prim => MArray ty (PrimState prim) -> CountOf ty -> prim (Array ty)
unsafeFreezeShrink :: MArray ty (PrimState prim) -> CountOf ty -> prim (Array ty)
unsafeFreezeShrink (MArray Offset ty
start CountOf ty
_ MutableArray# (PrimState prim) ty
ma) CountOf ty
n = MArray ty (PrimState prim) -> prim (Array ty)
forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> prim (Array ty)
unsafeFreeze (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
start CountOf ty
n MutableArray# (PrimState prim) ty
ma)

reverse :: Array ty -> Array ty
reverse :: Array ty -> Array ty
reverse Array ty
a = CountOf ty -> (Offset ty -> ty) -> Array ty
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) = Array ty -> CountOf ty
forall a. Array a -> CountOf a
length Array ty
a
    toEnd :: Offset ty -> ty
toEnd (Offset Int
i) = Array ty -> Offset ty -> ty
forall ty. Array ty -> Offset ty -> ty
unsafeIndex Array ty
a (Int -> Offset ty
forall ty. Int -> Offset ty
Offset (Int
s Int -> Int -> Difference Int
forall a. Subtractive a => a -> a -> Difference a
- Int
1 Int -> Int -> Difference Int
forall a. Subtractive a => a -> a -> Difference a
- Int
i))

foldr :: (ty -> a -> a) -> a -> Array ty -> a
foldr :: (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 = Array ty -> CountOf ty
forall a. Array a -> CountOf a
length Array ty
vec
    loop :: Offset ty -> a
loop !Offset ty
i
        | Offset ty
i Offset ty -> CountOf ty -> Bool
forall ty. Offset ty -> CountOf ty -> Bool
.==# CountOf ty
len = a
initialAcc
        | Bool
otherwise  = Array ty -> Offset ty -> ty
forall ty. Array ty -> Offset ty -> ty
unsafeIndex Array ty
vec Offset ty
i ty -> a -> a
`f` Offset ty -> a
loop (Offset ty
iOffset ty -> Offset ty -> Offset ty
forall a. Additive a => a -> a -> a
+Offset ty
1)

foldl' :: (a -> ty -> a) -> a -> Array ty -> a
foldl' :: (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 = Array ty -> CountOf ty
forall a. Array a -> CountOf a
length Array ty
vec
    loop :: Offset ty -> a -> a
loop !Offset ty
i !a
acc
        | Offset ty
i Offset ty -> CountOf ty -> Bool
forall ty. Offset ty -> CountOf ty -> Bool
.==# CountOf ty
len = a
acc
        | Bool
otherwise  = Offset ty -> a -> a
loop (Offset ty
iOffset ty -> Offset ty -> Offset ty
forall a. Additive a => a -> a -> a
+Offset ty
1) (a -> ty -> a
f a
acc (Array ty -> Offset ty -> ty
forall ty. Array ty -> Offset ty -> ty
unsafeIndex Array ty
vec Offset ty
i))

foldl1' :: (ty -> ty -> ty) -> NonEmpty (Array ty) -> ty
foldl1' :: (ty -> ty -> ty) -> NonEmpty (Array ty) -> ty
foldl1' ty -> ty -> ty
f NonEmpty (Array ty)
arr = let (Array ty
initialAcc, Array ty
rest) = CountOf ty -> Array ty -> (Array ty, Array ty)
forall ty. CountOf ty -> Array ty -> (Array ty, Array ty)
splitAt CountOf ty
1 (Array ty -> (Array ty, Array ty))
-> Array ty -> (Array ty, Array ty)
forall a b. (a -> b) -> a -> b
$ NonEmpty (Array ty) -> Array ty
forall a. NonEmpty a -> a
getNonEmpty NonEmpty (Array ty)
arr
               in (ty -> ty -> ty) -> ty -> Array ty -> ty
forall a ty. (a -> ty -> a) -> a -> Array ty -> a
foldl' ty -> ty -> ty
f (Array ty -> Offset ty -> ty
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 :: (ty -> ty -> ty) -> NonEmpty (Array ty) -> ty
foldr1 ty -> ty -> ty
f NonEmpty (Array ty)
arr = let (Array ty
initialAcc, Array ty
rest) = CountOf ty -> Array ty -> (Array ty, Array ty)
forall ty. CountOf ty -> Array ty -> (Array ty, Array ty)
revSplitAt CountOf ty
1 (Array ty -> (Array ty, Array ty))
-> Array ty -> (Array ty, Array ty)
forall a b. (a -> b) -> a -> b
$ NonEmpty (Array ty) -> Array ty
forall a. NonEmpty a -> a
getNonEmpty NonEmpty (Array ty)
arr
               in (ty -> ty -> ty) -> ty -> Array ty -> ty
forall ty a. (ty -> a -> a) -> a -> Array ty -> a
foldr ty -> ty -> ty
f (Array ty -> Offset ty -> ty
forall ty. Array ty -> Offset ty -> ty
unsafeIndex Array ty
initialAcc Offset ty
0) Array ty
rest

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

any :: (ty -> Bool) -> Array ty -> Bool
any :: (ty -> Bool) -> Array ty -> Bool
any ty -> Bool
p Array ty
ba = Offset ty -> Bool
loop Offset ty
0
  where
    len :: CountOf ty
len = Array ty -> CountOf ty
forall a. Array a -> CountOf a
length Array ty
ba
    loop :: Offset ty -> Bool
loop !Offset ty
i
      | Offset ty
i Offset ty -> CountOf ty -> Bool
forall ty. Offset ty -> CountOf ty -> Bool
.==# CountOf ty
len = Bool
False
      | ty -> Bool
p (Array ty -> Offset ty -> ty
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 Offset ty -> Offset ty -> Offset ty
forall a. Additive a => a -> a -> a
+ Offset ty
1)

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

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

builderAppend :: PrimMonad state => ty -> Builder (Array ty) (MArray ty) ty state err ()
builderAppend :: ty -> Builder (Array ty) (MArray ty) ty state err ()
builderAppend ty
v = State
  (Offset ty,
   BuildingState (Array ty) (MArray ty) ty (PrimState state),
   Maybe err)
  state
  ()
-> Builder (Array ty) (MArray ty) ty state err ()
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 (State
   (Offset ty,
    BuildingState (Array ty) (MArray ty) ty (PrimState state),
    Maybe err)
   state
   ()
 -> Builder (Array ty) (MArray ty) ty state err ())
-> State
     (Offset ty,
      BuildingState (Array ty) (MArray ty) ty (PrimState state),
      Maybe err)
     state
     ()
-> Builder (Array ty) (MArray ty) ty state err ()
forall a b. (a -> b) -> a -> b
$ ((Offset ty,
  BuildingState (Array ty) (MArray ty) ty (PrimState state),
  Maybe err)
 -> state
      ((),
       (Offset ty,
        BuildingState (Array ty) (MArray ty) ty (PrimState state),
        Maybe err)))
-> State
     (Offset ty,
      BuildingState (Array ty) (MArray ty) ty (PrimState state),
      Maybe err)
     state
     ()
forall s (m :: * -> *) a. (s -> m (a, s)) -> State s m a
State (((Offset ty,
   BuildingState (Array ty) (MArray ty) ty (PrimState state),
   Maybe err)
  -> state
       ((),
        (Offset ty,
         BuildingState (Array ty) (MArray ty) ty (PrimState state),
         Maybe err)))
 -> State
      (Offset ty,
       BuildingState (Array ty) (MArray ty) ty (PrimState state),
       Maybe err)
      state
      ())
-> ((Offset ty,
     BuildingState (Array ty) (MArray ty) ty (PrimState state),
     Maybe err)
    -> state
         ((),
          (Offset ty,
           BuildingState (Array ty) (MArray ty) ty (PrimState state),
           Maybe err)))
-> State
     (Offset ty,
      BuildingState (Array ty) (MArray ty) ty (PrimState state),
      Maybe err)
     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 Offset ty -> CountOf ty -> Bool
forall ty. Offset ty -> CountOf ty -> Bool
.==# BuildingState (Array ty) (MArray ty) ty (PrimState state)
-> CountOf ty
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      <- MArray ty (PrimState state) -> state (Array ty)
forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> prim (Array ty)
unsafeFreeze (BuildingState (Array ty) (MArray ty) ty (PrimState state)
-> MArray ty (PrimState state)
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 <- CountOf ty -> state (MArray ty (PrimState state))
forall (prim :: * -> *) ty.
PrimMonad prim =>
CountOf ty -> prim (MArray ty (PrimState prim))
new (BuildingState (Array ty) (MArray ty) ty (PrimState state)
-> CountOf ty
forall collection (mutCollection :: * -> *) step state.
BuildingState collection mutCollection step state -> CountOf step
chunkSize BuildingState (Array ty) (MArray ty) ty (PrimState state)
st)
            MArray ty (PrimState state) -> Offset ty -> ty -> state ()
forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> Offset ty -> ty -> prim ()
unsafeWrite MArray ty (PrimState state)
newChunk Offset ty
0 ty
v
            ((),
 (Offset ty,
  BuildingState (Array ty) (MArray ty) ty (PrimState state),
  Maybe err))
-> state
     ((),
      (Offset ty,
       BuildingState (Array ty) (MArray ty) ty (PrimState state),
       Maybe err))
forall (f :: * -> *) a. Applicative f => a -> f a
pure ((), (Int -> Offset ty
forall ty. Int -> Offset ty
Offset Int
1, BuildingState (Array ty) (MArray ty) ty (PrimState state)
st { prevChunks :: [Array ty]
prevChunks     = Array ty
cur Array ty -> [Array ty] -> [Array ty]
forall a. a -> [a] -> [a]
: BuildingState (Array ty) (MArray ty) ty (PrimState state)
-> [Array ty]
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 = BuildingState (Array ty) (MArray ty) ty (PrimState state)
-> CountOf ty
forall collection (mutCollection :: * -> *) step state.
BuildingState collection mutCollection step state -> CountOf step
chunkSize BuildingState (Array ty) (MArray ty) ty (PrimState state)
st CountOf ty -> CountOf ty -> CountOf ty
forall a. Additive a => a -> a -> a
+ BuildingState (Array ty) (MArray ty) ty (PrimState state)
-> CountOf ty
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
            MArray ty (PrimState state) -> Offset ty -> ty -> state ()
forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> Offset ty -> ty -> prim ()
unsafeWrite (BuildingState (Array ty) (MArray ty) ty (PrimState state)
-> MArray ty (PrimState state)
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
            ((),
 (Offset ty,
  BuildingState (Array ty) (MArray ty) ty (PrimState state),
  Maybe err))
-> state
     ((),
      (Offset ty,
       BuildingState (Array ty) (MArray ty) ty (PrimState state),
       Maybe err))
forall (f :: * -> *) a. Applicative f => a -> f a
pure ((), (Offset ty
iOffset ty -> Offset ty -> Offset ty
forall 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 :: 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 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
0 = Int
-> Builder (Array ty) (MArray ty) ty m err ()
-> m (Either err (Array ty))
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      <- CountOf ty -> m (MArray ty (PrimState m))
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) <- ((),
 (Offset ty, BuildingState (Array ty) (MArray ty) ty (PrimState m),
  Maybe err))
-> (Offset ty,
    BuildingState (Array ty) (MArray ty) ty (PrimState m), Maybe err)
forall a b. (a, b) -> b
snd (((),
  (Offset ty, BuildingState (Array ty) (MArray ty) ty (PrimState m),
   Maybe err))
 -> (Offset ty,
     BuildingState (Array ty) (MArray ty) ty (PrimState m), Maybe err))
-> m ((),
      (Offset ty, BuildingState (Array ty) (MArray ty) ty (PrimState m),
       Maybe err))
-> m (Offset ty,
      BuildingState (Array ty) (MArray ty) ty (PrimState m), Maybe err)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> State
  (Offset ty, BuildingState (Array ty) (MArray ty) ty (PrimState m),
   Maybe err)
  m
  ()
-> (Offset ty,
    BuildingState (Array ty) (MArray ty) ty (PrimState m), Maybe err)
-> m ((),
      (Offset ty, BuildingState (Array ty) (MArray ty) ty (PrimState m),
       Maybe err))
forall s (m :: * -> *) a. State s m a -> s -> m (a, s)
runState (Builder (Array ty) (MArray ty) ty m err ()
-> State
     (Offset ty, BuildingState (Array ty) (MArray ty) ty (PrimState m),
      Maybe err)
     m
     ()
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) (Int -> Offset ty
forall ty. Int -> Offset ty
Offset Int
0, [Array ty]
-> CountOf ty
-> MArray ty (PrimState m)
-> CountOf ty
-> BuildingState (Array ty) (MArray ty) ty (PrimState m)
forall collection (mutCollection :: * -> *) step state.
[collection]
-> CountOf step
-> mutCollection state
-> CountOf step
-> BuildingState collection mutCollection step state
BuildingState [] (Int -> CountOf ty
forall ty. Int -> CountOf ty
CountOf Int
0) MArray ty (PrimState m)
first CountOf ty
sizeChunks, Maybe err
forall a. Maybe a
Nothing)
        case Maybe err
e of
          Just err
err -> Either err (Array ty) -> m (Either err (Array ty))
forall (f :: * -> *) a. Applicative f => a -> f a
pure (err -> Either err (Array ty)
forall a b. a -> Either a b
Left err
err)
          Maybe err
Nothing -> do
            Array ty
cur <- MArray ty (PrimState m) -> CountOf ty -> m (Array ty)
forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> CountOf ty -> prim (Array ty)
unsafeFreezeShrink (BuildingState (Array ty) (MArray ty) ty (PrimState m)
-> MArray ty (PrimState m)
forall collection (mutCollection :: * -> *) step state.
BuildingState collection mutCollection step state
-> mutCollection state
curChunk BuildingState (Array ty) (MArray ty) ty (PrimState m)
st) (Offset ty -> CountOf ty
forall a. Offset a -> CountOf a
offsetAsSize Offset ty
i)
            -- Build final array
            let totalSize :: CountOf ty
totalSize = BuildingState (Array ty) (MArray ty) ty (PrimState m) -> CountOf ty
forall collection (mutCollection :: * -> *) step state.
BuildingState collection mutCollection step state -> CountOf step
prevChunksSize BuildingState (Array ty) (MArray ty) ty (PrimState m)
st CountOf ty -> CountOf ty -> CountOf ty
forall a. Additive a => a -> a -> a
+ Offset ty -> CountOf ty
forall a. Offset a -> CountOf a
offsetAsSize Offset ty
i
            Array ty
bytes <- CountOf ty -> m (MArray ty (PrimState m))
forall (prim :: * -> *) ty.
PrimMonad prim =>
CountOf ty -> prim (MArray ty (PrimState prim))
new CountOf ty
totalSize m (MArray ty (PrimState m))
-> (MArray ty (PrimState m) -> m (MArray ty (PrimState m)))
-> m (MArray ty (PrimState m))
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= CountOf ty
-> [Array ty]
-> MArray ty (PrimState m)
-> m (MArray ty (PrimState m))
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 Array ty -> [Array ty] -> [Array ty]
forall a. a -> [a] -> [a]
: BuildingState (Array ty) (MArray ty) ty (PrimState m) -> [Array ty]
forall collection (mutCollection :: * -> *) step state.
BuildingState collection mutCollection step state -> [collection]
prevChunks BuildingState (Array ty) (MArray ty) ty (PrimState m)
st) m (MArray ty (PrimState m))
-> (MArray ty (PrimState m) -> m (Array ty)) -> m (Array ty)
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= MArray ty (PrimState m) -> m (Array ty)
forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim) -> prim (Array ty)
unsafeFreeze
            Either err (Array ty) -> m (Either err (Array ty))
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Array ty -> Either err (Array ty)
forall a b. b -> Either a b
Right Array ty
bytes)
  where
    sizeChunks :: CountOf ty
sizeChunks = Int -> CountOf ty
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 = MArray ty (PrimState f) -> f (MArray ty (PrimState f))
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 = Array ty -> CountOf ty
forall a. Array a -> CountOf a
length Array ty
x
        let start :: CountOf ty
start = CountOf ty
end CountOf ty -> CountOf ty -> CountOf ty
forall a. CountOf a -> CountOf a -> CountOf a
`sizeSub` CountOf ty
sz
        MArray ty (PrimState f)
-> Offset ty -> Array ty -> Offset ty -> CountOf ty -> f ()
forall (prim :: * -> *) ty.
PrimMonad prim =>
MArray ty (PrimState prim)
-> Offset ty -> Array ty -> Offset ty -> CountOf ty -> prim ()
unsafeCopyAtRO MArray ty (PrimState f)
mua (CountOf ty -> Offset ty
forall a. CountOf a -> Offset a
sizeAsOffset CountOf ty
start) Array ty
x (Int -> Offset ty
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_ :: Int -> Builder (Array ty) (MArray ty) ty m () () -> m (Array ty)
builderBuild_ Int
sizeChunksI Builder (Array ty) (MArray ty) ty m () ()
ab = (() -> Array ty)
-> (Array ty -> Array ty) -> Either () (Array ty) -> Array ty
forall a c b. (a -> c) -> (b -> c) -> Either a b -> c
either (\() -> [Char] -> Array ty
forall a. [Char] -> a
internalError [Char]
"impossible output") Array ty -> Array ty
forall k (cat :: k -> k -> *) (a :: k). Category cat => cat a a
id (Either () (Array ty) -> Array ty)
-> m (Either () (Array ty)) -> m (Array ty)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Int
-> Builder (Array ty) (MArray ty) ty m () ()
-> m (Either () (Array ty))
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