fennec/include/fennec/containers/deque.h

// =====================================================================================================================
//  fennec, a free and open source game engine
//  Copyright © 2025 - 2026  Medusa Slockbower
//
//  This program is free software: you can redistribute it and/or modify
//  it under the terms of the GNU General Public License as published by
//  the Free Software Foundation, either version 3 of the License, or
//  (at your option) any later version.
//
//  This program is distributed in the hope that it will be useful,
//  but WITHOUT ANY WARRANTY; without even the implied warranty of
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//  GNU General Public License for more details.
//
//  You should have received a copy of the GNU General Public License
//  along with this program.  If not, see <https://www.gnu.org/licenses/>.
// =====================================================================================================================

///
/// \file fennec/containers/deque.h
/// \brief A header containing the definition for a double-ended queue
///
///
/// \details
/// \author Medusa Slockbower
///
/// \copyright Copyright © 2025 - 2026 Medusa Slockbower ([GPLv3](https://www.gnu.org/licenses/gpl-3.0.en.html))
///
///

#ifndef FENNEC_CONTAINERS_DEQUE_H
#define FENNEC_CONTAINERS_DEQUE_H

#include <fennec/memory/allocator.h>

// TODO: Document

namespace fennec
{

///
///
/// \brief Data structure defining a double-ended queue.
///
/// \details
/// This behaves the similar to fennec::list, however it does not allow arbitrary access, insertion, or deletion.
/// It is one of the few data structures in this library that is stable, i.e. pointers to elements do not change.
///
/// | Property    | Value      |
/// |:-----------:|:----------:|
/// | stable      |     ✅     |
/// | dynamic     |     ✅     |
/// | homogeneous |     ✅     |
/// | distinct    |     ⛔     |
/// | ordered     |     ⛔     |
/// | space       | \f$O(N)\f$ |
/// | linear      |     ⛔     |
/// | access      | \f$O(1)\f$ |
/// | find        | \f$O(N)\f$ |
/// | insertion   | \f$O(1)\f$ |
/// | deletion    | \f$O(1)\f$ |
/// | space       | \f$O(N)\f$ |
///
/// \tparam TypeT value type
template<typename TypeT, typename AllocT = allocator<TypeT>>
struct deque {

// Definitions =========================================================================================================
private:
	struct node;

public:

	/// \name Definitions
	/// @{

	using value_t = TypeT; //!< Alias for the value type
	using alloc_t = allocator_traits<AllocT>::template rebind<node>; //!< The underlying allocator type
	using elem_t  = node*;                                           //!< The underlying element type

	/// @}


	class iterator;


// Constructors ========================================================================================================

	/// \name Constructors & Destructor
	/// @{

	///
	/// \brief Default Constructor, initializes an empty deque
	///
	/// \par Complexity
	/// \f$O(1)\f$
	///
	deque()
		: _alloc()
		, _first(nullptr)
		, _last(nullptr)
		, _size(0) {
	}

	///
	/// \brief Alloc Constructor, initializes an empty deque with the specified allocator
	/// \param alloc the allocator to copy
	///
	/// \par Complexity
	/// \f$O(1)\f$
	///
	deque(const alloc_t& alloc)
		: _alloc(alloc)
		, _first(nullptr)
		, _last(nullptr)
		, _size(0) {
	}

	///
	/// \brief Copy Constructor
	/// \param deque the deque to copy
	///
	/// \par Complexity
	/// \f$O(N)\f$
	///
	deque(const deque& deque)
		: _alloc(deque._alloc)
		, _first(nullptr)
		, _last(nullptr)
		, _size(0) {
		const elem_t node = deque._first;
		while (node) {
			this->push_back(node->value);
			node = node->next;
		}
	}

	///
	/// \brief Deque Move Constructor
	/// \param deque the deque to move
	///
	/// \par Complexity
	/// \f$O(1)\f$
	///
	deque(deque&& deque) noexcept
		: _alloc(deque._alloc)
		, _first(deque._first)
		, _last(deque._last)
		, _size(deque._size) {
		deque._first = nullptr;
		deque._last  = nullptr;
	}

	///
	/// \brief Destructor, calls deque::clear
	///
	/// \par Complexity
	/// \f$O(N)\f$
	///
	~deque() {
		clear();
	}

	/// @}

// Properties ==========================================================================================================

	/// \name Properties
	/// @{

	///
	/// \returns \f$true\f$ when the deque is empty, \f$false\f$ otherwise
	///
	/// \par Complexity
	/// \f$O(1)\f$
	///
	constexpr bool is_empty() const {
		return _size == 0;
	}

	///
	/// \returns the number of elements in the deque
	///
	/// \par Complexity
	/// \f$O(1)\f$
	///
	constexpr size_t size() const {
		return _size;
	}

	/// @}


// Access ==============================================================================================================

	/// \name Access
	/// @{

	///
	/// \returns a reference to the first element in the deque
	///
	/// \par Complexity
	/// \f$O(1)\f$
	///
	value_t& front() {
		assert(not is_empty(), "Attempted to access an empty deque.");
		return _first->value;
	}

