{-|
Module      : Z.Data.Array
Description : Fast boxed and unboxed arrays
Copyright   : (c) Dong Han, 2017
License     : BSD
Maintainer  : winterland1989@gmail.com
Stability   : experimental
Portability : non-portable

Unified unboxed and boxed array operations using type family.

NONE of the operations are bound checked, if you need checked operations please use "Z.Data.Array.Checked" instead.
It exports the exact same APIs ,so it requires no extra effort to switch between them.

Some mnemonics:

  * 'newArr' and 'newArrWith' return mutable array.
    'readArr' and 'writeArr' perform read and write actions on mutable arrays.
    'setArr' fills the elements with offset and length.
    'indexArr' only works on immutable Array, use 'indexArr'' to avoid thunks building up in the heap.

  * 'freezeArr' and 'thawArr' make a copy thus need slicing params.
    'unsafeFreezeArr' and 'unsafeThawArr' DO NOT COPY, use with care.

  * The order of arguements of 'copyArr', 'copyMutableArr' and 'moveArr' are always target and its offset
    come first, and source and source offset follow, copying length comes last.
-}

module Z.Data.Array.Base (
  -- * Arr typeclass
    Arr(..)
  , singletonArr, doubletonArr
  , modifyIndexArr, insertIndexArr, deleteIndexArr, swapArr, swapMutableArr
  , doubleMutableArr, shuffleMutableArr
  , RealWorld
  -- * Boxed array type
  , Array(..)
  , MutableArray(..)
  , SmallArray(..)
  , SmallMutableArray(..)
  , uninitialized
  -- * Primitive array type
  , PrimArray(..)
  , MutablePrimArray(..)
  , Prim(..)
  -- * Primitive array operations
  , newPinnedPrimArray, newAlignedPinnedPrimArray
  , copyPrimArrayToPtr, copyMutablePrimArrayToPtr, copyPtrToMutablePrimArray
  , primArrayContents, mutablePrimArrayContents, withPrimArrayContents, withMutablePrimArrayContents
  , isPrimArrayPinned, isMutablePrimArrayPinned
  -- * Unlifted array type
  , UnliftedArray(..)
  , MutableUnliftedArray(..)
  , PrimUnlifted(..)
  -- * The 'ArrayException' type
  , ArrayException(..)
  -- * Cast between primitive arrays
  , Cast
  , castArray
  , castMutableArray
  -- * Re-export
  , sizeOf
  ) where

import           Control.Exception              (ArrayException (..), throw)
import           Control.Monad
import           Control.Monad.Primitive
import           Control.Monad.ST
import           Data.Bits                      (unsafeShiftL)
import           Data.Kind                      (Type)
import           Data.Primitive.Array
import           Data.Primitive.ByteArray
import           Data.Primitive.PrimArray
import           Data.Primitive.Ptr             (copyPtrToMutablePrimArray)
import           Data.Primitive.SmallArray
import           Data.Primitive.Types
import           GHC.Exts
import           System.Random.Stateful  ( UniformRange(uniformRM), StatefulGen )
import           Z.Data.Array.Cast
import           Z.Data.Array.UnliftedArray


-- | Bottom value (@throw ('UndefinedElement' 'Data.Array.uninitialized')@)
-- for new boxed array('Array', 'SmallArray'..) initialization.
--
uninitialized :: a
uninitialized :: forall a. a
uninitialized = forall a e. Exception e => e -> a
throw (String -> ArrayException
UndefinedElement String
"Data.Array.uninitialized")


-- | The typeclass that unifies box & unboxed and mutable & immutable array operations.
--
-- Most of these functions simply wrap their primitive counterpart.
-- When there are no primitive ones, we fulfilled the semantic with other operations.
--
-- One exception is 'shrinkMutableArr' which only performs closure resizing on 'PrimArray', because
-- currently, RTS only supports that. 'shrinkMutableArr' won't do anything on other array types.
--
-- It's reasonable to trust GHC to specialize & inline these polymorphic functions.
-- They are used across this package and perform identically to their monomorphic counterpart.
--
class Arr (arr :: Type -> Type) a where


    -- | The mutable version of this array type.
    --
    type MArr arr = (mar :: Type -> Type -> Type) | mar -> arr

    -- | The empty array reference.
    emptyArr :: Arr arr a => arr a

    -- | Make a new array with a given size.
    --
    -- For boxed arrays, all elements are 'uninitialized' , which shall not be accessed.
    -- For primitive arrays, elements are just random garbage.
    newArr :: (PrimMonad m, PrimState m ~ s) => Int -> m (MArr arr s a)


    -- | Make a new array and fill it with an initial value.
    newArrWith :: (PrimMonad m, PrimState m ~ s) => Int -> a -> m (MArr arr s a)


    -- | Read from specified index of mutable array in a primitive monad.
    readArr :: (PrimMonad m, PrimState m ~ s) => MArr arr s a -> Int -> m a


    -- | Write to specified index of mutable array in a primitive monad.
    writeArr :: (PrimMonad m, PrimState m ~ s) => MArr arr s a -> Int -> a -> m ()


    -- | Fill the mutable array with a given value.
    setArr :: (PrimMonad m, PrimState m ~ s) => MArr arr s a -> Int -> Int -> a -> m ()


    -- | Read from the specified index of an immutable array. It's pure and often
    -- results in an indexing thunk for lifted arrays, use 'indexArr\'' or 'indexArrM' to avoid this.
    indexArr :: arr a -> Int -> a


    -- | Read from the specified index of an immutable array. The result is packaged into an unboxed unary tuple; the result itself is not yet evaluated.
    -- Pattern matching on the tuple forces the indexing of the array to happen but does not evaluate the element itself.
    -- Evaluating the thunk prevents additional thunks from building up on the heap.
    -- Avoiding these thunks, in turn, reduces references to the argument array, allowing it to be garbage collected more promptly.
    indexArr' :: arr a -> Int -> (# a #)


    -- | Monadically read a value from the immutable array at the given index.
    -- This allows us to be strict in the array while remaining lazy in the read
    -- element which is very useful for collective operations. Suppose we want to
    -- copy an array. We could do something like this:
    --
    -- > copy marr arr ... = do ...
    -- >                        writeArray marr i (indexArray arr i) ...
    -- >                        ...
    --
    -- But since primitive arrays are lazy, the calls to 'indexArray' will not be
    -- evaluated. Rather, @marr@ will be filled with thunks each of which would
    -- retain a reference to @arr@. This is definitely not what we want!
    --
    -- With 'indexArrayM', we can instead write
    --
    -- > copy marr arr ... = do ...
    -- >                        x <- indexArrayM arr i
    -- >                        writeArray marr i x
    -- >                        ...
    --
    -- Now, indexing is executed immediately although the returned element is
    -- still not evaluated.
    --
    -- /Note:/ this function does not do bounds checking.
    indexArrM :: (Monad m) => arr a -> Int -> m a


    -- | Create an immutable copy of a slice of an array.
    -- This operation makes a copy of the specified section, so it is safe to continue using the mutable array afterward.
    freezeArr :: (PrimMonad m, PrimState m ~ s) => MArr arr s a -> Int -> Int -> m (arr a)


    -- | Create a mutable array from a slice of an immutable array.
    -- This operation makes a copy of the specified slice, so it is safe to use the immutable array afterward.
    thawArr :: (PrimMonad m, PrimState m ~ s) => arr a -> Int -> Int -> m (MArr arr s a)


    -- | Convert a mutable array to an immutable one without copying.
    -- The array should not be modified after the conversion.
    unsafeFreezeArr :: (PrimMonad m, PrimState m ~ s) => MArr arr s a -> m (arr a)



    -- | Convert a mutable array to an immutable one without copying. The
    -- array should not be modified after the conversion.
    unsafeThawArr :: (PrimMonad m, PrimState m ~ s) => arr a -> m (MArr arr s a)


    -- | Copy a slice of an immutable array to a mutable array at given offset.
    copyArr ::  (PrimMonad m, PrimState m ~ s)
            => MArr arr s a -- ^ target
            -> Int          -- ^ offset into target array
            -> arr a        -- ^ source
            -> Int          -- ^ offset into source array
            -> Int          -- ^ number of elements to copy
            -> m ()


    -- | Copy a slice of a mutable array to another mutable array at given offset.
    -- The two mutable arrays must not be the same.
    copyMutableArr :: (PrimMonad m, PrimState m ~ s)
                   => MArr arr s a  -- ^ target
                   -> Int           -- ^ offset into target array
                   -> MArr arr s a  -- ^ source
                   -> Int           -- ^ offset into source array
                   -> Int           -- ^ number of elements to copy
                   -> m ()


    -- | Copy a slice of a mutable array to a mutable array at given offset.
    -- The two mutable arrays can be the same.
    moveArr :: (PrimMonad m, PrimState m ~ s)
            => MArr arr s a  -- ^ target
            -> Int           -- ^ offset into target array
            -> MArr arr s a  -- ^ source
            -> Int           -- ^ offset into source array
            -> Int           -- ^ number of elements to copy
            -> m ()


    -- | Create an immutable copy with the given subrange of the original array.
    cloneArr :: arr a -> Int -> Int -> arr a


    -- | Create a mutable copy the given subrange of the original array.
    cloneMutableArr :: (PrimMonad m, PrimState m ~ s) => MArr arr s a -> Int -> Int -> m (MArr arr s a)


    -- | Resize a mutable array to the given size.
    resizeMutableArr :: (PrimMonad m, PrimState m ~ s) => MArr arr s a -> Int -> m (MArr arr s a)


    -- | Shrink a mutable array to the given size. This operation only works on primitive arrays.
    -- For some array types, this is a no-op, e.g. 'sizeOfMutableArr' will not change.
    shrinkMutableArr :: (PrimMonad m, PrimState m ~ s) => MArr arr s a -> Int -> m ()


    -- | Is two mutable array are reference equal.
    sameMutableArr :: MArr arr s a -> MArr arr s a -> Bool


    -- | Size of the immutable array.
    sizeofArr :: arr a -> Int


    -- | Size of the mutable array.
    sizeofMutableArr :: (PrimMonad m, PrimState m ~ s) => MArr arr s a -> m Int


    -- | Check whether the two immutable arrays refer to the same memory block
    --
    -- Note that the result of 'sameArr' may change depending on compiler's optimizations, for example,
    -- @let arr = runST ... in arr `sameArr` arr@ may return false if compiler decides to
    -- inline it.
    --
    -- See https://ghc.haskell.org/trac/ghc/ticket/13908 for more context.
    --
    sameArr :: arr a -> arr a -> Bool

