fennec/include/fennec/containers/map.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/map.h
/// \brief A header containing the definition for a mapping of keys to values
///
///
/// \details
/// \author Medusa Slockbower
///
/// \copyright Copyright © 2025 - 2026 Medusa Slockbower ([GPLv3](https://www.gnu.org/licenses/gpl-3.0.en.html))
///
///

#ifndef FENNEC_CONTAINERS_MAP_H
#define FENNEC_CONTAINERS_MAP_H

#include <fennec/containers/pair.h>
#include <fennec/containers/set.h>

namespace fennec
{

/* Ramblings
 *
 * Definitions:
 * user = Programmer using this data structure
 *
 * The STL maps are very contrived. Some of its functionality encourages younger programmers to use
 * the exception model. Ideally, I would like this structure to never throw an error with typical use.
 *
 * The array access operator is, in my opinion, poorly implemented. I do not think that this operator should handle
 * insertions and should handle access only. This is the only data structure in STL that has this behavior, no other
 * data structure modifies contents by inherently calling operator[].
 *
 * Currently, I am considering implementing this as the following:
 * Access will be handled only via operator[]. Return value will be a pointer which forces user validation.
 * Insertions will be handled only via an insert/emplace function.
 * Deletions will be handled only via an erase function.
*/

///
/// \brief Data Structure defining a mapping of \f$key\f$ \f$KeyT\f$ to \f$value\f$ \f$ValueT\f$
/// \details
/// | Property    | Value      |
/// |:-----------:|:----------:|
/// | stable      |     ⛔     |
/// | dynamic     |     ✅     |
/// | homogeneous |     ✅     |
/// | distinct    |     ✅     |
/// | ordered     |     ⛔     |
/// | space       | \f$O(N)\f$ |
/// | linear      |     ⛔     |
/// | access      | \f$O(1)\f$ |
/// | find        | \f$O(1)\f$ |
/// | insertion   | \f$O(1)\f$ |
/// | deletion    | \f$O(1)\f$ |
/// | space       | \f$O(N)\f$ |
///
/// \note These runtimes are amortized, in theory the worst case is \f$O(N)\f$, but that is highly improbable.
///
/// \tparam KeyT The Key Type
/// \tparam ValueT The Value Type
/// \tparam Hash The Hash to Use
/// \tparam Alloc The Allocator to Use
template<typename KeyT, typename ValueT, typename Hash = hash<KeyT>, typename Alloc = allocator<pair<KeyT, ValueT>>>
struct map {

// Definitions =========================================================================================================
public:

	/// \name Definitions
	/// @{

	struct key_hash;                                                           //!< Hash for node keys
	struct key_equals;                                                         //!< Comparison for node keys
	using key_t = KeyT;                                                        //!< The key type
	using value_t = ValueT;                                                    //!< The value type
	using elem_t = pair<KeyT, ValueT>;                                         //!< then node type
	using alloc_t = typename allocator_traits<Alloc>::template rebind<elem_t>; //!< Rebinds the allocator type to nodes
	using hash_t = Hash;                                                       //!< The hash type
	using set_t = set<elem_t, key_hash, key_equals, alloc_t>;                  //!< The underlying set
	using iterator = set_t::iterator;                                          //!< Iterator type

	///
	/// \brief key hash helper
	struct key_hash : hash_t {
		///
		/// \brief C++ 11 Hash Specification \f$operator()\f$
		/// \param p the pair to hash
		/// \returns the hash of the key
		constexpr size_t operator()(const elem_t& p) const {
			return hash_t::operator()(p.first);
		}
	};

	///
	/// \brief key comparison helper
	struct key_equals : equality<KeyT> {
		///
		/// \brief C++ 11 Compare Specification \f$operator()\f$
		/// \param a the first pair
		/// \param b the second pair
		/// \returns \f$true\f$ if the keys are equal, \f$false\f$ otherwise
		constexpr bool operator()(const elem_t& a, const elem_t& b) const {
			return equality<KeyT>::operator()(a.first, b.first);
		}
	};

	/// @}


// Constructors & Destructor ===========================================================================================
public:

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

	///
	/// \brief Default Constructor, initializes empty map
	constexpr map() = default;

	///
	/// \brief Destructor, Destructs all elements and releases the allocation
	constexpr ~map() = default;

	/// @}


// Properties ==========================================================================================================
public:

	/// \name Properties
	/// @{

	///
	/// \returns The size of the set
	constexpr size_t size() const {
		return _set.size();
	}

	///
	/// \returns \f$true\f$ when there are no elements in the set, \f$false\f$ otherwise
	constexpr size_t is_empty() const {
		return _set.size();
	}

	///
	/// \returns The capacity of the underlying allocation
	constexpr size_t capacity() const {
		return _set.capacity();
	}

	/// @}


// Access ==============================================================================================================
public:

	/// \name Access
	/// @{

	///
	/// \brief Key Access Operator
	/// \param key Key value to access
	/// \returns A pointer to the value associated with \f$key\f$, \f$nullptr\f$ if \f$key\f$ is not present.
	///
	/// \par Complexity
	/// \f$O(1)\f$
	///
	constexpr value_t* operator[](const KeyT& key) {
		auto it = _set.at(this->_find(key));
		return it ? &it->second : nullptr;
	}

