Processing math: 100%
ac-library-hs-1.2.3.0: Data structures and algorithms
Safe HaskellSafe-Inferred
LanguageGHC2021

AtCoder.Internal.Queue

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.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

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

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, returns the k-th value from the first element.

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, returns the k-th value from the first element.

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, returns the k-th value from the last element.

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, returns the k-th value from the last element.

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