hxflat_map.hpp

Go to the documentation of this file.

#pragma once
// SPDX-FileCopyrightText: © 2017-2026 Adrian Johnston.
// SPDX-License-Identifier: MIT
// This file is licensed under the MIT license found in the LICENSE.md file.

 
#include "libhatchet.h"
 
// HX_USE_MACROS_WITH_MODULE allows including macros alongside the module.
#if HX_USE_MACROS_WITH_MODULE
#error Header does not provide macros alone.
#endif
 
#include "hxallocator.hpp"
#include "hxrange.hpp"
#include "hxinitializer_list.hpp"
 
HX_NS_BEGIN_
 
#if HX_CPLUSPLUS >= 202002L
template<typename T_>
concept hxflat_map_concept_ = requires(T_& x_) {
    sizeof(T_);
    x_.~T_();
};
#else
#define hxflat_map_concept_ typename
#endif

template<typename key_t_, typename mapped_t_>
class hxflat_map_const_value_t {
public:
    bool operator==(const hxflat_map_const_value_t& x_) const {
        return hxkey_equal(key, x_.key) && hxkey_equal(value, x_.value);
    }

    bool operator<(const hxflat_map_const_value_t& x_) const {
        if(!hxkey_equal(key, x_.key)) { return hxkey_less(key, x_.key); }
        return hxkey_less(value, x_.value);
    }

    const key_t_& key;

    const mapped_t_& value;
 
protected:
    template<hxflat_map_concept_, hxflat_map_concept_, typename, bool, hxsize_t> friend class hxflat_map;
    hxflat_map_const_value_t(const key_t_& key_, const mapped_t_& mapped_)
        : key(key_), value(mapped_) { }
};

template<typename key_t_, typename mapped_t_>
class hxflat_map_value_t {
public:
    bool operator==(const hxflat_map_value_t& x_) const {
        return hxkey_equal(key, x_.key) && hxkey_equal(value, x_.value);
    }

    bool operator<(const hxflat_map_value_t& x_) const {
        if(!hxkey_equal(key, x_.key)) { return hxkey_less(key, x_.key); }
        return hxkey_less(value, x_.value);
    }

    const key_t_& key;

    mapped_t_& value;
 
protected:
    template<hxflat_map_concept_, hxflat_map_concept_, typename, bool, hxsize_t> friend class hxflat_map;
    hxflat_map_value_t(const key_t_& key_, mapped_t_& mapped_)
        : key(key_), value(mapped_) { }
};

template<hxflat_map_concept_ key_t_,
    hxflat_map_concept_ mapped_t_,
    typename compare_t_=hxkey_less_t<key_t_>,
    bool multi_t_=true,
    hxsize_t capacity_=hxallocator_dynamic_capacity>
class hxflat_map {
public:
    using key_t = key_t_;
    using mapped_t = mapped_t_;
    using compare_t = compare_t_;

    class const_iterator {
    public:
        const_iterator(void) : m_map_(hxnull), m_index_(0) { }

        hxflat_map_const_value_t<key_t_, mapped_t_> operator*(void) const {
            return hxflat_map_const_value_t<key_t_, mapped_t_>(this->key(), this->value());
        }

        const_iterator& operator+=(hxsize_t n_);

        const_iterator& operator-=(hxsize_t n_) { return operator+=(-n_); }

        const_iterator operator+(hxsize_t n_) const { const_iterator t_(*this); t_ += n_; return t_; }

        const_iterator operator-(hxsize_t n_) const { const_iterator t_(*this); t_ -= n_; return t_; }

        hxsize_t operator-(const const_iterator& x_) const;

        hxflat_map_const_value_t<key_t_, mapped_t_> operator[](hxsize_t n_) const { return *operator+(n_); }

        const_iterator& operator++(void) { return operator+=(1); }

        const_iterator operator++(int) { const_iterator t_(*this); operator++(); return t_; }

        const_iterator& operator--(void) { return operator+=(-1); }

        const_iterator operator--(int) { const_iterator t_(*this); operator--(); return t_; }

        bool operator==(const const_iterator& x_) const;

