{-# LANGUAGE RecordWildCards #-}

-- | A pushable vector with fixed capacity \(n\). Internally, it tracks the number of elements.
--
-- ==== __Example__
-- Create a buffer with capacity @4@:
--
-- >>> import AtCoder.Internal.Buffer qualified as B
-- >>> buf <- B.new @_ @Int 4
-- >>> B.capacity buf
-- 4
--
-- >>> B.null buf        -- [_   _  _  _]
-- True
--
-- Append elements with `pushBack`:
--
-- >>> B.pushBack buf 10 -- [10  _  _ _]
-- >>> B.pushBack buf 11 -- [10, 11  _  _]
-- >>> length buf
-- 2
--
-- Access each elements with `read`, `readMaybe`, `write`, `modify` or `modifyM`:
--
-- >>> B.read buf 0
-- 10
--
-- >>> B.readMaybe buf (-1)
-- Nothing
--
-- >>> B.readMaybe buf 0
-- Just 10
--
-- >>> B.readMaybe buf 2
-- Nothing
--
-- >>> B.write buf 1 0   -- [10, 0,  _  _]
--
-- Remove elements with `pushBack`:
--
-- >>> B.popBack buf     -- [10  _  _  _]
-- Just 0
--
-- Inspect the internal vector with `freeze`:
--
-- >>> B.freeze buf
-- [10]
--
-- >>> B.clear buf       -- []
-- >>> B.null buf
-- True
--
-- >>> B.unsafeFreeze buf
-- []
--
-- @since 1.0.0.0
module AtCoder.Internal.Buffer
  ( -- * Buffer
    Buffer,

    -- * Constructors
    new,
    build,

    -- * Metadata
    capacity,
    length,
    null,

    -- * Reading
    back,
    read,
    readMaybe,

    -- * Modifications
    pushBack,
    popBack,
    popBack_,
    write,
    modify,
    modifyM,
    clear,

    -- * Conversions
    freeze,
    unsafeFreeze,
  )
where

import AtCoder.Internal.Assert qualified as ACIA
import Control.Monad.Primitive (PrimMonad, PrimState, stToPrim)
import Control.Monad.ST (ST)
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)

-- | A pushable vector with fixed capacity \(n\). Internally, it tracks the number of elements.
--
-- @since 1.0.0.0
data Buffer s a = Buffer
  { forall s a. Buffer s a -> MVector s Int
lenB :: !(VUM.MVector s Int),
    forall s a. Buffer s a -> MVector s a
vecB :: !(VUM.MVector s a)
  }

-- | \(O(n)\) Creates a buffer with capacity \(n\).
--
-- @since 1.0.0.0
{-# INLINE new #-}
new :: (PrimMonad m, VU.Unbox a) => Int -> m (Buffer (PrimState m) a)
new :: forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> m (Buffer (PrimState m) a)
new Int
n = ST (PrimState m) (Buffer (PrimState m) a)
-> m (Buffer (PrimState m) a)
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) (Buffer (PrimState m) a)
 -> m (Buffer (PrimState m) a))
-> ST (PrimState m) (Buffer (PrimState m) a)
-> m (Buffer (PrimState m) a)
forall a b. (a -> b) -> a -> b
$ Int -> ST (PrimState m) (Buffer (PrimState m) a)
forall a s. Unbox a => Int -> ST s (Buffer s a)
newST Int
n

-- | \(O(n)\) Creates a buffer with capacity \(n\) with initial values.
--
-- @since 1.0.0.0
{-# INLINE build #-}
build :: (PrimMonad m, VU.Unbox a) => VU.Vector a -> m (Buffer (PrimState m) a)
build :: forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Vector a -> m (Buffer (PrimState m) a)
build Vector a
xs = ST (PrimState m) (Buffer (PrimState m) a)
-> m (Buffer (PrimState m) a)
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) (Buffer (PrimState m) a)
 -> m (Buffer (PrimState m) a))
-> ST (PrimState m) (Buffer (PrimState m) a)
-> m (Buffer (PrimState m) a)
forall a b. (a -> b) -> a -> b
$ Vector a -> ST (PrimState m) (Buffer (PrimState m) a)
forall a s. Unbox a => Vector a -> ST s (Buffer s a)
buildST Vector a
xs

