{-# 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,
    readBack,
    readBackMaybe,

    -- * Modifications

    -- ** Writing
    write,

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

    -- ** Misc
    clear,
    reverse,

    -- * Conversion
    freeze,
    unsafeFreeze,
  )
where

-- NOTE (perf): we have to inine all the functions for reasonable performance

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, reverse)

-- | Growable vector with some runtime overhead.
--
-- @since 1.0.0.0
data GrowVec s a = GrowVec
  { -- | Stores [l, r) range in the `vecGV`.
    --
    -- @since 1.0.0.0
    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.4.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)\) Yields the element at the given position. Will throw an exception if the index is out
-- of range.
--
-- @since 1.4.0.0
{-# INLINE readBack #-}
readBack :: (HasCallStack, PrimMonad m, VU.Unbox a) => GrowVec (PrimState m) a -> Int -> m a
readBack :: forall (m :: * -> *) a.
(HasCallStack, PrimMonad m, Unbox a) =>
GrowVec (PrimState m) a -> Int -> m a
readBack 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
readBackST 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.4.0.0
{-# INLINE readBackMaybe #-}
readBackMaybe :: (HasCallStack, PrimMonad m, VU.Unbox a) => GrowVec (PrimState m) a -> Int -> m (Maybe a)
readBackMaybe :: forall (m :: * -> *) a.
(HasCallStack, PrimMonad m, Unbox a) =>
GrowVec (PrimState m) a -> Int -> m (Maybe a)
readBackMaybe 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)
readBackMaybeST 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.4.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(1)\) Sets the length to zero.
--
-- @since 1.4.0.0
{-# INLINE clear #-}
clear :: (PrimMonad m, VU.Unbox a) => GrowVec (PrimState m) a -> m ()
clear :: forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
GrowVec (PrimState m) a -> m ()
clear 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)
..} = 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
$ do
  MVector (PrimState (ST (PrimState m))) Int
-> Int -> Int -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector (PrimState m) Int
MVector (PrimState (ST (PrimState m))) Int
posGV Int
0 Int
0

-- | \(O(n)\) Reverses all the elements.
--
-- @since 1.4.0.0
{-# INLINE reverse #-}
reverse :: (HasCallStack, PrimMonad m, Ord a, VU.Unbox a) => GrowVec (PrimState m) a -> m ()
reverse :: forall (m :: * -> *) a.
(HasCallStack, PrimMonad m, Ord a, Unbox a) =>
GrowVec (PrimState m) a -> m ()
reverse = 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.
(HasCallStack, Ord a, Unbox a) =>
GrowVec s a -> ST s ()
reverseST

-- | \(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
-- -------------------------------------------------------------------------------------------------

{-# INLINE 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
  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
  let !()
_ = HasCallStack => String -> Int -> Int -> ()
String -> Int -> Int -> ()
ACIA.checkIndex String
"AtCoder.Internal.GrowVec.readST" 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

{-# INLINE 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

{-# INLINE readBackST #-}
readBackST :: (HasCallStack, VU.Unbox a) => GrowVec s a -> Int -> ST s a
readBackST :: forall a s. (HasCallStack, Unbox a) => GrowVec s a -> Int -> ST s a
readBackST 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
  let !()
_ = HasCallStack => String -> Int -> Int -> ()
String -> Int -> Int -> ()
ACIA.checkIndex String
"AtCoder.Internal.GrowVec.readBackST" 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
len Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
i)

{-# INLINE readBackMaybeST #-}
readBackMaybeST :: (HasCallStack, VU.Unbox a) => GrowVec s a -> Int -> ST s (Maybe a)
readBackMaybeST :: forall a s.
(HasCallStack, Unbox a) =>
GrowVec s a -> Int -> ST s (Maybe a)
readBackMaybeST 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
len Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1 Int -> Int -> Int
forall a. Num a => a -> a -> a
- 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

{-# INLINE 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
  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
  let !()
_ = HasCallStack => String -> Int -> Int -> ()
String -> Int -> Int -> ()
ACIA.checkIndex String
"AtCoder.Internal.GrowVec.writeST" 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

{-# INLINE 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

{-# INLINE 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)

{-# INLINE 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

{-# INLINE reverseST #-}
reverseST :: (HasCallStack, Ord a, VU.Unbox a) => GrowVec s a -> ST s ()
reverseST :: forall a s.
(HasCallStack, Ord a, Unbox a) =>
GrowVec s a -> ST s ()
reverseST 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
  let slice :: MVector s a
slice = 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
  MVector (PrimState (ST s)) a -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> m ()
VGM.reverse MVector s a
MVector (PrimState (ST s)) a
slice

{-# INLINE 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

{-# INLINE 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