{-# LANGUAGE RecordWildCards #-}

-- | Growable vector with some runtime overhead (by `MutVar`).
--
-- ==== __Example__
-- >>> import AtCoder.Internal.GrowVec qualified as GV
-- >>> growVec <- GV.new @_ @Int 0
-- >>> GV.null growVec
-- True
--
-- >>> GV.pushBack growVec 10
-- >>> GV.pushBack growVec 11
-- >>> GV.pushBack growVec 12
-- >>> GV.freeze growVec
-- [10,11,12]
--
-- >>> GV.length growVec
-- 3
--
-- >>> GV.capacity growVec
-- 4
--
-- >>> GV.write growVec 1 20
-- >>> GV.read growVec 1
-- 20
--
-- >>> GV.readMaybe growVec (-1)
-- Nothing
--
-- >>> GV.readMaybe growVec 0
-- Just 10
--
-- >>> GV.readMaybe growVec 3
-- Nothing
--
-- >>> GV.popBack growVec
-- Just 12
--
-- >>> GV.popBack growVec
-- Just 20
--
-- >>> GV.reserve growVec 20
-- >>> GV.capacity growVec
-- 20
--
-- >>> GV.unsafeFreeze growVec
-- [10]
--
-- @since 1.0.0.0
module AtCoder.Internal.GrowVec
  ( -- * GrowVec
    GrowVec (vecGV),

    -- * Constructors
    new,
    build,
    reserve,

    -- * Metadata
    length,
    capacity,
    null,

    -- * Readings
    read,
    readMaybe,

    -- * Modifications

    -- ** Writing
    write,

    -- ** Push/pop
    pushBack,
    popBack,
    popBack_,

    -- * Conversion
    freeze,
    unsafeFreeze,
  )
where

import AtCoder.Internal.Assert qualified as ACIA
import Control.Monad (when)
import Control.Monad.Primitive (PrimMonad, PrimState, stToPrim)
import Control.Monad.ST (ST)
import Data.Primitive.MutVar (MutVar, newMutVar, readMutVar, writeMutVar)
import Data.Vector.Generic.Mutable qualified as VGM
import Data.Vector.Unboxed qualified as VU
import Data.Vector.Unboxed.Mutable qualified as VUM
import GHC.Stack (HasCallStack)
import Prelude hiding (length, null, read)

-- | Growable vector with some runtime overhead.
--
-- @since 1.0.0.0
data GrowVec s a = GrowVec
  { -- | Stores [l, r) range in the `vecGV`.
    forall s a. GrowVec s a -> MVector s Int
posGV :: !(VUM.MVector s Int),
    -- | @since 1.0.0.0
    forall s a. GrowVec s a -> MutVar s (MVector s a)
vecGV :: !(MutVar s (VUM.MVector s a))
  }

-- | \(O(n)\) Creates a `GrowVec` with initial capacity \(n\).
--
-- @since 1.0.0.0
{-# INLINE new #-}
new :: (PrimMonad m, VU.Unbox a) => Int -> m (GrowVec (PrimState m) a)
new :: forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> m (GrowVec (PrimState m) a)
new Int
n = do
  MVector (PrimState m) Int
posGV <- Int -> Int -> m (MVector (PrimState m) Int)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> a -> m (MVector (PrimState m) a)
VUM.replicate Int
1 (Int
0 :: Int)
  MutVar (PrimState m) (MVector (PrimState m) a)
vecGV <- MVector (PrimState m) a
-> m (MutVar (PrimState m) (MVector (PrimState m) a))
forall (m :: * -> *) a.
PrimMonad m =>
a -> m (MutVar (PrimState m) a)
newMutVar (MVector (PrimState m) a
 -> m (MutVar (PrimState m) (MVector (PrimState m) a)))
-> m (MVector (PrimState m) a)
-> m (MutVar (PrimState m) (MVector (PrimState m) a))
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< Int -> m (MVector (PrimState m) a)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> m (MVector (PrimState m) a)
VUM.unsafeNew Int
n
  GrowVec (PrimState m) a -> m (GrowVec (PrimState m) a)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure GrowVec {MVector (PrimState m) Int
MutVar (PrimState m) (MVector (PrimState m) a)
vecGV :: MutVar (PrimState m) (MVector (PrimState m) a)
posGV :: MVector (PrimState m) Int
posGV :: MVector (PrimState m) Int
vecGV :: MutVar (PrimState m) (MVector (PrimState m) a)
..}

-- | \(O(n)\) Creates a `GrowVec` with initial values.
--
-- @since 1.0.0.0
{-# INLINE build #-}
build :: (PrimMonad m, VU.Unbox a) => VU.Vector a -> m (GrowVec (PrimState m) a)
build :: forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Vector a -> m (GrowVec (PrimState m) a)
build Vector a
xs = do
  MVector (PrimState m) Int
posGV <- Int -> Int -> m (MVector (PrimState m) Int)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> a -> m (MVector (PrimState m) a)
VUM.replicate Int
1 (Int -> m (MVector (PrimState m) Int))
-> Int -> m (MVector (PrimState m) Int)
forall a b. (a -> b) -> a -> b
$ Vector a -> Int
forall a. Unbox a => Vector a -> Int
VU.length Vector a
xs
  MutVar (PrimState m) (MVector (PrimState m) a)
vecGV <- MVector (PrimState m) a
-> m (MutVar (PrimState m) (MVector (PrimState m) a))
forall (m :: * -> *) a.
PrimMonad m =>
a -> m (MutVar (PrimState m) a)
newMutVar (MVector (PrimState m) a
 -> m (MutVar (PrimState m) (MVector (PrimState m) a)))
-> m (MVector (PrimState m) a)
-> m (MutVar (PrimState m) (MVector (PrimState m) a))
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< Vector a -> m (MVector (PrimState m) a)
forall a (m :: * -> *).
(Unbox a, PrimMonad m) =>
Vector a -> m (MVector (PrimState m) a)
VU.thaw Vector a
xs
  GrowVec (PrimState m) a -> m (GrowVec (PrimState m) a)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure GrowVec {MVector (PrimState m) Int
MutVar (PrimState m) (MVector (PrimState m) a)
vecGV :: MutVar (PrimState m) (MVector (PrimState m) a)
posGV :: MVector (PrimState m) Int
posGV :: MVector (PrimState m) Int
vecGV :: MutVar (PrimState m) (MVector (PrimState m) a)
..}

-- | \(O(n)\) Reserves the internal storage capacity.
--
-- @since 1.0.0.0
{-# INLINE reserve #-}
reserve :: (HasCallStack, PrimMonad m, VU.Unbox a) => GrowVec (PrimState m) a -> Int -> m ()
reserve :: forall (m :: * -> *) a.
(HasCallStack, PrimMonad m, Unbox a) =>
GrowVec (PrimState m) a -> Int -> m ()
reserve GrowVec {MVector (PrimState m) Int
MutVar (PrimState m) (MVector (PrimState m) a)
vecGV :: forall s a. GrowVec s a -> MutVar s (MVector s a)
posGV :: forall s a. GrowVec s a -> MVector s Int
posGV :: MVector (PrimState m) Int
vecGV :: MutVar (PrimState m) (MVector (PrimState m) a)
..} Int
len = do
  MVector (PrimState m) a
vec <- MutVar (PrimState m) (MVector (PrimState m) a)
-> m (MVector (PrimState m) a)
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> m a
readMutVar MutVar (PrimState m) (MVector (PrimState m) a)
vecGV
  Bool -> m () -> m ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (MVector (PrimState m) a -> Int
forall a s. Unbox a => MVector s a -> Int
VUM.length MVector (PrimState m) a
vec Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
len) (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ do
    MVector (PrimState m) a
newVec <- MVector (PrimState m) a -> Int -> m (MVector (PrimState m) a)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
MVector (PrimState m) a -> Int -> m (MVector (PrimState m) a)
VUM.unsafeGrow MVector (PrimState m) a
vec (Int
len Int -> Int -> Int
forall a. Num a => a -> a -> a
- MVector (PrimState m) a -> Int
forall a s. Unbox a => MVector s a -> Int
VUM.length MVector (PrimState m) a
vec)
    MutVar (PrimState m) (MVector (PrimState m) a)
-> MVector (PrimState m) a -> m ()
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> a -> m ()
writeMutVar MutVar (PrimState m) (MVector (PrimState m) a)
vecGV MVector (PrimState m) a
newVec

-- | \(O(1)\) Returns the number of elements in the vector.
--
-- @since 1.0.0.0
{-# INLINE length #-}
length :: (PrimMonad m, VU.Unbox a) => GrowVec (PrimState m) a -> m Int
length :: forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
GrowVec (PrimState m) a -> m Int
length GrowVec {MVector (PrimState m) Int
posGV :: forall s a. GrowVec s a -> MVector s Int
posGV :: MVector (PrimState m) Int
posGV} = do
  MVector (PrimState m) Int -> Int -> m Int
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.unsafeRead MVector (PrimState m) Int
posGV Int
0

-- | \(O(1)\) Returns the capacity of the internal the vector.
--
-- @since 1.0.0.0
{-# INLINE capacity #-}
capacity :: (PrimMonad m, VU.Unbox a) => GrowVec (PrimState m) a -> m Int
capacity :: forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
GrowVec (PrimState m) a -> m Int
capacity GrowVec {MutVar (PrimState m) (MVector (PrimState m) a)
vecGV :: forall s a. GrowVec s a -> MutVar s (MVector s a)
vecGV :: MutVar (PrimState m) (MVector (PrimState m) a)
vecGV} = do
  MVector (PrimState m) a
vec <- MutVar (PrimState m) (MVector (PrimState m) a)
-> m (MVector (PrimState m) a)
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> m a
readMutVar MutVar (PrimState m) (MVector (PrimState m) a)
vecGV
  Int -> m Int
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Int -> m Int) -> Int -> m Int
forall a b. (a -> b) -> a -> b
$ MVector (PrimState m) a -> Int
forall a s. Unbox a => MVector s a -> Int
VUM.length MVector (PrimState m) a
vec

-- | \(O(1)\) Returns `True` if the vector is empty.
--
-- @since 1.0.0.0
{-# INLINE null #-}
null :: (PrimMonad m, VU.Unbox a) => GrowVec (PrimState m) a -> m Bool
null :: forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
GrowVec (PrimState m) a -> m Bool
null = (Int -> Bool) -> m Int -> m Bool
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
(<$>) (Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0) (m Int -> m Bool)
-> (GrowVec (PrimState m) a -> m Int)
-> GrowVec (PrimState m) a
-> m Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. GrowVec (PrimState m) a -> m Int
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
GrowVec (PrimState m) a -> m Int
length

-- | \(O(1)\) Yields the element at the given position. Will throw an exception if the index is out
-- of range.
--
-- @since 1.0.0.0
{-# INLINE read #-}
read :: (HasCallStack, PrimMonad m, VU.Unbox a) => GrowVec (PrimState m) a -> Int -> m a
read :: forall (m :: * -> *) a.
(HasCallStack, PrimMonad m, Unbox a) =>
GrowVec (PrimState m) a -> Int -> m a
read GrowVec (PrimState m) a
gv Int
i = ST (PrimState m) a -> m a
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) a -> m a) -> ST (PrimState m) a -> m a
forall a b. (a -> b) -> a -> b
$ GrowVec (PrimState m) a -> Int -> ST (PrimState m) a
forall a s. (HasCallStack, Unbox a) => GrowVec s a -> Int -> ST s a
readST GrowVec (PrimState m) a
gv Int
i

-- | \(O(1)\) Yields the element at the given position, or `Nothing` if the index is out of range.
--
-- @since 1.2.1.0
{-# INLINE readMaybe #-}
readMaybe :: (HasCallStack, PrimMonad m, VU.Unbox a) => GrowVec (PrimState m) a -> Int -> m (Maybe a)
readMaybe :: forall (m :: * -> *) a.
(HasCallStack, PrimMonad m, Unbox a) =>
GrowVec (PrimState m) a -> Int -> m (Maybe a)
readMaybe GrowVec (PrimState m) a
gv Int
i = ST (PrimState m) (Maybe a) -> m (Maybe a)
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) (Maybe a) -> m (Maybe a))
-> ST (PrimState m) (Maybe a) -> m (Maybe a)
forall a b. (a -> b) -> a -> b
$ GrowVec (PrimState m) a -> Int -> ST (PrimState m) (Maybe a)
forall a s.
(HasCallStack, Unbox a) =>
GrowVec s a -> Int -> ST s (Maybe a)
readMaybeST GrowVec (PrimState m) a
gv Int
i

-- | \(O(1)\) Writes to the element at the given position. Will throw an exception if the index is
-- out of range.
--
-- @since 1.0.0.0
{-# INLINE write #-}
write :: (HasCallStack, PrimMonad m, VU.Unbox a) => GrowVec (PrimState m) a -> Int -> a -> m ()
write :: forall (m :: * -> *) a.
(HasCallStack, PrimMonad m, Unbox a) =>
GrowVec (PrimState m) a -> Int -> a -> m ()
write GrowVec (PrimState m) a
gv Int
i a
x = ST (PrimState m) () -> m ()
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) () -> m ()) -> ST (PrimState m) () -> m ()
forall a b. (a -> b) -> a -> b
$ GrowVec (PrimState m) a -> Int -> a -> ST (PrimState m) ()
forall a s.
(HasCallStack, Unbox a) =>
GrowVec s a -> Int -> a -> ST s ()
writeST GrowVec (PrimState m) a
gv Int
i a
x

-- | Amortized \(O(1)\). Grow the capacity twice
--
-- @since 1.0.0.0
{-# INLINE pushBack #-}
pushBack :: (PrimMonad m, VU.Unbox a) => GrowVec (PrimState m) a -> a -> m ()
pushBack :: forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
GrowVec (PrimState m) a -> a -> m ()
pushBack GrowVec (PrimState m) a
gv a
e = ST (PrimState m) () -> m ()
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) () -> m ()) -> ST (PrimState m) () -> m ()
forall a b. (a -> b) -> a -> b
$ GrowVec (PrimState m) a -> a -> ST (PrimState m) ()
forall a s. Unbox a => GrowVec s a -> a -> ST s ()
pushBackST GrowVec (PrimState m) a
gv a
e

-- | \(O(1)\) Removes the last element from the buffer and returns it, or `Nothing` if it is empty.
--
-- @since 1.0.0.0
{-# INLINE popBack #-}
popBack :: (PrimMonad m, VU.Unbox a) => GrowVec (PrimState m) a -> m (Maybe a)
popBack :: forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
GrowVec (PrimState m) a -> m (Maybe a)
popBack = ST (PrimState m) (Maybe a) -> m (Maybe a)
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) (Maybe a) -> m (Maybe a))
-> (GrowVec (PrimState m) a -> ST (PrimState m) (Maybe a))
-> GrowVec (PrimState m) a
-> m (Maybe a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. GrowVec (PrimState m) a -> ST (PrimState m) (Maybe a)
forall a s. Unbox a => GrowVec s a -> ST s (Maybe a)
popBackST

-- | \(O(1)\) `popBack` with the return value discarded.
--
-- @since 1.0.0.0
{-# INLINE popBack_ #-}
popBack_ :: (PrimMonad m, VU.Unbox a) => GrowVec (PrimState m) a -> m ()
popBack_ :: forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
GrowVec (PrimState m) a -> m ()
popBack_ = ST (PrimState m) () -> m ()
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) () -> m ())
-> (GrowVec (PrimState m) a -> ST (PrimState m) ())
-> GrowVec (PrimState m) a
-> m ()
forall b c a. (b -> c) -> (a -> b) -> a -> c
. GrowVec (PrimState m) a -> ST (PrimState m) ()
forall a s. Unbox a => GrowVec s a -> ST s ()
popBackST_

-- | \(O(n)\) Yields an immutable copy of the mutable vector.
--
-- @since 1.0.0.0
{-# INLINE freeze #-}
freeze :: (PrimMonad m, VU.Unbox a) => GrowVec (PrimState m) a -> m (VU.Vector a)
freeze :: forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
GrowVec (PrimState m) a -> m (Vector a)
freeze = ST (PrimState m) (Vector a) -> m (Vector a)
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) (Vector a) -> m (Vector a))
-> (GrowVec (PrimState m) a -> ST (PrimState m) (Vector a))
-> GrowVec (PrimState m) a
-> m (Vector a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. GrowVec (PrimState m) a -> ST (PrimState m) (Vector a)
forall a s. Unbox a => GrowVec s a -> ST s (Vector a)
freezeST

-- | \(O(1)\) Unsafely converts a mutable vector to an immutable one without copying. The mutable
-- vector may not be used after this operation.
--
-- @since 1.0.0.0
{-# INLINE unsafeFreeze #-}
unsafeFreeze :: (PrimMonad m, VU.Unbox a) => GrowVec (PrimState m) a -> m (VU.Vector a)
unsafeFreeze :: forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
GrowVec (PrimState m) a -> m (Vector a)
unsafeFreeze = ST (PrimState m) (Vector a) -> m (Vector a)
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) (Vector a) -> m (Vector a))
-> (GrowVec (PrimState m) a -> ST (PrimState m) (Vector a))
-> GrowVec (PrimState m) a
-> m (Vector a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. GrowVec (PrimState m) a -> ST (PrimState m) (Vector a)
forall a s. Unbox a => GrowVec s a -> ST s (Vector a)
unsafeFreezeST

-- -------------------------------------------------------------------------------------------------
-- Internal
-- -------------------------------------------------------------------------------------------------

{-# INLINEABLE readST #-}
readST :: (HasCallStack, VU.Unbox a) => GrowVec s a -> Int -> ST s a
readST :: forall a s. (HasCallStack, Unbox a) => GrowVec s a -> Int -> ST s a
readST GrowVec {MVector s Int
MutVar s (MVector s a)
vecGV :: forall s a. GrowVec s a -> MutVar s (MVector s a)
posGV :: forall s a. GrowVec s a -> MVector s Int
posGV :: MVector s Int
vecGV :: MutVar s (MVector s a)
..} Int
i = do
  MVector s a
vec <- MutVar (PrimState (ST s)) (MVector s a) -> ST s (MVector s a)
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> m a
readMutVar MutVar s (MVector s a)
MutVar (PrimState (ST s)) (MVector s a)
vecGV
  let len :: Int
len = MVector s a -> Int
forall a s. Unbox a => MVector s a -> Int
VUM.length MVector s a
vec
  let !()
_ = HasCallStack => String -> Int -> Int -> ()
String -> Int -> Int -> ()
ACIA.checkIndex String
"AtCoder.Internal.GrowVec.read" Int
i Int
len
  MVector (PrimState (ST s)) a -> Int -> ST s a
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s a
MVector (PrimState (ST s)) a
vec Int
i

{-# INLINEABLE readMaybeST #-}
readMaybeST :: (HasCallStack, VU.Unbox a) => GrowVec s a -> Int -> ST s (Maybe a)
readMaybeST :: forall a s.
(HasCallStack, Unbox a) =>
GrowVec s a -> Int -> ST s (Maybe a)
readMaybeST GrowVec {MVector s Int
MutVar s (MVector s a)
vecGV :: forall s a. GrowVec s a -> MutVar s (MVector s a)
posGV :: forall s a. GrowVec s a -> MVector s Int
posGV :: MVector s Int
vecGV :: MutVar s (MVector s a)
..} Int
i = do
  MVector s a
vec <- MutVar (PrimState (ST s)) (MVector s a) -> ST s (MVector s a)
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> m a
readMutVar MutVar s (MVector s a)
MutVar (PrimState (ST s)) (MVector s a)
vecGV
  Int
len <- MVector (PrimState (ST s)) Int -> Int -> ST s Int
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.unsafeRead MVector s Int
MVector (PrimState (ST s)) Int
posGV Int
0
  if HasCallStack => Int -> Int -> Bool
Int -> Int -> Bool
ACIA.testIndex Int
i Int
len
    then a -> Maybe a
forall a. a -> Maybe a
Just (a -> Maybe a) -> ST s a -> ST s (Maybe a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> MVector (PrimState (ST s)) a -> Int -> ST s a
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.unsafeRead MVector s a
MVector (PrimState (ST s)) a
vec Int
i
    else Maybe a -> ST s (Maybe a)
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Maybe a
forall a. Maybe a
Nothing

{-# INLINEABLE writeST #-}
writeST :: (HasCallStack, VU.Unbox a) => GrowVec s a -> Int -> a -> ST s ()
writeST :: forall a s.
(HasCallStack, Unbox a) =>
GrowVec s a -> Int -> a -> ST s ()
writeST GrowVec {MVector s Int
MutVar s (MVector s a)
vecGV :: forall s a. GrowVec s a -> MutVar s (MVector s a)
posGV :: forall s a. GrowVec s a -> MVector s Int
posGV :: MVector s Int
vecGV :: MutVar s (MVector s a)
..} Int
i a
x = do
  MVector s a
vec <- MutVar (PrimState (ST s)) (MVector s a) -> ST s (MVector s a)
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> m a
readMutVar MutVar s (MVector s a)
MutVar (PrimState (ST s)) (MVector s a)
vecGV
  let len :: Int
len = MVector s a -> Int
forall a s. Unbox a => MVector s a -> Int
VUM.length MVector s a
vec
  let !()
_ = HasCallStack => String -> Int -> Int -> ()
String -> Int -> Int -> ()
ACIA.checkIndex String
"AtCoder.Internal.GrowVec.write" Int
i Int
len
  MVector (PrimState (ST s)) a -> Int -> a -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector s a
MVector (PrimState (ST s)) a
vec Int
i a
x

{-# INLINEABLE pushBackST #-}
pushBackST :: (VU.Unbox a) => GrowVec s a -> a -> ST s ()
pushBackST :: forall a s. Unbox a => GrowVec s a -> a -> ST s ()
pushBackST GrowVec {MVector s Int
MutVar s (MVector s a)
vecGV :: forall s a. GrowVec s a -> MutVar s (MVector s a)
posGV :: forall s a. GrowVec s a -> MVector s Int
posGV :: MVector s Int
vecGV :: MutVar s (MVector s a)
..} a
e = do
  Int
len <- MVector (PrimState (ST s)) Int -> Int -> ST s Int
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.unsafeRead MVector s Int
MVector (PrimState (ST s)) Int
posGV Int
0
  MVector s a
vec <- do
    MVector s a
vec <- MutVar (PrimState (ST s)) (MVector s a) -> ST s (MVector s a)
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> m a
readMutVar MutVar s (MVector s a)
MutVar (PrimState (ST s)) (MVector s a)
vecGV
    if MVector s a -> Int
forall a s. Unbox a => MVector s a -> Int
VUM.length MVector s a
vec Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
len
      then MVector s a -> ST s (MVector s a)
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure MVector s a
vec
      else do
        -- double the internal vector length
        MVector s a
newVec <- MVector (PrimState (ST s)) a
-> Int -> ST s (MVector (PrimState (ST s)) a)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
MVector (PrimState m) a -> Int -> m (MVector (PrimState m) a)
VUM.unsafeGrow MVector s a
MVector (PrimState (ST s)) a
vec (Int -> ST s (MVector (PrimState (ST s)) a))
-> Int -> ST s (MVector (PrimState (ST s)) a)
forall a b. (a -> b) -> a -> b
$ Int -> Int -> Int
forall a. Ord a => a -> a -> a
max Int
1 Int
len
        MutVar (PrimState (ST s)) (MVector s a) -> MVector s a -> ST s ()
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> a -> m ()
writeMutVar MutVar s (MVector s a)
MutVar (PrimState (ST s)) (MVector s a)
vecGV MVector s a
newVec
        MVector s a -> ST s (MVector s a)
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure MVector s a
newVec

  MVector (PrimState (ST s)) Int
-> (Int -> ST s Int) -> Int -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> (a -> m a) -> Int -> m ()
VGM.unsafeModifyM
    MVector s Int
MVector (PrimState (ST s)) Int
posGV
    ( \Int
r -> do
        MVector (PrimState (ST s)) a -> Int -> a -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector s a
MVector (PrimState (ST s)) a
vec Int
r a
e
        Int -> ST s Int
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Int -> ST s Int) -> Int -> ST s Int
forall a b. (a -> b) -> a -> b
$ Int
r Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1
    )
    Int
0

{-# INLINEABLE popBackST #-}
popBackST :: (VU.Unbox a) => GrowVec s a -> ST s (Maybe a)
popBackST :: forall a s. Unbox a => GrowVec s a -> ST s (Maybe a)
popBackST GrowVec {MVector s Int
MutVar s (MVector s a)
vecGV :: forall s a. GrowVec s a -> MutVar s (MVector s a)
posGV :: forall s a. GrowVec s a -> MVector s Int
posGV :: MVector s Int
vecGV :: MutVar s (MVector s a)
..} = do
  Int
pos <- MVector (PrimState (ST s)) Int -> Int -> ST s Int
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.unsafeRead MVector s Int
MVector (PrimState (ST s)) Int
posGV Int
0
  if Int
pos Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
0
    then Maybe a -> ST s (Maybe a)
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Maybe a
forall a. Maybe a
Nothing
    else do
      MVector (PrimState (ST s)) Int -> Int -> Int -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.unsafeWrite MVector s Int
MVector (PrimState (ST s)) Int
posGV Int
0 (Int -> ST s ()) -> Int -> ST s ()
forall a b. (a -> b) -> a -> b
$ Int
pos Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1
      MVector s a
vec <- MutVar (PrimState (ST s)) (MVector s a) -> ST s (MVector s a)
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> m a
readMutVar MutVar s (MVector s a)
MutVar (PrimState (ST s)) (MVector s a)
vecGV
      a -> Maybe a
forall a. a -> Maybe a
Just (a -> Maybe a) -> ST s a -> ST s (Maybe a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> MVector (PrimState (ST s)) a -> Int -> ST s a
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s a
MVector (PrimState (ST s)) a
vec (Int
pos Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)

{-# INLINEABLE popBackST_ #-}
popBackST_ :: (VU.Unbox a) => GrowVec s a -> ST s ()
popBackST_ :: forall a s. Unbox a => GrowVec s a -> ST s ()
popBackST_ GrowVec {MVector s Int
MutVar s (MVector s a)
vecGV :: forall s a. GrowVec s a -> MutVar s (MVector s a)
posGV :: forall s a. GrowVec s a -> MVector s Int
posGV :: MVector s Int
vecGV :: MutVar s (MVector s a)
..} = do
  Int
pos <- MVector (PrimState (ST s)) Int -> Int -> ST s Int
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.unsafeRead MVector s Int
MVector (PrimState (ST s)) Int
posGV Int
0
  MVector (PrimState (ST s)) Int -> Int -> Int -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.unsafeWrite MVector s Int
MVector (PrimState (ST s)) Int
posGV Int
0 (Int -> ST s ()) -> Int -> ST s ()
forall a b. (a -> b) -> a -> b
$ Int -> Int -> Int
forall a. Ord a => a -> a -> a
max Int
0 (Int -> Int) -> Int -> Int
forall a b. (a -> b) -> a -> b
$ Int
pos Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1

{-# INLINEABLE freezeST #-}
freezeST :: (VU.Unbox a) => GrowVec s a -> ST s (VU.Vector a)
freezeST :: forall a s. Unbox a => GrowVec s a -> ST s (Vector a)
freezeST GrowVec {MVector s Int
MutVar s (MVector s a)
vecGV :: forall s a. GrowVec s a -> MutVar s (MVector s a)
posGV :: forall s a. GrowVec s a -> MVector s Int
posGV :: MVector s Int
vecGV :: MutVar s (MVector s a)
..} = do
  Int
len <- MVector (PrimState (ST s)) Int -> Int -> ST s Int
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.unsafeRead MVector s Int
MVector (PrimState (ST s)) Int
posGV Int
0
  MVector s a
vec <- MutVar (PrimState (ST s)) (MVector s a) -> ST s (MVector s a)
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> m a
readMutVar MutVar s (MVector s a)
MutVar (PrimState (ST s)) (MVector s a)
vecGV
  MVector (PrimState (ST s)) a -> ST s (Vector a)
forall a (m :: * -> *).
(Unbox a, PrimMonad m) =>
MVector (PrimState m) a -> m (Vector a)
VU.freeze (MVector (PrimState (ST s)) a -> ST s (Vector a))
-> MVector (PrimState (ST s)) a -> ST s (Vector a)
forall a b. (a -> b) -> a -> b
$ Int -> MVector s a -> MVector s a
forall a s. Unbox a => Int -> MVector s a -> MVector s a
VUM.take Int
len MVector s a
vec

{-# INLINEABLE unsafeFreezeST #-}
unsafeFreezeST :: (VU.Unbox a) => GrowVec s a -> ST s (VU.Vector a)
unsafeFreezeST :: forall a s. Unbox a => GrowVec s a -> ST s (Vector a)
unsafeFreezeST GrowVec {MVector s Int
MutVar s (MVector s a)
vecGV :: forall s a. GrowVec s a -> MutVar s (MVector s a)
posGV :: forall s a. GrowVec s a -> MVector s Int
posGV :: MVector s Int
vecGV :: MutVar s (MVector s a)
..} = do
  Int
len <- MVector (PrimState (ST s)) Int -> Int -> ST s Int
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.unsafeRead MVector s Int
MVector (PrimState (ST s)) Int
posGV Int
0
  MVector s a
vec <- MutVar (PrimState (ST s)) (MVector s a) -> ST s (MVector s a)
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> m a
readMutVar MutVar s (MVector s a)
MutVar (PrimState (ST s)) (MVector s a)
vecGV
  MVector (PrimState (ST s)) a -> ST s (Vector a)
forall a (m :: * -> *).
(Unbox a, PrimMonad m) =>
MVector (PrimState m) a -> m (Vector a)
VU.unsafeFreeze (MVector (PrimState (ST s)) a -> ST s (Vector a))
-> MVector (PrimState (ST s)) a -> ST s (Vector a)
forall a b. (a -> b) -> a -> b
$ Int -> MVector s a -> MVector s a
forall a s. Unbox a => Int -> MVector s a -> MVector s a
VUM.take Int
len MVector s a
vec