Circular Array Queue

template<typename Elem>
class CircArrayQueue : public dsa::IQueue<Elem, CircArrayQueue>

Circular array queue.

An unbounded, generic queue type that implements the Queue ADT dsa::IQueue using a circular array along with a dynamic resizing scheme. This class template statically inherits the Queue ADT template class using the Curiously Recurring Template Pattern (CRTP).

Note

The queue elements have value semantics.

Template Parameters:

Elem – The queue element type.

Public Functions

CircArrayQueue(std::size_t init_cap = 4096)

Creates an empty queue.

Note

Memory will be allocated according to init_cap and the element type Elem.

Parameters:

init_cap – The initially anticipated maximum number of elements to be stored in the queue.

CircArrayQueue(CircArrayQueue const&)

Copy-constructs a new queue from an existing queue.

CircArrayQueue(CircArrayQueue&&) noexcept

Move-constructs a new queue from an existing queue.

CircArrayQueue &operator=(CircArrayQueue const&)

Copy-assigns an existing queue to this queue.

CircArrayQueue &operator=(CircArrayQueue&&) noexcept

Move-assigns an existing queue to this queue.

std::size_t capacity() const noexcept

Maximum number of elements this queue can store without allocating additional memory.

Returns:

The maximum number.

Private Functions

std::size_t size_() const noexcept

Number of elements in the queue.

bool empty_() const noexcept

Determines if this queue has no elements.

void iter_(std::function<void(Elem const&)> action) const

Iterates over all elements of this queue from the front.

The given operation will be performed on each element iterated.

Parameters:

action – The operation to be performed on each element.

Elem &front_()

Accesses the element at the front of this queue.

Throws:

dsa::EmptyQueueError – if the queue is empty.

Returns:

The front element.

Elem const &front_() const

Accesses (read-only) the element at the front of this queue.

Throws:

dsa::EmptyQueueError – if the queue is empty.

Returns:

The front element (immutable).

void enqueue_(Elem const &elem)

Adds an element to the end of this queue.

A deep copy of the element will be copy-constructed and then put into the queue.

Note

Additional memory will be allocated prior to this operation if the number of elements of this queue exceeds the current capacity.

Parameters:

elem – The element to be added.

Throws:

std::bad_alloc – or any exception thrown by the constuctor of type Elem.

void enqueue_(Elem &&elem)

Adds an element to the end of this queue.

The element will be put into the queue using move semantics.

Note

Additional memory will be allocated prior to this operation if the number of elements of this queue exceeds the current capacity.

Parameters:

elem – The element to be added.

Throws:

std::bad_alloc – or any exception thrown by the constuctor of type Elem.

void dequeue_()

Removes the element at end of this queue.

Note

Removing an element will trigger memory deallocation (and re-allocation of half the size) only when the number of elements in this queue is a quarter of the current capacity.

Throws:

dsa::EmptyQueueError – if this queue is empty.

template<typename ...Args>
void emplace_(Args&&... args)

Creates a new element in-place after the last element of this queue.

The new element is constructed in-place using all of the arguments passed to this member function.

Note

Additional memory will be allocated prior to this operation if the number of elements of this queue exceeds the current capacity.

Template Parameters:

Args – Types of the arguments to be passed to the constructor of the element type Elem.

Parameters:

args – Variable number of arguments to be passed to the constructor of the element type Elem.

Throws:

std::bad_alloc – or any exception thrown by the constuctor of type Elem.