DoubleEndedQueue

Git Source

A sequence of items with the ability to efficiently push and pop items (i.e. insert and remove) on both ends of the sequence (called front and back).

Storage use is optimized, and all operations are O(1) constant time. The struct is called Deque and holds PendingAction's. This data structure can only be used in storage, and not in memory.

Functions

pushBack

Inserts an item at the end of the queue. Reverts with QueueFull if the queue is full.

function pushBack(Deque storage deque, Types.PendingAction memory value) external returns (uint128 backIndex_);

Parameters

Name	Type	Description
`deque`	`Deque`	The queue.
`value`	`Types.PendingAction`	The item to insert.

Returns

Name	Type	Description
`backIndex_`	`uint128`	The raw index of the inserted item.

popBack

Removes the item at the end of the queue and returns it. Reverts with QueueEmpty if the queue is empty.

function popBack(Deque storage deque) public returns (Types.PendingAction memory value_);

Parameters

Name	Type	Description
`deque`	`Deque`	The queue.

Returns

Name	Type	Description
`value_`	`Types.PendingAction`	The removed item.

pushFront

Inserts an item at the beginning of the queue. Reverts with QueueFull if the queue is full.

function pushFront(Deque storage deque, Types.PendingAction memory value) external returns (uint128 frontIndex_);

Parameters

Name	Type	Description
`deque`	`Deque`	The queue.
`value`	`Types.PendingAction`	The item to insert.

Returns

Name	Type	Description
`frontIndex_`	`uint128`	The raw index of the inserted item.

popFront

Removes the item at the beginning of the queue and returns it. Reverts with QueueEmpty if the queue is empty.

function popFront(Deque storage deque) public returns (Types.PendingAction memory value_);

Parameters

Name	Type	Description
`deque`	`Deque`	The queue.

Returns

Name	Type	Description
`value_`	`Types.PendingAction`	The removed item.

front

Returns the item at the beginning of the queue. Reverts with QueueEmpty if the queue is empty.

function front(Deque storage deque) external view returns (Types.PendingAction memory value_, uint128 rawIndex_);

Parameters

Name	Type	Description
`deque`	`Deque`	The queue.

Returns

Name	Type	Description
`value_`	`Types.PendingAction`	The item at the front of the queue.
`rawIndex_`	`uint128`	The raw index of the returned item.

back

Returns the item at the end of the queue. Reverts with QueueEmpty if the queue is empty.

function back(Deque storage deque) external view returns (Types.PendingAction memory value_, uint128 rawIndex_);

Parameters

Name	Type	Description
`deque`	`Deque`	The queue.

Returns

Name	Type	Description
`value_`	`Types.PendingAction`	The item at the back of the queue.
`rawIndex_`	`uint128`	The raw index of the returned item.

at

Returns the item at a position in the queue given by index, with the first item at 0 and the last item at length(deque) - 1. Reverts with QueueOutOfBounds if the index is out of bounds.

function at(Deque storage deque, uint256 index)
    external
    view
    returns (Types.PendingAction memory value_, uint128 rawIndex_);

Parameters

Name	Type	Description
`deque`	`Deque`	The queue.
`index`	`uint256`	The index of the item to return.

Returns

Name	Type	Description
`value_`	`Types.PendingAction`	The item at the given index.
`rawIndex_`	`uint128`	The raw index of the item.

atRaw

Returns the item at a position in the queue given by rawIndex, indexing into the underlying storage array directly. Reverts with QueueOutOfBounds if the index is out of bounds.

function atRaw(Deque storage deque, uint128 rawIndex) external view returns (Types.PendingAction memory value_);

Parameters

Name	Type	Description
`deque`	`Deque`	The queue.
`rawIndex`	`uint128`	The index of the item to return.

Returns

Name	Type	Description
`value_`	`Types.PendingAction`	The item at the given index.

Deletes the item at a position in the queue given by rawIndex, indexing into the underlying storage array directly. If clearing the front or back item, then the bounds are updated. Otherwise, the values are simply set to zero and the queue's begin and end indices are not updated.

function clearAt(Deque storage deque, uint128 rawIndex) external;

Parameters

Name	Type	Description
`deque`	`Deque`	The queue.
`rawIndex`	`uint128`	The index of the item to delete.

isValid

Checks if the raw index is valid (in bounds).

function isValid(Deque storage deque, uint128 rawIndex) public view returns (bool valid_);

Parameters

Name	Type	Description
`deque`	`Deque`	The queue.
`rawIndex`	`uint128`	The raw index to check.

Returns

Name	Type	Description
`valid_`	`bool`	Whether the raw index is valid.

length

Returns the number of items in the queue.

function length(Deque storage deque) public view returns (uint256 length_);

Parameters

Name	Type	Description
`deque`	`Deque`	The queue.

Returns

Name	Type	Description
`length_`	`uint256`	The number of items in the queue.

empty

Returns true if the queue is empty.

function empty(Deque storage deque) internal view returns (bool empty_);

Parameters

Name	Type	Description
`deque`	`Deque`	The queue.

Returns

Name	Type	Description
`empty_`	`bool`	True if the queue is empty.

Errors

QueueEmpty

An operation (e.g. front) couldn't be completed due to the queue being empty.

error QueueEmpty();

QueueFull

A push operation couldn't be completed due to the queue being full.

error QueueFull();

QueueOutOfBounds

An operation (e.g. atRaw) couldn't be completed due to an index being out of bounds.

error QueueOutOfBounds();

Structs

Deque

Indices are 128 bits so begin and end are packed in a single storage slot for efficient access. Struct members have an underscore prefix indicating that they are "private" and should not be read or written to directly. Use the functions provided below instead. Modifying the struct manually may violate assumptions and lead to unexpected behavior. The first item is at data[begin] and the last item is at data[end - 1]. This range can wrap around.

struct Deque {
    uint128 _begin;
    uint128 _end;
    mapping(uint128 index => Types.PendingAction) _data;
}

Properties

Name	Type	Description
`_begin`	`uint128`	The index of the first item in the queue.
`_end`	`uint128`	The index of the item after the last item in the queue.
`_data`	`mapping(uint128 index => Types.PendingAction)`	The items in the queue.