Safe Haskell	None
Language	GHC2021

AtCoder.Internal.Queue

Contents

Queue
Constructor
Modifying the queue
Accessors
Clearing
Conversions

Description

Fixed-sized queue. Internally it has \(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.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

Synopsis

data Queue s a
new :: (PrimMonad m, Unbox a) => Int -> m (Queue (PrimState m) a)
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 ()
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
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 #

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

Since: 1.0.0

Constructor

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

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

Since: 1.0.0

Modifying the queue

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

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

Since: 1.0.0

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

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

Since: 1.0.0

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

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

Since: 1.0.0

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

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

Since: 1.0.0

Accessors

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

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

Since: 1.0.0

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

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

Since: 1.0.0

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

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

Since: 1.0.0

Clearing

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

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

Since: 1.0.0

Conversions

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

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

Since: 1.0.0

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

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