Safe Haskell	None
Language	GHC2021

AtCoder.Internal.Queue

Contents

Queue
Constructor
Metadata
Element access
Conversions

Description

Fixed-sized double-ended 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.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]

Synopsis

data Queue s a
new :: (PrimMonad m, Unbox a) => Int -> m (Queue (PrimState m) a)
newDeque :: (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
peekBack :: (PrimMonad m, Unbox a) => Queue (PrimState m) a -> m (Maybe a)
peekFront :: (PrimMonad m, Unbox a) => Queue (PrimState m) a -> m (Maybe 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 ()
popBack :: (PrimMonad m, Unbox a) => Queue (PrimState m) a -> m (Maybe a)
popBack_ :: (PrimMonad m, Unbox a) => Queue (PrimState m) a -> m ()
popFront :: (PrimMonad m, Unbox a) => Queue (PrimState m) a -> m (Maybe a)
popFront_ :: (PrimMonad m, Unbox a) => Queue (PrimState m) a -> m ()
readFront :: (HasCallStack, PrimMonad m, Unbox a) => Queue (PrimState m) a -> Int -> m a
readBack :: (HasCallStack, PrimMonad m, Unbox a) => Queue (PrimState m) a -> Int -> m a
readMaybeFront :: (PrimMonad m, Unbox a) => Queue (PrimState m) a -> Int -> m (Maybe a)
readMaybeBack :: (PrimMonad m, Unbox a) => Queue (PrimState m) a -> Int -> m (Maybe a)
writeFront :: (HasCallStack, PrimMonad m, Unbox a) => Queue (PrimState m) a -> Int -> a -> m ()
writeBack :: (HasCallStack, PrimMonad m, Unbox a) => Queue (PrimState m) a -> Int -> a -> m ()
modifyFront :: (HasCallStack, PrimMonad m, Unbox a) => Queue (PrimState m) a -> (a -> a) -> Int -> m ()
modifyFrontM :: (HasCallStack, PrimMonad m, Unbox a) => Queue (PrimState m) a -> (a -> m a) -> Int -> m ()
modifyBack :: (HasCallStack, PrimMonad m, Unbox a) => Queue (PrimState m) a -> (a -> a) -> Int -> m ()
modifyBackM :: (HasCallStack, PrimMonad m, Unbox a) => Queue (PrimState m) a -> (a -> m a) -> Int -> 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 double-ended 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

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

\(O(n)\) Creates a Queue with capacity \(2n + 1\), where the internal front/back position is initialzed at \(n\).

Since: 1.2.4.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

Element access

Peek

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

\(O(1)\) Peeks the last element in the queue.

Since: 1.2.3.0

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

\(O(1)\) Peeks the first element in the queue.

Since: 1.2.3.0

Push

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

op

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

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

Since: 1.2.3.0

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

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

Since: 1.2.3.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

Readwritemodify

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

\(O(1)\) Returns the \(k\)-th value from the first element.

Since: 1.2.3.0

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

\(O(1)\) Returns the \(k\)-th value from the last element.

Since: 1.2.3.0

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

\(O(1)\) Returns the \(k\)-th value from the first element.

Since: 1.2.3.0

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

\(O(1)\) Returns the \(k\)-th value from the last element.

Since: 1.2.3.0

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

\(O(1)\) Writes to the \(k\)-th value from the first element.

Since: 1.2.3.0

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

\(O(1)\) Writes to the \(k\)-th value from the last element.

Since: 1.2.3.0

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

\(O(1)\) Given user function \(f\), modifies the \(k\)-th value from the first element with it.

Since: 1.2.3.0

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

\(O(1)\) Given user function \(f\), modifies the \(k\)-th value from the first element with it.

Since: 1.2.3.0

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

\(O(1)\) Given user function \(f\), modifies the \(k\)-th value from the last element with it.

Since: 1.2.3.0

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

\(O(1)\) Given user function \(f\), modifies the \(k\)-th value from the last element with it.

Since: 1.2.3.0

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