Safe Haskell	Safe-Inferred
Language	GHC2021

AtCoder.Internal.Queue

Contents

Queue
Constructor
Metadata
Modifications
- Push/pop
- Reset
Conversions

Description

Fixed-sized queue. Internally it has an \([l, r)\) pair of valid element bounds.

Example

Expand

>>> 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.pushFront que 10   -- [10, 1, 2  _]
>>> Q.pushFront que 1000
*** Exception: AtCoder.Internal.Queue.pushFront: no empty front space
...

>>> Q.unsafeFreeze que -- [10, 1, 2  _]
[10,1,2]

>>> Q.clear que      -- [_  _  _  _]
>>> Q.pushBack que 0 -- [0  _  _  _]
>>> Q.pushBack que 1 -- [0, 1  _  _]
>>> Q.pushBack que 2 -- [0, 1, 2  _]
>>> Q.freeze que
[0,1,2]

Since: 1.0.0.0

Synopsis

data Queue s a
new :: (PrimMonad m, Unbox a) => Int -> m (Queue (PrimState m) a)
capacity :: Unbox a => Queue s a -> Int
length :: (PrimMonad m, Unbox a) => Queue (PrimState m) a -> m Int
null :: (PrimMonad m, Unbox a) => Queue (PrimState m) a -> m Bool
pushBack :: (HasCallStack, PrimMonad m, Unbox a) => Queue (PrimState m) a -> a -> m ()
pushFront :: (HasCallStack, PrimMonad m, Unbox a) => Queue (PrimState m) a -> a -> m ()
popFront :: (PrimMonad m, Unbox a) => Queue (PrimState m) a -> m (Maybe a)
popFront_ :: (PrimMonad m, Unbox a) => Queue (PrimState m) a -> m ()
clear :: (PrimMonad m, Unbox a) => Queue (PrimState m) a -> m ()
freeze :: (PrimMonad m, Unbox a) => Queue (PrimState m) a -> m (Vector a)
unsafeFreeze :: (PrimMonad m, Unbox a) => Queue (PrimState m) a -> m (Vector a)

Queue

data Queue s a Source #

Fixed-sized queue. Internally it has an \([l, r)\) pair of valid element bounds.

Since: 1.0.0.0

Constructor

new :: (PrimMonad m, Unbox a) => Int -> m (Queue (PrimState m) a) Source #

\(O(n)\) Creates a Queue with capacity \(n\).

Since: 1.0.0.0

Metadata

capacity :: Unbox a => Queue s a -> Int Source #

\(O(1)\) Returns the array size.

Since: 1.0.0.0

length :: (PrimMonad m, Unbox a) => Queue (PrimState m) a -> m Int Source #

\(O(1)\) Returns the number of elements in the queue.

Since: 1.0.0.0

null :: (PrimMonad m, Unbox a) => Queue (PrimState m) a -> m Bool Source #

\(O(1)\) Returns True if the buffer is empty.

Since: 1.0.0.0

Modifications

Push/pop

pushBack :: (HasCallStack, PrimMonad m, Unbox a) => Queue (PrimState m) a -> a -> m () Source #

\(O(1)\) Appends an element to the back. Will throw an exception if the index is out of range.

Since: 1.0.0.0

pushFront :: (HasCallStack, PrimMonad m, Unbox a) => Queue (PrimState m) a -> a -> m () Source #

\(O(1)\) Appends an element to the back. Will throw an exception if the index is out of range.

Since: 1.0.0.0

popFront :: (PrimMonad m, Unbox a) => Queue (PrimState m) a -> m (Maybe a) Source #

\(O(1)\) Removes the first element from the queue and returns it, or Nothing if it is empty.

Since: 1.0.0.0

popFront_ :: (PrimMonad m, Unbox a) => Queue (PrimState m) a -> m () Source #

\(O(1)\) popFront with the return value discarded.

Since: 1.0.0.0

Reset

clear :: (PrimMonad m, Unbox a) => Queue (PrimState m) a -> m () Source #

\(O(1)\) Sets the length to zero.

Since: 1.0.0.0

Conversions

freeze :: (PrimMonad m, Unbox a) => Queue (PrimState m) a -> m (Vector a) Source #

\(O(n)\) Yields an immutable copy of the mutable vector.

Since: 1.0.0.0

unsafeFreeze :: (PrimMonad m, Unbox a) => Queue (PrimState m) a -> m (Vector a) Source #

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