map.h

Go to the documentation of this file.

// =====================================================================================================================
//  fennec, a free and open source game engine
//  Copyright © 2025  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/>.
// =====================================================================================================================
 
 
#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.
*/
 
template<typename KeyT, typename ValueT, typename Hash = hash<KeyT>, typename Alloc = allocator<pair<KeyT, ValueT>>>
struct map {
 
// Definitions =========================================================================================================
public:
    struct key_hash; 
    struct key_equals; 
    using key_t = KeyT; 
    using value_t = ValueT; 
    using elem_t = pair<KeyT, ValueT>; 
    using alloc_t = typename allocator_traits<Alloc>::template rebind<elem_t>; 
    using hash_t = Hash; 
    using set_t = set<elem_t, key_hash, key_equals, alloc_t>; 
    using iterator = set_t::iterator; 
 
    // We only want to hash the key
    struct key_hash : hash_t {
        constexpr size_t operator()(const elem_t& p) const {
            return hash_t::operator()(p.first);
        }
    };
 
    // We only want to compare the keys
    struct key_equals : equality<KeyT> {
        constexpr bool operator()(const elem_t& a, const elem_t& b) const {
            return equality<KeyT>::operator()(a.first, b.first);
        }
    };
 
 
// Constructors & Destructor ===========================================================================================
 
 
    constexpr map() = default;
 
    constexpr ~map() = default;
 
 
 
// Properties ==========================================================================================================
 
 
    constexpr size_t size() const {
        return _set.size();
    }
 
    constexpr size_t empty() const {
        return _set.size();
    }
 
    constexpr size_t capacity() const {
        return _set.capacity();
    }
 
 
 
// Access ==============================================================================================================
 
 
    constexpr value_t* operator[](const KeyT& key) {
        auto it = _set.at(this->_find(key));
        return it ? &it->second : nullptr;
    }
 
    constexpr const value_t* operator[](const KeyT& key) const {
        auto it = _set.at(this->_find(key));
        return it ? &it->second : nullptr;
    }
 
    template<typename...ArgsT>
    constexpr value_t* operator[](ArgsT&&...args) {
        auto it = _set.at(this->_find(fennec::forward<ArgsT>(args)...));
        return it ? &it->second : nullptr;
    }
 
    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 ===========================================================================================================
 
 
    constexpr void insert(elem_t&& pair) {
        this->_insert(fennec::forward<elem_t>(pair));
    }
 
    template<typename...ArgsT>
    constexpr void emplace(const KeyT& key, ArgsT&&...args) {
        this->_insert(key, fennec::forward<ArgsT>(args)...);
    }
 
    template<typename...ArgsT>
    constexpr void emplace(ArgsT&&...args) {
        this->_insert(fennec::forward<ArgsT>(args)...);
    }
 
    constexpr void erase(KeyT&& key) {
        _set.erase(this->_find(fennec::forward<KeyT>(key)));
    }
 
    constexpr void erase(const KeyT& key) {
        _set.erase(this->_find(key));
    }
 
    template<typename...ArgsT>
    constexpr void erase(ArgsT&&...args) {
        _set.erase(this->_find(fennec::forward<ArgsT>(args)...));
    }
 
    void clear() {
        _set.clear();
    }
 
 
 
// Iteration ===========================================================================================================
 
 
    constexpr iterator begin() {
        return _set.begin();
    }
 
 
    constexpr iterator end() {
        return _set.end();
    }
 
 
 
private:
     set_t _set;
 
    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