        bool operator<(const const_iterator& x_) const;

        bool operator>(const const_iterator& x_) const { return x_ < *this; }

        bool operator<=(const const_iterator& x_) const { return !(x_ < *this); }

        bool operator>=(const const_iterator& x_) const { return !(*this < x_); }
 
#if HX_CPLUSPLUS < 202002L
        bool operator!=(const const_iterator& x_) const;
#endif

        const key_t_& key(void) const;

        const mapped_t_& value(void) const;
 
    protected:
        friend class hxflat_map;
        const_iterator(const hxflat_map* map_, hxsize_t index_)
            : m_map_(map_), m_index_(index_) { }
        const hxflat_map* m_map_;
        hxsize_t m_index_;
    };

    class iterator : public const_iterator {
    public:
        iterator(void) { }

        hxflat_map_value_t<key_t_, mapped_t_> operator*(void) const {
            return hxflat_map_value_t<key_t_, mapped_t_>(this->key(), this->value());
        }

        iterator& operator+=(hxsize_t n_) { const_iterator::operator+=(n_); return *this; }

        iterator& operator-=(hxsize_t n_) { return operator+=(-n_); }

        iterator operator+(hxsize_t n_) const { iterator t_(*this); t_ += n_; return t_; }

        iterator operator-(hxsize_t n_) const { iterator t_(*this); t_ -= n_; return t_; }

        hxsize_t operator-(const const_iterator& x_) const { return const_iterator::operator-(x_); }

        hxflat_map_value_t<key_t_, mapped_t_> operator[](hxsize_t n_) const { return *operator+(n_); }

        iterator& operator++(void) { const_iterator::operator++(); return *this; }

        iterator operator++(int) { iterator t_(*this); const_iterator::operator++(); return t_; }

        iterator& operator--(void) { const_iterator::operator--(); return *this; }

        iterator operator--(int) { iterator t_(*this); const_iterator::operator--(); return t_; }

        mapped_t_& value(void) const;
 
    protected:
        friend class hxflat_map;
        iterator(hxflat_map* map_, hxsize_t index_) : const_iterator(map_, index_) { }
        iterator(const const_iterator& x_) : const_iterator(x_) { }
    };

    class pair_t_ {
    public:
        key_t_ key_;
        mapped_t_ mapped_;
    };

    explicit hxflat_map(void);

    hxflat_map(const hxflat_map& x_) noexcept;

    hxflat_map(hxflat_map&& x_) noexcept;

    hxflat_map(std::initializer_list<pair_t_> x_) noexcept;

    ~hxflat_map(void) noexcept;
 
#if HX_CPLUSPLUS >= 202302L
    template<typename self_t_, typename callable_t_>
    hxattr_nodiscard auto and_then(
        this self_t_&& self_, const key_t_& key_, callable_t_&& callable_)
        -> hxremove_cvref_t<decltype(
            hxforward<callable_t_>(callable_)(
                hxforward_like<self_t_>(hxdeclval<mapped_t_&>())))>;

    template<typename self_t_, typename callable_t_>
    hxattr_nodiscard auto and_then(
        this self_t_&& self_, const_iterator it_, callable_t_&& callable_)
        -> hxremove_cvref_t<decltype(
            hxforward<callable_t_>(callable_)(hxforward_like<self_t_>(
                hxdeclval<const mapped_t_&>())))>;
#endif // HX_CPLUSPLUS >= 202302L

    void operator=(const hxflat_map& x_) noexcept;

    template<hxsize_t capacity_x_>
    void operator=(const hxflat_map<key_t_, mapped_t_, compare_t_, multi_t_,
        capacity_x_>& x_) noexcept;

    void operator=(hxflat_map&& x_) noexcept;

    hxattr_nodiscard const_iterator operator[](hxsize_t index_) const;
 
    hxattr_nodiscard iterator operator[](hxsize_t index_);

    template<hxsize_t capacity_x_>
    hxattr_nodiscard bool operator==(const hxflat_map<key_t_, mapped_t_, compare_t_,
        multi_t_, capacity_x_>& x_) const;