	///
	/// \returns a const-qualified reference to the first element in the deque
	///
	/// \par Complexity
	/// \f$O(1)\f$
	///
	const value_t& front() const {
		assert(not is_empty(), "Attempted to access an empty deque.");
		return _first->value;
	}

	///
	/// \returns a reference to the last element in the deque
	///
	/// \par Complexity
	/// \f$O(1)\f$
	///
	value_t& back() {
		assert(not is_empty(), "Attempted to access an empty deque.");
		return _last->value;
	}

	///
	/// \returns a const-qualified reference to the last element in the deque
	///
	/// \par Complexity
	/// \f$O(1)\f$
	///
	const value_t& back() const {
		assert(not is_empty(), "Attempted to access an empty deque.");
		return _last->value;
	}

	/// @}


// Modifiers ===========================================================================================================

	/// \name Modifiers
	/// @{

	///
	/// \brief Push Front Move, moves a value to the front of the deque
	/// \param elem the value to move
	///
	/// \par Complexity
	/// \f$O(1)\f$
	///
	void push_front(value_t&& elem) {
		this->_push_front(elem);
	}

	///
	/// \brief Push Front Copy, copies a value to the front of the deque
	/// \param elem the value to copy
	///
	/// \par Complexity
	/// \f$O(1)\f$
	///
	void push_front(const value_t& elem) {
		this->_push_front(elem);
	}

	///
	/// \brief Emplace Front, constructs a new value at the front of the deque
	/// \tparam ArgsT Argument types
	/// \param args Arguments used to construct the value
	///
	/// \par Complexity
	/// \f$O(1)\f$
	///
	template<typename...ArgsT>
	void emplace_front(ArgsT&&...args) {
		this->_push_front(fennec::forward<ArgsT>(args)...);
	}


	///
	/// \brief Push Back Move, moves a value to the back of the deque
	/// \param elem the value to move
	///
	/// \par Complexity
	/// \f$O(1)\f$
	///
	void push_back(value_t&& elem) {
		this->_push_back(elem);
	}

	///
	/// \brief Push Back Copy, copies a value to the back of the deque
	/// \param elem the value to copy
	///
	/// \par Complexity
	/// \f$O(1)\f$
	///
	void push_back(const value_t& elem) {
		this->_push_back(elem);
	}

	///
	/// \brief Emplace Back, constructs a new value at the back of the deque
	/// \tparam ArgsT Argument types
	/// \param args Arguments used to construct the value
	///
	/// \par Complexity
	/// \f$O(1)\f$
	///
	template<typename...ArgsT>
	void emplace_back(ArgsT&&...args) {
		this->_push_back(fennec::forward<ArgsT>(args)...);
	}

	///
	/// \brief Clears the contents of the deque
	///
	/// \par Complexity
	/// \f$O(N)\f$
	///
	void clear() {
		elem_t it = _first;
		while (it) {
			elem_t next = it->next;
			fennec::destruct(it);
			_alloc.deallocate(it);
			it = next;
		}
		_first = nullptr;
		_last  = nullptr;
		_size  = 0;
	}

	///
	/// \brief Erase the First Element
	///
	/// \par Complexity
	/// \f$O(1)\f$
	///
	void pop_front() {
		if (_first == nullptr) {
			return;
		}
		elem_t next = _first->next;
		fennec::destruct(_first);
		_alloc.deallocate(_first);
		_first = next;
		_last = next ? _last : nullptr;
		--_size;
	}

	///
	/// \brief Erase the Last Element
	///
	/// \par Complexity
	/// \f$O(1)\f$
	///
	void pop_back() {
		if (_last == nullptr) {
			return;
		}
		elem_t prev = _last->prev;
		fennec::destruct(_last);
		_alloc.deallocate(_last);
		_last = prev;
		_first = prev ? _first : nullptr;
		--_size;
	}

	/// @}


// Iteration ===========================================================================================================

	/*
	 * TODO: Decide whether you should be able to iterate over a deque
	 */


// Private Member Variables ============================================================================================
private:
	alloc_t _alloc;
	node   *_first, *_last;
	size_t  _size;


// Private Helpers =====================================================================================================
private:
	template<typename...ArgsT>
	void _push_front(ArgsT&&...args) {
		elem_t next = _first;
		_first = _alloc.allocate(1);
		fennec::construct(_first, nullptr, next, fennec::forward<ArgsT>(args)...);
		if (next) {
			next->prev = _first;
		} else {
			_last = _first;
		}
		++_size;
	}

	template<typename...ArgsT>
	void _push_back(ArgsT&&...args) {
		elem_t prev = _last;
		_last = _alloc.allocate(1);
		fennec::construct(_last, prev, nullptr, fennec::forward<ArgsT>(args)...);
		if (prev) {
			prev->next = _last;
		} else {
			_first = _last;
		}
		++_size;
	}


// Private Definitions =================================================================================================
private:
	struct node {
		value_t value;
		node *prev, *next;

		template<typename...ArgsT>
		node(node* prev, node* next, ArgsT&&...args)
			: value(fennec::forward<ArgsT>(args)...)
			, prev(prev), next(next) {
		}

		~node() = default;
	};
};


}

#endif // FENNEC_CONTAINERS_DEQUE_H