instance Arr Array a where
    type MArr Array = MutableArray
    emptyArr :: Arr Array a => Array a
emptyArr = forall a. Array a
emptyArray
    {-# INLINE emptyArr #-}
    newArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
Int -> m (MArr Array s a)
newArr Int
n = forall (m :: * -> *) a.
PrimMonad m =>
Int -> a -> m (MutableArray (PrimState m) a)
newArray Int
n forall a. a
uninitialized
    {-# INLINE newArr #-}
    newArrWith :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
Int -> a -> m (MArr Array s a)
newArrWith = forall (m :: * -> *) a.
PrimMonad m =>
Int -> a -> m (MutableArray (PrimState m) a)
newArray
    {-# INLINE newArrWith #-}
    readArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
MArr Array s a -> Int -> m a
readArr = forall (m :: * -> *) a.
PrimMonad m =>
MutableArray (PrimState m) a -> Int -> m a
readArray
    {-# INLINE readArr #-}
    writeArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
MArr Array s a -> Int -> a -> m ()
writeArr = forall (m :: * -> *) a.
PrimMonad m =>
MutableArray (PrimState m) a -> Int -> a -> m ()
writeArray
    {-# INLINE writeArr #-}
    setArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
MArr Array s a -> Int -> Int -> a -> m ()
setArr MArr Array s a
marr Int
s Int
l a
x = Int -> m ()
go Int
s
      where
        !sl :: Int
sl = Int
s forall a. Num a => a -> a -> a
+ Int
l
        go :: Int -> m ()
go !Int
i | Int
i forall a. Ord a => a -> a -> Bool
>= Int
sl = forall (m :: * -> *) a. Monad m => a -> m a
return ()
              | Bool
otherwise = forall (m :: * -> *) a.
PrimMonad m =>
MutableArray (PrimState m) a -> Int -> a -> m ()
writeArray MArr Array s a
marr Int
i a
x forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> Int -> m ()
go (Int
iforall a. Num a => a -> a -> a
+Int
1)
    {-# INLINE setArr #-}
    indexArr :: Array a -> Int -> a
indexArr = forall a. Array a -> Int -> a
indexArray
    {-# INLINE indexArr #-}
    indexArr' :: Array a -> Int -> (# a #)
indexArr' (Array Array# a
arr#) (I# Int#
i#) = forall a. Array# a -> Int# -> (# a #)
indexArray# Array# a
arr# Int#
i#
    {-# INLINE indexArr' #-}
    indexArrM :: forall (m :: * -> *). Monad m => Array a -> Int -> m a
indexArrM = forall (m :: * -> *) a. Monad m => Array a -> Int -> m a
indexArrayM
    {-# INLINE indexArrM #-}
    freezeArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
MArr Array s a -> Int -> Int -> m (Array a)
freezeArr = forall (m :: * -> *) a.
PrimMonad m =>
MutableArray (PrimState m) a -> Int -> Int -> m (Array a)
freezeArray
    {-# INLINE freezeArr #-}
    thawArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
Array a -> Int -> Int -> m (MArr Array s a)
thawArr = forall (m :: * -> *) a.
PrimMonad m =>
Array a -> Int -> Int -> m (MutableArray (PrimState m) a)
thawArray
    {-# INLINE thawArr #-}
    unsafeFreezeArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
MArr Array s a -> m (Array a)
unsafeFreezeArr = forall (m :: * -> *) a.
PrimMonad m =>
MutableArray (PrimState m) a -> m (Array a)
unsafeFreezeArray
    {-# INLINE unsafeFreezeArr #-}
    unsafeThawArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
Array a -> m (MArr Array s a)
unsafeThawArr = forall (m :: * -> *) a.
PrimMonad m =>
Array a -> m (MutableArray (PrimState m) a)
unsafeThawArray
    {-# INLINE unsafeThawArr #-}

    copyArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
MArr Array s a -> Int -> Array a -> Int -> Int -> m ()
copyArr = forall (m :: * -> *) a.
PrimMonad m =>
MutableArray (PrimState m) a
-> Int -> Array a -> Int -> Int -> m ()
copyArray
    {-# INLINE copyArr #-}
    copyMutableArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
MArr Array s a -> Int -> MArr Array s a -> Int -> Int -> m ()
copyMutableArr = forall (m :: * -> *) a.
PrimMonad m =>
MutableArray (PrimState m) a
-> Int -> MutableArray (PrimState m) a -> Int -> Int -> m ()
copyMutableArray
    {-# INLINE copyMutableArr #-}

    moveArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
MArr Array s a -> Int -> MArr Array s a -> Int -> Int -> m ()
moveArr MArr Array s a
marr1 Int
s1 MArr Array s a
marr2 Int
s2 Int
l
        | Int
l forall a. Ord a => a -> a -> Bool
<= Int
0 = forall (m :: * -> *) a. Monad m => a -> m a
return ()
        | forall s a. MutableArray s a -> MutableArray s a -> Bool
sameMutableArray MArr Array s a
marr1 MArr Array s a
marr2 =
            case forall a. Ord a => a -> a -> Ordering
compare Int
s1 Int
s2 of
                Ordering
LT ->
                    let !d :: Int
d = Int
s2 forall a. Num a => a -> a -> a
- Int
s1
                        !s2l :: Int
s2l = Int
s2 forall a. Num a => a -> a -> a
+ Int
l
                        go :: Int -> m ()
go !Int
i | Int
i forall a. Ord a => a -> a -> Bool
>= Int
s2l = forall (m :: * -> *) a. Monad m => a -> m a
return ()
                              | Bool
otherwise = do a
x <- forall (m :: * -> *) a.
PrimMonad m =>
MutableArray (PrimState m) a -> Int -> m a
readArray MArr Array s a
marr2 Int
i
                                               forall (m :: * -> *) a.
PrimMonad m =>
MutableArray (PrimState m) a -> Int -> a -> m ()
writeArray MArr Array s a
marr1 (Int
iforall a. Num a => a -> a -> a
-Int
d) a
x
                                               Int -> m ()
go (Int
iforall a. Num a => a -> a -> a
+Int
1)
                    in Int -> m ()
go Int
s2

                Ordering
EQ -> forall (m :: * -> *) a. Monad m => a -> m a
return ()

                Ordering
GT ->
                    let !d :: Int
d = Int
s1 forall a. Num a => a -> a -> a
- Int
s2
                        go :: Int -> m ()
go !Int
i | Int
i forall a. Ord a => a -> a -> Bool
< Int
s2 = forall (m :: * -> *) a. Monad m => a -> m a
return ()
                              | Bool
otherwise = do a
x <- forall (m :: * -> *) a.
PrimMonad m =>
MutableArray (PrimState m) a -> Int -> m a
readArray MArr Array s a
marr2 Int
i
                                               forall (m :: * -> *) a.
PrimMonad m =>
MutableArray (PrimState m) a -> Int -> a -> m ()
writeArray MArr Array s a
marr1 (Int
iforall a. Num a => a -> a -> a
+Int
d) a
x
                                               Int -> m ()
go (Int
iforall a. Num a => a -> a -> a
-Int
1)
                    in Int -> m ()
go (Int
s2forall a. Num a => a -> a -> a
+Int
lforall a. Num a => a -> a -> a
-Int
1)
        | Bool
otherwise = forall (m :: * -> *) a.
PrimMonad m =>
MutableArray (PrimState m) a
-> Int -> MutableArray (PrimState m) a -> Int -> Int -> m ()
copyMutableArray MArr Array s a
marr1 Int
s1 MArr Array s a
marr2 Int
s2 Int
l
    {-# INLINE moveArr #-}

    cloneArr :: Array a -> Int -> Int -> Array a
cloneArr = forall a. Array a -> Int -> Int -> Array a
cloneArray
    {-# INLINE cloneArr #-}
    cloneMutableArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
MArr Array s a -> Int -> Int -> m (MArr Array s a)
cloneMutableArr = forall (m :: * -> *) a.
PrimMonad m =>
MutableArray (PrimState m) a
-> Int -> Int -> m (MutableArray (PrimState m) a)
cloneMutableArray
    {-# INLINE cloneMutableArr #-}

    resizeMutableArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
MArr Array s a -> Int -> m (MArr Array s a)
resizeMutableArr MArr Array s a
marr Int
n = do
        MutableArray s a
marr' <- forall (m :: * -> *) a.
PrimMonad m =>
Int -> a -> m (MutableArray (PrimState m) a)
newArray Int
n forall a. a
uninitialized
        forall (m :: * -> *) a.
PrimMonad m =>
MutableArray (PrimState m) a
-> Int -> MutableArray (PrimState m) a -> Int -> Int -> m ()
copyMutableArray MutableArray s a
marr' Int
0 MArr Array s a
marr Int
0 (forall s a. MutableArray s a -> Int
sizeofMutableArray MArr Array s a
marr)
        forall (m :: * -> *) a. Monad m => a -> m a
return MutableArray s a
marr'
    {-# INLINE resizeMutableArr #-}
    shrinkMutableArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
MArr Array s a -> Int -> m ()
shrinkMutableArr MArr Array s a
_ Int
_ = forall (m :: * -> *) a. Monad m => a -> m a
return ()
    {-# INLINE shrinkMutableArr #-}

    sameMutableArr :: forall s. MArr Array s a -> MArr Array s a -> Bool
sameMutableArr = forall s a. MutableArray s a -> MutableArray s a -> Bool
sameMutableArray
    {-# INLINE sameMutableArr #-}
    sizeofArr :: Array a -> Int
sizeofArr = forall a. Array a -> Int
sizeofArray
    {-# INLINE sizeofArr #-}
    sizeofMutableArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
MArr Array s a -> m Int
sizeofMutableArr = forall (m :: * -> *) a. Monad m => a -> m a
return forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall s a. MutableArray s a -> Int
sizeofMutableArray
    {-# INLINE sizeofMutableArr #-}

    sameArr :: Array a -> Array a -> Bool
sameArr (Array Array# a
arr1#) (Array Array# a
arr2#) = Int# -> Bool
isTrue# (
        forall d a. MutableArray# d a -> MutableArray# d a -> Int#
sameMutableArray# (unsafeCoerce# :: forall a b. a -> b
unsafeCoerce# Array# a
arr1#) (unsafeCoerce# :: forall a b. a -> b
unsafeCoerce# Array# a
arr2#))
    {-# INLINE sameArr #-}

instance Arr SmallArray a where
    type MArr SmallArray = SmallMutableArray
    emptyArr :: Arr SmallArray a => SmallArray a
emptyArr = forall a. SmallArray a
emptySmallArray
    {-# INLINE emptyArr #-}
    newArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
Int -> m (MArr SmallArray s a)
newArr Int
n = forall (m :: * -> *) a.
PrimMonad m =>
Int -> a -> m (SmallMutableArray (PrimState m) a)
newSmallArray Int
n forall a. a
uninitialized
    {-# INLINE newArr #-}
    newArrWith :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
Int -> a -> m (MArr SmallArray s a)
newArrWith = forall (m :: * -> *) a.
PrimMonad m =>
Int -> a -> m (SmallMutableArray (PrimState m) a)
newSmallArray
    {-# INLINE newArrWith #-}
    readArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
MArr SmallArray s a -> Int -> m a
readArr = forall (m :: * -> *) a.
PrimMonad m =>
SmallMutableArray (PrimState m) a -> Int -> m a
readSmallArray
    {-# INLINE readArr #-}
    writeArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
MArr SmallArray s a -> Int -> a -> m ()
writeArr = forall (m :: * -> *) a.
PrimMonad m =>
SmallMutableArray (PrimState m) a -> Int -> a -> m ()
writeSmallArray
    {-# INLINE writeArr #-}
    setArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
MArr SmallArray s a -> Int -> Int -> a -> m ()
setArr MArr SmallArray s a
marr Int
s Int
l a
x = Int -> m ()
go Int
s
      where
        !sl :: Int
sl = Int
s forall a. Num a => a -> a -> a
+ Int
l
        go :: Int -> m ()
go !Int
i | Int
i forall a. Ord a => a -> a -> Bool
>= Int
sl = forall (m :: * -> *) a. Monad m => a -> m a
return ()
              | Bool
otherwise = forall (m :: * -> *) a.
PrimMonad m =>
SmallMutableArray (PrimState m) a -> Int -> a -> m ()
writeSmallArray MArr SmallArray s a
marr Int
i a
x forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> Int -> m ()
go (Int
iforall a. Num a => a -> a -> a
+Int
1)
    {-# INLINE setArr #-}
    indexArr :: SmallArray a -> Int -> a
indexArr = forall a. SmallArray a -> Int -> a
indexSmallArray
    {-# INLINE indexArr #-}
    indexArr' :: SmallArray a -> Int -> (# a #)
indexArr' (SmallArray SmallArray# a
arr#) (I# Int#
i#) = forall a. SmallArray# a -> Int# -> (# a #)
indexSmallArray# SmallArray# a
arr# Int#
i#
    {-# INLINE indexArr' #-}
    indexArrM :: forall (m :: * -> *). Monad m => SmallArray a -> Int -> m a
indexArrM = forall (m :: * -> *) a. Monad m => SmallArray a -> Int -> m a
indexSmallArrayM
    {-# INLINE indexArrM #-}
    freezeArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
MArr SmallArray s a -> Int -> Int -> m (SmallArray a)
freezeArr = forall (m :: * -> *) a.
PrimMonad m =>
SmallMutableArray (PrimState m) a -> Int -> Int -> m (SmallArray a)
freezeSmallArray
    {-# INLINE freezeArr #-}
    thawArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
SmallArray a -> Int -> Int -> m (MArr SmallArray s a)
thawArr = forall (m :: * -> *) a.
PrimMonad m =>
SmallArray a -> Int -> Int -> m (SmallMutableArray (PrimState m) a)
thawSmallArray
    {-# INLINE thawArr #-}
    unsafeFreezeArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
MArr SmallArray s a -> m (SmallArray a)
unsafeFreezeArr = forall (m :: * -> *) a.
PrimMonad m =>
SmallMutableArray (PrimState m) a -> m (SmallArray a)
unsafeFreezeSmallArray
    {-# INLINE unsafeFreezeArr #-}
    unsafeThawArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
SmallArray a -> m (MArr SmallArray s a)
unsafeThawArr = forall (m :: * -> *) a.
PrimMonad m =>
SmallArray a -> m (SmallMutableArray (PrimState m) a)
unsafeThawSmallArray
    {-# INLINE unsafeThawArr #-}

    copyArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
MArr SmallArray s a -> Int -> SmallArray a -> Int -> Int -> m ()
copyArr = forall (m :: * -> *) a.
PrimMonad m =>
SmallMutableArray (PrimState m) a
-> Int -> SmallArray a -> Int -> Int -> m ()
copySmallArray
    {-# INLINE copyArr #-}
    copyMutableArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
MArr SmallArray s a
-> Int -> MArr SmallArray s a -> Int -> Int -> m ()
copyMutableArr = forall (m :: * -> *) a.
PrimMonad m =>
SmallMutableArray (PrimState m) a
-> Int -> SmallMutableArray (PrimState m) a -> Int -> Int -> m ()
copySmallMutableArray
    {-# INLINE copyMutableArr #-}

    moveArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
MArr SmallArray s a
-> Int -> MArr SmallArray s a -> Int -> Int -> m ()
moveArr MArr SmallArray s a
marr1 Int
s1 MArr SmallArray s a
marr2 Int
s2 Int
l
        | Int
l forall a. Ord a => a -> a -> Bool
<= Int
0 = forall (m :: * -> *) a. Monad m => a -> m a
return ()
        | forall (arr :: * -> *) a s.
Arr arr a =>
MArr arr s a -> MArr arr s a -> Bool
sameMutableArr MArr SmallArray s a
marr1 MArr SmallArray s a
marr2 =
            case forall a. Ord a => a -> a -> Ordering
compare Int
s1 Int
s2 of
                Ordering
LT ->
                    let !d :: Int
d = Int
s2 forall a. Num a => a -> a -> a
- Int
s1
                        !s2l :: Int
s2l = Int
s2 forall a. Num a => a -> a -> a
+ Int
l
                        go :: Int -> m ()
go !Int
i | Int
i forall a. Ord a => a -> a -> Bool
>= Int
s2l = forall (m :: * -> *) a. Monad m => a -> m a
return ()
                              | Bool
otherwise = do a
x <- forall (m :: * -> *) a.
PrimMonad m =>
SmallMutableArray (PrimState m) a -> Int -> m a
readSmallArray MArr SmallArray s a
marr2 Int
i
                                               forall (m :: * -> *) a.
PrimMonad m =>
SmallMutableArray (PrimState m) a -> Int -> a -> m ()
writeSmallArray MArr SmallArray s a
marr1 (Int
iforall a. Num a => a -> a -> a
-Int
d) a
x
                                               Int -> m ()
go (Int
iforall a. Num a => a -> a -> a
+Int
1)
                    in Int -> m ()
go Int
s2

                Ordering
EQ -> forall (m :: * -> *) a. Monad m => a -> m a
return ()

                Ordering
GT ->
                    let !d :: Int
d = Int
s1 forall a. Num a => a -> a -> a
- Int
s2
                        go :: Int -> m ()
go !Int
i | Int
i forall a. Ord a => a -> a -> Bool
< Int
s2 = forall (m :: * -> *) a. Monad m => a -> m a
return ()
                              | Bool
otherwise = do a
x <- forall (m :: * -> *) a.
PrimMonad m =>
SmallMutableArray (PrimState m) a -> Int -> m a
readSmallArray MArr SmallArray s a
marr2 Int
i
                                               forall (m :: * -> *) a.
PrimMonad m =>
SmallMutableArray (PrimState m) a -> Int -> a -> m ()
writeSmallArray MArr SmallArray s a
marr1 (Int
iforall a. Num a => a -> a -> a
+Int
d) a
x
                                               Int -> m ()
go (Int
iforall a. Num a => a -> a -> a
-Int
1)
                    in Int -> m ()
go (Int
s2forall a. Num a => a -> a -> a
+Int
lforall a. Num a => a -> a -> a
-Int
1)
        | Bool
otherwise = forall (m :: * -> *) a.
PrimMonad m =>
SmallMutableArray (PrimState m) a
-> Int -> SmallMutableArray (PrimState m) a -> Int -> Int -> m ()
copySmallMutableArray MArr SmallArray s a
marr1 Int
s1 MArr SmallArray s a
marr2 Int
s2 Int
l
    {-# INLINE moveArr #-}

    cloneArr :: SmallArray a -> Int -> Int -> SmallArray a
cloneArr = forall a. SmallArray a -> Int -> Int -> SmallArray a
cloneSmallArray
    {-# INLINE cloneArr #-}
    cloneMutableArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
MArr SmallArray s a -> Int -> Int -> m (MArr SmallArray s a)
cloneMutableArr = forall (m :: * -> *) a.
PrimMonad m =>
SmallMutableArray (PrimState m) a
-> Int -> Int -> m (SmallMutableArray (PrimState m) a)
cloneSmallMutableArray
    {-# INLINE cloneMutableArr #-}

    resizeMutableArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
MArr SmallArray s a -> Int -> m (MArr SmallArray s a)
resizeMutableArr MArr SmallArray s a
marr Int
n = do
        SmallMutableArray s a
marr' <- forall (m :: * -> *) a.
PrimMonad m =>
Int -> a -> m (SmallMutableArray (PrimState m) a)
newSmallArray Int
n forall a. a
uninitialized
        forall (m :: * -> *) a.
PrimMonad m =>
SmallMutableArray (PrimState m) a
-> Int -> SmallMutableArray (PrimState m) a -> Int -> Int -> m ()
copySmallMutableArray SmallMutableArray s a
marr' Int
0 MArr SmallArray s a
marr Int
0 (forall s a. SmallMutableArray s a -> Int
sizeofSmallMutableArray MArr SmallArray s a
marr)
        forall (m :: * -> *) a. Monad m => a -> m a
return SmallMutableArray s a
marr'
    {-# INLINE resizeMutableArr #-}
    shrinkMutableArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
MArr SmallArray s a -> Int -> m ()
shrinkMutableArr = forall (m :: * -> *) a.
PrimMonad m =>
SmallMutableArray (PrimState m) a -> Int -> m ()
shrinkSmallMutableArray
    {-# INLINE shrinkMutableArr #-}

    sameMutableArr :: forall s. MArr SmallArray s a -> MArr SmallArray s a -> Bool
sameMutableArr (SmallMutableArray SmallMutableArray# s a
smarr1#) (SmallMutableArray SmallMutableArray# s a
smarr2#) =
        Int# -> Bool
isTrue# (forall d a.
SmallMutableArray# d a -> SmallMutableArray# d a -> Int#
sameSmallMutableArray# SmallMutableArray# s a
smarr1# SmallMutableArray# s a
smarr2#)
    {-# INLINE sameMutableArr #-}
    sizeofArr :: SmallArray a -> Int
sizeofArr = forall a. SmallArray a -> Int
sizeofSmallArray
    {-# INLINE sizeofArr #-}
    sizeofMutableArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
MArr SmallArray s a -> m Int
sizeofMutableArr = forall (m :: * -> *) a. Monad m => a -> m a
return forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall s a. SmallMutableArray s a -> Int
sizeofSmallMutableArray
    {-# INLINE sizeofMutableArr #-}

    sameArr :: SmallArray a -> SmallArray a -> Bool
sameArr (SmallArray SmallArray# a
arr1#) (SmallArray SmallArray# a
arr2#) = Int# -> Bool
isTrue# (
        forall d a.
SmallMutableArray# d a -> SmallMutableArray# d a -> Int#
sameSmallMutableArray# (unsafeCoerce# :: forall a b. a -> b
unsafeCoerce# SmallArray# a
arr1#) (unsafeCoerce# :: forall a b. a -> b
unsafeCoerce# SmallArray# a
arr2#))
    {-# INLINE sameArr #-}

instance Prim a => Arr PrimArray a where
    type MArr PrimArray = MutablePrimArray
    emptyArr :: Arr PrimArray a => PrimArray a
emptyArr = forall a. PrimArray a
emptyPrimArray
    {-# INLINE emptyArr #-}
    newArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
Int -> m (MArr PrimArray s a)
newArr = forall (m :: * -> *) a.
(PrimMonad m, Prim a) =>
Int -> m (MutablePrimArray (PrimState m) a)
newPrimArray
    {-# INLINE newArr #-}
    newArrWith :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
Int -> a -> m (MArr PrimArray s a)
newArrWith Int
n a
x = do
        MutablePrimArray s a
marr <- forall (m :: * -> *) a.
(PrimMonad m, Prim a) =>
Int -> m (MutablePrimArray (PrimState m) a)
newPrimArray Int
n
        forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (Int
n forall a. Ord a => a -> a -> Bool
> Int
0) (forall a (m :: * -> *).
(Prim a, PrimMonad m) =>
MutablePrimArray (PrimState m) a -> Int -> Int -> a -> m ()
setPrimArray MutablePrimArray s a
marr Int
0 Int
n a
x)
        forall (m :: * -> *) a. Monad m => a -> m a
return MutablePrimArray s a
marr
    {-# INLINE newArrWith #-}
    readArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
MArr PrimArray s a -> Int -> m a
readArr = forall a (m :: * -> *).
(Prim a, PrimMonad m) =>
MutablePrimArray (PrimState m) a -> Int -> m a
readPrimArray
    {-# INLINE readArr #-}
    writeArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
MArr PrimArray s a -> Int -> a -> m ()
writeArr = forall a (m :: * -> *).
(Prim a, PrimMonad m) =>
MutablePrimArray (PrimState m) a -> Int -> a -> m ()
writePrimArray
    {-# INLINE writeArr #-}
    setArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
MArr PrimArray s a -> Int -> Int -> a -> m ()
setArr = forall a (m :: * -> *).
(Prim a, PrimMonad m) =>
MutablePrimArray (PrimState m) a -> Int -> Int -> a -> m ()
setPrimArray
    {-# INLINE setArr #-}
    indexArr :: PrimArray a -> Int -> a
indexArr = forall a. Prim a => PrimArray a -> Int -> a
indexPrimArray
    {-# INLINE indexArr #-}
    indexArr' :: PrimArray a -> Int -> (# a #)
indexArr' PrimArray a
arr Int
i = (# forall a. Prim a => PrimArray a -> Int -> a
indexPrimArray PrimArray a
arr Int
i #)
    {-# INLINE indexArr' #-}
    indexArrM :: forall (m :: * -> *). Monad m => PrimArray a -> Int -> m a
indexArrM PrimArray a
arr Int
i = forall (m :: * -> *) a. Monad m => a -> m a
return (forall a. Prim a => PrimArray a -> Int -> a
indexPrimArray PrimArray a
arr Int
i)
    {-# INLINE indexArrM #-}
    freezeArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
MArr PrimArray s a -> Int -> Int -> m (PrimArray a)
freezeArr = forall (m :: * -> *) a.
(PrimMonad m, Prim a) =>
MutablePrimArray (PrimState m) a -> Int -> Int -> m (PrimArray a)
freezePrimArray
    {-# INLINE freezeArr #-}
    thawArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
PrimArray a -> Int -> Int -> m (MArr PrimArray s a)
thawArr = forall (m :: * -> *) a.
(PrimMonad m, Prim a) =>
PrimArray a -> Int -> Int -> m (MutablePrimArray (PrimState m) a)
thawPrimArray
    {-# INLINE thawArr #-}
    unsafeFreezeArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
MArr PrimArray s a -> m (PrimArray a)
unsafeFreezeArr = forall (m :: * -> *) a.
PrimMonad m =>
MutablePrimArray (PrimState m) a -> m (PrimArray a)
unsafeFreezePrimArray
    {-# INLINE unsafeFreezeArr #-}
    unsafeThawArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
PrimArray a -> m (MArr PrimArray s a)
unsafeThawArr = forall (m :: * -> *) a.
PrimMonad m =>
PrimArray a -> m (MutablePrimArray (PrimState m) a)
unsafeThawPrimArray
    {-# INLINE unsafeThawArr #-}

    copyArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
MArr PrimArray s a -> Int -> PrimArray a -> Int -> Int -> m ()
copyArr = forall (m :: * -> *) a.
(PrimMonad m, Prim a) =>
MutablePrimArray (PrimState m) a
-> Int -> PrimArray a -> Int -> Int -> m ()
copyPrimArray
    {-# INLINE copyArr #-}
    copyMutableArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
MArr PrimArray s a
-> Int -> MArr PrimArray s a -> Int -> Int -> m ()
copyMutableArr = forall (m :: * -> *) a.
(PrimMonad m, Prim a) =>
MutablePrimArray (PrimState m) a
-> Int -> MutablePrimArray (PrimState m) a -> Int -> Int -> m ()
copyMutablePrimArray
    {-# INLINE copyMutableArr #-}

    moveArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
MArr PrimArray s a
-> Int -> MArr PrimArray s a -> Int -> Int -> m ()
moveArr (MutablePrimArray MutableByteArray# s
dst) Int
doff (MutablePrimArray MutableByteArray# s
src) Int
soff Int
n =
        forall (m :: * -> *).
PrimMonad m =>
MutableByteArray (PrimState m)
-> Int -> MutableByteArray (PrimState m) -> Int -> Int -> m ()
moveByteArray (forall s. MutableByteArray# s -> MutableByteArray s
MutableByteArray MutableByteArray# s
dst) (Int
doffforall a. Num a => a -> a -> a
*Int
siz) (forall s. MutableByteArray# s -> MutableByteArray s
MutableByteArray MutableByteArray# s
src) (Int
soffforall a. Num a => a -> a -> a
*Int
siz) (Int
nforall a. Num a => a -> a -> a
*Int
siz)
      where siz :: Int
siz = forall a. Prim a => a -> Int
sizeOf (forall a. HasCallStack => a
undefined :: a)
    {-# INLINE moveArr #-}

    cloneArr :: PrimArray a -> Int -> Int -> PrimArray a
cloneArr = forall a. Prim a => PrimArray a -> Int -> Int -> PrimArray a
clonePrimArray
    {-# INLINE cloneArr #-}
    cloneMutableArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
MArr PrimArray s a -> Int -> Int -> m (MArr PrimArray s a)
cloneMutableArr = forall (m :: * -> *) a.
(PrimMonad m, Prim a) =>
MutablePrimArray (PrimState m) a
-> Int -> Int -> m (MutablePrimArray (PrimState m) a)
cloneMutablePrimArray
    {-# INLINE cloneMutableArr #-}

    resizeMutableArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
MArr PrimArray s a -> Int -> m (MArr PrimArray s a)
resizeMutableArr = forall (m :: * -> *) a.
(PrimMonad m, Prim a) =>
MutablePrimArray (PrimState m) a
-> Int -> m (MutablePrimArray (PrimState m) a)
resizeMutablePrimArray
    {-# INLINE resizeMutableArr #-}
    shrinkMutableArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
MArr PrimArray s a -> Int -> m ()
shrinkMutableArr = forall (m :: * -> *) a.
(PrimMonad m, Prim a) =>
MutablePrimArray (PrimState m) a -> Int -> m ()
shrinkMutablePrimArray
    {-# INLINE shrinkMutableArr #-}

    sameMutableArr :: forall s. MArr PrimArray s a -> MArr PrimArray s a -> Bool
sameMutableArr = forall s a. MutablePrimArray s a -> MutablePrimArray s a -> Bool
sameMutablePrimArray
    {-# INLINE sameMutableArr #-}
    sizeofArr :: PrimArray a -> Int
sizeofArr = forall a. Prim a => PrimArray a -> Int
sizeofPrimArray
    {-# INLINE sizeofArr #-}
    sizeofMutableArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
MArr PrimArray s a -> m Int
sizeofMutableArr = forall (m :: * -> *) a.
(PrimMonad m, Prim a) =>
MutablePrimArray (PrimState m) a -> m Int
getSizeofMutablePrimArray
    {-# INLINE sizeofMutableArr #-}

    sameArr :: PrimArray a -> PrimArray a -> Bool
sameArr (PrimArray ByteArray#
ba1#) (PrimArray ByteArray#
ba2#) =
        Int# -> Bool
isTrue# (forall d. MutableByteArray# d -> MutableByteArray# d -> Int#
sameMutableByteArray# (unsafeCoerce# :: forall a b. a -> b
unsafeCoerce# ByteArray#
ba1#) (unsafeCoerce# :: forall a b. a -> b
unsafeCoerce# ByteArray#
ba2#))
    {-# INLINE sameArr #-}

instance PrimUnlifted a => Arr UnliftedArray a where
    type MArr UnliftedArray = MutableUnliftedArray
    emptyArr :: Arr UnliftedArray a => UnliftedArray a
emptyArr = forall a. PrimUnlifted a => UnliftedArray a
emptyUnliftedArray
    {-# INLINE emptyArr #-}
    newArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
Int -> m (MArr UnliftedArray s a)
newArr = forall {k} (m :: * -> *) (a :: k).
PrimMonad m =>
Int -> m (MutableUnliftedArray (PrimState m) a)
unsafeNewUnliftedArray
    {-# INLINE newArr #-}
    newArrWith :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
Int -> a -> m (MArr UnliftedArray s a)
newArrWith = forall (m :: * -> *) a.
(PrimMonad m, PrimUnlifted a) =>
Int -> a -> m (MutableUnliftedArray (PrimState m) a)
newUnliftedArray
    {-# INLINE newArrWith #-}
    readArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
MArr UnliftedArray s a -> Int -> m a
readArr = forall (m :: * -> *) a.
(PrimMonad m, PrimUnlifted a) =>
MutableUnliftedArray (PrimState m) a -> Int -> m a
readUnliftedArray
    {-# INLINE readArr #-}
    writeArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
MArr UnliftedArray s a -> Int -> a -> m ()
writeArr = forall (m :: * -> *) a.
(PrimMonad m, PrimUnlifted a) =>
MutableUnliftedArray (PrimState m) a -> Int -> a -> m ()
writeUnliftedArray
    {-# INLINE writeArr #-}
    setArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
MArr UnliftedArray s a -> Int -> Int -> a -> m ()
setArr = forall (m :: * -> *) a.
(PrimMonad m, PrimUnlifted a) =>
MutableUnliftedArray (PrimState m) a -> Int -> Int -> a -> m ()
setUnliftedArray
    {-# INLINE setArr #-}
    indexArr :: UnliftedArray a -> Int -> a
indexArr = forall a. PrimUnlifted a => UnliftedArray a -> Int -> a
indexUnliftedArray
    {-# INLINE indexArr #-}
    indexArr' :: UnliftedArray a -> Int -> (# a #)
indexArr' UnliftedArray a
arr Int
i = (# forall a. PrimUnlifted a => UnliftedArray a -> Int -> a
indexUnliftedArray UnliftedArray a
arr Int
i #)
    {-# INLINE indexArr' #-}
    indexArrM :: forall (m :: * -> *). Monad m => UnliftedArray a -> Int -> m a
indexArrM UnliftedArray a
arr Int
i = forall (m :: * -> *) a. Monad m => a -> m a
return (forall a. PrimUnlifted a => UnliftedArray a -> Int -> a
indexUnliftedArray UnliftedArray a
arr Int
i)
    {-# INLINE indexArrM #-}
    freezeArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
MArr UnliftedArray s a -> Int -> Int -> m (UnliftedArray a)
freezeArr = forall {k} (m :: * -> *) (a :: k).
PrimMonad m =>
MutableUnliftedArray (PrimState m) a
-> Int -> Int -> m (UnliftedArray a)
freezeUnliftedArray
    {-# INLINE freezeArr #-}
    thawArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
UnliftedArray a -> Int -> Int -> m (MArr UnliftedArray s a)
thawArr = forall {k} (m :: * -> *) (a :: k).
PrimMonad m =>
UnliftedArray a
-> Int -> Int -> m (MutableUnliftedArray (PrimState m) a)
thawUnliftedArray
    {-# INLINE thawArr #-}
    unsafeFreezeArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
MArr UnliftedArray s a -> m (UnliftedArray a)
unsafeFreezeArr = forall {k} (m :: * -> *) (a :: k).
PrimMonad m =>
MutableUnliftedArray (PrimState m) a -> m (UnliftedArray a)
unsafeFreezeUnliftedArray
    {-# INLINE unsafeFreezeArr #-}
    unsafeThawArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
UnliftedArray a -> m (MArr UnliftedArray s a)
unsafeThawArr (UnliftedArray ArrayArray#
arr#) = forall (m :: * -> *) a.
PrimMonad m =>
(State# (PrimState m) -> (# State# (PrimState m), a #)) -> m a
primitive ( \ State# (PrimState m)
s0# ->
            let !(# State# s
s1#, MutableArray# s Any
marr# #) = forall a d.
Array# a -> State# d -> (# State# d, MutableArray# d a #)
unsafeThawArray# (unsafeCoerce# :: forall a b. a -> b
unsafeCoerce# ArrayArray#
arr#) State# (PrimState m)
s0#
                                                        -- ArrayArray# and Array# use the same representation
            in (# State# s
s1#, forall {k} s (a :: k).
MutableArrayArray# s -> MutableUnliftedArray s a
MutableUnliftedArray (unsafeCoerce# :: forall a b. a -> b
unsafeCoerce# MutableArray# s Any
marr#) #)    -- so this works
        )
    {-# INLINE unsafeThawArr #-}

    copyArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
MArr UnliftedArray s a
-> Int -> UnliftedArray a -> Int -> Int -> m ()
copyArr = forall {k} (m :: * -> *) (a :: k).
PrimMonad m =>
MutableUnliftedArray (PrimState m) a
-> Int -> UnliftedArray a -> Int -> Int -> m ()
copyUnliftedArray
    {-# INLINE copyArr #-}
    copyMutableArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
MArr UnliftedArray s a
-> Int -> MArr UnliftedArray s a -> Int -> Int -> m ()
copyMutableArr = forall {k} (m :: * -> *) (a :: k).
PrimMonad m =>
MutableUnliftedArray (PrimState m) a
-> Int
-> MutableUnliftedArray (PrimState m) a
-> Int
-> Int
-> m ()
copyMutableUnliftedArray
    {-# INLINE copyMutableArr #-}

    moveArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
MArr UnliftedArray s a
-> Int -> MArr UnliftedArray s a -> Int -> Int -> m ()
moveArr MArr UnliftedArray s a
marr1 Int
s1 MArr UnliftedArray s a
marr2 Int
s2 Int
l
        | Int
l forall a. Ord a => a -> a -> Bool
<= Int
0 = forall (m :: * -> *) a. Monad m => a -> m a
return ()
        | forall {k} s (a :: k).
MutableUnliftedArray s a -> MutableUnliftedArray s a -> Bool
sameMutableUnliftedArray MArr UnliftedArray s a
marr1 MArr UnliftedArray s a
marr2 =
            case forall a. Ord a => a -> a -> Ordering
compare Int
s1 Int
s2 of
                Ordering
LT ->
                    let !d :: Int
d = Int
s2 forall a. Num a => a -> a -> a
- Int
s1
                        !s2l :: Int
s2l = Int
s2 forall a. Num a => a -> a -> a
+ Int
l
                        go :: Int -> m ()
go !Int
i | Int
i forall a. Ord a => a -> a -> Bool
>= Int
s2l = forall (m :: * -> *) a. Monad m => a -> m a
return ()
                              | Bool
otherwise = do a
x <- forall (m :: * -> *) a.
(PrimMonad m, PrimUnlifted a) =>
MutableUnliftedArray (PrimState m) a -> Int -> m a
readUnliftedArray MArr UnliftedArray s a
marr2 Int
i
                                               forall (m :: * -> *) a.
(PrimMonad m, PrimUnlifted a) =>
MutableUnliftedArray (PrimState m) a -> Int -> a -> m ()
writeUnliftedArray MArr UnliftedArray s a
marr1 (Int
iforall a. Num a => a -> a -> a
-Int
d) a
x
                                               Int -> m ()
go (Int
iforall a. Num a => a -> a -> a
+Int
1)
                    in Int -> m ()
go Int
s2

                Ordering
EQ -> forall (m :: * -> *) a. Monad m => a -> m a
return ()

                Ordering
GT ->
                    let !d :: Int
d = Int
s1 forall a. Num a => a -> a -> a
- Int
s2
                        go :: Int -> m ()
go !Int
i | Int
i forall a. Ord a => a -> a -> Bool
< Int
s2 = forall (m :: * -> *) a. Monad m => a -> m a
return ()
                              | Bool
otherwise = do a
x <- forall (m :: * -> *) a.
(PrimMonad m, PrimUnlifted a) =>
MutableUnliftedArray (PrimState m) a -> Int -> m a
readUnliftedArray MArr UnliftedArray s a
marr2 Int
i
                                               forall (m :: * -> *) a.
(PrimMonad m, PrimUnlifted a) =>
MutableUnliftedArray (PrimState m) a -> Int -> a -> m ()
writeUnliftedArray MArr UnliftedArray s a
marr1 (Int
iforall a. Num a => a -> a -> a
+Int
d) a
x
                                               Int -> m ()
go (Int
iforall a. Num a => a -> a -> a
-Int
1)
                    in Int -> m ()
go (Int
s2forall a. Num a => a -> a -> a
+Int
lforall a. Num a => a -> a -> a
-Int
1)
        | Bool
otherwise = forall {k} (m :: * -> *) (a :: k).
PrimMonad m =>
MutableUnliftedArray (PrimState m) a
-> Int
-> MutableUnliftedArray (PrimState m) a
-> Int
-> Int
-> m ()
copyMutableUnliftedArray MArr UnliftedArray s a
marr1 Int
s1 MArr UnliftedArray s a
marr2 Int
s2 Int
l
    {-# INLINE moveArr #-}

    cloneArr :: UnliftedArray a -> Int -> Int -> UnliftedArray a
cloneArr = forall {k} (a :: k).
UnliftedArray a -> Int -> Int -> UnliftedArray a
cloneUnliftedArray
    {-# INLINE cloneArr #-}
    cloneMutableArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
MArr UnliftedArray s a -> Int -> Int -> m (MArr UnliftedArray s a)
cloneMutableArr = forall {k} (m :: * -> *) (a :: k).
PrimMonad m =>
MutableUnliftedArray (PrimState m) a
-> Int -> Int -> m (MutableUnliftedArray (PrimState m) a)
cloneMutableUnliftedArray
    {-# INLINE cloneMutableArr #-}

    resizeMutableArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
MArr UnliftedArray s a -> Int -> m (MArr UnliftedArray s a)
resizeMutableArr MArr UnliftedArray s a
marr Int
n = do
        MutableUnliftedArray s a
marr' <- forall (m :: * -> *) a.
(PrimMonad m, PrimUnlifted a) =>
Int -> a -> m (MutableUnliftedArray (PrimState m) a)
newUnliftedArray Int
n forall a. a
uninitialized
        forall {k} (m :: * -> *) (a :: k).
PrimMonad m =>
MutableUnliftedArray (PrimState m) a
-> Int
-> MutableUnliftedArray (PrimState m) a
-> Int
-> Int
-> m ()
copyMutableUnliftedArray MutableUnliftedArray s a
marr' Int
0 MArr UnliftedArray s a
marr Int
0 (forall {k} s (e :: k). MutableUnliftedArray s e -> Int
sizeofMutableUnliftedArray MArr UnliftedArray s a
marr)
        forall (m :: * -> *) a. Monad m => a -> m a
return MutableUnliftedArray s a
marr'
    {-# INLINE resizeMutableArr #-}
    shrinkMutableArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
MArr UnliftedArray s a -> Int -> m ()
shrinkMutableArr MArr UnliftedArray s a
_ Int
_ = forall (m :: * -> *) a. Monad m => a -> m a
return ()
    {-# INLINE shrinkMutableArr #-}

    sameMutableArr :: forall s. MArr UnliftedArray s a -> MArr UnliftedArray s a -> Bool
sameMutableArr = forall {k} s (a :: k).
MutableUnliftedArray s a -> MutableUnliftedArray s a -> Bool
sameMutableUnliftedArray
    {-# INLINE sameMutableArr #-}
    sizeofArr :: UnliftedArray a -> Int
sizeofArr = forall {k} (e :: k). UnliftedArray e -> Int
sizeofUnliftedArray
    {-# INLINE sizeofArr #-}
    sizeofMutableArr :: forall (m :: * -> *) s.
(PrimMonad m, PrimState m ~ s) =>
MArr UnliftedArray s a -> m Int
sizeofMutableArr = forall (m :: * -> *) a. Monad m => a -> m a
return forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall {k} s (e :: k). MutableUnliftedArray s e -> Int
sizeofMutableUnliftedArray
    {-# INLINE sizeofMutableArr #-}

    sameArr :: UnliftedArray a -> UnliftedArray a -> Bool
sameArr (UnliftedArray ArrayArray#
arr1#) (UnliftedArray ArrayArray#
arr2#) = Int# -> Bool
isTrue# (
        forall d. MutableArrayArray# d -> MutableArrayArray# d -> Int#
sameMutableArrayArray# (unsafeCoerce# :: forall a b. a -> b
unsafeCoerce# ArrayArray#
arr1#) (unsafeCoerce# :: forall a b. a -> b
unsafeCoerce# ArrayArray#
arr2#))
    {-# INLINE sameArr #-}

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

-- | Obtain the pointer to the content of an array, and the pointer should only be used during the IO action.
--
-- This operation is only safe on /pinned/ primitive arrays (Arrays allocated by 'newPinnedPrimArray' or
-- 'newAlignedPinnedPrimArray').
--
-- Don't pass a forever loop to this function, see <https://ghc.haskell.org/trac/ghc/ticket/14346 #14346>.
withPrimArrayContents :: PrimArray a -> (Ptr a -> IO b) -> IO b
{-# INLINE withPrimArrayContents #-}
withPrimArrayContents :: forall a b. PrimArray a -> (Ptr a -> IO b) -> IO b
withPrimArrayContents (PrimArray ByteArray#
ba#) Ptr a -> IO b
f = do
    let addr# :: Addr#
addr# = ByteArray# -> Addr#
byteArrayContents# ByteArray#
ba#
        ptr :: Ptr a
ptr = forall a. Addr# -> Ptr a
Ptr Addr#
addr#
    b
b <- Ptr a -> IO b
f Ptr a
ptr
    forall (m :: * -> *).
PrimMonad m =>
(State# (PrimState m) -> State# (PrimState m)) -> m ()
primitive_ (touch# :: forall a. a -> State# RealWorld -> State# RealWorld
touch# ByteArray#
ba#)
    forall (m :: * -> *) a. Monad m => a -> m a
return b
b

-- | Obtain the pointer to the content of an mutable array, and the pointer should only be used during the IO action.
--
-- This operation is only safe on /pinned/ primitive arrays (Arrays allocated by 'newPinnedPrimArray' or
-- 'newAlignedPinnedPrimArray').
--
-- Don't pass a forever loop to this function, see <https://ghc.haskell.org/trac/ghc/ticket/14346 #14346>.
withMutablePrimArrayContents :: MutablePrimArray RealWorld a -> (Ptr a -> IO b) -> IO b
{-# INLINE withMutablePrimArrayContents #-}
withMutablePrimArrayContents :: forall a b. MutablePrimArray RealWorld a -> (Ptr a -> IO b) -> IO b
withMutablePrimArrayContents (MutablePrimArray MutableByteArray# RealWorld
mba#) Ptr a -> IO b
f = do
    let addr# :: Addr#
addr# = ByteArray# -> Addr#
byteArrayContents# (unsafeCoerce# :: forall a b. a -> b
unsafeCoerce# MutableByteArray# RealWorld
mba#)
        ptr :: Ptr a
ptr = forall a. Addr# -> Ptr a
Ptr Addr#
addr#
    b
b <- Ptr a -> IO b
f Ptr a
ptr
    forall (m :: * -> *).
PrimMonad m =>
(State# (PrimState m) -> State# (PrimState m)) -> m ()
primitive_ (touch# :: forall a. a -> State# RealWorld -> State# RealWorld
touch# MutableByteArray# RealWorld
mba#)
    forall (m :: * -> *) a. Monad m => a -> m a
return b
b

-- | Cast between arrays
castArray :: (Arr arr a, Cast a b) => arr a -> arr b
{-# INLINE castArray #-}
castArray :: forall (arr :: * -> *) a b. (Arr arr a, Cast a b) => arr a -> arr b
castArray = unsafeCoerce# :: forall a b. a -> b
unsafeCoerce#


-- | Cast between mutable arrays
castMutableArray :: (Arr arr a, Cast a b) => MArr arr s a -> MArr arr s b
{-# INLINE castMutableArray #-}
castMutableArray :: forall (arr :: * -> *) a b s.
(Arr arr a, Cast a b) =>
MArr arr s a -> MArr arr s b
castMutableArray = unsafeCoerce# :: forall a b. a -> b
unsafeCoerce#

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

singletonArr :: Arr arr a => a -> arr a
{-# INLINE singletonArr #-}
singletonArr :: forall (arr :: * -> *) a. Arr arr a => a -> arr a
singletonArr a
x = forall a. (forall s. ST s a) -> a
runST forall a b. (a -> b) -> a -> b
$ do
    MArr arr s a
marr <- forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
Int -> a -> m (MArr arr s a)
newArrWith Int
1 a
x
    forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> m (arr a)
unsafeFreezeArr MArr arr s a
marr

doubletonArr :: Arr arr a => a -> a -> arr a
{-# INLINE doubletonArr #-}
doubletonArr :: forall (arr :: * -> *) a. Arr arr a => a -> a -> arr a
doubletonArr a
x a
y = forall a. (forall s. ST s a) -> a
runST forall a b. (a -> b) -> a -> b
$ do
    MArr arr s a
marr <- forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
Int -> a -> m (MArr arr s a)
newArrWith Int
2 a
x
    forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr arr s a
marr Int
1 a
y
    forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> m (arr a)
unsafeFreezeArr MArr arr s a
marr

-- | Modify(strictly) an immutable some elements of an array with specified subrange.
-- This function will produce a new array.
modifyIndexArr :: Arr arr a
               => arr a
               -> Int        -- ^ offset
               -> Int        -- ^ length
               -> Int        -- ^ index in new array
               -> (a -> a)   -- ^ modify function
               -> arr a
{-# INLINE modifyIndexArr #-}
modifyIndexArr :: forall (arr :: * -> *) a.
Arr arr a =>
arr a -> Int -> Int -> Int -> (a -> a) -> arr a
modifyIndexArr arr a
arr Int
off Int
len Int
ix a -> a
f = forall a. (forall s. ST s a) -> a
runST forall a b. (a -> b) -> a -> b
$ do
    MArr arr s a
marr <- forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
arr a -> m (MArr arr s a)
unsafeThawArr (forall (arr :: * -> *) a. Arr arr a => arr a -> Int -> Int -> arr a
cloneArr arr a
arr Int
off Int
len)
    !a
v <- a -> a
f forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> Int -> m a
readArr MArr arr s a
marr Int
ix
    forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr arr s a
marr Int
ix a
v
    forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> m (arr a)
unsafeFreezeArr MArr arr s a
marr

-- | Insert a value to an immutable array at given index. This function will produce a new array.
insertIndexArr :: Arr arr a
               => arr a
               -> Int        -- ^ offset
               -> Int        -- ^ length
               -> Int        -- ^ insert index in new array
               -> a          -- ^ value to be inserted
               -> arr a
{-# INLINE insertIndexArr #-}
insertIndexArr :: forall (arr :: * -> *) a.
Arr arr a =>
arr a -> Int -> Int -> Int -> a -> arr a
insertIndexArr arr a
arr Int
s Int
l Int
i a
x = forall a. (forall s. ST s a) -> a
runST forall a b. (a -> b) -> a -> b
$ do
    MArr arr s a
marr <- forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
Int -> a -> m (MArr arr s a)
newArrWith (Int
lforall a. Num a => a -> a -> a
+Int
1) a
x
    forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (Int
iforall a. Ord a => a -> a -> Bool
>Int
0) forall a b. (a -> b) -> a -> b
$ forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> Int -> arr a -> Int -> Int -> m ()
copyArr MArr arr s a
marr Int
0 arr a
arr Int
s Int
i
    forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (Int
iforall a. Ord a => a -> a -> Bool
<Int
l) forall a b. (a -> b) -> a -> b
$ forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> Int -> arr a -> Int -> Int -> m ()
copyArr MArr arr s a
marr (Int
iforall a. Num a => a -> a -> a
+Int
1) arr a
arr (Int
iforall a. Num a => a -> a -> a
+Int
s) (Int
lforall a. Num a => a -> a -> a
-Int
i)
    forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> m (arr a)
unsafeFreezeArr MArr arr s a
marr

-- | Delete an element of the immutable array's at given index. This function will produce a new array.
deleteIndexArr :: Arr arr a
               => arr a
               -> Int        -- ^ offset
               -> Int        -- ^ length
               -> Int        -- ^ the index of the element to delete
               -> arr a
{-# INLINE deleteIndexArr #-}
deleteIndexArr :: forall (arr :: * -> *) a.
Arr arr a =>
arr a -> Int -> Int -> Int -> arr a
deleteIndexArr arr a
arr Int
s Int
l Int
i = forall a. (forall s. ST s a) -> a
runST forall a b. (a -> b) -> a -> b
$ do
    MArr arr s a
marr <- forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
Int -> m (MArr arr s a)
newArr (Int
lforall a. Num a => a -> a -> a
-Int
1)
    forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (Int
iforall a. Ord a => a -> a -> Bool
>Int
0) forall a b. (a -> b) -> a -> b
$ forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> Int -> arr a -> Int -> Int -> m ()
copyArr MArr arr s a
marr Int
0 arr a
arr Int
s Int
i
    let i' :: Int
i' = Int
iforall a. Num a => a -> a -> a
+Int
1
    forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (Int
i'forall a. Ord a => a -> a -> Bool
<Int
l) forall a b. (a -> b) -> a -> b
$ forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> Int -> arr a -> Int -> Int -> m ()
copyArr MArr arr s a
marr Int
i arr a
arr (Int
i'forall a. Num a => a -> a -> a
+Int
s) (Int
lforall a. Num a => a -> a -> a
-Int
i')
    forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> m (arr a)
unsafeFreezeArr MArr arr s a
marr

-- | Swap two elements under given index and return a new array.
swapArr :: Arr arr a
             => arr a
             -> Int
             -> Int
             -> arr a
{-# INLINE swapArr #-}
swapArr :: forall (arr :: * -> *) a. Arr arr a => arr a -> Int -> Int -> arr a
swapArr arr a
arr Int
i Int
j = forall a. (forall s. ST s a) -> a
runST forall a b. (a -> b) -> a -> b
$ do
    MArr arr s a
marr <- forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
arr a -> Int -> Int -> m (MArr arr s a)
thawArr arr a
arr Int
0 (forall (arr :: * -> *) a. Arr arr a => arr a -> Int
sizeofArr arr a
arr)
    forall (m :: * -> *) s (arr :: * -> *) a.
(PrimMonad m, PrimState m ~ s, Arr arr a) =>
MArr arr s a -> Int -> Int -> m ()
swapMutableArr MArr arr s a
marr Int
i Int
j
    forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> m (arr a)
unsafeFreezeArr MArr arr s a
marr

-- | Swap two elements under given index, no atomically guarantee is given.
swapMutableArr :: (PrimMonad m, PrimState m ~ s, Arr arr a)
             => MArr arr s a
             -> Int
             -> Int
             -> m ()
{-# INLINE swapMutableArr #-}
swapMutableArr :: forall (m :: * -> *) s (arr :: * -> *) a.
(PrimMonad m, PrimState m ~ s, Arr arr a) =>
MArr arr s a -> Int -> Int -> m ()
swapMutableArr MArr arr s a
marr Int
i Int
j = do
    a
x <- forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> Int -> m a
readArr MArr arr s a
marr Int
i
    a
y <- forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> Int -> m a
readArr MArr arr s a
marr Int
j
    forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr arr s a
marr Int
i a
y
    forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr arr s a
marr Int
j a
x

-- | Resize mutable array to @max (given_size) (2 * original_size)@ if orignal array is smaller than @give_size@.
doubleMutableArr :: (Arr arr a, PrimMonad m, PrimState m ~ s) => MArr arr s a -> Int -> m (MArr arr s a)
{-# INLINE doubleMutableArr #-}
doubleMutableArr :: forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> Int -> m (MArr arr s a)
doubleMutableArr MArr arr s a
marr Int
l = do
    Int
siz <- forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> m Int
sizeofMutableArr MArr arr s a
marr
    if (Int
siz forall a. Ord a => a -> a -> Bool
< Int
l)
    then forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> Int -> m (MArr arr s a)
resizeMutableArr MArr arr s a
marr (forall a. Ord a => a -> a -> a
max (Int
siz forall a. Bits a => a -> Int -> a
`unsafeShiftL` Int
1) Int
l)
    else forall (m :: * -> *) a. Monad m => a -> m a
return MArr arr s a
marr


-- | Shuffle array's elements in slice range.
--
-- This function use <https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle Fisher-Yates> algorithm.
shuffleMutableArr :: (StatefulGen g m, PrimMonad m, PrimState m ~ s, Arr arr a) => g -> MArr arr s a
            -> Int  -- ^ offset
            -> Int  -- ^ length
            -> m ()
{-# INLINE shuffleMutableArr #-}
shuffleMutableArr :: forall g (m :: * -> *) s (arr :: * -> *) a.
(StatefulGen g m, PrimMonad m, PrimState m ~ s, Arr arr a) =>
g -> MArr arr s a -> Int -> Int -> m ()
shuffleMutableArr g
g MArr arr s a
marr Int
off Int
n = Int -> m ()
go (Int
offforall a. Num a => a -> a -> a
+Int
nforall a. Num a => a -> a -> a
-Int
1)
  where
    go :: Int -> m ()
go Int
i | Int
i forall a. Ord a => a -> a -> Bool
< Int
offforall a. Num a => a -> a -> a
+Int
1 = forall (m :: * -> *) a. Monad m => a -> m a
return ()
         | Bool
otherwise = do
            Int
j <- forall a g (m :: * -> *).
(UniformRange a, StatefulGen g m) =>
(a, a) -> g -> m a
uniformRM (Int
off, Int
i) g
g
            forall (m :: * -> *) s (arr :: * -> *) a.
(PrimMonad m, PrimState m ~ s, Arr arr a) =>
MArr arr s a -> Int -> Int -> m ()
swapMutableArr MArr arr s a
marr Int
i Int
j
            Int -> m ()
go (Int
i forall a. Num a => a -> a -> a
- Int
1)