    template<hxsize_t capacity_x_>
    hxattr_nodiscard bool operator<(const hxflat_map<key_t_, mapped_t_, compare_t_,
        multi_t_, capacity_x_>& x_) const;

    const_iterator begin(void) const { return const_iterator(this, 0); }

    iterator begin(void) { return iterator(this, 0); }

    hxattr_nodiscard hxsize_t capacity(void) const { return m_keys_.capacity(); }

    const_iterator cbegin(void) const { return const_iterator(this, 0); }

    const_iterator cend(void) const { return const_iterator(this, m_size_); }

    void clear(void) noexcept;

    hxattr_nodiscard hxsize_t count(const key_t_& key_) const;

    template<typename... args_t_>
    iterator emplace(const key_t_& key_, args_t_&&... args_) noexcept;

    hxattr_nodiscard bool empty(void) const { return m_size_ == 0; }

    const_iterator end(void) const { return const_iterator(this, m_size_); }

    iterator end(void) { return iterator(this, m_size_); }

    hxsize_t erase(const key_t_& key_) noexcept;

    iterator erase(const_iterator it_) noexcept;

    hxattr_nodiscard const_iterator find(const key_t_& key_) const;
 
    hxattr_nodiscard iterator find(const key_t_& key_);

    hxattr_nodiscard bool full(void) const { return m_size_ == m_keys_.capacity(); }

    hxattr_nodiscard bool has_value(const key_t_& key_) const;

    iterator insert(const key_t_& key_, const mapped_t_& mapped_) noexcept;

    iterator insert(const key_t_& key_, mapped_t_&& mapped_) noexcept;

    hxattr_nodiscard const key_t_* keys(void) const noexcept;

    hxattr_nodiscard const_iterator lower_bound(const key_t_& key_) const;
 
    hxattr_nodiscard iterator lower_bound(const key_t_& key_);

    hxattr_nodiscard hxsize_t max_size(void) const { return this->capacity(); }
 
#if HX_CPLUSPLUS >= 202302L
    template<typename self_t_, typename callable_t_>
    hxattr_nodiscard auto or_else(
        this self_t_&& self_, const key_t_& key_, callable_t_&& callable_)
        -> decltype(self_.end());

    template<typename self_t_, typename callable_t_>
    hxattr_nodiscard auto or_else(
        this self_t_&& self_, const_iterator it_, callable_t_&& callable_)
        -> decltype(self_.end());
#endif // HX_CPLUSPLUS >= 202302L

    void reserve(hxsize_t cap_,
            hxsystem_allocator_t allocator_=hxsystem_allocator_current,
            hxalignment_t alignment_=hxalignment) noexcept;

    hxattr_nodiscard hxsize_t size(void) const { return m_size_; }

    void swap(hxflat_map& x_) noexcept;

    hxattr_nodiscard const_iterator upper_bound(const key_t_& key_) const;
 
    hxattr_nodiscard iterator upper_bound(const key_t_& key_);
 
#if HX_CPLUSPLUS >= 202302L
    template<typename self_t_, typename... args_t_>
    hxattr_nodiscard mapped_t_ value_or(
        this self_t_&& self_, const key_t_& key_, args_t_&&... args_);

    template<typename self_t_, typename... args_t_>
    hxattr_nodiscard mapped_t_ value_or(
        this self_t_&& self_, const_iterator it_, args_t_&&... args_);
#endif // HX_CPLUSPLUS >= 202302L

    hxattr_nodiscard const mapped_t_* values(void) const noexcept;
 
    hxattr_nodiscard mapped_t_* values(void) noexcept;
 
private:
    template<hxflat_map_concept_, hxflat_map_concept_, typename, bool, hxsize_t>
    friend class hxflat_map;
 
    template<typename mapped_u_>
    iterator insert_at_(hxsize_t index_, const key_t_& key_, mapped_u_&& mapped_) noexcept;
 
    hxsize_t m_size_;
    hxallocator<key_t_, capacity_> m_keys_;
    hxallocator<mapped_t_, capacity_> m_values_;
};
 
#include "detail/hxflat_map.inl"
HX_NS_END_