IndexedMultimap.hpp

Go to the documentation of this file.

#pragma once
 
#include "Map.hpp"
#include "SmallFlatMap.hpp"
 
#include "CeresEngine/Foundation/Allocator.hpp"
#include "CeresEngine/Foundation/Iterator.hpp"
#include "CeresEngine/Foundation/Hash.hpp"
 
namespace CeresEngine {
 
    template<typename Key, typename Value, typename Container> class BasicIndexedMultimap : private Container {
        using super = Container;
 
    public:
        using key_type = typename super::key_type;
        using mapped_type = typename super::mapped_type;
        using value_type = typename super::value_type;
        using size_type = typename super::size_type;
        using difference_type = typename super::difference_type;
        using key_compare = typename super::key_compare;
        using allocator_type = typename super::allocator_type;
        using reference = typename super::reference;
        using const_reference = typename super::const_reference;
        using pointer = typename super::pointer;
        using const_pointer = typename super::const_pointer;
        using iterator = typename super::iterator;
        using const_iterator = typename super::const_iterator;
        using reverse_iterator = typename super::reverse_iterator;
        using const_reverse_iterator = typename super::const_reverse_iterator;
 
        using super::begin;
        using super::end;
 
        using super::cbegin;
        using super::cend;
 
        using super::rbegin;
        using super::rend;
 
        using super::crbegin;
        using super::crend;
 
        using super::equal_range;
        using super::lower_bound;
        using super::upper_bound;
 
        using super::clear;
        using super::contains;
        using super::empty;
        using super::erase;
        using super::size;
        using super::swap;
 
        auto keys() const {
            using CeresEngine::keys;
            return unique(keys(*this));
        }
 
        template<typename K = Key> auto values(const K& key) const {
            using CeresEngine::values;
            return values(wrap(equal_range(key)));
        }
 
        template<typename K = Key> auto values(const Key& key) {
            using CeresEngine::values;
            return values(wrap(equal_range(key)));
        }
 
        template<typename K = Key> mapped_type& at(const K& key, size_t index) { return const_cast<mapped_type&>(std::as_const(*this).at(key, index)); }
 
        template<typename K = Key> const mapped_type& at(const K& key, size_t index) const {
            const const_iterator lower = lower_bound(key);
            const const_iterator upper = upper_bound(key);
            const size_type currentSize = std::distance(lower, upper);
 
            if(lower == upper) {
                throw std::out_of_range("key");
            }
 
            if(currentSize < index) {
                throw std::out_of_range("index");
            }
 
            const const_iterator desired = std::next(lower, index);
            return desired->second;
        }
 
        template<typename K = Key> bool contains(const K& key, size_t index) const { return super::count(key) > index; }
 
        static constexpr bool has_reserve = requires(super & container) { container.reserve(size_type()); };
 
        void reserve(size_type newCapacity) requires has_reserve
        {
            super::reserve(newCapacity);
        }
 
        static constexpr bool has_shrink_to_fit = requires(super & container) { container.shrink_to_fit(); };
 
        void shrink_to_fit() requires has_shrink_to_fit
        {
            super::shrink_to_fit();
        }
 
        template<typename K = Key> void resize(const K& key, size_type newSize, const Value& value = Value()) {
            const iterator lower = lower_bound(key);
            iterator upper = upper_bound(key);
            const size_type currentSize = std::distance(lower, upper);
 
            if(currentSize < newSize) {
                for(const size_type index : range(newSize - currentSize)) {
                    (void)index;
                    upper = super::emplace_hint(upper, key, value);
                }
            } else if(currentSize > newSize) {
                erase(std::prev(upper, currentSize - newSize), upper);
            }
        }
 
        template<typename K = Key> void clear(const K& key) { erase(key); }
 
        static constexpr bool has_capacity = requires(const super& container) {
                                                 { container.capacity() } -> std::template same_as<size_type>;
                                             };
 
        [[nodiscard]] size_type capacity() const requires has_capacity
        {
            return super::capacity();
        }
 
        template<typename K = Key> [[nodiscard]] size_type size(const K& key) const { return super::count(key); }
 
        template<typename K = Key> [[nodiscard]] iterator erase(const K& key, size_type index) const {
            const iterator lower = lower_bound(key);
            const iterator upper = upper_bound(key);
            const size_type currentSize = std::distance(lower, upper);
 
            if(lower == upper) {
                throw std::out_of_range("index");
            }
 
            if(currentSize < index) {
                throw std::out_of_range("index");
            }
 
            return erase(std::next(lower, index));
        }
 
        template<typename K = Key, typename... Args> mapped_type& emplace_back(const K& key, Args&&... args) {
            return super::emplace_hint(upper_bound(key), std::piecewise_construct, std::forward_as_tuple(key), std::forward_as_tuple(args...))->second;
        }
 
        template<typename K = Key> mapped_type& push_back(const K& key, const Value& value) { return super::insert(upper_bound(key), {key, value})->second; }
 
        template<typename K = Key> mapped_type& push_back(const K& key, Value&& value) {
            return super::insert(upper_bound(key), {key, std::forward<Value>(value)})->second;
        }
 
        template<typename K = Key> const mapped_type& operator()(const K& key, size_type index) const { return at(key, index); }
 
        template<typename K = Key> mapped_type& operator()(const K& key, size_type index) {
            ensureSize(key, index + 1u);
            return at(key, index);
        }
 
    private:
        template<typename K = Key> void ensureSize(const K& key, size_type desiredSize) {
            if(size(key) < desiredSize) {
                resize(key, desiredSize + 1);
            }
        }
 
        friend struct std::hash<BasicIndexedMultimap<Key, Value, Container>>;
    };
 
    template<typename Key, typename Value, typename Compare = std::less<>, typename RawAllocator = DefaultAllocator>
    using IndexedMultimap =
        BasicIndexedMultimap<Key, Value, std::multimap<Key, Value, Compare, ScopedAllocatorAdaptor<StdAllocator<Pair<const Key, Value>, RawAllocator>>>>;
 
    template<typename Key, typename Value, size_t N, typename Compare = std::less<>, typename RawAllocator = DefaultAllocator>
    using SmallFlatIndexedMultimap = BasicIndexedMultimap<Key, Value, sfl::small_flat_multimap<Key, Value, N, Compare, StdAllocator<Pair<Key, Value>, RawAllocator>>>;
 
} // namespace CeresEngine
 
template<typename Key, typename Value, typename Container> struct std::hash<CeresEngine::BasicIndexedMultimap<Key, Value, Container>> {
    using ValueType = CeresEngine::BasicIndexedMultimap<Key, Value, Container>;
    [[nodiscard]] size_t operator()(const ValueType& value) { return std::hash<Container>{}(value); }
};