{-# LANGUAGE RecordWildCards #-}

-- | Fixed-sized queue. Internally it has an \([l, r)\) pair of valid element bounds.
--
-- ==== __Example__
-- >>> import AtCoder.Internal.Queue qualified as Q
-- >>> que <- Q.new @_ @Int 3
-- >>> Q.capacity que
-- 3
--
-- >>> Q.pushBack que 0 -- [0  _  _  _]
-- >>> Q.pushBack que 1 -- [0, 1  _  _]
-- >>> Q.pushBack que 2 -- [0, 1, 2  _]
-- >>> Q.length que
-- 3
--
-- >>> Q.popFront que   -- [_  1, 2  _]
-- Just 0
--
-- >>> Q.freeze que     -- [_  1, 2  _]
-- [1,2]
--
-- >>> Q.readFront que 0
-- 1
--
-- >>> Q.readFront que 1
-- 2
--
-- >>> Q.readFront que (-1)
-- *** Exception: AtCoder.Internal.Queue.readFront: index out of bounds
-- ...
--
-- >>> Q.readFront que 2
-- *** Exception: AtCoder.Internal.Queue.readFront: index out of bounds
-- ...
--
-- >>> Q.readMaybeFront que (-1)
-- Nothing
--
-- >>> Q.readMaybeFront que 2
-- Nothing
--
-- >>> Q.writeFront que 0 10 -- [_ 10, 2  _]
-- >>> Q.writeFront que 1 20 -- [_ 10, 20 _]
--
-- >>> Q.writeFront que (-1) 777
-- *** Exception: AtCoder.Internal.Queue.modifyFrontM: index out of bounds
-- ...
--
-- >>> Q.writeFront que 2 777
-- *** Exception: AtCoder.Internal.Queue.modifyFrontM: index out of bounds
-- ...
--
-- >>> Q.readBack que 0
-- 20
--
-- >>> Q.readBack que 1
-- 10
--
-- >>> Q.readBack que (-1)
-- *** Exception: AtCoder.Internal.Queue.readBack: index out of bounds
-- ...
--
-- >>> Q.readBack que 2
-- *** Exception: AtCoder.Internal.Queue.readBack: index out of bounds
-- ...
--
-- >>> Q.readMaybeBack que (-1)
-- Nothing
--
-- >>> Q.readMaybeBack que 2
-- Nothing
--
-- >>> Q.writeBack que 0 200
-- >>> Q.writeBack que 1 100
--
-- >>> Q.writeBack que (-1) 777
-- *** Exception: AtCoder.Internal.Queue.modifyBackM: index out of bounds
-- ...
--
-- >>> Q.writeBack que 2 777
-- *** Exception: AtCoder.Internal.Queue.modifyBackM: index out of bounds
-- ...
--
-- >>> Q.pushFront que 10 -- [10, 100, 200  _]
-- >>> Q.pushFront que 1000
-- *** Exception: AtCoder.Internal.Queue.pushFrontST: no empty front space
-- ...
--
-- >>> Q.unsafeFreeze que -- [10, 100, 200  _]
-- [10,100,200]
--
-- >>> Q.clear que        -- [_  _  _  _]
-- >>> Q.peekBack que
-- Nothing
--
-- >>> Q.popFront que
-- Nothing
--
-- >>> Q.popBack que
-- Nothing
--
-- >>> Q.pushBack que 0 -- [0  _  _  _]
-- >>> Q.peekBack que
-- Just 0
--
-- >>> Q.pushBack que 1 -- [0, 1  _  _]
-- >>> Q.pushBack que 2 -- [0, 1, 2  _]
-- >>> Q.popBack que    -- [0, 1  _  _]
-- Just 2
--
-- >>> Q.freeze que
-- [0,1]

-- >>> Q.clear que
-- >>> Q.freeze que
-- []
--
-- @since 1.0.0.0
module AtCoder.Internal.Queue
  ( -- * Queue
    Queue,

    -- * Constructor
    new,
    newDeque,

    -- * Metadata
    capacity,
    length,
    null,

    -- * Element access

    -- ** Peek
    peekBack,
    peekFront,

    -- ** Push
    pushBack,
    pushFront,

    -- ** op
    popBack,
    popBack_,
    popFront,
    popFront_,

    -- ** Read/write/modify
    readFront,
    readBack,
    readMaybeFront,
    readMaybeBack,
    writeFront,
    writeBack,
    modifyFront,
    modifyFrontM,
    modifyBack,
    modifyBackM,

    -- ** Clear (reset)
    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.Maybe (fromMaybe)
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)

-- | Fixed-sized queue. Internally it has an \([l, r)\) pair of valid element bounds.
--
-- @since 1.0.0.0
data Queue s a = Queue
  { -- | Stores [l, r) range in the `vecQ`.
    forall s a. Queue s a -> MVector s Int
posQ :: !(VUM.MVector s Int),
    forall s a. Queue s a -> MVector s a
vecQ :: !(VUM.MVector s a)
  }

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

-- | \(O(n)\) Creates a `Queue` with capacity \(2n + 1\) where the internal front/back position is
-- initialzed at \(n\).
--
-- @since 1.2.4.0
{-# INLINEABLE newDeque #-}
newDeque :: (PrimMonad m, VU.Unbox a) => Int -> m (Queue (PrimState m) a)
newDeque :: forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> m (Queue (PrimState m) a)
newDeque Int
n = ST (PrimState m) (Queue (PrimState m) a)
-> m (Queue (PrimState m) a)
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) (Queue (PrimState m) a)
 -> m (Queue (PrimState m) a))
