Safe Haskell | Safe-Inferred |
---|---|
Language | GHC2021 |
AtCoder.Internal.Queue
Description
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]
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
- 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
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
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