    -- |
    -- 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 (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c (Array ty)
    gunfold forall b r. Data b => c (b -> r) -> c r
    _ forall r. r -> c r
    _  = [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 -> () -> ()
    forall a b. a -> b -> b
    `seq` Offset a -> ()
    loop (Offset a
    iOffset a -> Offset a -> Offset a
    forall a. Additive a => a -> a -> a
    +Offset a
    1)

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

    instance Functor Array where
        fmap :: forall a b. (a -> b) -> Array a -> Array b
    fmap = (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 = [ty] -> Array ty
    [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 -> [ty]
    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 :: forall ty st. MArray ty st -> Int
    mutableLength (MArray Offset ty
    _ (CountOf Int
    len) MutableArray# st ty
    _) = Int
    len
    {-# INLINE mutableLength #-}

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

    -- | Return the element at a specific index from an array.
    --
    -- If the index @n is out of bounds, an error is raised.
    index :: Array ty -> Offset ty -> ty
    index :: forall ty. Array ty -> Offset ty -> ty
    index Array ty
    array Offset ty
    n
        | 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 :: forall ty. 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 :: forall (prim :: * -> *) ty.
    PrimMonad prim =>
    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 :: forall (prim :: * -> *) ty.
    PrimMonad prim =>
    MArray ty (PrimState prim) -> Offset ty -> prim ty
    unsafeRead (MArray Offset ty
    start CountOf ty
    _ MutableArray# (PrimState prim) ty
    ma) Offset ty
    i = 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 :: forall (prim :: * -> *) ty.
    PrimMonad prim =>
    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 :: forall (prim :: * -> *) ty.
    PrimMonad prim =>
    MArray ty (PrimState prim) -> Offset ty -> ty -> prim ()
    unsafeWrite (MArray Offset ty
    start CountOf ty
    _ MutableArray# (PrimState prim) ty
    ma) Offset ty
    ofs ty
    v =
        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 :: forall (prim :: * -> *) ty.
    PrimMonad prim =>
    MArray ty (PrimState prim) -> prim (Array ty)
    unsafeFreeze (MArray Offset ty
    ofs CountOf ty
    sz MutableArray# (PrimState prim) ty
    ma) = (State# (PrimState prim)
     -> (# State# (PrimState prim), Array ty #))
    -> prim (Array ty)
    forall a.
    (State# (PrimState prim) -> (# State# (PrimState prim), a #))
    -> prim a
    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 :: forall (prim :: * -> *) ty.
    PrimMonad prim =>
    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 a.
    (State# (PrimState prim) -> (# State# (PrimState prim), a #))
    -> prim a
    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
    forall a b. a -> b
    unsafeCoerce# Array# ty
    a) #)
    {-# INLINE unsafeThaw #-}

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

    freeze :: PrimMonad prim => MArray ty (PrimState prim) -> prim (Array ty)
    freeze :: forall (prim :: * -> *) ty.
    PrimMonad prim =>
    MArray ty (PrimState prim) -> prim (Array ty)
    freeze MArray ty (PrimState prim)
    marray = do
        m <- CountOf ty -> prim (MArray ty (PrimState prim))
    forall (prim :: * -> *) ty.
    PrimMonad prim =>
    CountOf ty -> prim (MArray ty (PrimState prim))
    new CountOf ty
    sz
        copyAt m (Offset 0) marray (Offset 0) sz
        unsafeFreeze 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 :: forall ty. 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 a b. ST s a -> (a -> ST s b) -> ST s b
    forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
    >>= MArray ty s -> ST s (Array ty)
    MArray ty (PrimState (ST 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 :: forall (prim :: * -> *) ty.
    PrimMonad prim =>
    MArray ty (PrimState prim)
    -> Offset ty
    -> MArray ty (PrimState prim)
    -> Offset ty
    -> CountOf ty
    -> prim ()
    copyAt MArray ty (PrimState prim)
    dst Offset ty
    od MArray ty (PrimState prim)
    src Offset ty
    os CountOf ty
    n = Offset ty -> Offset ty -> prim ()
    loop Offset ty
    od Offset ty
    os
      where -- !endIndex = os `offsetPlusE` n
            loop :: Offset ty -> Offset ty -> prim ()
    loop Offset ty
    d Offset ty
    s
                | Offset ty
    s Offset ty -> CountOf ty -> Bool
    forall ty. Offset ty -> CountOf ty -> Bool
    .==# CountOf ty
    n  = () -> prim ()
    forall a. a -> prim a
    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 a b. prim a -> (a -> prim b) -> prim b
    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 a b. prim a -> prim b -> prim b
    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 :: forall (prim :: * -> *) ty.
    PrimMonad prim =>
    MArray ty (PrimState prim)
    -> Offset ty -> Array ty -> Offset ty -> CountOf ty -> prim ()
    unsafeCopyAtRO (MArray (Offset (I# Int#
    dstart)) CountOf ty
    _ MutableArray# (PrimState prim) ty
    da) (Offset (I# Int#
    dofs))
                   (Array  (Offset (I# Int#
    sstart)) CountOf ty
    _ Array# ty
    sa) (Offset (I# Int#
    sofs))
                   (CountOf (I# Int#
    n)) =
        (State# (PrimState prim) -> (# State# (PrimState prim), () #))
    -> prim ()
    forall a.
    (State# (PrimState prim) -> (# State# (PrimState prim), a #))
    -> prim a
    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 :: forall ty s.
    Array ty
    -> CountOf ty
    -> (Array ty -> Offset ty -> MArray ty s -> ST s ())
    -> ST s (Array ty)
    unsafeCopyFrom Array ty
    v' CountOf ty
    newLen Array ty -> Offset ty -> MArray ty s -> ST s ()
    f = 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 a b. ST s a -> (a -> ST s b) -> ST s b
    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 a b. ST s a -> (a -> ST s b) -> ST s b
    forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
    >>= MArray ty s -> ST s (Array ty)
    MArray ty (PrimState (ST 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 a. a -> ST s a
    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 :: forall (prim :: * -> *) ty.
    PrimMonad prim =>
    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 a.
    (State# (PrimState prim) -> (# State# (PrimState prim), a #))
    -> prim a
    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 :: forall ty. 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 a b. ST s a -> (a -> ST s b) -> ST s b
    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 :: forall (prim :: * -> *).
    PrimMonad prim =>
    (Offset ty -> ty) -> MArray ty (PrimState prim) -> prim (Array ty)
    iter Offset ty -> ty
    f MArray ty (PrimState prim)
    ma = Offset ty -> prim (Array ty)
    loop Offset ty
    0
          where
            loop :: Offset ty -> prim (Array ty)
    loop Offset ty
    s
                | Offset ty
    s 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 a b. prim a -> prim b -> prim b
    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 :: forall a. Eq a => 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 :: forall a. Ord a => Array a -> Array a -> Ordering
    vCompare Array a
    a Array a
    b = Offset a -> Ordering
    loop Offset a
    0
      where
        !la :: CountOf a
    la = 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 :: forall a. 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 :: forall a. Array a -> CountOf a
    length (Array Offset a
    _ CountOf a
    sz Array# a
    _) = CountOf a
    sz

    vFromList :: [a] -> Array a
    vFromList :: forall a. [a] -> Array a
    vFromList [a]
    l = (forall 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 a b. ST s a -> (a -> ST s b) -> ST s b
    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 a b. prim a -> prim b -> prim b
    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 :: forall a. 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
        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
        sz <- loop 0 l ma
        unsafeFreezeShrink ma sz
      where
        -- TODO rewrite without ma as parameter
        loop :: Offset a -> [a] -> MArray a s -> ST s (CountOf a)
        loop :: forall s. Offset a -> [a] -> MArray a s -> ST s (CountOf a)
    loop Offset a
    i []     MArray a s
    _  = CountOf a -> ST s (CountOf a)
    forall a. a -> ST s 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 a. a -> ST s 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 a b. ST s a -> ST s b -> ST s b
    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 :: forall a. 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 a b. (a -> b) -> [a] -> [b]
    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 :: forall a. Array a -> Array a -> Array a
    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
        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)
        unsafeCopyAtRO r (Offset 0) a (Offset 0) la
        unsafeCopyAtRO r (sizeAsOffset la) b (Offset 0) lb
        unsafeFreeze 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 :: forall a. [Array a] -> Array a
    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
        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 a b. (a -> b) -> [a] -> [b]
    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)
        loop r (Offset 0) l
        unsafeFreeze r
      where loop :: MArray ty (PrimState f) -> Offset ty -> [Array ty] -> f ()
    loop MArray ty (PrimState f)
    _ Offset ty
    _ []     = () -> f ()
    forall a. a -> f a
    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 :: forall (m :: * -> *) a.
    PrimMonad m =>
    Int
    -> (MutableArray# (PrimState m) a
        -> State# (PrimState m) -> State# (PrimState m))
    -> m (Array a)
    onNewArray len :: Int
    len@(I# Int#
    len#) MutableArray# (PrimState m) a
    -> State# (PrimState m) -> State# (PrimState m)
    f = (State# (PrimState m) -> (# State# (PrimState m), Array a #))
    -> m (Array a)
    forall a.
    (State# (PrimState m) -> (# State# (PrimState m), a #)) -> m 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 :: forall ty. 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 b c a. (b -> c) -> (a -> b) -> a -> c
    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 :: forall ty. CountOf ty -> Array ty -> Array ty
    take CountOf ty
    nbElems a :: Array ty
    a@(Array Offset ty
    start CountOf ty
    len Array# ty
    arr)
        | CountOf ty
    nbElems 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 :: forall ty. CountOf ty -> Array ty -> Array ty
    drop CountOf ty
    nbElems a :: Array ty
    a@(Array Offset ty
    start CountOf ty
    len Array# ty
    arr)
        | CountOf ty
    nbElems CountOf ty -> CountOf ty -> Bool
    forall a. Ord a => a -> a -> Bool
    <= CountOf ty
    0                               = Array ty
    a
        | Just CountOf ty
    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 :: forall ty. CountOf ty -> Array ty -> (Array ty, Array ty)
    splitAt CountOf ty
    nbElems a :: Array ty
    a@(Array Offset ty
    start CountOf ty
    len Array# ty
    arr)
        | CountOf ty
    nbElems 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 CountOf ty
    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 :: forall ty. 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 :: forall ty. 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 :: forall ty. 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 :: forall ty. 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 :: forall ty. (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 :: forall ty. Array ty -> Offset ty -> Offset ty -> Array ty
    sub (Array Offset ty
    start CountOf ty
    len Array# ty
    a) Offset ty
    startIdx Offset ty
    expectedEndIdx
        | Offset ty
    startIdx 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 :: forall ty. (ty -> Bool) -> Array ty -> (Array ty, Array ty)
    break ty -> Bool
    predicate Array ty
    v = Offset ty -> (Array ty, Array ty)
    findBreak Offset ty
    0
      where
        !len :: CountOf ty
    len = 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 :: forall ty. (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 :: forall ty. 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
        Maybe (CountOf ty)
    Difference (CountOf ty)
    Nothing -> Array ty
    v
        Just CountOf ty
    0 -> Array ty
    v
        Just CountOf ty
    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 :: forall ty s.
    Offset ty -> ty -> Array ty -> Offset ty -> MArray ty s -> ST s ()
    go Offset ty
    endI ty
    sep' Array ty
    oldV Offset ty
    oldI MArray ty s
    newV
                | Offset ty
    oldI 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 :: forall ty. (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 b c a. (b -> c) -> (a -> b) -> a -> c
    forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
    Category cat =>
    cat b c -> cat a b -> cat a c
    . ty -> Bool
    p)

    spanEnd ::  (ty -> Bool) -> Array ty -> (Array ty, Array ty)
    spanEnd :: forall ty. (ty -> Bool) -> Array ty -> (Array ty, Array ty)
    spanEnd ty -> Bool
    p = (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 b c a. (b -> c) -> (a -> b) -> a -> c
    forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
    Category cat =>
    cat b c -> cat a b -> cat a c
    . ty -> Bool
    p)

    map :: (a -> b) -> Array a -> Array b
    map :: forall a b. (a -> b) -> Array a -> Array b
    map a -> b
    f Array a
    a = 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 :: forall a b. PrimType a => (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 b c a. (b -> c) -> (a -> b) -> a -> c
    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 a b. (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 b c a. (b -> c) -> (a -> b) -> a -> c
    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]
    UArray a -> [Item (UArray 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 :: forall b a. PrimType b => (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 b c a. (b -> c) -> (a -> b) -> a -> c
    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 a b. (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 b c a. (b -> c) -> (a -> b) -> a -> c
    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]
    Array a -> [Item (Array 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 :: forall ty. 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
        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
        unsafeWrite a 0 e
        unsafeFreeze a

    replicate :: CountOf ty -> ty -> Array ty
    replicate :: forall ty. 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 :: forall ty. 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
            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)
            unsafeWrite mv 0 e
            unsafeCopyAtRO mv (Offset 1) vec (Offset 0) len
            unsafeFreeze 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 :: forall ty. 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
            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)
            unsafeCopyAtRO mv 0 vec 0 len
            unsafeWrite mv (sizeAsOffset len) e
            unsafeFreeze 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 :: forall ty. 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 :: forall ty. 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
        Maybe (CountOf ty)
    Difference (CountOf ty)
    Nothing -> Maybe (Array ty, ty)
    forall a. Maybe a
    Nothing
        Just CountOf ty
    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 :: forall ty. Eq ty => ty -> Array ty -> Bool
    elem !ty
    ty Array ty
    arr = Offset ty -> Bool
    loop Offset ty
    0
      where
        !sz :: CountOf ty
    sz = 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 :: forall ty. (ty -> Bool) -> Array ty -> Maybe ty
    find ty -> Bool
    predicate Array ty
    vec = Offset ty -> Maybe ty
    loop Offset ty
    0
      where
        !len :: CountOf ty
    len = 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 :: forall ty. (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 a b. ST s a -> (a -> ST s b) -> ST s b
    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 :: forall (prim :: * -> *).
    PrimMonad prim =>
    (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 a b. prim a -> prim b -> prim b
    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 :: forall ty. (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 a b. ST s a -> (a -> ST s b) -> ST s b
    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 :: forall (prim :: * -> *).
    PrimMonad prim =>
    (ty -> Bool)
    -> (Offset ty -> ty)
    -> MArray ty (PrimState prim)
    -> prim (Array ty)
    copyFilterFreeze ty -> Bool
    predi Offset ty -> ty
    getVec MArray ty (PrimState prim)
    mvec = Offset ty -> Offset ty -> prim (Offset ty)
    loop (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 a b. prim a -> (a -> prim b) -> prim b
    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 a. a -> prim a
    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 a b. prim a -> prim b -> prim b
    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 :: forall (prim :: * -> *) ty.
    PrimMonad prim =>
    MArray ty (PrimState prim) -> Offset ty -> prim (Array ty)
    freezeUntilIndex MArray ty (PrimState prim)
    mvec Offset ty
    d = do
        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)
        copyAt m (Offset 0) mvec (Offset 0) (offsetAsSize d)
        unsafeFreeze m

    unsafeFreezeShrink :: PrimMonad prim => MArray ty (PrimState prim) -> CountOf ty -> prim (Array ty)
    unsafeFreezeShrink :: forall (prim :: * -> *) ty.
    PrimMonad prim =>
    MArray ty (PrimState prim) -> CountOf ty -> prim (Array ty)
    unsafeFreezeShrink (MArray Offset ty
    start CountOf ty
    _ MutableArray# (PrimState prim) ty
    ma) CountOf ty
    n = 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 :: forall ty. 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 :: forall ty a. (ty -> a -> a) -> a -> Array ty -> a
    foldr ty -> a -> a
    f a
    initialAcc Array ty
    vec = Offset ty -> a
    loop Offset ty
    0
      where
        len :: CountOf ty
    len = 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' :: forall a ty. (a -> ty -> a) -> a -> Array ty -> a
    foldl' a -> ty -> a
    f a
    initialAcc Array ty
    vec = Offset ty -> a -> a
    loop Offset ty
    0 a
    initialAcc
      where
        len :: CountOf ty
    len = 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' :: forall ty. (ty -> ty -> ty) -> NonEmpty (Array ty) -> ty
    foldl1' ty -> ty -> ty
    f NonEmpty (Array ty)
    arr = let (Array ty
    initialAcc, Array ty
    rest) = 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 :: forall ty. (ty -> ty -> ty) -> NonEmpty (Array ty) -> ty
    foldr1 ty -> ty -> ty
    f NonEmpty (Array ty)
    arr = let (Array ty
    initialAcc, Array ty
    rest) = 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 :: forall ty. (ty -> Bool) -> Array ty -> Bool
    all ty -> Bool
    p Array ty
    ba = Offset ty -> Bool
    loop Offset ty
    0
      where
        len :: CountOf ty
    len = 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 :: forall ty. (ty -> Bool) -> Array ty -> Bool
    any ty -> Bool
    p Array ty
    ba = Offset ty -> Bool
    loop Offset ty
    0
      where
        len :: CountOf ty
    len = 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 :: forall a. Eq a => Array a -> Array a -> 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 :: forall a. Eq a => Array a -> Array a -> 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 :: forall (state :: * -> *) ty err.
    PrimMonad state =>
    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
                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)
                newChunk <- new (chunkSize st)
                unsafeWrite newChunk 0 v
                pure ((), (Offset 1, st { prevChunks     = cur : prevChunks st
                                          , prevChunksSize = chunkSize st + prevChunksSize st
                                          , curChunk       = newChunk
                                          }, 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 a. a -> state a
    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 :: forall (m :: * -> *) ty err.
    PrimMonad m =>
    Int
    -> Builder (Array ty) (MArray ty) ty m err ()
    -> m (Either err (Array ty))
    builderBuild Int
    sizeChunksI Builder (Array ty) (MArray ty) ty m err ()
    ab
        | Int
    sizeChunksI 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
            first      <- CountOf ty -> m (MArray ty (PrimState m))
    forall (prim :: * -> *) ty.
    PrimMonad prim =>
    CountOf ty -> prim (MArray ty (PrimState prim))
    new CountOf ty
    sizeChunks
            (i, st, e) <- snd <$> runState (runBuilder ab) (Offset 0, BuildingState [] (CountOf 0) first sizeChunks, Nothing)
            case e of
              Just err
    err -> Either err (Array ty) -> m (Either err (Array ty))
    forall a. a -> m a
    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
                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 = 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
                bytes <- new totalSize >>= fillFromEnd totalSize (cur : prevChunks st) >>= unsafeFreeze
                pure (Right 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 a. a -> f a
    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_ :: forall (m :: * -> *) ty.
    PrimMonad m =>
    Int -> Builder (Array ty) (MArray ty) ty m () () -> m (Array ty)
    builderBuild_ Int
    sizeChunksI Builder (Array ty) (MArray ty) ty m () ()
    ab = (() -> 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 a. a -> a
    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