	///
	/// \brief Key Const Access Operator
	/// \param key Key value to access
	/// \returns A const-qualified pointer to the value associated with \f$key\f$, \f$nullptr\f$ if \f$key\f$ is not present.
	///
	/// \par Complexity
	/// \f$O(1)\f$
	///
	constexpr const value_t* operator[](const KeyT& key) const {
		auto it = _set.at(this->_find(key));
		return it ? &it->second : nullptr;
	}

	///
	/// \brief Argument Key Access Operator
	/// \tparam ArgsT Argument Types
	/// \param args Arguments to construct the key with
	/// \returns A pointer to the value associated with \f$key\f$, \f$nullptr\f$ if \f$key\f$ is not present.
	///
	/// \par Complexity
	/// \f$O(1)\f$
	///
	template<typename...ArgsT>
	constexpr value_t* operator[](ArgsT&&...args) {
		auto it = _set.at(this->_find(fennec::forward<ArgsT>(args)...));
		return it ? &it->second : nullptr;
	}

	///
	/// \brief Argument Key Const Access Operator
	/// \tparam ArgsT Argument Type
	/// \param args Argument to construct the key with
	/// \returns A const-qualified pointer to the value associated with \f$key\f$, \f$nullptr\f$ if \f$key\f$ is not present.
	///
	/// \par Complexity
	/// \f$O(1)\f$
	///
	template<typename...ArgsT>
	constexpr const value_t* operator[](ArgsT&&...args) const {
		auto it = _set.at(this->_find(fennec::forward<ArgsT>(args)...));
		return it ? &it->second : nullptr;
	}

	/// @}


// Modifiers ===========================================================================================================
public:

	/// \name Modifiers
	/// @{

	///
	/// \brief Key-Value Insertion
	/// \param pair a pair containing the key and its value
	///
	/// \par Complexity
	/// \f$O(1)\f$
	///
	constexpr void insert(elem_t&& pair) {
		this->_insert(fennec::forward<elem_t>(pair));
	}

	///
	/// \brief Key-Value Insertion
	/// \param key key to insert
	/// \param args Arguments for constructing the key-value pair
	///
	/// \par Complexity
	/// \f$O(1)\f$
	///
	template<typename...ArgsT>
	constexpr void emplace(const KeyT& key, ArgsT&&...args) {
		this->_insert(key, fennec::forward<ArgsT>(args)...);
	}

	///
	/// \brief Key-Value Insertion
	/// \param args Arguments for constructing the key-value pair
	///
	/// \par Complexity
	/// \f$O(1)\f$
	///
	template<typename...ArgsT>
	constexpr void emplace(ArgsT&&...args) {
		this->_insert(fennec::forward<ArgsT>(args)...);
	}

	///
	/// \brief Erase a key
	/// \param key key to erase
	///
	/// \par Complexity
	/// \f$O(1)\f$
	///
	constexpr void erase(KeyT&& key) {
		_set.erase(this->_find(fennec::forward<KeyT>(key)));
	}

	///
	/// \brief Erase a key
	/// \param key key to erase
	///
	/// \par Complexity
	/// \f$O(1)\f$
	///
	constexpr void erase(const KeyT& key) {
		_set.erase(this->_find(key));
	}

	///
	/// \brief Argument Erase
	/// \tparam ArgsT Argument Types
	/// \param args Arguments to construct a key to erase
	///
	/// \par Complexity
	/// \f$O(1)\f$
	///
	template<typename...ArgsT>
	constexpr void erase(ArgsT&&...args) {
		_set.erase(this->_find(fennec::forward<ArgsT>(args)...));
	}

	///
	/// \brief Clears the map destructing all elements
	///
	/// \par Complexity
	/// \f$O(1)\f$
	///
	void clear() {
		_set.clear();
	}

	/// @}


// Iteration ===========================================================================================================
public:

	/// \name Iteration
	/// @{

	///
	/// \brief C++ Iterator Specification \f$begin()\f$
	/// \returns an iterator at the start of the map
	///
	/// \par Complexity
	/// \f$O(1)\f$
	///
	constexpr iterator begin() {
		return _set.begin();
	}


	///
	/// \brief C++ Iterator Specification \f$end()\f$
	/// \returns an iterator at the end of the map
	///
	/// \par Complexity
	/// \f$O(1)\f$
	///
	constexpr iterator end() {
		return _set.end();
	}

	/// @}


// Private Member Variables ============================================================================================
private:
	 set_t _set;


// Private Helpers =====================================================================================================
private:
	template<typename...ArgsT>
	set_t::iterator _find(ArgsT&&...args) const {
		union U { // Hacky way of avoiding constructing the value, TODO: Check for warnings on other compilers
			pair<KeyT, char[sizeof(ValueT)]> root;
			pair<KeyT, ValueT> val;

			~U() {
				fennec::destruct(&root);
			}
		} trick = {
			.root = { KeyT(fennec::forward<ArgsT>(args)...), 0 }
		};
		return _set.find(trick.val);
	}

	template<typename...ArgsT>
	constexpr void _insert(ArgsT&&...args) {
		elem_t elem(fennec::forward<ArgsT>(args)...);
		auto it = this->_find(elem.first);
		if (it != _set.end()) {
			_set.at(it)->second = fennec::move(elem.second);
		} else {
			_set.insert(fennec::move(elem));
		}
	}
};

}

#endif // FENNEC_CONTAINERS_MAP_H