FlatMap.hpp

Go to the documentation of this file.

//
//  CeresEngine - A game development framework
//
//  Created by Rogiel Sulzbach.
//  Copyright (c) 2018-2022 Rogiel Sulzbach. All rights reserved.
//
#pragma once
 
#include "Pair.hpp"
#include "SmallVector.hpp"
#include "StaticVector.hpp"
#include "Vector.hpp"
 
#include "CeresEngine/DataTypes.hpp"
 
#include <algorithm>
#include <cstring>
#include <stdexcept>
#include <type_traits>
#include <vector>
 
namespace CeresEngine {
 
    template<typename Key, typename T, typename Compare = std::less<>, typename Container = Vector<Pair<Key, T>>> class FlatMap {
    public:
        using key_type = Key;
        using mapped_type = T;
        using value_type = std::pair<Key, T>;
        using container_type = Container;
        using key_compare = Compare;
        using reference = value_type&;
        using const_reference = const value_type&;
        using allocator_type = typename container_type::allocator_type;
        using pointer = typename std::allocator_traits<allocator_type>::pointer;
        using const_pointer = typename std::allocator_traits<allocator_type>::pointer;
        using iterator = typename container_type::iterator;
        using const_iterator = typename container_type::const_iterator;
        using reverse_iterator = typename container_type::reverse_iterator;
        using const_reverse_iterator = typename container_type::const_reverse_iterator;
        using difference_type = typename container_type::difference_type;
        using size_type = typename container_type::size_type;
 
        FlatMap() {}
 
        explicit FlatMap(const key_compare& comp, const allocator_type& alloc = allocator_type()) : m_cmp(comp), m_container(alloc) {}
 
        FlatMap(const FlatMap& x) = default;
        FlatMap(FlatMap&& x) = default;
 
        FlatMap& operator=(const FlatMap& x) {
            m_cmp = x.m_cmp;
            m_container = x.m_container;
            return *this;
        }
        FlatMap& operator=(FlatMap&& x) {
            m_cmp = std::move(x.m_cmp);
            m_container = std::move(x.m_container);
            return *this;
        }
 
        iterator begin() noexcept { return m_container.begin(); }
        [[nodiscard]] const_iterator begin() const noexcept { return m_container.begin(); }
        iterator end() noexcept { return m_container.end(); }
        [[nodiscard]] const_iterator end() const noexcept { return m_container.end(); }
        reverse_iterator rbegin() noexcept { return m_container.rbegin(); }
        [[nodiscard]] const_reverse_iterator rbegin() const noexcept { return m_container.rbegin(); }
        reverse_iterator rend() noexcept { return m_container.rend(); }
        [[nodiscard]] const_reverse_iterator rend() const noexcept { return m_container.rend(); }
        [[nodiscard]] const_iterator cbegin() const noexcept { return m_container.cbegin(); }
        [[nodiscard]] const_iterator cend() const noexcept { return m_container.cend(); }
 
        [[nodiscard]] bool empty() const noexcept { return m_container.empty(); }
        [[nodiscard]] size_type size() const noexcept { return m_container.size(); }
        [[nodiscard]] size_type max_size() const noexcept { return m_container.max_size(); }
 
        void reserve(size_type count) { return m_container.reserve(count); }
        [[nodiscard]] size_type capacity() const noexcept { return m_container.capacity(); }
 
        void clear() noexcept { m_container.clear(); }
 
        template<typename K = key_type> iterator lower_bound(const K& k) { return std::lower_bound(m_container.begin(), m_container.end(), k, m_cmp); }
 
        template<typename K = key_type> [[nodiscard]] const_iterator lower_bound(const K& k) const { return std::lower_bound(m_container.begin(), m_container.end(), k, m_cmp); }
 
        template<typename K = key_type> iterator find(const K& k) {
            auto i = lower_bound(k);
            if(i != end() && !m_cmp(k, *i)) {
                return i;
            }
 
            return end();
        }
 
        template<typename K = key_type> [[nodiscard]] const_iterator find(const K& k) const {
            auto i = lower_bound(k);
            if(i != end() && !m_cmp(k, *i)) {
                return i;
            }
 
            return end();
        }
 
        template<typename K = key_type> [[nodiscard]] size_t count(const K& k) const { return find(k) == end() ? 0 : 1; }
 
        template<typename P> std::pair<iterator, bool> insert(P&& val) {
            auto i = lower_bound(val.first);
            if(i != end() && !m_cmp(val.first, *i)) {
                return {i, false};
            }
 
            return {m_container.emplace(i, std::forward<P>(val)), true};
        }
 
        std::pair<iterator, bool> insert(const value_type& val) {
            auto i = lower_bound(val.first);
            if(i != end() && !m_cmp(val.first, *i)) {
                return {i, false};
            }
 
            return {m_container.emplace(i, val), true};
        }
 
        template<typename... Args> std::pair<iterator, bool> emplace(Args&&... args) {
            value_type val(std::forward<Args>(args)...);
            return insert(std::move(val));
        }
 
        iterator erase(iterator pos) { return m_container.erase(pos); }
        iterator erase(const_iterator pos) { return m_container.erase(pos); }
 
        template<typename K = key_type> size_type erase(const K& k) {
            auto i = find(k);
            if(i == end()) {
                return 0;
            }
 
            erase(i);
            return 1;
        }
 
        template<typename K = key_type> mapped_type& operator[](const K& k) {
            auto i = lower_bound(k);
            if(i != end() && !m_cmp(k, *i)) {
                return i->second;
            }
 
            i = m_container.emplace(i, k, mapped_type());
            return i->second;
        }
 
        template<typename K = key_type> mapped_type& operator[](K&& k) {
            auto i = lower_bound(k);
            if(i != end() && !m_cmp(k, *i)) {
                return i->second;
            }
 
            i = m_container.emplace(i, std::forward<K>(k), mapped_type());
            return i->second;
        }
 
        template<typename K = key_type> mapped_type& at(const K& k) {
            auto i = lower_bound(k);
            if(i == end() || m_cmp(*i, k)) {
                throw std::out_of_range("FlatMap out of range");
            }
 
            return i->second;
        }
 
        template<typename K = key_type> [[nodiscard]] const mapped_type& at(const K& k) const {
            auto i = lower_bound(k);
            if(i == end() || m_cmp(*i, k)) {
                throw std::out_of_range("FlatMap out of range");
            }
 
            return i->second;
        }
 
        void swap(FlatMap& x) {
            std::swap(m_cmp, x.m_cmp);
            m_container.swap(x.m_container);
        }
 
        [[nodiscard]] const container_type& container() const noexcept { return m_container; }
 
        // DANGER! If you're not careful with this function, you may irreversably break the map
        container_type& modify_container() noexcept { return m_container; }
 
    private:
        struct pair_compare {
            pair_compare() = default;
            pair_compare(const key_compare& kc) : kcmp(kc) {}
 
            template<typename K = key_type> bool operator()(const value_type& a, const K& b) const { return kcmp(a.first, b); }
            template<typename K = key_type> bool operator()(const K& a, const value_type& b) const { return kcmp(a, b.first); }
 
            key_compare kcmp;
        };
        pair_compare m_cmp;
        container_type m_container;
    };
 
    template<typename Key, typename T, typename Compare, typename Container>
    bool operator==(const FlatMap<Key, T, Compare, Container>& a, const FlatMap<Key, T, Compare, Container>& b) {
        return a.container() == b.container();
    }
 
    template<typename Key, typename T, typename Compare, typename Container>
    bool operator!=(const FlatMap<Key, T, Compare, Container>& a, const FlatMap<Key, T, Compare, Container>& b) {
        return a.container() != b.container();
    }
 
    template<typename Key, typename T, size_t Capacity, typename Compare = std::less<>>
    using StaticFlatMap = FlatMap<Key, T, Compare, StaticVector<Pair<Key, T>, Capacity>>;
 
} // namespace CeresEngine