-- | \(O(1)\) Returns the array size.
--
-- @since 1.0.0.0
{-# INLINE capacity #-}
capacity :: (VU.Unbox a) => Buffer s a -> Int
capacity :: forall a s. Unbox a => Buffer s a -> Int
capacity = MVector s a -> Int
forall a s. Unbox a => MVector s a -> Int
VUM.length (MVector s a -> Int)
-> (Buffer s a -> MVector s a) -> Buffer s a -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Buffer s a -> MVector s a
forall s a. Buffer s a -> MVector s a
vecB

-- | \(O(1)\) Returns the number of elements in the buffer.
--
-- @since 1.0.0.0
{-# INLINE length #-}
length :: (PrimMonad m, VU.Unbox a) => Buffer (PrimState m) a -> m Int
length :: forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Buffer (PrimState m) a -> m Int
length Buffer {MVector (PrimState m) a
MVector (PrimState m) Int
lenB :: forall s a. Buffer s a -> MVector s Int
vecB :: forall s a. Buffer s a -> MVector s a
lenB :: MVector (PrimState m) Int
vecB :: MVector (PrimState m) a
..} = MVector (PrimState m) Int -> Int -> m Int
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector (PrimState m) Int
lenB Int
0

-- | \(O(1)\) Returns `True` if the buffer is empty.
--
-- @since 1.0.0.0
{-# INLINE null #-}
null :: (PrimMonad m, VU.Unbox a) => Buffer (PrimState m) a -> m Bool
null :: forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Buffer (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)
-> (Buffer (PrimState m) a -> m Int)
-> Buffer (PrimState m) a
-> m Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Buffer (PrimState m) a -> m Int
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Buffer (PrimState m) a -> m Int
length

-- | \(O(1)\) Returns the last value in the buffer, or `Nothing` if it is empty.
--
-- @since 1.0.0.0
{-# INLINE back #-}
back :: (PrimMonad m, VU.Unbox a) => Buffer (PrimState m) a -> m (Maybe a)
back :: forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Buffer (PrimState m) a -> m (Maybe a)
back = 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))
-> (Buffer (PrimState m) a -> ST (PrimState m) (Maybe a))
-> Buffer (PrimState m) a
-> m (Maybe a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Buffer (PrimState m) a -> ST (PrimState m) (Maybe a)
forall a s. Unbox a => Buffer s a -> ST s (Maybe a)
backST

-- | \(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) => Buffer (PrimState m) a -> Int -> m a
read :: forall (m :: * -> *) a.
(HasCallStack, PrimMonad m, Unbox a) =>
Buffer (PrimState m) a -> Int -> m a
read Buffer (PrimState m) a
buf 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
$ Buffer (PrimState m) a -> Int -> ST (PrimState m) a
forall a s. (HasCallStack, Unbox a) => Buffer s a -> Int -> ST s a
readST Buffer (PrimState m) a
buf 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 :: (PrimMonad m, VU.Unbox a) => Buffer (PrimState m) a -> Int -> m (Maybe a)
readMaybe :: forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Buffer (PrimState m) a -> Int -> m (Maybe a)
readMaybe Buffer (PrimState m) a
buf 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
$ Buffer (PrimState m) a -> Int -> ST (PrimState m) (Maybe a)
forall a s. Unbox a => Buffer s a -> Int -> ST s (Maybe a)
readMaybeST Buffer (PrimState m) a
buf Int
i

-- | \(O(1)\) Appends an element to the back.
--
-- @since 1.0.0.0
{-# INLINE pushBack #-}
pushBack :: (HasCallStack, PrimMonad m, VU.Unbox a) => Buffer (PrimState m) a -> a -> m ()
pushBack :: forall (m :: * -> *) a.
(HasCallStack, PrimMonad m, Unbox a) =>
Buffer (PrimState m) a -> a -> m ()
pushBack Buffer (PrimState m) a
buf 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
$ Buffer (PrimState m) a -> a -> ST (PrimState m) ()
forall a s. (HasCallStack, Unbox a) => Buffer s a -> a -> ST s ()
pushBackST Buffer (PrimState m) a
buf 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) => Buffer (PrimState m) a -> m (Maybe a)
popBack :: forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Buffer (PrimState m) a -> m (Maybe a)
popBack Buffer (PrimState m) a
buf = 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
$ Buffer (PrimState m) a -> ST (PrimState m) (Maybe a)
forall a s. Unbox a => Buffer s a -> ST s (Maybe a)
popBackST Buffer (PrimState m) a
buf

-- | \(O(1)\) Removes the last element from the buffer and discards it.
--
-- @since 1.1.1.0
{-# INLINE popBack_ #-}
popBack_ :: (PrimMonad m, VU.Unbox a) => Buffer (PrimState m) a -> m ()
popBack_ :: forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Buffer (PrimState m) a -> m ()
popBack_ Buffer (PrimState m) a
buf = 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
$ Buffer (PrimState m) a -> ST (PrimState m) ()
forall a s. Unbox a => Buffer s a -> ST s ()
popBackST_ Buffer (PrimState m) a
buf

-- | \(O(1)\) Writes to the element at the given position. Will throw an exception if the index is
-- out of bounds.
--
-- @since 1.0.0.0
{-# INLINE write #-}
write :: (HasCallStack, PrimMonad m, VU.Unbox a) => Buffer (PrimState m) a -> Int -> a -> m ()
write :: forall (m :: * -> *) a.
(HasCallStack, PrimMonad m, Unbox a) =>
Buffer (PrimState m) a -> Int -> a -> m ()
write Buffer (PrimState m) a
buf Int
i 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
$ Buffer (PrimState m) a -> Int -> a -> ST (PrimState m) ()
forall a s.
(HasCallStack, Unbox a) =>
Buffer s a -> Int -> a -> ST s ()
writeST Buffer (PrimState m) a
buf Int
i a
e

-- | \(O(1)\) Writes to the element at the given position. Will throw an exception if the index is
-- out of bounds.
--
-- @since 1.0.0.0
{-# INLINE modify #-}
modify :: (HasCallStack, PrimMonad m, VU.Unbox a) => Buffer (PrimState m) a -> (a -> a) -> Int -> m ()
modify :: forall (m :: * -> *) a.
(HasCallStack, PrimMonad m, Unbox a) =>
Buffer (PrimState m) a -> (a -> a) -> Int -> m ()
modify Buffer (PrimState m) a
buf a -> a
f Int
i = 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
$ Buffer (PrimState m) a -> (a -> a) -> Int -> ST (PrimState m) ()
forall a s.
(HasCallStack, Unbox a) =>
Buffer s a -> (a -> a) -> Int -> ST s ()
modifyST Buffer (PrimState m) a
buf a -> a
f Int
i

-- | \(O(1)\) Writes to the element at the given position. Will throw an exception if the index is
-- out of bounds.
--
-- @since 1.0.0.0
{-# INLINEABLE modifyM #-}
modifyM :: (HasCallStack, PrimMonad m, VU.Unbox a) => Buffer (PrimState m) a -> (a -> m a) -> Int -> m ()
modifyM :: forall (m :: * -> *) a.
(HasCallStack, PrimMonad m, Unbox a) =>
Buffer (PrimState m) a -> (a -> m a) -> Int -> m ()
modifyM Buffer {MVector (PrimState m) a
MVector (PrimState m) Int
lenB :: forall s a. Buffer s a -> MVector s Int
vecB :: forall s a. Buffer s a -> MVector s a
lenB :: MVector (PrimState m) Int
vecB :: MVector (PrimState m) a
..} a -> m a
f Int
i = do
  Int
len <- ST (PrimState m) Int -> m Int
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) Int -> m Int) -> ST (PrimState m) Int -> m Int
forall a b. (a -> b) -> a -> b
$ MVector (PrimState (ST (PrimState m))) Int
-> Int -> ST (PrimState m) Int
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector (PrimState m) Int
MVector (PrimState (ST (PrimState m))) Int
lenB Int
0
  let !()
_ = HasCallStack => String -> Int -> Int -> ()
String -> Int -> Int -> ()
ACIA.checkIndex String
"AtCoder.Internal.Buffer.modifyM" Int
i Int
len
  MVector (PrimState m) a -> (a -> m a) -> Int -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> (a -> m a) -> Int -> m ()
VGM.modifyM MVector (PrimState m) a
vecB a -> m a
f Int
i

-- | \(O(1)\) Sets the `length` to zero.
--
-- @since 1.0.0.0
{-# INLINE clear #-}
clear :: (PrimMonad m, VU.Unbox a) => Buffer (PrimState m) a -> m ()
clear :: forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Buffer (PrimState m) a -> m ()
clear Buffer {MVector (PrimState m) a
MVector (PrimState m) Int
lenB :: forall s a. Buffer s a -> MVector s Int
vecB :: forall s a. Buffer s a -> MVector s a
lenB :: MVector (PrimState m) Int
vecB :: 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
lenB Int
0 Int
0

-- | \(O(n)\) Yields an immutable copy of the mutable vector.
--
-- @since 1.0.0.0
{-# INLINE freeze #-}
freeze :: (PrimMonad m, VU.Unbox a) => Buffer (PrimState m) a -> m (VU.Vector a)
freeze :: forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Buffer (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))
-> (Buffer (PrimState m) a -> ST (PrimState m) (Vector a))
-> Buffer (PrimState m) a
-> m (Vector a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Buffer (PrimState m) a -> ST (PrimState m) (Vector a)
forall a s. Unbox a => Buffer 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) => Buffer (PrimState m) a -> m (VU.Vector a)
unsafeFreeze :: forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Buffer (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))
-> (Buffer (PrimState m) a -> ST (PrimState m) (Vector a))
-> Buffer (PrimState m) a
-> m (Vector a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Buffer (PrimState m) a -> ST (PrimState m) (Vector a)
forall a s. Unbox a => Buffer s a -> ST s (Vector a)
unsafeFreezeST

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

{-# INLINEABLE newST #-}
newST :: (VU.Unbox a) => Int -> ST s (Buffer s a)
newST :: forall a s. Unbox a => Int -> ST s (Buffer s a)
newST Int
n = do
  MVector s Int
lenB <- Int -> Int -> ST s (MVector (PrimState (ST s)) Int)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> a -> m (MVector (PrimState m) a)
VUM.replicate Int
1 (Int
0 :: Int)
  MVector s a
vecB <- Int -> ST s (MVector (PrimState (ST s)) a)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> m (MVector (PrimState m) a)
VUM.unsafeNew Int
n
  Buffer s a -> ST s (Buffer s a)
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Buffer {MVector s a
MVector s Int
lenB :: MVector s Int
vecB :: MVector s a
lenB :: MVector s Int
vecB :: MVector s a
..}

{-# INLINEABLE buildST #-}
buildST :: (VU.Unbox a) => VU.Vector a -> ST s (Buffer s a)
buildST :: forall a s. Unbox a => Vector a -> ST s (Buffer s a)
buildST Vector a
xs = do
  MVector s Int
lenB <- Int -> Int -> ST s (MVector (PrimState (ST s)) Int)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> a -> m (MVector (PrimState m) a)
VUM.replicate Int
1 (Int -> ST s (MVector (PrimState (ST s)) Int))
-> Int -> ST s (MVector (PrimState (ST s)) Int)
forall a b. (a -> b) -> a -> b
$ Vector a -> Int
forall a. Unbox a => Vector a -> Int
VU.length Vector a
xs
  MVector s a
vecB <- Vector a -> ST s (MVector (PrimState (ST s)) a)
forall a (m :: * -> *).
(Unbox a, PrimMonad m) =>
Vector a -> m (MVector (PrimState m) a)
VU.thaw Vector a
xs
  Buffer s a -> ST s (Buffer s a)
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Buffer {MVector s a
MVector s Int
lenB :: MVector s Int
vecB :: MVector s a
lenB :: MVector s Int
vecB :: MVector s a
..}

{-# INLINEABLE backST #-}
backST :: (VU.Unbox a) => Buffer s a -> ST s (Maybe a)
backST :: forall a s. Unbox a => Buffer s a -> ST s (Maybe a)
backST Buffer {MVector s a
MVector s Int
lenB :: forall s a. Buffer s a -> MVector s Int
vecB :: forall s a. Buffer s a -> MVector s a
lenB :: MVector s Int
vecB :: MVector s a
..} = do
  Int
len <- MVector (PrimState (ST s)) Int -> Int -> ST s Int
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Int
MVector (PrimState (ST s)) Int
lenB Int
0
  if Int
len Int -> Int -> Bool
forall a. Eq 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
      a
x <- 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
vecB (Int
len Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)
      Maybe a -> ST s (Maybe a)
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Maybe a -> ST s (Maybe a)) -> Maybe a -> ST s (Maybe a)
forall a b. (a -> b) -> a -> b
$ a -> Maybe a
forall a. a -> Maybe a
Just a
x

{-# INLINEABLE readST #-}
readST :: (HasCallStack, VU.Unbox a) => Buffer s a -> Int -> ST s a
readST :: forall a s. (HasCallStack, Unbox a) => Buffer s a -> Int -> ST s a
readST Buffer {MVector s a
MVector s Int
lenB :: forall s a. Buffer s a -> MVector s Int
vecB :: forall s a. Buffer s a -> MVector s a
lenB :: MVector s Int
vecB :: MVector s a
..} Int
i = do
  Int
len <- MVector (PrimState (ST s)) Int -> Int -> ST s Int
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Int
MVector (PrimState (ST s)) Int
lenB Int
0
  let !()
_ = HasCallStack => String -> Int -> Int -> ()
String -> Int -> Int -> ()
ACIA.checkIndex String
"AtCoder.Internal.Buffer.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
vecB Int
i

{-# INLINEABLE readMaybeST #-}
readMaybeST :: (VU.Unbox a) => Buffer s a -> Int -> ST s (Maybe a)
readMaybeST :: forall a s. Unbox a => Buffer s a -> Int -> ST s (Maybe a)
readMaybeST Buffer {MVector s a
MVector s Int
lenB :: forall s a. Buffer s a -> MVector s Int
vecB :: forall s a. Buffer s a -> MVector s a
lenB :: MVector s Int
vecB :: MVector s a
..} Int
i = do
  Int
len <- MVector (PrimState (ST s)) Int -> Int -> ST s Int
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Int
MVector (PrimState (ST s)) Int
lenB 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
vecB 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 pushBackST #-}
pushBackST :: (HasCallStack, VU.Unbox a) => Buffer s a -> a -> ST s ()
pushBackST :: forall a s. (HasCallStack, Unbox a) => Buffer s a -> a -> ST s ()
pushBackST Buffer {MVector s a
MVector s Int
lenB :: forall s a. Buffer s a -> MVector s Int
vecB :: forall s a. Buffer s a -> MVector s a
lenB :: MVector s Int
vecB :: MVector s a
..} a
e = do
  Int
len <- MVector (PrimState (ST s)) Int -> Int -> ST s Int
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Int
MVector (PrimState (ST s)) Int
lenB Int
0
  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
vecB Int
len a
e
  MVector (PrimState (ST s)) Int -> Int -> Int -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector s Int
MVector (PrimState (ST s)) Int
lenB Int
0 (Int
len Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)

{-# INLINEABLE popBackST #-}
popBackST :: (VU.Unbox a) => Buffer s a -> ST s (Maybe a)
popBackST :: forall a s. Unbox a => Buffer s a -> ST s (Maybe a)
popBackST Buffer {MVector s a
MVector s Int
lenB :: forall s a. Buffer s a -> MVector s Int
vecB :: forall s a. Buffer s a -> MVector s a
lenB :: MVector s Int
vecB :: MVector s a
..} = do
  Int
len <- MVector (PrimState (ST s)) Int -> Int -> ST s Int
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Int
MVector (PrimState (ST s)) Int
lenB Int
0
  if Int
len Int -> Int -> Bool
forall a. Eq 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
      a
x <- 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
vecB (Int
len Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)
      MVector (PrimState (ST s)) Int -> Int -> Int -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector s Int
MVector (PrimState (ST s)) Int
lenB Int
0 (Int
len Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)
      Maybe a -> ST s (Maybe a)
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Maybe a -> ST s (Maybe a)) -> Maybe a -> ST s (Maybe a)
forall a b. (a -> b) -> a -> b
$ a -> Maybe a
forall a. a -> Maybe a
Just a
x

{-# INLINEABLE popBackST_ #-}
popBackST_ :: (VU.Unbox a) => Buffer s a -> ST s ()
popBackST_ :: forall a s. Unbox a => Buffer s a -> ST s ()
popBackST_ Buffer s a
buf = do
  Maybe a
_ <- Buffer (PrimState (ST s)) a -> ST s (Maybe a)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Buffer (PrimState m) a -> m (Maybe a)
popBack Buffer s a
Buffer (PrimState (ST s)) a
buf
  () -> ST s ()
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure ()

{-# INLINEABLE writeST #-}
writeST :: (HasCallStack, VU.Unbox a) => Buffer s a -> Int -> a -> ST s ()
writeST :: forall a s.
(HasCallStack, Unbox a) =>
Buffer s a -> Int -> a -> ST s ()
writeST Buffer {MVector s a
MVector s Int
lenB :: forall s a. Buffer s a -> MVector s Int
vecB :: forall s a. Buffer s a -> MVector s a
lenB :: MVector s Int
vecB :: MVector s a
..} Int
i a
e = do
  Int
len <- MVector (PrimState (ST s)) Int -> Int -> ST s Int
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Int
MVector (PrimState (ST s)) Int
lenB Int
0
  let !()
_ = HasCallStack => String -> Int -> Int -> ()
String -> Int -> Int -> ()
ACIA.checkIndex String
"AtCoder.Internal.Buffer.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
vecB Int
i a
e

{-# INLINEABLE modifyST #-}
modifyST :: (HasCallStack, VU.Unbox a) => Buffer s a -> (a -> a) -> Int -> ST s ()
modifyST :: forall a s.
(HasCallStack, Unbox a) =>
Buffer s a -> (a -> a) -> Int -> ST s ()
modifyST Buffer {MVector s a
MVector s Int
lenB :: forall s a. Buffer s a -> MVector s Int
vecB :: forall s a. Buffer s a -> MVector s a
lenB :: MVector s Int
vecB :: MVector s a
..} a -> a
f Int
i = do
  Int
len <- MVector (PrimState (ST s)) Int -> Int -> ST s Int
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Int
MVector (PrimState (ST s)) Int
lenB Int
0
  let !()
_ = HasCallStack => String -> Int -> Int -> ()
String -> Int -> Int -> ()
ACIA.checkIndex String
"AtCoder.Internal.Buffer.modify" Int
i Int
len
  MVector (PrimState (ST s)) a -> (a -> a) -> Int -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> (a -> a) -> Int -> m ()
VGM.modify MVector s a
MVector (PrimState (ST s)) a
vecB a -> a
f Int
i

{-# INLINEABLE freezeST #-}
freezeST :: (VU.Unbox a) => Buffer s a -> ST s (VU.Vector a)
freezeST :: forall a s. Unbox a => Buffer s a -> ST s (Vector a)
freezeST Buffer {MVector s a
MVector s Int
lenB :: forall s a. Buffer s a -> MVector s Int
vecB :: forall s a. Buffer s a -> MVector s a
lenB :: MVector s Int
vecB :: MVector s a
..} = do
  Int
len <- MVector (PrimState (ST s)) Int -> Int -> ST s Int
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Int
MVector (PrimState (ST s)) Int
lenB Int
0
  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
vecB

{-# INLINEABLE unsafeFreezeST #-}
unsafeFreezeST :: (VU.Unbox a) => Buffer s a -> ST s (VU.Vector a)
unsafeFreezeST :: forall a s. Unbox a => Buffer s a -> ST s (Vector a)
unsafeFreezeST Buffer {MVector s a
MVector s Int
lenB :: forall s a. Buffer s a -> MVector s Int
vecB :: forall s a. Buffer s a -> MVector s a
lenB :: MVector s Int
vecB :: MVector s a
..} = do
  Int
len <- MVector (PrimState (ST s)) Int -> Int -> ST s Int
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Int
MVector (PrimState (ST s)) Int
lenB Int
0
  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
vecB