{-# LANGUAGE BangPatterns, CPP, MagicHash, Rank2Types, UnboxedTuples #-}
{-# OPTIONS_GHC -funbox-strict-fields #-}
-- |
-- Module: Data.Vector.Persistent.Array
-- Copyright: Johan Tibell <johan.tibell@gmail.com>
-- License: BSD3
--
-- Zero based arrays.
--
-- Note that no bounds checking are performed.
module Data.Vector.Persistent.Array
    ( Array
    , MArray

      -- * Creation
    , new
    , new_
    , empty
    , singleton
    , singleton'
    , pair

      -- * Basic interface
    , length
    , lengthM
    , read
    , write
    , index
    , index#
    , index_
    , indexM_
    , update
    , update'
    , updateWith
    , unsafeUpdate'
    , insert
    , insert'
    , delete
    , delete'

    , unsafeFreeze
    , unsafeThaw
    , run
    , run2
    , copy
    , copyM

      -- * Folds
    , foldl
    , foldl'
    , boundedFoldl'
    , foldr
    , foldr'
    , boundedFoldr

    , thaw
    , map
    , map'
    , traverseArray
    , filter
    , fromList
    , fromListRev
    , toList
    ) where

import qualified Data.Traversable as Traversable
import qualified Control.Applicative as A
import Control.DeepSeq
import Control.Monad.ST
import qualified GHC.Exts as Ext
import GHC.ST (ST(..))
import Prelude hiding (filter, foldl, foldr, length, map, read)
import qualified Data.Foldable as F
#if !MIN_VERSION_base(4,8,0)
import Data.Monoid (mappend)
#endif

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

#if defined(ASSERTS)
-- This fugly hack is brought by GHC's apparent reluctance to deal
-- with MagicHash and UnboxedTuples when inferring types. Eek!
# define CHECK_BOUNDS(_func_,_len_,_k_) \
if (_k_) < 0 || (_k_) >= (_len_) then error ("Data.HashMap.Array." ++ (_func_) ++ ": bounds error, offset " ++ show (_k_) ++ ", length " ++ show (_len_)) else
# define CHECK_OP(_func_,_op_,_lhs_,_rhs_) \
if not ((_lhs_) _op_ (_rhs_)) then error ("Data.HashMap.Array." ++ (_func_) ++ ": Check failed: _lhs_ _op_ _rhs_ (" ++ show (_lhs_) ++ " vs. " ++ show (_rhs_) ++ ")") else
# define CHECK_GT(_func_,_lhs_,_rhs_) CHECK_OP(_func_,>,_lhs_,_rhs_)
# define CHECK_GE(_func_,_lhs_,_rhs_) CHECK_OP(_func_,>=,_lhs_,_rhs_)
# define CHECK_LE(_func_,_lhs_,_rhs_) CHECK_OP(_func_,<=,_lhs_,_rhs_)
#else
# define CHECK_BOUNDS(_func_,_len_,_k_)
# define CHECK_OP(_func_,_op_,_lhs_,_rhs_)
# define CHECK_GT(_func_,_lhs_,_rhs_)
# define CHECK_GE(_func_,_lhs_,_rhs_)
# define CHECK_LE(_func_,_lhs_,_rhs_)
#endif

data Array a = Array {
      Array a -> Array# a
unArray :: !(Ext.Array# a)
#if __GLASGOW_HASKELL__ < 702
    , length :: !Int
#endif
    }

instance Show a => Show (Array a) where
    show :: Array a -> String
show = [a] -> String
forall a. Show a => a -> String
show ([a] -> String) -> (Array a -> [a]) -> Array a -> String
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Array a -> [a]
forall a. Array a -> [a]
toList

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
arrayEq

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
arrayCompare

arrayEq :: Eq a => Array a -> Array a -> Bool
{-# INLINABLE arrayEq #-}
arrayEq :: Array a -> Array a -> Bool
arrayEq Array a
a1 Array a
a2 = Array a -> Int
forall a. Array a -> Int
length Array a
a1 Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Array a -> Int
forall a. Array a -> Int
length Array a
a2 Bool -> Bool -> Bool
&&
  (Int -> Bool) -> [Int] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
F.all (\Int
i -> Array a -> Int -> a
forall a. Array a -> Int -> a
index Array a
a1 Int
i a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== Array a -> Int -> a
forall a. Array a -> Int -> a
index Array a
a2 Int
i) [Int
0..(Array a -> Int
forall a. Array a -> Int
length Array a
a1 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)]

arrayCompare :: Ord a => Array a -> Array a -> Ordering
{-# INLINABLE arrayCompare #-}
arrayCompare :: Array a -> Array a -> Ordering
arrayCompare Array a
a1 Array a
a2 = Int -> Int -> Ordering
forall a. Ord a => a -> a -> Ordering
compare (Array a -> Int
forall a. Array a -> Int
length Array a
a1) (Array a -> Int
forall a. Array a -> Int
length Array a
a2) Ordering -> Ordering -> Ordering
forall a. Monoid a => a -> a -> a
`mappend`
  (Int -> Ordering) -> [Int] -> Ordering
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
F.foldMap (\Int
i -> Array a -> Int -> a
forall a. Array a -> Int -> a
index Array a
a1 Int
i a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
`compare` Array a -> Int -> a
forall a. Array a -> Int -> a
index Array a
a2 Int
i) [Int
0..(Array a -> Int
forall a. Array a -> Int
length Array a
a1 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)]

#if __GLASGOW_HASKELL__ >= 702
length :: Array a -> Int
length :: Array a -> Int
length Array a
ary = Int# -> Int
Ext.I# (Array# a -> Int#
forall a. Array# a -> Int#
Ext.sizeofArray# (Array a -> Array# a
forall a. Array a -> Array# a
unArray Array a
ary))
{-# INLINE length #-}
#endif

-- | Smart constructor
array :: Ext.Array# a -> Int -> Array a
#if __GLASGOW_HASKELL__ >= 702
array :: Array# a -> Int -> Array a
array Array# a
ary Int
_n = Array# a -> Array a
forall a. Array# a -> Array a
Array Array# a
ary
#else
array = Array
#endif
{-# INLINE array #-}

data MArray s a = MArray {
      MArray s a -> MutableArray# s a
unMArray :: !(Ext.MutableArray# s a)
#if __GLASGOW_HASKELL__ < 702
    , lengthM :: !Int
#endif
    }

#if __GLASGOW_HASKELL__ >= 702
lengthM :: MArray s a -> Int
lengthM :: MArray s a -> Int
lengthM MArray s a
mary = Int# -> Int
Ext.I# (MutableArray# s a -> Int#
forall d a. MutableArray# d a -> Int#
Ext.sizeofMutableArray# (MArray s a -> MutableArray# s a
forall s a. MArray s a -> MutableArray# s a
unMArray MArray s a
mary))
{-# INLINE lengthM #-}
#endif

-- | Smart constructor
marray :: Ext.MutableArray# s a -> Int -> MArray s a
#if __GLASGOW_HASKELL__ >= 702
marray :: MutableArray# s a -> Int -> MArray s a
marray MutableArray# s a
mary Int
_n = MutableArray# s a -> MArray s a
forall s a. MutableArray# s a -> MArray s a
MArray MutableArray# s a
mary
#else
marray = MArray
#endif
{-# INLINE marray #-}

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

instance NFData a => NFData (Array a) where
    rnf :: Array a -> ()
rnf = Array a -> ()
forall a. NFData a => Array a -> ()
rnfArray

rnfArray :: NFData a => Array a -> ()
rnfArray :: Array a -> ()
rnfArray Array a
ary0 = Array a -> Int -> Int -> ()
forall a. NFData a => Array a -> Int -> Int -> ()
go Array a
ary0 Int
n0 Int
0
  where
    n0 :: Int
n0 = Array a -> Int
forall a. Array a -> Int
length Array a
ary0
    go :: Array a -> Int -> Int -> ()
go !Array a
ary !Int
n !Int
i
        | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
n = ()
        | Bool
otherwise = a -> ()
forall a. NFData a => a -> ()
rnf (Array a -> Int -> a
forall a. Array a -> Int -> a
index Array a
ary Int
i) () -> () -> ()
`seq` Array a -> Int -> Int -> ()
go Array a
ary Int
n (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1)
{-# INLINE rnfArray #-}

-- | Create a new mutable array of specified size, in the specified
-- state thread, with each element containing the specified initial
-- value.
new :: Int -> a -> ST s (MArray s a)
new :: Int -> a -> ST s (MArray s a)
new n :: Int
n@(Ext.I# Int#
n#) a
b =
    CHECK_GE("new",n,(0 :: Int))
    STRep s (MArray s a) -> ST s (MArray s a)
forall s a. STRep s a -> ST s a
ST (STRep s (MArray s a) -> ST s (MArray s a))
-> STRep s (MArray s a) -> ST s (MArray s a)
forall a b. (a -> b) -> a -> b
$ \State# s
s ->
        case Int# -> a -> State# s -> (# State# s, MutableArray# s a #)
forall a d.
Int# -> a -> State# d -> (# State# d, MutableArray# d a #)
Ext.newArray# Int#
n# a
b State# s
s of
            (# State# s
s', MutableArray# s a
ary #) -> (# State# s
s', MutableArray# s a -> Int -> MArray s a
forall s a. MutableArray# s a -> Int -> MArray s a
marray MutableArray# s a
ary Int
n #)
{-# INLINE new #-}

new_ :: Int -> ST s (MArray s a)
new_ :: Int -> ST s (MArray s a)
new_ Int
n = Int -> a -> ST s (MArray s a)
forall a s. Int -> a -> ST s (MArray s a)
new Int
n a
forall a. a
undefinedElem

-- The globally shared empty array. There's no point
-- allocating a new empty array every time we need one
-- when we can just follow a pointer to get one.
empty :: Array a
empty :: Array a
empty = (forall s. ST s (Array a)) -> Array a
forall a. (forall s. ST s a) -> a
runST (Int -> ST s (MArray s a)
forall s a. Int -> ST s (MArray s a)
new_ Int
0 ST s (MArray s a)
-> (MArray s a -> ST s (Array a)) -> ST s (Array a)
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= MArray s a -> ST s (Array a)
forall s a. MArray s a -> ST s (Array a)
unsafeFreeze)
{-# NOINLINE empty #-}

singleton :: a -> Array a
singleton :: a -> Array a
singleton a
x = (forall s. ST s (Array a)) -> Array a
forall a. (forall s. ST s a) -> a
runST (a -> ST s (Array a)
forall a s. a -> ST s (Array a)
singleton' a
x)
{-# INLINE singleton #-}

singleton' :: a -> ST s (Array a)
singleton' :: a -> ST s (Array a)
singleton' a
x = Int -> a -> ST s (MArray s a)
forall a s. Int -> a -> ST s (MArray s a)
new Int
1 a
x ST s (MArray s a)
-> (MArray s a -> ST s (Array a)) -> ST s (Array a)
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= MArray s a -> ST s (Array a)
forall s a. MArray s a -> ST s (Array a)
unsafeFreeze
{-# INLINE singleton' #-}

pair :: a -> a -> Array a
pair :: a -> a -> Array a
pair a
x a
y = (forall s. ST s (MArray s a)) -> Array a
forall e. (forall s. ST s (MArray s e)) -> Array e
run ((forall s. ST s (MArray s a)) -> Array a)
-> (forall s. ST s (MArray s a)) -> Array a
forall a b. (a -> b) -> a -> b
$ do
    MArray s a
ary <- Int -> a -> ST s (MArray s a)
forall a s. Int -> a -> ST s (MArray s a)
new Int
2 a
x
    MArray s a -> Int -> a -> ST s ()
forall s a. MArray s a -> Int -> a -> ST s ()
write MArray s a
ary Int
1 a
y
    MArray s a -> ST s (MArray s a)
forall (m :: * -> *) a. Monad m => a -> m a
return MArray s a
ary
{-# INLINE pair #-}

read :: MArray s a -> Int -> ST s a
read :: MArray s a -> Int -> ST s a
read MArray s a
ary _i :: Int
_i@(Ext.I# Int#
i#) = STRep s a -> ST s a
forall s a. STRep s a -> ST s a
ST (STRep s a -> ST s a) -> STRep s a -> ST s a
forall a b. (a -> b) -> a -> b
$ \ State# s
s ->
    CHECK_BOUNDS("read", lengthM ary, _i)
        MutableArray# s a -> Int# -> STRep s a
forall d a.
MutableArray# d a -> Int# -> State# d -> (# State# d, a #)
Ext.readArray# (MArray s a -> MutableArray# s a
forall s a. MArray s a -> MutableArray# s a
unMArray MArray s a
ary) Int#
i# State# s
s
{-# INLINE read #-}

write :: MArray s a -> Int -> a -> ST s ()
write :: MArray s a -> Int -> a -> ST s ()
write MArray s a
ary _i :: Int
_i@(Ext.I# Int#
i#) a
b = STRep s () -> ST s ()
forall s a. STRep s a -> ST s a
ST (STRep s () -> ST s ()) -> STRep s () -> ST s ()
forall a b. (a -> b) -> a -> b
$ \ State# s
s ->
    CHECK_BOUNDS("write", lengthM ary, _i)
        case MutableArray# s a -> Int# -> a -> State# s -> State# s
forall d a. MutableArray# d a -> Int# -> a -> State# d -> State# d
Ext.writeArray# (MArray s a -> MutableArray# s a
forall s a. MArray s a -> MutableArray# s a
unMArray MArray s a
ary) Int#
i# a
b State# s
s of
            State# s
s' -> (# State# s
s' , () #)
{-# INLINE write #-}

index :: Array a -> Int -> a
index :: Array a -> Int -> a
index Array a
ary _i :: Int
_i@(Ext.I# Int#
i#) =
    CHECK_BOUNDS("index", length ary, _i)
        case Array# a -> Int# -> (# a #)
forall a. Array# a -> Int# -> (# a #)
Ext.indexArray# (Array a -> Array# a
forall a. Array a -> Array# a
unArray Array a
ary) Int#
i# of (# a
b #) -> a
b
{-# INLINE index #-}

index# :: Array a -> Int -> (# a #)
index# :: Array a -> Int -> (# a #)
index# Array a
ary _i :: Int
_i@(Ext.I# Int#
i#) =
    CHECK_BOUNDS("index", length ary, _i)
        Array# a -> Int# -> (# a #)
forall a. Array# a -> Int# -> (# a #)
Ext.indexArray# (Array a -> Array# a
forall a. Array a -> Array# a
unArray Array a
ary) Int#
i#
{-# INLINE index# #-}

index_ :: Array a -> Int -> ST s a
index_ :: Array a -> Int -> ST s a
index_ Array a
ary _i :: Int
_i@(Ext.I# Int#
i#) =
    CHECK_BOUNDS("index_", length ary, _i)
        case Array# a -> Int# -> (# a #)
forall a. Array# a -> Int# -> (# a #)
Ext.indexArray# (Array a -> Array# a
forall a. Array a -> Array# a
unArray Array a
ary) Int#
i# of (# a
b #) -> a -> ST s a
forall (m :: * -> *) a. Monad m => a -> m a
return a
b
{-# INLINE index_ #-}

indexM_ :: MArray s a -> Int -> ST s a
indexM_ :: MArray s a -> Int -> ST s a
indexM_ MArray s a
ary _i :: Int
_i@(Ext.I# Int#
i#) =
    CHECK_BOUNDS("index_", lengthM ary, _i)
        STRep s a -> ST s a
forall s a. STRep s a -> ST s a
ST (STRep s a -> ST s a) -> STRep s a -> ST s a
forall a b. (a -> b) -> a -> b
$ \ State# s
s# -> MutableArray# s a -> Int# -> STRep s a
forall d a.
MutableArray# d a -> Int# -> State# d -> (# State# d, a #)
Ext.readArray# (MArray s a -> MutableArray# s a
forall s a. MArray s a -> MutableArray# s a
unMArray MArray s a
ary) Int#
i# State# s
s#
{-# INLINE indexM_ #-}

unsafeFreeze :: MArray s a -> ST s (Array a)
unsafeFreeze :: MArray s a -> ST s (Array a)
unsafeFreeze MArray s a
mary
    = STRep s (Array a) -> ST s (Array a)
forall s a. STRep s a -> ST s a
ST (STRep s (Array a) -> ST s (Array a))
-> STRep s (Array a) -> ST s (Array a)
forall a b. (a -> b) -> a -> b
$ \State# s
s -> case MutableArray# s a -> State# s -> (# State# s, Array# a #)
forall d a.
MutableArray# d a -> State# d -> (# State# d, Array# a #)
Ext.unsafeFreezeArray# (MArray s a -> MutableArray# s a
forall s a. MArray s a -> MutableArray# s a
unMArray MArray s a
mary) State# s
s of
                   (# State# s
s', Array# a
ary #) -> (# State# s
s', Array# a -> Int -> Array a
forall a. Array# a -> Int -> Array a
array Array# a
ary (MArray s a -> Int
forall s a. MArray s a -> Int
lengthM MArray s a
mary) #)
{-# INLINE unsafeFreeze #-}

unsafeThaw :: Array a -> ST s (MArray s a)
unsafeThaw :: Array a -> ST s (MArray s a)
unsafeThaw Array a
ary
    = STRep s (MArray s a) -> ST s (MArray s a)
forall s a. STRep s a -> ST s a
ST (STRep s (MArray s a) -> ST s (MArray s a))
-> STRep s (MArray s a) -> ST s (MArray s a)
forall a b. (a -> b) -> a -> b
$ \State# s
s -> case Array# a -> State# s -> (# State# s, MutableArray# s a #)
forall a d.
Array# a -> State# d -> (# State# d, MutableArray# d a #)
Ext.unsafeThawArray# (Array a -> Array# a
forall a. Array a -> Array# a
unArray Array a
ary) State# s
s of
                   (# State# s
s', MutableArray# s a
mary #) -> (# State# s
s', MutableArray# s a -> Int -> MArray s a
forall s a. MutableArray# s a -> Int -> MArray s a
marray MutableArray# s a
mary (Array a -> Int
forall a. Array a -> Int
length Array a
ary) #)
{-# INLINE unsafeThaw #-}

run :: (forall s . ST s (MArray s e)) -> Array e
run :: (forall s. ST s (MArray s e)) -> Array e
run forall s. ST s (MArray s e)
act = (forall s. ST s (Array e)) -> Array e
forall a. (forall s. ST s a) -> a
runST ((forall s. ST s (Array e)) -> Array e)
-> (forall s. ST s (Array e)) -> Array e
forall a b. (a -> b) -> a -> b
$ ST s (MArray s e)
forall s. ST s (MArray s e)
act ST s (MArray s e)
-> (MArray s e -> ST s (Array e)) -> ST s (Array e)
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= MArray s e -> ST s (Array e)
forall s a. MArray s a -> ST s (Array a)
unsafeFreeze
{-# INLINE run #-}

run2 :: (forall s. ST s (MArray s e, a)) -> (Array e, a)
run2 :: (forall s. ST s (MArray s e, a)) -> (Array e, a)
run2 forall s. ST s (MArray s e, a)
k = (forall s. ST s (Array e, a)) -> (Array e, a)
forall a. (forall s. ST s a) -> a
runST (do
                 (MArray s e
marr,a
b) <- ST s (MArray s e, a)
forall s. ST s (MArray s e, a)
k
                 Array e
arr <- MArray s e -> ST s (Array e)
forall s a. MArray s a -> ST s (Array a)
unsafeFreeze MArray s e
marr
                 (Array e, a) -> ST s (Array e, a)
forall (m :: * -> *) a. Monad m => a -> m a
return (Array e
arr,a
b))

-- | Unsafely copy the elements of an array. Array bounds are not checked.
copy :: Array e -> Int -> MArray s e -> Int -> Int -> ST s ()
#if __GLASGOW_HASKELL__ >= 702
copy :: Array e -> Int -> MArray s e -> Int -> Int -> ST s ()
copy !Array e
src !_sidx :: Int
_sidx@(Ext.I# Int#
sidx#) !MArray s e
dst !_didx :: Int
_didx@(Ext.I# Int#
didx#) _n :: Int
_n@(Ext.I# Int#
n#) =
    CHECK_LE("copy", _sidx + _n, length src)
    CHECK_LE("copy", _didx + _n, lengthM dst)
        STRep s () -> ST s ()
forall s a. STRep s a -> ST s a
ST (STRep s () -> ST s ()) -> STRep s () -> ST s ()
forall a b. (a -> b) -> a -> b
$ \ State# s
s# ->
        case Array# e
-> Int#
-> MutableArray# s e
-> Int#
-> Int#
-> State# s
-> State# s
forall a d.
Array# a
-> Int#
-> MutableArray# d a
-> Int#
-> Int#
-> State# d
-> State# d
Ext.copyArray# (Array e -> Array# e
forall a. Array a -> Array# a
unArray Array e
src) Int#
sidx# (MArray s e -> MutableArray# s e
forall s a. MArray s a -> MutableArray# s a
unMArray MArray s e
dst) Int#
didx# Int#
n# State# s
s# of
            State# s
s2 -> (# State# s
s2, () #)
#else
copy !src !sidx !dst !didx n =
    CHECK_LE("copy", sidx + n, length src)
    CHECK_LE("copy", didx + n, lengthM dst)
        copy_loop sidx didx 0
  where
    copy_loop !i !j !c
        | c >= n = return ()
        | otherwise = do b <- index_ src i
                         write dst j b
                         copy_loop (i+1) (j+1) (c+1)
#endif

-- | Unsafely copy the elements of an array. Array bounds are not checked.
copyM :: MArray s e -> Int -> MArray s e -> Int -> Int -> ST s ()
#if __GLASGOW_HASKELL__ >= 702
copyM :: MArray s e -> Int -> MArray s e -> Int -> Int -> ST s ()
copyM !MArray s e
src !_sidx :: Int
_sidx@(Ext.I# Int#
sidx#) !MArray s e
dst !_didx :: Int
_didx@(Ext.I# Int#
didx#) _n :: Int
_n@(Ext.I# Int#
n#) =
    CHECK_BOUNDS("copyM: src", lengthM src, _sidx + _n - 1)
    CHECK_BOUNDS("copyM: dst", lengthM dst, _didx + _n - 1)
    STRep s () -> ST s ()
forall s a. STRep s a -> ST s a
ST (STRep s () -> ST s ()) -> STRep s () -> ST s ()
forall a b. (a -> b) -> a -> b
$ \ State# s
s# ->
    case MutableArray# s e
-> Int#
-> MutableArray# s e
-> Int#
-> Int#
-> State# s
-> State# s
forall d a.
MutableArray# d a
-> Int#
-> MutableArray# d a
-> Int#
-> Int#
-> State# d
-> State# d
Ext.copyMutableArray# (MArray s e -> MutableArray# s e
forall s a. MArray s a -> MutableArray# s a
unMArray MArray s e
src) Int#
sidx# (MArray s e -> MutableArray# s e
forall s a. MArray s a -> MutableArray# s a
unMArray MArray s e
dst) Int#
didx# Int#
n# State# s
s# of
        State# s
s2 -> (# State# s
s2, () #)
#else
copyM !src !sidx !dst !didx n =
    CHECK_BOUNDS("copyM: src", lengthM src, sidx + n - 1)
    CHECK_BOUNDS("copyM: dst", lengthM dst, didx + n - 1)
    copy_loop sidx didx 0
  where
    copy_loop !i !j !c
        | c >= n = return ()
        | otherwise = do b <- indexM_ src i
                         write dst j b
                         copy_loop (i+1) (j+1) (c+1)
#endif

-- | /O(n)/ Insert an element at the given position in this array,
-- increasing its size by one.
insert :: Array e -> Int -> e -> Array e
insert :: Array e -> Int -> e -> Array e
insert Array e
ary Int
idx e
b = (forall s. ST s (Array e)) -> Array e
forall a. (forall s. ST s a) -> a
runST (Array e -> Int -> e -> ST s (Array e)
forall e s. Array e -> Int -> e -> ST s (Array e)
insert' Array e
ary Int
idx e
b)
{-# INLINE insert #-}

-- | /O(n)/ Insert an element at the given position in this array,
-- increasing its size by one.
insert' :: Array e -> Int -> e -> ST s (Array e)
insert' :: Array e -> Int -> e -> ST s (Array e)
insert' Array e
ary Int
idx e
b =
    CHECK_BOUNDS("insert'", count + 1, idx)
        do MArray s e
mary <- Int -> ST s (MArray s e)
forall s a. Int -> ST s (MArray s a)
new_ (Int
countInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1)
           Array e -> Int -> MArray s e -> Int -> Int -> ST s ()
forall e s. Array e -> Int -> MArray s e -> Int -> Int -> ST s ()
copy Array e
ary Int
0 MArray s e
mary Int
0 Int
idx
           MArray s e -> Int -> e -> ST s ()
forall s a. MArray s a -> Int -> a -> ST s ()
write MArray s e
mary Int
idx e
b
           Array e -> Int -> MArray s e -> Int -> Int -> ST s ()
forall e s. Array e -> Int -> MArray s e -> Int -> Int -> ST s ()
copy Array e
ary Int
idx MArray s e
mary (Int
idxInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) (Int
countInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
idx)
           MArray s e -> ST s (Array e)
forall s a. MArray s a -> ST s (Array a)
unsafeFreeze MArray s e
mary
  where !count :: Int
count = Array e -> Int
forall a. Array a -> Int
length Array e
ary
{-# INLINE insert' #-}

-- | /O(n)/ Update the element at the given position in this array.
update :: Array e -> Int -> e -> Array e
update :: Array e -> Int -> e -> Array e
update Array e
ary Int
idx e
b = (forall s. ST s (Array e)) -> Array e
forall a. (forall s. ST s a) -> a
runST (Array e -> Int -> e -> ST s (Array e)
forall e s. Array e -> Int -> e -> ST s (Array e)
update' Array e
ary Int
idx e
b)
{-# INLINE update #-}

-- | /O(n)/ Update the element at the given position in this array.
update' :: Array e -> Int -> e -> ST s (Array e)
update' :: Array e -> Int -> e -> ST s (Array e)
update' Array e
ary Int
idx e
b =
    CHECK_BOUNDS("update'", count, idx)
        do MArray s e
mary <- Array e -> Int -> Int -> ST s (MArray s e)
forall e s. Array e -> Int -> Int -> ST s (MArray s e)
thaw Array e
ary Int
0 Int
count
           MArray s e -> Int -> e -> ST s ()
forall s a. MArray s a -> Int -> a -> ST s ()
write MArray s e
mary Int
idx e
b
           MArray s e -> ST s (Array e)
forall s a. MArray s a -> ST s (Array a)
unsafeFreeze MArray s e
mary
  where !count :: Int
count = Array e -> Int
forall a. Array a -> Int
length Array e
ary
{-# INLINE update' #-}

-- | /O(n)/ Update the element at the given positio in this array, by
-- applying a function to it.  Evaluates the element to WHNF before
-- inserting it into the array.
updateWith :: Array e -> Int -> (e -> e) -> Array e
updateWith :: Array e -> Int -> (e -> e) -> Array e
updateWith Array e
ary Int
idx e -> e
f = Array e -> Int -> e -> Array e
forall e. Array e -> Int -> e -> Array e
update Array e
ary Int
idx (e -> Array e) -> e -> Array e
forall a b. (a -> b) -> a -> b
$! e -> e
f (Array e -> Int -> e
forall a. Array a -> Int -> a
index Array e
ary Int
idx)
{-# INLINE updateWith #-}

-- | /O(1)/ Update the element at the given position in this array,
-- without copying.
unsafeUpdate' :: Array e -> Int -> e -> ST s ()
unsafeUpdate' :: Array e -> Int -> e -> ST s ()
unsafeUpdate' Array e
ary Int
idx e
b =
    CHECK_BOUNDS("unsafeUpdate'", length ary, idx)
        do MArray s e
mary <- Array e -> ST s (MArray s e)
forall a s. Array a -> ST s (MArray s a)
unsafeThaw Array e
ary
           MArray s e -> Int -> e -> ST s ()
forall s a. MArray s a -> Int -> a -> ST s ()
write MArray s e
mary Int
idx e
b
           Array e
_ <- MArray s e -> ST s (Array e)
forall s a. MArray s a -> ST s (Array a)
unsafeFreeze MArray s e
mary
           () -> ST s ()
forall (m :: * -> *) a. Monad m => a -> m a
return ()
{-# INLINE unsafeUpdate' #-}

-- | Note: strict in the initial accumulator value.
foldl' :: (b -> a -> b) -> b -> Array a -> b
foldl' :: (b -> a -> b) -> b -> Array a -> b
foldl' b -> a -> b
f !b
z0 !Array a
ary0 = Array a -> Int -> Int -> b -> b
go Array a
ary0 (Array a -> Int
forall a. Array a -> Int
length Array a
ary0) Int
0 b
z0
  where
    go :: Array a -> Int -> Int -> b -> b
go !Array a
ary Int
n !Int
i !b
z
        | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
n    = b
z
        | (# a
x #) <- Array a -> Int -> (# a #)
forall a. Array a -> Int -> (# a #)
index# Array a
ary Int
i
        = Array a -> Int -> Int -> b -> b
go Array a
ary Int
n (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) (b -> a -> b
f b
z a
x)
{-# INLINE foldl' #-}

foldl :: (b -> a -> b) -> b -> Array a -> b
foldl :: (b -> a -> b) -> b -> Array a -> b
foldl b -> a -> b
f b
z0 !Array a
ary0 = Array a -> Int -> b -> b
go Array a
ary0 (Array a -> Int
forall a. Array a -> Int
length Array a
ary0) b
z0
  where
    go :: Array a -> Int -> b -> b
go !Array a
ary !Int
i b
z
        | Int
i Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0    = b
z
        | (# a
x #) <- Array a -> Int -> (# a #)
forall a. Array a -> Int -> (# a #)
index# Array a
ary (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)
        = b -> a -> b
f (Array a -> Int -> b -> b
go Array a
ary (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1) b
z) a
x
{-# INLINE foldl #-}

boundedFoldl' :: (b -> a -> b) -> Int -> Int -> b -> Array a -> b
boundedFoldl' :: (b -> a -> b) -> Int -> Int -> b -> Array a -> b
boundedFoldl' b -> a -> b
f !Int
start !Int
end b
z0 Array a
ary0 =
  Array a -> Int -> Int -> b -> b
go Array a
ary0 (Int -> Int -> Int
forall a. Ord a => a -> a -> a
min Int
end (Array a -> Int
forall a. Array a -> Int
length Array a
ary0)) (Int -> Int -> Int
forall a. Ord a => a -> a -> a
max Int
0 Int
start) b
z0
  where
    go :: Array a -> Int -> Int -> b -> b
go Array a
ary Int
n Int
i !b
z
      | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
n = b
z
      | (# a
x #) <- Array a -> Int -> (# a #)
forall a. Array a -> Int -> (# a #)
index# Array a
ary Int
i
      = Array a -> Int -> Int -> b -> b
go Array a
ary Int
n (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) (b -> a -> b
f b
z a
x)
{-# INLINE boundedFoldl' #-}

foldr :: (a -> b -> b) -> b -> Array a -> b
foldr :: (a -> b -> b) -> b -> Array a -> b
foldr a -> b -> b
f b
z0 !Array a
ary0 = Array a -> Int -> Int -> b -> b
go Array a
ary0 (Array a -> Int
forall a. Array a -> Int
length Array a
ary0) Int
0 b
z0
-- foldr f = \ z0 ary0 -> go ary0 (length ary0) 0 z0
  where
    go :: Array a -> Int -> Int -> b -> b
go !Array a
ary !Int
n !Int
i b
z
        | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
n    = b
z
        | (# a
x #) <- Array a -> Int -> (# a #)
forall a. Array a -> Int -> (# a #)
index# Array a
ary Int
i
        = a -> b -> b
f a
x (Array a -> Int -> Int -> b -> b
go Array a
ary Int
n (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) b
z)
{-# INLINE foldr #-}

-- | Note: Strict in the initial accumulator value.
foldr' :: (a -> b -> b) -> b -> Array a -> b
foldr' :: (a -> b -> b) -> b -> Array a -> b
foldr' a -> b -> b
f !b
z0 !Array a
ary0 = Array a -> Int -> b -> b
go Array a
ary0 (Array a -> Int
forall a. Array a -> Int
length Array a
ary0) b
z0
  where
    go :: Array a -> Int -> b -> b
go !Array a
ary !Int
i !b
z
        | Int
i Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0 = b
z
        | (# a
x #) <- Array a -> Int -> (# a #)
forall a. Array a -> Int -> (# a #)
index# Array a
ary (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)
        = Array a -> Int -> b -> b
go Array a
ary (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1) (a -> b -> b
f a
x b
z)
{-# INLINE foldr' #-}

boundedFoldr :: (a -> b -> b) -> Int -> Int -> b -> Array a -> b
boundedFoldr :: (a -> b -> b) -> Int -> Int -> b -> Array a -> b
boundedFoldr a -> b -> b
f !Int
start !Int
end b
z0 !Array a
ary0 =
  Array a -> Int -> Int -> b -> b
go Array a
ary0 (Int -> Int -> Int
forall a. Ord a => a -> a -> a
min Int
end (Array a -> Int
forall a. Array a -> Int
length Array a
ary0)) (Int -> Int -> Int
forall a. Ord a => a -> a -> a
max Int
0 Int
start) b
z0
  where
    go :: Array a -> Int -> Int -> b -> b
go !Array a
ary !Int
n !Int
i b
z
      | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
n = b
z
      | (# a
x #) <- Array a -> Int -> (# a #)
forall a. Array a -> Int -> (# a #)
index# Array a
ary Int
i
      = a -> b -> b
f a
x (Array a -> Int -> Int -> b -> b
go Array a
ary Int
n (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) b
z)
{-# INLINE boundedFoldr #-}

undefinedElem :: a
undefinedElem :: a
undefinedElem = String -> a
forall a. HasCallStack => String -> a
error String
"Data.HashMap.Array: Undefined element"
{-# NOINLINE undefinedElem #-}

thaw :: Array e -> Int -> Int -> ST s (MArray s e)
#if __GLASGOW_HASKELL__ >= 702
thaw :: Array e -> Int -> Int -> ST s (MArray s e)
thaw !Array e
ary !_o :: Int
_o@(Ext.I# Int#
o#) !n :: Int
n@(Ext.I# Int#
n#) =
    CHECK_LE("thaw", _o + n, length ary)
        STRep s (MArray s e) -> ST s (MArray s e)
forall s a. STRep s a -> ST s a
ST (STRep s (MArray s e) -> ST s (MArray s e))
-> STRep s (MArray s e) -> ST s (MArray s e)
forall a b. (a -> b) -> a -> b
$ \ State# s
s -> case Array# e
-> Int# -> Int# -> State# s -> (# State# s, MutableArray# s e #)
forall a d.
Array# a
-> Int# -> Int# -> State# d -> (# State# d, MutableArray# d a #)
Ext.thawArray# (Array e -> Array# e
forall a. Array a -> Array# a
unArray Array e
ary) Int#
o# Int#
n# State# s
s of
            (# State# s
s2, MutableArray# s e
mary# #) -> (# State# s
s2, MutableArray# s e -> Int -> MArray s e
forall s a. MutableArray# s a -> Int -> MArray s a
marray MutableArray# s e
mary# Int
n #)
#else
thaw !ary !o !n =
    CHECK_LE("thaw", o + n, length ary)
        do mary <- new_ n
           copy ary o mary 0 n
           return mary
#endif
{-# INLINE thaw #-}

-- | /O(n)/ Delete an element at the given position in this array,
-- decreasing its size by one.
delete :: Array e -> Int -> Array e
delete :: Array e -> Int -> Array e
delete Array e
ary Int
idx = (forall s. ST s (Array e)) -> Array e
forall a. (forall s. ST s a) -> a
runST (Array e -> Int -> ST s (Array e)
forall e s. Array e -> Int -> ST s (Array e)
delete' Array e
ary Int
idx)
{-# INLINE delete #-}

-- | /O(n)/ Delete an element at the given position in this array,
-- decreasing its size by one.
delete' :: Array e -> Int -> ST s (Array e)
delete' :: Array e -> Int -> ST s (Array e)
delete' Array e
ary Int
idx = do
    MArray s e
mary <- Int -> ST s (MArray s e)
forall s a. Int -> ST s (MArray s a)
new_ (Int
countInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1)
    Array e -> Int -> MArray s e -> Int -> Int -> ST s ()
forall e s. Array e -> Int -> MArray s e -> Int -> Int -> ST s ()
copy Array e
ary Int
0 MArray s e
mary Int
0 Int
idx
    Array e -> Int -> MArray s e -> Int -> Int -> ST s ()
forall e s. Array e -> Int -> MArray s e -> Int -> Int -> ST s ()
copy Array e
ary (Int
idxInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) MArray s e
mary Int
idx (Int
countInt -> Int -> Int
forall a. Num a => a -> a -> a
-(Int
idxInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1))
    MArray s e -> ST s (Array e)
forall s a. MArray s a -> ST s (Array a)
unsafeFreeze MArray s e
mary
  where !count :: Int
count = Array e -> Int
forall a. Array a -> Int
length Array e
ary
{-# INLINE delete' #-}

map :: (a -> b) -> Array a -> Array b
map :: (a -> b) -> Array a -> Array b
map a -> b
f = \ Array a
ary ->
    let !n :: Int
n = Array a -> Int
forall a. Array a -> Int
length Array a
ary
    in (forall s. ST s (MArray s b)) -> Array b
forall e. (forall s. ST s (MArray s e)) -> Array e
run ((forall s. ST s (MArray s b)) -> Array b)
-> (forall s. ST s (MArray s b)) -> Array b
forall a b. (a -> b) -> a -> b
$ do
        MArray s b
mary <- Int -> ST s (MArray s b)
forall s a. Int -> ST s (MArray s a)
new_ Int
n
        Array a -> MArray s b -> Int -> Int -> ST s (MArray s b)
forall s. Array a -> MArray s b -> Int -> Int -> ST s (MArray s b)
go Array a
ary MArray s b
mary Int
0 Int
n
  where
    go :: Array a -> MArray s b -> Int -> Int -> ST s (MArray s b)
go Array a
ary MArray s b
mary Int
i Int
n
        | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
n    = MArray s b -> ST s (MArray s b)
forall (m :: * -> *) a. Monad m => a -> m a
return MArray s b
mary
        | Bool
otherwise = do
             MArray s b -> Int -> b -> ST s ()
forall s a. MArray s a -> Int -> a -> ST s ()
write MArray s b
mary Int
i (b -> ST s ()) -> b -> ST s ()
forall a b. (a -> b) -> a -> b
$ a -> b
f (Array a -> Int -> a
forall a. Array a -> Int -> a
index Array a
ary Int
i)
             Array a -> MArray s b -> Int -> Int -> ST s (MArray s b)
go Array a
ary MArray s b
mary (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) Int
n
{-# INLINE map #-}

-- | Strict version of 'map'.
map' :: (a -> b) -> Array a -> Array b
map' :: (a -> b) -> Array a -> Array b
map' a -> b
f = \ Array a
ary ->
    let !n :: Int
n = Array a -> Int
forall a. Array a -> Int
length Array a
ary
    in (forall s. ST s (MArray s b)) -> Array b
forall e. (forall s. ST s (MArray s e)) -> Array e
run ((forall s. ST s (MArray s b)) -> Array b)
-> (forall s. ST s (MArray s b)) -> Array b
forall a b. (a -> b) -> a -> b
$ do
        MArray s b
mary <- Int -> ST s (MArray s b)
forall s a. Int -> ST s (MArray s a)
new_ Int
n
        Array a -> MArray s b -> Int -> Int -> ST s (MArray s b)
forall s. Array a -> MArray s b -> Int -> Int -> ST s (MArray s b)
go Array a
ary MArray s b
mary Int
0 Int
n
  where
    go :: Array a -> MArray s b -> Int -> Int -> ST s (MArray s b)
go Array a
ary MArray s b
mary Int
i Int
n
        | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
n    = MArray s b -> ST s (MArray s b)
forall (m :: * -> *) a. Monad m => a -> m a
return MArray s b
mary
        | Bool
otherwise = do
             MArray s b -> Int -> b -> ST s ()
forall s a. MArray s a -> Int -> a -> ST s ()
write MArray s b
mary Int
i (b -> ST s ()) -> b -> ST s ()
forall a b. (a -> b) -> a -> b
$! a -> b
f (Array a -> Int -> a
forall a. Array a -> Int -> a
index Array a
ary Int
i)
             Array a -> MArray s b -> Int -> Int -> ST s (MArray s b)
go Array a
ary MArray s b
mary (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) Int
n
{-# INLINE map' #-}

fromList :: Int -> [a] -> Array a
fromList :: Int -> [a] -> Array a
fromList Int
n [a]
xs0 = (forall s. ST s (MArray s a)) -> Array a
forall e. (forall s. ST s (MArray s e)) -> Array e
run ((forall s. ST s (MArray s a)) -> Array a)
-> (forall s. ST s (MArray s a)) -> Array a
forall a b. (a -> b) -> a -> b
$ do
    MArray s a
mary <- Int -> ST s (MArray s a)
forall s a. Int -> ST s (MArray s a)
new_ Int
n
    [a] -> MArray s a -> Int -> ST s (MArray s a)
forall a s. [a] -> MArray s a -> Int -> ST s (MArray s a)
go [a]
xs0 MArray s a
mary Int
0
  where
    go :: [a] -> MArray s a -> Int -> ST s (MArray s a)
go [] !MArray s a
mary !Int
_   = MArray s a -> ST s (MArray s a)
forall (m :: * -> *) a. Monad m => a -> m a
return MArray s a
mary
    go (a
x:[a]
xs) !MArray s a
mary !Int
i = do MArray s a -> Int -> a -> ST s ()
forall s a. MArray s a -> Int -> a -> ST s ()
write MArray s a
mary Int
i a
x
                            [a] -> MArray s a -> Int -> ST s (MArray s a)
go [a]
xs MArray s a
mary (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1)

fromListRev :: Int -> [a] -> Array a
fromListRev :: Int -> [a] -> Array a
fromListRev Int
n [a]
xs0 = (forall s. ST s (MArray s a)) -> Array a
forall e. (forall s. ST s (MArray s e)) -> Array e
run ((forall s. ST s (MArray s a)) -> Array a)
-> (forall s. ST s (MArray s a)) -> Array a
forall a b. (a -> b) -> a -> b
$ do
    MArray s a
mary <- Int -> ST s (MArray s a)
forall s a. Int -> ST s (MArray s a)
new_ Int
n
    [a] -> MArray s a -> Int -> ST s (MArray s a)
forall a s. [a] -> MArray s a -> Int -> ST s (MArray s a)
go [a]
xs0 MArray s a
mary (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)
  where
    go :: [a] -> MArray s a -> Int -> ST s (MArray s a)
go [] !MArray s a
mary !Int
_   = MArray s a -> ST s (MArray s a)
forall (m :: * -> *) a. Monad m => a -> m a
return MArray s a
mary
    go (a
x:[a]
xs) !MArray s a
mary !Int
i = do MArray s a -> Int -> a -> ST s ()
forall s a. MArray s a -> Int -> a -> ST s ()
write MArray s a
mary Int
i a
x
                            [a] -> MArray s a -> Int -> ST s (MArray s a)
go [a]
xs MArray s a
mary (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1)

toList :: Array a -> [a]
toList :: Array a -> [a]
toList = (a -> [a] -> [a]) -> [a] -> Array a -> [a]
forall a b. (a -> b -> b) -> b -> Array a -> b
foldr (:) []

traverseArray :: A.Applicative f => (a -> f b) -> Array a -> f (Array b)
traverseArray :: (a -> f b) -> Array a -> f (Array b)
traverseArray a -> f b
f = \ Array a
ary -> Int -> [b] -> Array b
forall a. Int -> [a] -> Array a
fromList (Array a -> Int
forall a. Array a -> Int
length Array a
ary) ([b] -> Array b) -> f [b] -> f (Array b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
`fmap`
                      (a -> f b) -> [a] -> f [b]
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
Traversable.traverse a -> f b
f (Array a -> [a]
forall a. Array a -> [a]
toList Array a
ary)
{-# INLINE traverseArray #-}

filter :: (a -> Bool) -> Array a -> Array a
filter :: (a -> Bool) -> Array a -> Array a
filter a -> Bool
p = \ Array a
ary ->
    let !n :: Int
n = Array a -> Int
forall a. Array a -> Int
length Array a
ary
    in (forall s. ST s (MArray s a)) -> Array a
forall e. (forall s. ST s (MArray s e)) -> Array e
run ((forall s. ST s (MArray s a)) -> Array a)
-> (forall s. ST s (MArray s a)) -> Array a
forall a b. (a -> b) -> a -> b
$ do
        MArray s a
mary <- Int -> ST s (MArray s a)
forall s a. Int -> ST s (MArray s a)
new_ Int
n
        Array a -> MArray s a -> Int -> Int -> Int -> ST s (MArray s a)
forall s.
Array a -> MArray s a -> Int -> Int -> Int -> ST s (MArray s a)
go Array a
ary MArray s a
mary Int
0 Int
0 Int
n
  where
    go :: Array a -> MArray s a -> Int -> Int -> Int -> ST s (MArray s a)
go Array a
ary MArray s a
mary Int
i Int
j Int
n
        | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
n    = if Int
i Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
j
                      then MArray s a -> ST s (MArray s a)
forall (m :: * -> *) a. Monad m => a -> m a
return MArray s a
mary
                      else do MArray s a
mary2 <- Int -> ST s (MArray s a)
forall s a. Int -> ST s (MArray s a)
new_ Int
j
                              MArray s a -> Int -> MArray s a -> Int -> Int -> ST s ()
forall s e.
MArray s e -> Int -> MArray s e -> Int -> Int -> ST s ()
copyM MArray s a
mary Int
0 MArray s a
mary2 Int
0 Int
j
                              MArray s a -> ST s (MArray s a)
forall (m :: * -> *) a. Monad m => a -> m a
return MArray s a
mary2
        | a -> Bool
p a
el      = MArray s a -> Int -> a -> ST s ()
forall s a. MArray s a -> Int -> a -> ST s ()
write MArray s a
mary Int
j a
el ST s () -> ST s (MArray s a) -> ST s (MArray s a)
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> Array a -> MArray s a -> Int -> Int -> Int -> ST s (MArray s a)
go Array a
ary MArray s a
mary (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) (Int
jInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) Int
n
        | Bool
otherwise = Array a -> MArray s a -> Int -> Int -> Int -> ST s (MArray s a)
go Array a
ary MArray s a
mary (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) Int
j Int
n
      where el :: a
el = Array a -> Int -> a
forall a. Array a -> Int -> a
index Array a
ary Int
i
{-# INLINE filter #-}