-> ST (PrimState m) (Queue (PrimState m) a)
-> m (Queue (PrimState m) a)
forall a b. (a -> b) -> a -> b
$ do
  MVector (PrimState m) Int
posQ <- Int
-> Int
-> ST (PrimState m) (MVector (PrimState (ST (PrimState m))) Int)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> a -> m (MVector (PrimState m) a)
VUM.replicate Int
2 Int
n
  MVector (PrimState m) a
vecQ <- Int -> ST (PrimState m) (MVector (PrimState (ST (PrimState m))) a)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> m (MVector (PrimState m) a)
VUM.unsafeNew (Int
2 Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
  Queue (PrimState m) a -> ST (PrimState m) (Queue (PrimState m) a)
forall a. a -> ST (PrimState m) a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Queue {MVector (PrimState m) a
MVector (PrimState m) Int
vecQ :: MVector (PrimState m) a
posQ :: MVector (PrimState m) Int
posQ :: MVector (PrimState m) Int
vecQ :: MVector (PrimState m) a
..}

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

-- | \(O(1)\) Returns the number of elements in the queue.
--
-- @since 1.0.0.0
{-# INLINE length #-}
length :: (PrimMonad m, VU.Unbox a) => Queue (PrimState m) a -> m Int
length :: forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Queue (PrimState m) a -> m Int
length Queue (PrimState m) a
que = 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
$ Queue (PrimState m) a -> ST (PrimState m) Int
forall a s. Unbox a => Queue s a -> ST s Int
lengthST Queue (PrimState m) a
que

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

-- | \(O(1)\) Peeks the last element in the queue.
--
-- @since 1.2.3.0
{-# INLINE peekBack #-}
peekBack :: (PrimMonad m, VU.Unbox a) => Queue (PrimState m) a -> m (Maybe a)
peekBack :: forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Queue (PrimState m) a -> m (Maybe a)
peekBack Queue (PrimState m) a
que = 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
$ Queue (PrimState m) a -> ST (PrimState m) (Maybe a)
forall a s. Unbox a => Queue s a -> ST s (Maybe a)
peekBackST Queue (PrimState m) a
que

-- | \(O(1)\) Peeks the first element in the queue.
--
-- @since 1.2.3.0
{-# INLINE peekFront #-}
peekFront :: (PrimMonad m, VU.Unbox a) => Queue (PrimState m) a -> m (Maybe a)
peekFront :: forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Queue (PrimState m) a -> m (Maybe a)
peekFront Queue (PrimState m) a
que = 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
$ Queue (PrimState m) a -> ST (PrimState m) (Maybe a)
forall a s. Unbox a => Queue s a -> ST s (Maybe a)
peekFrontST Queue (PrimState m) a
que

-- | \(O(1)\) Appends an element to the back. Will throw an exception if the index is out of range.
--
-- @since 1.0.0.0
{-# INLINE pushBack #-}
pushBack :: (HasCallStack, PrimMonad m, VU.Unbox a) => Queue (PrimState m) a -> a -> m ()
pushBack :: forall (m :: * -> *) a.
(HasCallStack, PrimMonad m, Unbox a) =>
Queue (PrimState m) a -> a -> m ()
pushBack Queue (PrimState m) a
que 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
$ Queue (PrimState m) a -> a -> ST (PrimState m) ()
forall a s. (HasCallStack, Unbox a) => Queue s a -> a -> ST s ()
pushBackST Queue (PrimState m) a
que a
e

-- | \(O(1)\) Appends an element to the back. Will throw an exception if the index is out of range.
--
-- @since 1.0.0.0
{-# INLINE pushFront #-}
pushFront :: (HasCallStack, PrimMonad m, VU.Unbox a) => Queue (PrimState m) a -> a -> m ()
pushFront :: forall (m :: * -> *) a.
(HasCallStack, PrimMonad m, Unbox a) =>
Queue (PrimState m) a -> a -> m ()
pushFront Queue (PrimState m) a
que 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
$ Queue (PrimState m) a -> a -> ST (PrimState m) ()
forall a s. (HasCallStack, Unbox a) => Queue s a -> a -> ST s ()
pushFrontST Queue (PrimState m) a
que a
e

-- | \(O(1)\) Removes the last element from the queue and returns it, or `Nothing` if it is empty.
--
-- @since 1.2.3.0
{-# INLINE popBack #-}
popBack :: (PrimMonad m, VU.Unbox a) => Queue (PrimState m) a -> m (Maybe a)
popBack :: forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Queue (PrimState m) a -> m (Maybe a)
popBack Queue (PrimState m) a
que = 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
$ Queue (PrimState m) a -> ST (PrimState m) (Maybe a)
forall a s. Unbox a => Queue s a -> ST s (Maybe a)
popBackST Queue (PrimState m) a
que

-- | \(O(1)\) `popBack` with the return value discarded.
--
-- @since 1.2.3.0
{-# INLINE popBack_ #-}
popBack_ :: (PrimMonad m, VU.Unbox a) => Queue (PrimState m) a -> m ()
popBack_ :: forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Queue (PrimState m) a -> m ()
popBack_ Queue (PrimState m) a
que = 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
$ Queue (PrimState m) a -> ST (PrimState m) ()
forall a s. Unbox a => Queue s a -> ST s ()
popBackST_ Queue (PrimState m) a
que

-- | \(O(1)\) Removes the first element from the queue and returns it, or `Nothing` if it is empty.
--
-- @since 1.0.0.0
{-# INLINE popFront #-}
popFront :: (PrimMonad m, VU.Unbox a) => Queue (PrimState m) a -> m (Maybe a)
popFront :: forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Queue (PrimState m) a -> m (Maybe a)
popFront Queue (PrimState m) a
que = 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
$ Queue (PrimState m) a -> ST (PrimState m) (Maybe a)
forall a s. Unbox a => Queue s a -> ST s (Maybe a)
popFrontST Queue (PrimState m) a
que

-- | \(O(1)\) `popFront` with the return value discarded.
--
-- @since 1.0.0.0
{-# INLINE popFront_ #-}
popFront_ :: (PrimMonad m, VU.Unbox a) => Queue (PrimState m) a -> m ()
popFront_ :: forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Queue (PrimState m) a -> m ()
popFront_ Queue (PrimState m) a
que = 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
$ Queue (PrimState m) a -> ST (PrimState m) ()
forall a s. Unbox a => Queue s a -> ST s ()
popFrontST_ Queue (PrimState m) a
que

-- | \(O(1)\) Returns the \(k\)-th value from the first element.
--
-- @since 1.2.3.0
{-# INLINE readFront #-}
readFront :: (HasCallStack, PrimMonad m, VU.Unbox a) => Queue (PrimState m) a -> Int -> m a
readFront :: forall (m :: * -> *) a.
(HasCallStack, PrimMonad m, Unbox a) =>
Queue (PrimState m) a -> Int -> m a
readFront Queue (PrimState m) a
que 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
$ a -> Maybe a -> a
forall a. a -> Maybe a -> a
fromMaybe ([Char] -> a
forall a. HasCallStack => [Char] -> a
error [Char]
msg) (Maybe a -> a) -> ST (PrimState m) (Maybe a) -> ST (PrimState m) a
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Queue (PrimState m) a -> Int -> ST (PrimState m) (Maybe a)
forall a s. Unbox a => Queue s a -> Int -> ST s (Maybe a)
readMaybeFrontST Queue (PrimState m) a
que Int
i
  where
    msg :: [Char]
msg = [Char]
"AtCoder.Internal.Queue.readFront: index out of bounds"

-- | \(O(1)\) Returns the \(k\)-th value from the last element.
--
-- @since 1.2.3.0
{-# INLINE readBack #-}
readBack :: (HasCallStack, PrimMonad m, VU.Unbox a) => Queue (PrimState m) a -> Int -> m a
readBack :: forall (m :: * -> *) a.
(HasCallStack, PrimMonad m, Unbox a) =>
Queue (PrimState m) a -> Int -> m a
readBack Queue (PrimState m) a
que 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
$ a -> Maybe a -> a
forall a. a -> Maybe a -> a
fromMaybe ([Char] -> a
forall a. HasCallStack => [Char] -> a
error [Char]
msg) (Maybe a -> a) -> ST (PrimState m) (Maybe a) -> ST (PrimState m) a
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Queue (PrimState m) a -> Int -> ST (PrimState m) (Maybe a)
forall a s. Unbox a => Queue s a -> Int -> ST s (Maybe a)
readMaybeBackST Queue (PrimState m) a
que Int
i
  where
    msg :: [Char]
msg = [Char]
"AtCoder.Internal.Queue.readBack: index out of bounds"

-- | \(O(1)\) Returns the \(k\)-th value from the first element.
--
-- @since 1.2.3.0
{-# INLINE readMaybeFront #-}
readMaybeFront :: (PrimMonad m, VU.Unbox a) => Queue (PrimState m) a -> Int -> m (Maybe a)
readMaybeFront :: forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Queue (PrimState m) a -> Int -> m (Maybe a)
readMaybeFront Queue (PrimState m) a
que 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
$ Queue (PrimState m) a -> Int -> ST (PrimState m) (Maybe a)
forall a s. Unbox a => Queue s a -> Int -> ST s (Maybe a)
readMaybeFrontST Queue (PrimState m) a
que Int
i

-- | \(O(1)\) Returns the \(k\)-th value from the last element.
--
-- @since 1.2.3.0
{-# INLINE readMaybeBack #-}
readMaybeBack :: (PrimMonad m, VU.Unbox a) => Queue (PrimState m) a -> Int -> m (Maybe a)
readMaybeBack :: forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Queue (PrimState m) a -> Int -> m (Maybe a)
readMaybeBack Queue (PrimState m) a
que 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
$ Queue (PrimState m) a -> Int -> ST (PrimState m) (Maybe a)
forall a s. Unbox a => Queue s a -> Int -> ST s (Maybe a)
readMaybeBackST Queue (PrimState m) a
que Int
i

-- | \(O(1)\) Writes to the \(k\)-th value from the first element.
--
-- @since 1.2.3.0
{-# INLINE writeFront #-}
writeFront :: (HasCallStack, PrimMonad m, VU.Unbox a) => Queue (PrimState m) a -> Int -> a -> m ()
writeFront :: forall (m :: * -> *) a.
(HasCallStack, PrimMonad m, Unbox a) =>
Queue (PrimState m) a -> Int -> a -> m ()
writeFront Queue (PrimState m) a
que 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
$ do
  Queue (PrimState (ST (PrimState m))) a
-> (a -> ST (PrimState m) a) -> Int -> ST (PrimState m) ()
forall (m :: * -> *) a.
(HasCallStack, PrimMonad m, Unbox a) =>
Queue (PrimState m) a -> (a -> m a) -> Int -> m ()
modifyFrontM Queue (PrimState m) a
Queue (PrimState (ST (PrimState m))) a
que (a -> ST (PrimState m) a
forall a. a -> ST (PrimState m) a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (a -> ST (PrimState m) a) -> (a -> a) -> a -> ST (PrimState m) a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> a -> a
forall a b. a -> b -> a
const a
x) Int
i

-- | \(O(1)\) Writes to the \(k\)-th value from the last element.
--
-- @since 1.2.3.0
{-# INLINE writeBack #-}
writeBack :: (HasCallStack, PrimMonad m, VU.Unbox a) => Queue (PrimState m) a -> Int -> a -> m ()
writeBack :: forall (m :: * -> *) a.
(HasCallStack, PrimMonad m, Unbox a) =>
Queue (PrimState m) a -> Int -> a -> m ()
writeBack Queue (PrimState m) a
que 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
$ do
  Queue (PrimState (ST (PrimState m))) a
-> (a -> ST (PrimState m) a) -> Int -> ST (PrimState m) ()
forall (m :: * -> *) a.
(HasCallStack, PrimMonad m, Unbox a) =>
Queue (PrimState m) a -> (a -> m a) -> Int -> m ()
modifyBackM Queue (PrimState m) a
Queue (PrimState (ST (PrimState m))) a
que (a -> ST (PrimState m) a
forall a. a -> ST (PrimState m) a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (a -> ST (PrimState m) a) -> (a -> a) -> a -> ST (PrimState m) a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> a -> a
forall a b. a -> b -> a
const a
x) Int
i

-- | \(O(1)\) Given user function \(f\), returns the \(k\)-th value from the first element.
--
-- @since 1.2.3.0
{-# INLINE modifyFront #-}
modifyFront :: (HasCallStack, PrimMonad m, VU.Unbox a) => Queue (PrimState m) a -> (a -> a) -> Int -> m ()
modifyFront :: forall (m :: * -> *) a.
(HasCallStack, PrimMonad m, Unbox a) =>
Queue (PrimState m) a -> (a -> a) -> Int -> m ()
modifyFront Queue (PrimState m) a
que 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
$ do
  Queue (PrimState (ST (PrimState m))) a
-> (a -> ST (PrimState m) a) -> Int -> ST (PrimState m) ()
forall (m :: * -> *) a.
(HasCallStack, PrimMonad m, Unbox a) =>
Queue (PrimState m) a -> (a -> m a) -> Int -> m ()
modifyFrontM Queue (PrimState m) a
Queue (PrimState (ST (PrimState m))) a
que (a -> ST (PrimState m) a
forall a. a -> ST (PrimState m) a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (a -> ST (PrimState m) a) -> (a -> a) -> a -> ST (PrimState m) a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> a
f) Int
i

-- | \(O(1)\) Given user function \(f\), returns the \(k\)-th value from the last element.
--
-- @since 1.2.3.0
{-# INLINE modifyBack #-}
modifyBack :: (HasCallStack, PrimMonad m, VU.Unbox a) => Queue (PrimState m) a -> (a -> a) -> Int -> m ()
modifyBack :: forall (m :: * -> *) a.
(HasCallStack, PrimMonad m, Unbox a) =>
Queue (PrimState m) a -> (a -> a) -> Int -> m ()
modifyBack Queue (PrimState m) a
que 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
$ do
  Queue (PrimState (ST (PrimState m))) a
-> (a -> ST (PrimState m) a) -> Int -> ST (PrimState m) ()
forall (m :: * -> *) a.
(HasCallStack, PrimMonad m, Unbox a) =>
Queue (PrimState m) a -> (a -> m a) -> Int -> m ()
modifyBackM Queue (PrimState m) a
Queue (PrimState (ST (PrimState m))) a
que (a -> ST (PrimState m) a
forall a. a -> ST (PrimState m) a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (a -> ST (PrimState m) a) -> (a -> a) -> a -> ST (PrimState m) a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> a
f) Int
i

-- | \(O(1)\) Given user function \(f\), returns the \(k\)-th value from the first element.
--
-- @since 1.2.3.0
{-# INLINE modifyFrontM #-}
modifyFrontM :: (HasCallStack, PrimMonad m, VU.Unbox a) => Queue (PrimState m) a -> (a -> m a) -> Int -> m ()
modifyFrontM :: forall (m :: * -> *) a.
(HasCallStack, PrimMonad m, Unbox a) =>
Queue (PrimState m) a -> (a -> m a) -> Int -> m ()
modifyFrontM Queue {MVector (PrimState m) a
MVector (PrimState m) Int
vecQ :: forall s a. Queue s a -> MVector s a
posQ :: forall s a. Queue s a -> MVector s Int
posQ :: MVector (PrimState m) Int
vecQ :: MVector (PrimState m) a
..} a -> m a
f Int
i = do
  Int
l <- 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
posQ Int
0
  Int
r <- 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
posQ Int
1
  let !()
_ = HasCallStack => Bool -> [Char] -> ()
Bool -> [Char] -> ()
ACIA.runtimeAssert (Int
0 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
i Bool -> Bool -> Bool
&& Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
r Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
l) [Char]
"AtCoder.Internal.Queue.modifyFrontM: index out of bounds"
  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
vecQ a -> m a
f (Int
l Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
i)

-- | \(O(1)\) Given user function \(f\), returns the \(k\)-th value from the last element.
--
-- @since 1.2.3.0
{-# INLINE modifyBackM #-}
modifyBackM :: (HasCallStack, PrimMonad m, VU.Unbox a) => Queue (PrimState m) a -> (a -> m a) -> Int -> m ()
modifyBackM :: forall (m :: * -> *) a.
(HasCallStack, PrimMonad m, Unbox a) =>
Queue (PrimState m) a -> (a -> m a) -> Int -> m ()
modifyBackM Queue {MVector (PrimState m) a
MVector (PrimState m) Int
vecQ :: forall s a. Queue s a -> MVector s a
posQ :: forall s a. Queue s a -> MVector s Int
posQ :: MVector (PrimState m) Int
vecQ :: MVector (PrimState m) a
..} a -> m a
f Int
i = do
  Int
l <- 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
posQ Int
0
  Int
r <- 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
posQ Int
1
  let !()
_ = HasCallStack => Bool -> [Char] -> ()
Bool -> [Char] -> ()
ACIA.runtimeAssert (Int
0 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
i Bool -> Bool -> Bool
&& Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
r Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
l) [Char]
"AtCoder.Internal.Queue.modifyBackM: index out of bounds"
  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
vecQ a -> m a
f (Int
r Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
i)

-- | \(O(1)\) Sets the `length` to zero.
--
-- @since 1.0.0.0
{-# INLINE clear #-}
clear :: (PrimMonad m, VU.Unbox a) => Queue (PrimState m) a -> m ()
clear :: forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Queue (PrimState m) a -> m ()
clear Queue {MVector (PrimState m) a
MVector (PrimState m) Int
vecQ :: forall s a. Queue s a -> MVector s a
posQ :: forall s a. Queue s a -> MVector s Int
posQ :: MVector (PrimState m) Int
vecQ :: MVector (PrimState m) a
..} = do
  MVector (PrimState m) Int -> Int -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> a -> m ()
VGM.set MVector (PrimState m) Int
posQ 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) => Queue (PrimState m) a -> m (VU.Vector a)
freeze :: forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Queue (PrimState m) a -> m (Vector a)
freeze Queue (PrimState m) a
que = 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))
-> ST (PrimState m) (Vector a) -> m (Vector a)
forall a b. (a -> b) -> a -> b
$ Queue (PrimState m) a -> ST (PrimState m) (Vector a)
forall a s. Unbox a => Queue s a -> ST s (Vector a)
freezeST Queue (PrimState m) a
que

-- | \(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) => Queue (PrimState m) a -> m (VU.Vector a)
unsafeFreeze :: forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Queue (PrimState m) a -> m (Vector a)
unsafeFreeze Queue (PrimState m) a
que = 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))
-> ST (PrimState m) (Vector a) -> m (Vector a)
forall a b. (a -> b) -> a -> b
$ Queue (PrimState m) a -> ST (PrimState m) (Vector a)
forall a s. Unbox a => Queue s a -> ST s (Vector a)
unsafeFreezeST Queue (PrimState m) a
que

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

{-# INLINEABLE newST #-}
newST :: (VU.Unbox a) => Int -> ST s (Queue s a)
newST :: forall a s. Unbox a => Int -> ST s (Queue s a)
newST Int
n = do
  MVector s Int
posQ <- 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
2 (Int
0 :: Int)
  MVector s a
vecQ <- 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
  Queue s a -> ST s (Queue s a)
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Queue {MVector s a
MVector s Int
vecQ :: MVector s a
posQ :: MVector s Int
posQ :: MVector s Int
vecQ :: MVector s a
..}

{-# INLINEABLE lengthST #-}
lengthST :: (VU.Unbox a) => Queue s a -> ST s Int
lengthST :: forall a s. Unbox a => Queue s a -> ST s Int
lengthST Queue {MVector s a
MVector s Int
vecQ :: forall s a. Queue s a -> MVector s a
posQ :: forall s a. Queue s a -> MVector s Int
posQ :: MVector s Int
vecQ :: MVector s a
..} = do
  Int
l <- 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
posQ Int
0
  Int
r <- 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
posQ Int
1
  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
l

{-# INLINEABLE peekBackST #-}
peekBackST :: (VU.Unbox a) => Queue s a -> ST s (Maybe a)
peekBackST :: forall a s. Unbox a => Queue s a -> ST s (Maybe a)
peekBackST Queue {MVector s a
MVector s Int
vecQ :: forall s a. Queue s a -> MVector s a
posQ :: forall s a. Queue s a -> MVector s Int
posQ :: MVector s Int
vecQ :: MVector s a
..} = do
  Int
l <- 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
posQ Int
0
  Int
r <- 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
posQ Int
1
  if Int
l Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
r
    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 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
vecQ (Int
r Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)

{-# INLINEABLE peekFrontST #-}
peekFrontST :: (VU.Unbox a) => Queue s a -> ST s (Maybe a)
peekFrontST :: forall a s. Unbox a => Queue s a -> ST s (Maybe a)
peekFrontST Queue {MVector s a
MVector s Int
vecQ :: forall s a. Queue s a -> MVector s a
posQ :: forall s a. Queue s a -> MVector s Int
posQ :: MVector s Int
vecQ :: MVector s a
..} = do
  Int
l <- 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
posQ Int
0
  Int
r <- 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
posQ Int
1
  if Int
l Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
r
    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 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
vecQ Int
l

{-# INLINEABLE pushBackST #-}
pushBackST :: (HasCallStack, VU.Unbox a) => Queue s a -> a -> ST s ()
pushBackST :: forall a s. (HasCallStack, Unbox a) => Queue s a -> a -> ST s ()
pushBackST Queue {MVector s a
MVector s Int
vecQ :: forall s a. Queue s a -> MVector s a
posQ :: forall s a. Queue s a -> MVector s Int
posQ :: MVector s Int
vecQ :: MVector s a
..} a
e = do
  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
posQ
    ( \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
vecQ 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
1

{-# INLINEABLE pushFrontST #-}
pushFrontST :: (HasCallStack, VU.Unbox a) => Queue s a -> a -> ST s ()
pushFrontST :: forall a s. (HasCallStack, Unbox a) => Queue s a -> a -> ST s ()
pushFrontST Queue {MVector s a
MVector s Int
vecQ :: forall s a. Queue s a -> MVector s a
posQ :: forall s a. Queue s a -> MVector s Int
posQ :: MVector s Int
vecQ :: MVector s a
..} a
e = do
  Int
l0 <- 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
posQ Int
0
  let !()
_ = HasCallStack => Bool -> [Char] -> ()
Bool -> [Char] -> ()
ACIA.runtimeAssert (Int
l0 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0) [Char]
"AtCoder.Internal.Queue.pushFrontST: no empty front space"
  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
posQ
    ( \Int
l -> 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
vecQ (Int
l Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) 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
l Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1
    )
    Int
0

{-# INLINEABLE popBackST #-}
popBackST :: (VU.Unbox a) => Queue s a -> ST s (Maybe a)
popBackST :: forall a s. Unbox a => Queue s a -> ST s (Maybe a)
popBackST Queue {MVector s a
MVector s Int
vecQ :: forall s a. Queue s a -> MVector s a
posQ :: forall s a. Queue s a -> MVector s Int
posQ :: MVector s Int
vecQ :: MVector s a
..} = do
  Int
l <- 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
posQ Int
0
  Int
r <- 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
posQ Int
1
  if Int
l Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
r
    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
vecQ (Int
r 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.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.unsafeWrite MVector s Int
MVector (PrimState (ST s)) Int
posQ Int
1 (Int
r 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) => Queue s a -> ST s ()
popBackST_ :: forall a s. Unbox a => Queue s a -> ST s ()
popBackST_ Queue s a
que = do
  Maybe a
_ <- Queue s a -> ST s (Maybe a)
forall a s. Unbox a => Queue s a -> ST s (Maybe a)
popBackST Queue s a
que
  () -> ST s ()
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure ()

{-# INLINEABLE popFrontST #-}
popFrontST :: (VU.Unbox a) => Queue s a -> ST s (Maybe a)
popFrontST :: forall a s. Unbox a => Queue s a -> ST s (Maybe a)
popFrontST Queue {MVector s a
MVector s Int
vecQ :: forall s a. Queue s a -> MVector s a
posQ :: forall s a. Queue s a -> MVector s Int
posQ :: MVector s Int
vecQ :: MVector s a
..} = do
  Int
l <- 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
posQ Int
0
  Int
r <- 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
posQ Int
1
  if Int
l Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
r
    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
vecQ Int
l
      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
posQ Int
0 (Int
l 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 popFrontST_ #-}
popFrontST_ :: (VU.Unbox a) => Queue s a -> ST s ()
popFrontST_ :: forall a s. Unbox a => Queue s a -> ST s ()
popFrontST_ Queue s a
que = do
  Maybe a
_ <- Queue s a -> ST s (Maybe a)
forall a s. Unbox a => Queue s a -> ST s (Maybe a)
popFrontST Queue s a
que
  () -> ST s ()
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure ()

{-# INLINEABLE readMaybeFrontST #-}
readMaybeFrontST :: (VU.Unbox a) => Queue s a -> Int -> ST s (Maybe a)
readMaybeFrontST :: forall a s. Unbox a => Queue s a -> Int -> ST s (Maybe a)
readMaybeFrontST Queue {MVector s a
MVector s Int
vecQ :: forall s a. Queue s a -> MVector s a
posQ :: forall s a. Queue s a -> MVector s Int
posQ :: MVector s Int
vecQ :: MVector s a
..} Int
i = do
  Int
l <- 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
posQ Int
0
  Int
r <- 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
posQ Int
1
  if Int
0 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
i Bool -> Bool -> Bool
&& Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
r Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
l
    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.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s a
MVector (PrimState (ST s)) a
vecQ (Int
l 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

{-# INLINEABLE readMaybeBackST #-}
readMaybeBackST :: (VU.Unbox a) => Queue s a -> Int -> ST s (Maybe a)
readMaybeBackST :: forall a s. Unbox a => Queue s a -> Int -> ST s (Maybe a)
readMaybeBackST Queue {MVector s a
MVector s Int
vecQ :: forall s a. Queue s a -> MVector s a
posQ :: forall s a. Queue s a -> MVector s Int
posQ :: MVector s Int
vecQ :: MVector s a
..} Int
i = do
  Int
l <- 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
posQ Int
0
  Int
r <- 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
posQ Int
1
  if Int
0 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
i Bool -> Bool -> Bool
&& Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
r Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
l
    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.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s a
MVector (PrimState (ST s)) a
vecQ (Int
r 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

{-# INLINEABLE freezeST #-}
freezeST :: (VU.Unbox a) => Queue s a -> ST s (VU.Vector a)
freezeST :: forall a s. Unbox a => Queue s a -> ST s (Vector a)
freezeST Queue {MVector s a
MVector s Int
vecQ :: forall s a. Queue s a -> MVector s a
posQ :: forall s a. Queue s a -> MVector s Int
posQ :: MVector s Int
vecQ :: MVector s a
..} = do
  Int
l <- 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
posQ Int
0
  Int
r <- 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
posQ Int
1
  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 (PrimState (ST s)) a -> MVector (PrimState (ST s)) a
forall a s. Unbox a => Int -> MVector s a -> MVector s a
VUM.take (Int
r Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
l) (MVector (PrimState (ST s)) a -> MVector (PrimState (ST s)) a)
-> MVector (PrimState (ST s)) a -> MVector (PrimState (ST s)) 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.drop Int
l MVector s a
vecQ

{-# INLINEABLE unsafeFreezeST #-}
unsafeFreezeST :: (VU.Unbox a) => Queue s a -> ST s (VU.Vector a)
unsafeFreezeST :: forall a s. Unbox a => Queue s a -> ST s (Vector a)
unsafeFreezeST Queue {MVector s a
MVector s Int
vecQ :: forall s a. Queue s a -> MVector s a
posQ :: forall s a. Queue s a -> MVector s Int
posQ :: MVector s Int
vecQ :: MVector s a
..} = do
  Int
l <- 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
posQ Int
0
  Int
r <- 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
posQ Int
1
  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 (PrimState (ST s)) a -> MVector (PrimState (ST s)) a
forall a s. Unbox a => Int -> MVector s a -> MVector s a
VUM.take (Int
r Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
l) (MVector (PrimState (ST s)) a -> MVector (PrimState (ST s)) a)
-> MVector (PrimState (ST s)) a -> MVector (PrimState (ST s)) 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.drop Int
l MVector s a
vecQ