From 3bf42c6ff3805a0d42bbc661794a95ff31bedc26 Mon Sep 17 00:00:00 2001 From: untodesu Date: Sat, 15 Mar 2025 16:22:09 +0500 Subject: Add whatever I was working on for the last month --- deps/include/entt/container/dense_map.hpp | 1043 +++++++++++++++++++++++++++++ deps/include/entt/container/dense_set.hpp | 927 +++++++++++++++++++++++++ deps/include/entt/container/fwd.hpp | 38 ++ deps/include/entt/container/table.hpp | 460 +++++++++++++ 4 files changed, 2468 insertions(+) create mode 100644 deps/include/entt/container/dense_map.hpp create mode 100644 deps/include/entt/container/dense_set.hpp create mode 100644 deps/include/entt/container/fwd.hpp create mode 100644 deps/include/entt/container/table.hpp (limited to 'deps/include/entt/container') diff --git a/deps/include/entt/container/dense_map.hpp b/deps/include/entt/container/dense_map.hpp new file mode 100644 index 0000000..4674761 --- /dev/null +++ b/deps/include/entt/container/dense_map.hpp @@ -0,0 +1,1043 @@ +#ifndef ENTT_CONTAINER_DENSE_MAP_HPP +#define ENTT_CONTAINER_DENSE_MAP_HPP + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include "../config/config.h" +#include "../core/compressed_pair.hpp" +#include "../core/iterator.hpp" +#include "../core/memory.hpp" +#include "../core/bit.hpp" +#include "../core/type_traits.hpp" +#include "fwd.hpp" + +namespace entt { + +/*! @cond TURN_OFF_DOXYGEN */ +namespace internal { + +template +struct dense_map_node final { + using value_type = std::pair; + + template + dense_map_node(const std::size_t pos, Args &&...args) + : next{pos}, + element{std::forward(args)...} {} + + template + dense_map_node(std::allocator_arg_t, const Allocator &allocator, const std::size_t pos, Args &&...args) + : next{pos}, + element{entt::make_obj_using_allocator(allocator, std::forward(args)...)} {} + + template + dense_map_node(std::allocator_arg_t, const Allocator &allocator, const dense_map_node &other) + : next{other.next}, + element{entt::make_obj_using_allocator(allocator, other.element)} {} + + template + dense_map_node(std::allocator_arg_t, const Allocator &allocator, dense_map_node &&other) + : next{other.next}, + element{entt::make_obj_using_allocator(allocator, std::move(other.element))} {} + + std::size_t next; + value_type element; +}; + +template +class dense_map_iterator final { + template + friend class dense_map_iterator; + + using first_type = decltype(std::as_const(std::declval()->element.first)); + using second_type = decltype((std::declval()->element.second)); + +public: + using value_type = std::pair; + using pointer = input_iterator_pointer; + using reference = value_type; + using difference_type = std::ptrdiff_t; + using iterator_category = std::input_iterator_tag; + using iterator_concept = std::random_access_iterator_tag; + + constexpr dense_map_iterator() noexcept + : it{} {} + + constexpr dense_map_iterator(const It iter) noexcept + : it{iter} {} + + template && std::is_constructible_v>> + constexpr dense_map_iterator(const dense_map_iterator &other) noexcept + : it{other.it} {} + + constexpr dense_map_iterator &operator++() noexcept { + return ++it, *this; + } + + constexpr dense_map_iterator operator++(int) noexcept { + dense_map_iterator orig = *this; + return ++(*this), orig; + } + + constexpr dense_map_iterator &operator--() noexcept { + return --it, *this; + } + + constexpr dense_map_iterator operator--(int) noexcept { + dense_map_iterator orig = *this; + return operator--(), orig; + } + + constexpr dense_map_iterator &operator+=(const difference_type value) noexcept { + it += value; + return *this; + } + + constexpr dense_map_iterator operator+(const difference_type value) const noexcept { + dense_map_iterator copy = *this; + return (copy += value); + } + + constexpr dense_map_iterator &operator-=(const difference_type value) noexcept { + return (*this += -value); + } + + constexpr dense_map_iterator operator-(const difference_type value) const noexcept { + return (*this + -value); + } + + [[nodiscard]] constexpr reference operator[](const difference_type value) const noexcept { + return {it[value].element.first, it[value].element.second}; + } + + [[nodiscard]] constexpr pointer operator->() const noexcept { + return operator*(); + } + + [[nodiscard]] constexpr reference operator*() const noexcept { + return operator[](0); + } + + template + friend constexpr std::ptrdiff_t operator-(const dense_map_iterator &, const dense_map_iterator &) noexcept; + + template + friend constexpr bool operator==(const dense_map_iterator &, const dense_map_iterator &) noexcept; + + template + friend constexpr bool operator<(const dense_map_iterator &, const dense_map_iterator &) noexcept; + +private: + It it; +}; + +template +[[nodiscard]] constexpr std::ptrdiff_t operator-(const dense_map_iterator &lhs, const dense_map_iterator &rhs) noexcept { + return lhs.it - rhs.it; +} + +template +[[nodiscard]] constexpr bool operator==(const dense_map_iterator &lhs, const dense_map_iterator &rhs) noexcept { + return lhs.it == rhs.it; +} + +template +[[nodiscard]] constexpr bool operator!=(const dense_map_iterator &lhs, const dense_map_iterator &rhs) noexcept { + return !(lhs == rhs); +} + +template +[[nodiscard]] constexpr bool operator<(const dense_map_iterator &lhs, const dense_map_iterator &rhs) noexcept { + return lhs.it < rhs.it; +} + +template +[[nodiscard]] constexpr bool operator>(const dense_map_iterator &lhs, const dense_map_iterator &rhs) noexcept { + return rhs < lhs; +} + +template +[[nodiscard]] constexpr bool operator<=(const dense_map_iterator &lhs, const dense_map_iterator &rhs) noexcept { + return !(lhs > rhs); +} + +template +[[nodiscard]] constexpr bool operator>=(const dense_map_iterator &lhs, const dense_map_iterator &rhs) noexcept { + return !(lhs < rhs); +} + +template +class dense_map_local_iterator final { + template + friend class dense_map_local_iterator; + + using first_type = decltype(std::as_const(std::declval()->element.first)); + using second_type = decltype((std::declval()->element.second)); + +public: + using value_type = std::pair; + using pointer = input_iterator_pointer; + using reference = value_type; + using difference_type = std::ptrdiff_t; + using iterator_category = std::input_iterator_tag; + using iterator_concept = std::forward_iterator_tag; + + constexpr dense_map_local_iterator() noexcept + : it{}, + offset{} {} + + constexpr dense_map_local_iterator(It iter, const std::size_t pos) noexcept + : it{iter}, + offset{pos} {} + + template && std::is_constructible_v>> + constexpr dense_map_local_iterator(const dense_map_local_iterator &other) noexcept + : it{other.it}, + offset{other.offset} {} + + constexpr dense_map_local_iterator &operator++() noexcept { + return offset = it[offset].next, *this; + } + + constexpr dense_map_local_iterator operator++(int) noexcept { + dense_map_local_iterator orig = *this; + return ++(*this), orig; + } + + [[nodiscard]] constexpr pointer operator->() const noexcept { + return operator*(); + } + + [[nodiscard]] constexpr reference operator*() const noexcept { + return {it[offset].element.first, it[offset].element.second}; + } + + [[nodiscard]] constexpr std::size_t index() const noexcept { + return offset; + } + +private: + It it; + std::size_t offset; +}; + +template +[[nodiscard]] constexpr bool operator==(const dense_map_local_iterator &lhs, const dense_map_local_iterator &rhs) noexcept { + return lhs.index() == rhs.index(); +} + +template +[[nodiscard]] constexpr bool operator!=(const dense_map_local_iterator &lhs, const dense_map_local_iterator &rhs) noexcept { + return !(lhs == rhs); +} + +} // namespace internal +/*! @endcond */ + +/** + * @brief Associative container for key-value pairs with unique keys. + * + * Internally, elements are organized into buckets. Which bucket an element is + * placed into depends entirely on the hash of its key. Keys with the same hash + * code appear in the same bucket. + * + * @tparam Key Key type of the associative container. + * @tparam Type Mapped type of the associative container. + * @tparam Hash Type of function to use to hash the keys. + * @tparam KeyEqual Type of function to use to compare the keys for equality. + * @tparam Allocator Type of allocator used to manage memory and elements. + */ +template +class dense_map { + static constexpr float default_threshold = 0.875f; + static constexpr std::size_t minimum_capacity = 8u; + + using node_type = internal::dense_map_node; + using alloc_traits = std::allocator_traits; + static_assert(std::is_same_v>, "Invalid value type"); + using sparse_container_type = std::vector>; + using packed_container_type = std::vector>; + + template + [[nodiscard]] std::size_t key_to_bucket(const Other &key) const noexcept { + return fast_mod(static_cast(sparse.second()(key)), bucket_count()); + } + + template + [[nodiscard]] auto constrained_find(const Other &key, std::size_t bucket) { + for(auto it = begin(bucket), last = end(bucket); it != last; ++it) { + if(packed.second()(it->first, key)) { + return begin() + static_cast(it.index()); + } + } + + return end(); + } + + template + [[nodiscard]] auto constrained_find(const Other &key, std::size_t bucket) const { + for(auto it = cbegin(bucket), last = cend(bucket); it != last; ++it) { + if(packed.second()(it->first, key)) { + return cbegin() + static_cast(it.index()); + } + } + + return cend(); + } + + template + [[nodiscard]] auto insert_or_do_nothing(Other &&key, Args &&...args) { + const auto index = key_to_bucket(key); + + if(auto it = constrained_find(key, index); it != end()) { + return std::make_pair(it, false); + } + + packed.first().emplace_back(sparse.first()[index], std::piecewise_construct, std::forward_as_tuple(std::forward(key)), std::forward_as_tuple(std::forward(args)...)); + sparse.first()[index] = packed.first().size() - 1u; + rehash_if_required(); + + return std::make_pair(--end(), true); + } + + template + [[nodiscard]] auto insert_or_overwrite(Other &&key, Arg &&value) { + const auto index = key_to_bucket(key); + + if(auto it = constrained_find(key, index); it != end()) { + it->second = std::forward(value); + return std::make_pair(it, false); + } + + packed.first().emplace_back(sparse.first()[index], std::forward(key), std::forward(value)); + sparse.first()[index] = packed.first().size() - 1u; + rehash_if_required(); + + return std::make_pair(--end(), true); + } + + void move_and_pop(const std::size_t pos) { + if(const auto last = size() - 1u; pos != last) { + size_type *curr = &sparse.first()[key_to_bucket(packed.first().back().element.first)]; + packed.first()[pos] = std::move(packed.first().back()); + for(; *curr != last; curr = &packed.first()[*curr].next) {} + *curr = pos; + } + + packed.first().pop_back(); + } + + void rehash_if_required() { + if(size() > (bucket_count() * max_load_factor())) { + rehash(bucket_count() * 2u); + } + } + +public: + /*! @brief Allocator type. */ + using allocator_type = Allocator; + /*! @brief Key type of the container. */ + using key_type = Key; + /*! @brief Mapped type of the container. */ + using mapped_type = Type; + /*! @brief Key-value type of the container. */ + using value_type = std::pair; + /*! @brief Unsigned integer type. */ + using size_type = std::size_t; + /*! @brief Type of function to use to hash the keys. */ + using hasher = Hash; + /*! @brief Type of function to use to compare the keys for equality. */ + using key_equal = KeyEqual; + /*! @brief Input iterator type. */ + using iterator = internal::dense_map_iterator; + /*! @brief Constant input iterator type. */ + using const_iterator = internal::dense_map_iterator; + /*! @brief Input iterator type. */ + using local_iterator = internal::dense_map_local_iterator; + /*! @brief Constant input iterator type. */ + using const_local_iterator = internal::dense_map_local_iterator; + + /*! @brief Default constructor. */ + dense_map() + : dense_map{minimum_capacity} {} + + /** + * @brief Constructs an empty container with a given allocator. + * @param allocator The allocator to use. + */ + explicit dense_map(const allocator_type &allocator) + : dense_map{minimum_capacity, hasher{}, key_equal{}, allocator} {} + + /** + * @brief Constructs an empty container with a given allocator and user + * supplied minimal number of buckets. + * @param cnt Minimal number of buckets. + * @param allocator The allocator to use. + */ + dense_map(const size_type cnt, const allocator_type &allocator) + : dense_map{cnt, hasher{}, key_equal{}, allocator} {} + + /** + * @brief Constructs an empty container with a given allocator, hash + * function and user supplied minimal number of buckets. + * @param cnt Minimal number of buckets. + * @param hash Hash function to use. + * @param allocator The allocator to use. + */ + dense_map(const size_type cnt, const hasher &hash, const allocator_type &allocator) + : dense_map{cnt, hash, key_equal{}, allocator} {} + + /** + * @brief Constructs an empty container with a given allocator, hash + * function, compare function and user supplied minimal number of buckets. + * @param cnt Minimal number of buckets. + * @param hash Hash function to use. + * @param equal Compare function to use. + * @param allocator The allocator to use. + */ + explicit dense_map(const size_type cnt, const hasher &hash = hasher{}, const key_equal &equal = key_equal{}, const allocator_type &allocator = allocator_type{}) + : sparse{allocator, hash}, + packed{allocator, equal} { + rehash(cnt); + } + + /*! @brief Default copy constructor. */ + dense_map(const dense_map &) = default; + + /** + * @brief Allocator-extended copy constructor. + * @param other The instance to copy from. + * @param allocator The allocator to use. + */ + dense_map(const dense_map &other, const allocator_type &allocator) + : sparse{std::piecewise_construct, std::forward_as_tuple(other.sparse.first(), allocator), std::forward_as_tuple(other.sparse.second())}, + packed{std::piecewise_construct, std::forward_as_tuple(other.packed.first(), allocator), std::forward_as_tuple(other.packed.second())}, + threshold{other.threshold} {} + + /*! @brief Default move constructor. */ + dense_map(dense_map &&) noexcept(std::is_nothrow_move_constructible_v> && std::is_nothrow_move_constructible_v>) = default; + + /** + * @brief Allocator-extended move constructor. + * @param other The instance to move from. + * @param allocator The allocator to use. + */ + dense_map(dense_map &&other, const allocator_type &allocator) + : sparse{std::piecewise_construct, std::forward_as_tuple(std::move(other.sparse.first()), allocator), std::forward_as_tuple(std::move(other.sparse.second()))}, + packed{std::piecewise_construct, std::forward_as_tuple(std::move(other.packed.first()), allocator), std::forward_as_tuple(std::move(other.packed.second()))}, + threshold{other.threshold} {} + + /*! @brief Default destructor. */ + ~dense_map() noexcept = default; + + /** + * @brief Default copy assignment operator. + * @return This container. + */ + dense_map &operator=(const dense_map &) = default; + + /** + * @brief Default move assignment operator. + * @return This container. + */ + dense_map &operator=(dense_map &&) noexcept(std::is_nothrow_move_assignable_v> && std::is_nothrow_move_assignable_v>) = default; + + /** + * @brief Returns the associated allocator. + * @return The associated allocator. + */ + [[nodiscard]] constexpr allocator_type get_allocator() const noexcept { + return sparse.first().get_allocator(); + } + + /** + * @brief Returns an iterator to the beginning. + * + * If the array is empty, the returned iterator will be equal to `end()`. + * + * @return An iterator to the first instance of the internal array. + */ + [[nodiscard]] const_iterator cbegin() const noexcept { + return packed.first().begin(); + } + + /*! @copydoc cbegin */ + [[nodiscard]] const_iterator begin() const noexcept { + return cbegin(); + } + + /*! @copydoc begin */ + [[nodiscard]] iterator begin() noexcept { + return packed.first().begin(); + } + + /** + * @brief Returns an iterator to the end. + * @return An iterator to the element following the last instance of the + * internal array. + */ + [[nodiscard]] const_iterator cend() const noexcept { + return packed.first().end(); + } + + /*! @copydoc cend */ + [[nodiscard]] const_iterator end() const noexcept { + return cend(); + } + + /*! @copydoc end */ + [[nodiscard]] iterator end() noexcept { + return packed.first().end(); + } + + /** + * @brief Checks whether a container is empty. + * @return True if the container is empty, false otherwise. + */ + [[nodiscard]] bool empty() const noexcept { + return packed.first().empty(); + } + + /** + * @brief Returns the number of elements in a container. + * @return Number of elements in a container. + */ + [[nodiscard]] size_type size() const noexcept { + return packed.first().size(); + } + + /** + * @brief Returns the maximum possible number of elements. + * @return Maximum possible number of elements. + */ + [[nodiscard]] size_type max_size() const noexcept { + return packed.first().max_size(); + } + + /*! @brief Clears the container. */ + void clear() noexcept { + sparse.first().clear(); + packed.first().clear(); + rehash(0u); + } + + /** + * @brief Inserts an element into the container, if the key does not exist. + * @param value A key-value pair eventually convertible to the value type. + * @return A pair consisting of an iterator to the inserted element (or to + * the element that prevented the insertion) and a bool denoting whether the + * insertion took place. + */ + std::pair insert(const value_type &value) { + return insert_or_do_nothing(value.first, value.second); + } + + /*! @copydoc insert */ + std::pair insert(value_type &&value) { + return insert_or_do_nothing(std::move(value.first), std::move(value.second)); + } + + /** + * @copydoc insert + * @tparam Arg Type of the key-value pair to insert into the container. + */ + template + std::enable_if_t, std::pair> + insert(Arg &&value) { + return insert_or_do_nothing(std::forward(value).first, std::forward(value).second); + } + + /** + * @brief Inserts elements into the container, if their keys do not exist. + * @tparam It Type of input iterator. + * @param first An iterator to the first element of the range of elements. + * @param last An iterator past the last element of the range of elements. + */ + template + void insert(It first, It last) { + for(; first != last; ++first) { + insert(*first); + } + } + + /** + * @brief Inserts an element into the container or assigns to the current + * element if the key already exists. + * @tparam Arg Type of the value to insert or assign. + * @param key A key used both to look up and to insert if not found. + * @param value A value to insert or assign. + * @return A pair consisting of an iterator to the element and a bool + * denoting whether the insertion took place. + */ + template + std::pair insert_or_assign(const key_type &key, Arg &&value) { + return insert_or_overwrite(key, std::forward(value)); + } + + /*! @copydoc insert_or_assign */ + template + std::pair insert_or_assign(key_type &&key, Arg &&value) { + return insert_or_overwrite(std::move(key), std::forward(value)); + } + + /** + * @brief Constructs an element in-place, if the key does not exist. + * + * The element is also constructed when the container already has the key, + * in which case the newly constructed object is destroyed immediately. + * + * @tparam Args Types of arguments to forward to the constructor of the + * element. + * @param args Arguments to forward to the constructor of the element. + * @return A pair consisting of an iterator to the inserted element (or to + * the element that prevented the insertion) and a bool denoting whether the + * insertion took place. + */ + template + std::pair emplace([[maybe_unused]] Args &&...args) { + if constexpr(sizeof...(Args) == 0u) { + return insert_or_do_nothing(key_type{}); + } else if constexpr(sizeof...(Args) == 1u) { + return insert_or_do_nothing(std::forward(args).first..., std::forward(args).second...); + } else if constexpr(sizeof...(Args) == 2u) { + return insert_or_do_nothing(std::forward(args)...); + } else { + auto &node = packed.first().emplace_back(packed.first().size(), std::forward(args)...); + const auto index = key_to_bucket(node.element.first); + + if(auto it = constrained_find(node.element.first, index); it != end()) { + packed.first().pop_back(); + return std::make_pair(it, false); + } + + std::swap(node.next, sparse.first()[index]); + rehash_if_required(); + + return std::make_pair(--end(), true); + } + } + + /** + * @brief Inserts in-place if the key does not exist, does nothing if the + * key exists. + * @tparam Args Types of arguments to forward to the constructor of the + * element. + * @param key A key used both to look up and to insert if not found. + * @param args Arguments to forward to the constructor of the element. + * @return A pair consisting of an iterator to the inserted element (or to + * the element that prevented the insertion) and a bool denoting whether the + * insertion took place. + */ + template + std::pair try_emplace(const key_type &key, Args &&...args) { + return insert_or_do_nothing(key, std::forward(args)...); + } + + /*! @copydoc try_emplace */ + template + std::pair try_emplace(key_type &&key, Args &&...args) { + return insert_or_do_nothing(std::move(key), std::forward(args)...); + } + + /** + * @brief Removes an element from a given position. + * @param pos An iterator to the element to remove. + * @return An iterator following the removed element. + */ + iterator erase(const_iterator pos) { + const auto diff = pos - cbegin(); + erase(pos->first); + return begin() + diff; + } + + /** + * @brief Removes the given elements from a container. + * @param first An iterator to the first element of the range of elements. + * @param last An iterator past the last element of the range of elements. + * @return An iterator following the last removed element. + */ + iterator erase(const_iterator first, const_iterator last) { + const auto dist = first - cbegin(); + + for(auto from = last - cbegin(); from != dist; --from) { + erase(packed.first()[from - 1u].element.first); + } + + return (begin() + dist); + } + + /** + * @brief Removes the element associated with a given key. + * @param key A key value of an element to remove. + * @return Number of elements removed (either 0 or 1). + */ + size_type erase(const key_type &key) { + for(size_type *curr = &sparse.first()[key_to_bucket(key)]; *curr != (std::numeric_limits::max)(); curr = &packed.first()[*curr].next) { + if(packed.second()(packed.first()[*curr].element.first, key)) { + const auto index = *curr; + *curr = packed.first()[*curr].next; + move_and_pop(index); + return 1u; + } + } + + return 0u; + } + + /** + * @brief Exchanges the contents with those of a given container. + * @param other Container to exchange the content with. + */ + void swap(dense_map &other) { + using std::swap; + swap(sparse, other.sparse); + swap(packed, other.packed); + swap(threshold, other.threshold); + } + + /** + * @brief Accesses a given element with bounds checking. + * @param key A key of an element to find. + * @return A reference to the mapped value of the requested element. + */ + [[nodiscard]] mapped_type &at(const key_type &key) { + auto it = find(key); + ENTT_ASSERT(it != end(), "Invalid key"); + return it->second; + } + + /*! @copydoc at */ + [[nodiscard]] const mapped_type &at(const key_type &key) const { + auto it = find(key); + ENTT_ASSERT(it != cend(), "Invalid key"); + return it->second; + } + + /** + * @brief Accesses or inserts a given element. + * @param key A key of an element to find or insert. + * @return A reference to the mapped value of the requested element. + */ + [[nodiscard]] mapped_type &operator[](const key_type &key) { + return insert_or_do_nothing(key).first->second; + } + + /** + * @brief Accesses or inserts a given element. + * @param key A key of an element to find or insert. + * @return A reference to the mapped value of the requested element. + */ + [[nodiscard]] mapped_type &operator[](key_type &&key) { + return insert_or_do_nothing(std::move(key)).first->second; + } + + /** + * @brief Returns the number of elements matching a key (either 1 or 0). + * @param key Key value of an element to search for. + * @return Number of elements matching the key (either 1 or 0). + */ + [[nodiscard]] size_type count(const key_type &key) const { + return find(key) != end(); + } + + /** + * @brief Returns the number of elements matching a key (either 1 or 0). + * @tparam Other Type of the key value of an element to search for. + * @param key Key value of an element to search for. + * @return Number of elements matching the key (either 1 or 0). + */ + template + [[nodiscard]] std::enable_if_t && is_transparent_v, std::conditional_t> + count(const Other &key) const { + return find(key) != end(); + } + + /** + * @brief Finds an element with a given key. + * @param key Key value of an element to search for. + * @return An iterator to an element with the given key. If no such element + * is found, a past-the-end iterator is returned. + */ + [[nodiscard]] iterator find(const key_type &key) { + return constrained_find(key, key_to_bucket(key)); + } + + /*! @copydoc find */ + [[nodiscard]] const_iterator find(const key_type &key) const { + return constrained_find(key, key_to_bucket(key)); + } + + /** + * @brief Finds an element with a key that compares _equivalent_ to a given + * key. + * @tparam Other Type of the key value of an element to search for. + * @param key Key value of an element to search for. + * @return An iterator to an element with the given key. If no such element + * is found, a past-the-end iterator is returned. + */ + template + [[nodiscard]] std::enable_if_t && is_transparent_v, std::conditional_t> + find(const Other &key) { + return constrained_find(key, key_to_bucket(key)); + } + + /*! @copydoc find */ + template + [[nodiscard]] std::enable_if_t && is_transparent_v, std::conditional_t> + find(const Other &key) const { + return constrained_find(key, key_to_bucket(key)); + } + + /** + * @brief Returns a range containing all elements with a given key. + * @param key Key value of an element to search for. + * @return A pair of iterators pointing to the first element and past the + * last element of the range. + */ + [[nodiscard]] std::pair equal_range(const key_type &key) { + const auto it = find(key); + return {it, it + !(it == end())}; + } + + /*! @copydoc equal_range */ + [[nodiscard]] std::pair equal_range(const key_type &key) const { + const auto it = find(key); + return {it, it + !(it == cend())}; + } + + /** + * @brief Returns a range containing all elements that compare _equivalent_ + * to a given key. + * @tparam Other Type of an element to search for. + * @param key Key value of an element to search for. + * @return A pair of iterators pointing to the first element and past the + * last element of the range. + */ + template + [[nodiscard]] std::enable_if_t && is_transparent_v, std::conditional_t>> + equal_range(const Other &key) { + const auto it = find(key); + return {it, it + !(it == end())}; + } + + /*! @copydoc equal_range */ + template + [[nodiscard]] std::enable_if_t && is_transparent_v, std::conditional_t>> + equal_range(const Other &key) const { + const auto it = find(key); + return {it, it + !(it == cend())}; + } + + /** + * @brief Checks if the container contains an element with a given key. + * @param key Key value of an element to search for. + * @return True if there is such an element, false otherwise. + */ + [[nodiscard]] bool contains(const key_type &key) const { + return (find(key) != cend()); + } + + /** + * @brief Checks if the container contains an element with a key that + * compares _equivalent_ to a given value. + * @tparam Other Type of the key value of an element to search for. + * @param key Key value of an element to search for. + * @return True if there is such an element, false otherwise. + */ + template + [[nodiscard]] std::enable_if_t && is_transparent_v, std::conditional_t> + contains(const Other &key) const { + return (find(key) != cend()); + } + + /** + * @brief Returns an iterator to the beginning of a given bucket. + * @param index An index of a bucket to access. + * @return An iterator to the beginning of the given bucket. + */ + [[nodiscard]] const_local_iterator cbegin(const size_type index) const { + return {packed.first().begin(), sparse.first()[index]}; + } + + /** + * @brief Returns an iterator to the beginning of a given bucket. + * @param index An index of a bucket to access. + * @return An iterator to the beginning of the given bucket. + */ + [[nodiscard]] const_local_iterator begin(const size_type index) const { + return cbegin(index); + } + + /** + * @brief Returns an iterator to the beginning of a given bucket. + * @param index An index of a bucket to access. + * @return An iterator to the beginning of the given bucket. + */ + [[nodiscard]] local_iterator begin(const size_type index) { + return {packed.first().begin(), sparse.first()[index]}; + } + + /** + * @brief Returns an iterator to the end of a given bucket. + * @param index An index of a bucket to access. + * @return An iterator to the end of the given bucket. + */ + [[nodiscard]] const_local_iterator cend([[maybe_unused]] const size_type index) const { + return {packed.first().begin(), (std::numeric_limits::max)()}; + } + + /** + * @brief Returns an iterator to the end of a given bucket. + * @param index An index of a bucket to access. + * @return An iterator to the end of the given bucket. + */ + [[nodiscard]] const_local_iterator end(const size_type index) const { + return cend(index); + } + + /** + * @brief Returns an iterator to the end of a given bucket. + * @param index An index of a bucket to access. + * @return An iterator to the end of the given bucket. + */ + [[nodiscard]] local_iterator end([[maybe_unused]] const size_type index) { + return {packed.first().begin(), (std::numeric_limits::max)()}; + } + + /** + * @brief Returns the number of buckets. + * @return The number of buckets. + */ + [[nodiscard]] size_type bucket_count() const { + return sparse.first().size(); + } + + /** + * @brief Returns the maximum number of buckets. + * @return The maximum number of buckets. + */ + [[nodiscard]] size_type max_bucket_count() const { + return sparse.first().max_size(); + } + + /** + * @brief Returns the number of elements in a given bucket. + * @param index The index of the bucket to examine. + * @return The number of elements in the given bucket. + */ + [[nodiscard]] size_type bucket_size(const size_type index) const { + return static_cast(std::distance(begin(index), end(index))); + } + + /** + * @brief Returns the bucket for a given key. + * @param key The value of the key to examine. + * @return The bucket for the given key. + */ + [[nodiscard]] size_type bucket(const key_type &key) const { + return key_to_bucket(key); + } + + /** + * @brief Returns the average number of elements per bucket. + * @return The average number of elements per bucket. + */ + [[nodiscard]] float load_factor() const { + return size() / static_cast(bucket_count()); + } + + /** + * @brief Returns the maximum average number of elements per bucket. + * @return The maximum average number of elements per bucket. + */ + [[nodiscard]] float max_load_factor() const { + return threshold; + } + + /** + * @brief Sets the desired maximum average number of elements per bucket. + * @param value A desired maximum average number of elements per bucket. + */ + void max_load_factor(const float value) { + ENTT_ASSERT(value > 0.f, "Invalid load factor"); + threshold = value; + rehash(0u); + } + + /** + * @brief Reserves at least the specified number of buckets and regenerates + * the hash table. + * @param cnt New number of buckets. + */ + void rehash(const size_type cnt) { + auto value = cnt > minimum_capacity ? cnt : minimum_capacity; + const auto cap = static_cast(size() / max_load_factor()); + value = value > cap ? value : cap; + + if(const auto sz = next_power_of_two(value); sz != bucket_count()) { + sparse.first().resize(sz); + + for(auto &&elem: sparse.first()) { + elem = (std::numeric_limits::max)(); + } + + for(size_type pos{}, last = size(); pos < last; ++pos) { + const auto index = key_to_bucket(packed.first()[pos].element.first); + packed.first()[pos].next = std::exchange(sparse.first()[index], pos); + } + } + } + + /** + * @brief Reserves space for at least the specified number of elements and + * regenerates the hash table. + * @param cnt New number of elements. + */ + void reserve(const size_type cnt) { + packed.first().reserve(cnt); + rehash(static_cast(std::ceil(cnt / max_load_factor()))); + } + + /** + * @brief Returns the function used to hash the keys. + * @return The function used to hash the keys. + */ + [[nodiscard]] hasher hash_function() const { + return sparse.second(); + } + + /** + * @brief Returns the function used to compare keys for equality. + * @return The function used to compare keys for equality. + */ + [[nodiscard]] key_equal key_eq() const { + return packed.second(); + } + +private: + compressed_pair sparse; + compressed_pair packed; + float threshold{default_threshold}; +}; + +} // namespace entt + +/*! @cond TURN_OFF_DOXYGEN */ +namespace std { + +template +struct uses_allocator, Allocator> + : std::true_type {}; + +} // namespace std +/*! @endcond */ + +#endif diff --git a/deps/include/entt/container/dense_set.hpp b/deps/include/entt/container/dense_set.hpp new file mode 100644 index 0000000..d996dfd --- /dev/null +++ b/deps/include/entt/container/dense_set.hpp @@ -0,0 +1,927 @@ +#ifndef ENTT_CONTAINER_DENSE_SET_HPP +#define ENTT_CONTAINER_DENSE_SET_HPP + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include "../config/config.h" +#include "../core/bit.hpp" +#include "../core/compressed_pair.hpp" +#include "../core/type_traits.hpp" +#include "fwd.hpp" + +namespace entt { + +/*! @cond TURN_OFF_DOXYGEN */ +namespace internal { + +template +class dense_set_iterator final { + template + friend class dense_set_iterator; + +public: + using value_type = typename It::value_type::second_type; + using pointer = const value_type *; + using reference = const value_type &; + using difference_type = std::ptrdiff_t; + using iterator_category = std::random_access_iterator_tag; + + constexpr dense_set_iterator() noexcept + : it{} {} + + constexpr dense_set_iterator(const It iter) noexcept + : it{iter} {} + + template && std::is_constructible_v>> + constexpr dense_set_iterator(const dense_set_iterator &other) noexcept + : it{other.it} {} + + constexpr dense_set_iterator &operator++() noexcept { + return ++it, *this; + } + + constexpr dense_set_iterator operator++(int) noexcept { + dense_set_iterator orig = *this; + return ++(*this), orig; + } + + constexpr dense_set_iterator &operator--() noexcept { + return --it, *this; + } + + constexpr dense_set_iterator operator--(int) noexcept { + dense_set_iterator orig = *this; + return operator--(), orig; + } + + constexpr dense_set_iterator &operator+=(const difference_type value) noexcept { + it += value; + return *this; + } + + constexpr dense_set_iterator operator+(const difference_type value) const noexcept { + dense_set_iterator copy = *this; + return (copy += value); + } + + constexpr dense_set_iterator &operator-=(const difference_type value) noexcept { + return (*this += -value); + } + + constexpr dense_set_iterator operator-(const difference_type value) const noexcept { + return (*this + -value); + } + + [[nodiscard]] constexpr reference operator[](const difference_type value) const noexcept { + return it[value].second; + } + + [[nodiscard]] constexpr pointer operator->() const noexcept { + return std::addressof(operator[](0)); + } + + [[nodiscard]] constexpr reference operator*() const noexcept { + return operator[](0); + } + + template + friend constexpr std::ptrdiff_t operator-(const dense_set_iterator &, const dense_set_iterator &) noexcept; + + template + friend constexpr bool operator==(const dense_set_iterator &, const dense_set_iterator &) noexcept; + + template + friend constexpr bool operator<(const dense_set_iterator &, const dense_set_iterator &) noexcept; + +private: + It it; +}; + +template +[[nodiscard]] constexpr std::ptrdiff_t operator-(const dense_set_iterator &lhs, const dense_set_iterator &rhs) noexcept { + return lhs.it - rhs.it; +} + +template +[[nodiscard]] constexpr bool operator==(const dense_set_iterator &lhs, const dense_set_iterator &rhs) noexcept { + return lhs.it == rhs.it; +} + +template +[[nodiscard]] constexpr bool operator!=(const dense_set_iterator &lhs, const dense_set_iterator &rhs) noexcept { + return !(lhs == rhs); +} + +template +[[nodiscard]] constexpr bool operator<(const dense_set_iterator &lhs, const dense_set_iterator &rhs) noexcept { + return lhs.it < rhs.it; +} + +template +[[nodiscard]] constexpr bool operator>(const dense_set_iterator &lhs, const dense_set_iterator &rhs) noexcept { + return rhs < lhs; +} + +template +[[nodiscard]] constexpr bool operator<=(const dense_set_iterator &lhs, const dense_set_iterator &rhs) noexcept { + return !(lhs > rhs); +} + +template +[[nodiscard]] constexpr bool operator>=(const dense_set_iterator &lhs, const dense_set_iterator &rhs) noexcept { + return !(lhs < rhs); +} + +template +class dense_set_local_iterator final { + template + friend class dense_set_local_iterator; + +public: + using value_type = typename It::value_type::second_type; + using pointer = const value_type *; + using reference = const value_type &; + using difference_type = std::ptrdiff_t; + using iterator_category = std::forward_iterator_tag; + + constexpr dense_set_local_iterator() noexcept + : it{}, + offset{} {} + + constexpr dense_set_local_iterator(It iter, const std::size_t pos) noexcept + : it{iter}, + offset{pos} {} + + template && std::is_constructible_v>> + constexpr dense_set_local_iterator(const dense_set_local_iterator &other) noexcept + : it{other.it}, + offset{other.offset} {} + + constexpr dense_set_local_iterator &operator++() noexcept { + return offset = it[offset].first, *this; + } + + constexpr dense_set_local_iterator operator++(int) noexcept { + dense_set_local_iterator orig = *this; + return ++(*this), orig; + } + + [[nodiscard]] constexpr pointer operator->() const noexcept { + return std::addressof(it[offset].second); + } + + [[nodiscard]] constexpr reference operator*() const noexcept { + return *operator->(); + } + + [[nodiscard]] constexpr std::size_t index() const noexcept { + return offset; + } + +private: + It it; + std::size_t offset; +}; + +template +[[nodiscard]] constexpr bool operator==(const dense_set_local_iterator &lhs, const dense_set_local_iterator &rhs) noexcept { + return lhs.index() == rhs.index(); +} + +template +[[nodiscard]] constexpr bool operator!=(const dense_set_local_iterator &lhs, const dense_set_local_iterator &rhs) noexcept { + return !(lhs == rhs); +} + +} // namespace internal +/*! @endcond */ + +/** + * @brief Associative container for unique objects of a given type. + * + * Internally, elements are organized into buckets. Which bucket an element is + * placed into depends entirely on its hash. Elements with the same hash code + * appear in the same bucket. + * + * @tparam Type Value type of the associative container. + * @tparam Hash Type of function to use to hash the values. + * @tparam KeyEqual Type of function to use to compare the values for equality. + * @tparam Allocator Type of allocator used to manage memory and elements. + */ +template +class dense_set { + static constexpr float default_threshold = 0.875f; + static constexpr std::size_t minimum_capacity = 8u; + + using node_type = std::pair; + using alloc_traits = std::allocator_traits; + static_assert(std::is_same_v, "Invalid value type"); + using sparse_container_type = std::vector>; + using packed_container_type = std::vector>; + + template + [[nodiscard]] std::size_t value_to_bucket(const Other &value) const noexcept { + return fast_mod(static_cast(sparse.second()(value)), bucket_count()); + } + + template + [[nodiscard]] auto constrained_find(const Other &value, std::size_t bucket) { + for(auto it = begin(bucket), last = end(bucket); it != last; ++it) { + if(packed.second()(*it, value)) { + return begin() + static_cast(it.index()); + } + } + + return end(); + } + + template + [[nodiscard]] auto constrained_find(const Other &value, std::size_t bucket) const { + for(auto it = cbegin(bucket), last = cend(bucket); it != last; ++it) { + if(packed.second()(*it, value)) { + return cbegin() + static_cast(it.index()); + } + } + + return cend(); + } + + template + [[nodiscard]] auto insert_or_do_nothing(Other &&value) { + const auto index = value_to_bucket(value); + + if(auto it = constrained_find(value, index); it != end()) { + return std::make_pair(it, false); + } + + packed.first().emplace_back(sparse.first()[index], std::forward(value)); + sparse.first()[index] = packed.first().size() - 1u; + rehash_if_required(); + + return std::make_pair(--end(), true); + } + + void move_and_pop(const std::size_t pos) { + if(const auto last = size() - 1u; pos != last) { + size_type *curr = &sparse.first()[value_to_bucket(packed.first().back().second)]; + packed.first()[pos] = std::move(packed.first().back()); + for(; *curr != last; curr = &packed.first()[*curr].first) {} + *curr = pos; + } + + packed.first().pop_back(); + } + + void rehash_if_required() { + if(size() > (bucket_count() * max_load_factor())) { + rehash(bucket_count() * 2u); + } + } + +public: + /*! @brief Allocator type. */ + using allocator_type = Allocator; + /*! @brief Key type of the container. */ + using key_type = Type; + /*! @brief Value type of the container. */ + using value_type = Type; + /*! @brief Unsigned integer type. */ + using size_type = std::size_t; + /*! @brief Type of function to use to hash the elements. */ + using hasher = Hash; + /*! @brief Type of function to use to compare the elements for equality. */ + using key_equal = KeyEqual; + /*! @brief Random access iterator type. */ + using iterator = internal::dense_set_iterator; + /*! @brief Constant random access iterator type. */ + using const_iterator = internal::dense_set_iterator; + /*! @brief Reverse iterator type. */ + using reverse_iterator = std::reverse_iterator; + /*! @brief Constant reverse iterator type. */ + using const_reverse_iterator = std::reverse_iterator; + /*! @brief Forward iterator type. */ + using local_iterator = internal::dense_set_local_iterator; + /*! @brief Constant forward iterator type. */ + using const_local_iterator = internal::dense_set_local_iterator; + + /*! @brief Default constructor. */ + dense_set() + : dense_set{minimum_capacity} {} + + /** + * @brief Constructs an empty container with a given allocator. + * @param allocator The allocator to use. + */ + explicit dense_set(const allocator_type &allocator) + : dense_set{minimum_capacity, hasher{}, key_equal{}, allocator} {} + + /** + * @brief Constructs an empty container with a given allocator and user + * supplied minimal number of buckets. + * @param cnt Minimal number of buckets. + * @param allocator The allocator to use. + */ + dense_set(const size_type cnt, const allocator_type &allocator) + : dense_set{cnt, hasher{}, key_equal{}, allocator} {} + + /** + * @brief Constructs an empty container with a given allocator, hash + * function and user supplied minimal number of buckets. + * @param cnt Minimal number of buckets. + * @param hash Hash function to use. + * @param allocator The allocator to use. + */ + dense_set(const size_type cnt, const hasher &hash, const allocator_type &allocator) + : dense_set{cnt, hash, key_equal{}, allocator} {} + + /** + * @brief Constructs an empty container with a given allocator, hash + * function, compare function and user supplied minimal number of buckets. + * @param cnt Minimal number of buckets. + * @param hash Hash function to use. + * @param equal Compare function to use. + * @param allocator The allocator to use. + */ + explicit dense_set(const size_type cnt, const hasher &hash = hasher{}, const key_equal &equal = key_equal{}, const allocator_type &allocator = allocator_type{}) + : sparse{allocator, hash}, + packed{allocator, equal} { + rehash(cnt); + } + + /*! @brief Default copy constructor. */ + dense_set(const dense_set &) = default; + + /** + * @brief Allocator-extended copy constructor. + * @param other The instance to copy from. + * @param allocator The allocator to use. + */ + dense_set(const dense_set &other, const allocator_type &allocator) + : sparse{std::piecewise_construct, std::forward_as_tuple(other.sparse.first(), allocator), std::forward_as_tuple(other.sparse.second())}, + packed{std::piecewise_construct, std::forward_as_tuple(other.packed.first(), allocator), std::forward_as_tuple(other.packed.second())}, + threshold{other.threshold} {} + + /*! @brief Default move constructor. */ + dense_set(dense_set &&) noexcept(std::is_nothrow_move_constructible_v> && std::is_nothrow_move_constructible_v>) = default; + + /** + * @brief Allocator-extended move constructor. + * @param other The instance to move from. + * @param allocator The allocator to use. + */ + dense_set(dense_set &&other, const allocator_type &allocator) + : sparse{std::piecewise_construct, std::forward_as_tuple(std::move(other.sparse.first()), allocator), std::forward_as_tuple(std::move(other.sparse.second()))}, + packed{std::piecewise_construct, std::forward_as_tuple(std::move(other.packed.first()), allocator), std::forward_as_tuple(std::move(other.packed.second()))}, + threshold{other.threshold} {} + + /*! @brief Default destructor. */ + ~dense_set() noexcept = default; + + /** + * @brief Default copy assignment operator. + * @return This container. + */ + dense_set &operator=(const dense_set &) = default; + + /** + * @brief Default move assignment operator. + * @return This container. + */ + dense_set &operator=(dense_set &&) noexcept(std::is_nothrow_move_assignable_v> && std::is_nothrow_move_assignable_v>) = default; + + /** + * @brief Returns the associated allocator. + * @return The associated allocator. + */ + [[nodiscard]] constexpr allocator_type get_allocator() const noexcept { + return sparse.first().get_allocator(); + } + + /** + * @brief Returns an iterator to the beginning. + * + * If the array is empty, the returned iterator will be equal to `end()`. + * + * @return An iterator to the first instance of the internal array. + */ + [[nodiscard]] const_iterator cbegin() const noexcept { + return packed.first().begin(); + } + + /*! @copydoc cbegin */ + [[nodiscard]] const_iterator begin() const noexcept { + return cbegin(); + } + + /*! @copydoc begin */ + [[nodiscard]] iterator begin() noexcept { + return packed.first().begin(); + } + + /** + * @brief Returns an iterator to the end. + * @return An iterator to the element following the last instance of the + * internal array. + */ + [[nodiscard]] const_iterator cend() const noexcept { + return packed.first().end(); + } + + /*! @copydoc cend */ + [[nodiscard]] const_iterator end() const noexcept { + return cend(); + } + + /*! @copydoc end */ + [[nodiscard]] iterator end() noexcept { + return packed.first().end(); + } + + /** + * @brief Returns a reverse iterator to the beginning. + * + * If the array is empty, the returned iterator will be equal to `rend()`. + * + * @return An iterator to the first instance of the reversed internal array. + */ + [[nodiscard]] const_reverse_iterator crbegin() const noexcept { + return std::make_reverse_iterator(cend()); + } + + /*! @copydoc crbegin */ + [[nodiscard]] const_reverse_iterator rbegin() const noexcept { + return crbegin(); + } + + /*! @copydoc rbegin */ + [[nodiscard]] reverse_iterator rbegin() noexcept { + return std::make_reverse_iterator(end()); + } + + /** + * @brief Returns a reverse iterator to the end. + * @return An iterator to the element following the last instance of the + * reversed internal array. + */ + [[nodiscard]] const_reverse_iterator crend() const noexcept { + return std::make_reverse_iterator(cbegin()); + } + + /*! @copydoc crend */ + [[nodiscard]] const_reverse_iterator rend() const noexcept { + return crend(); + } + + /*! @copydoc rend */ + [[nodiscard]] reverse_iterator rend() noexcept { + return std::make_reverse_iterator(begin()); + } + + /** + * @brief Checks whether a container is empty. + * @return True if the container is empty, false otherwise. + */ + [[nodiscard]] bool empty() const noexcept { + return packed.first().empty(); + } + + /** + * @brief Returns the number of elements in a container. + * @return Number of elements in a container. + */ + [[nodiscard]] size_type size() const noexcept { + return packed.first().size(); + } + + /** + * @brief Returns the maximum possible number of elements. + * @return Maximum possible number of elements. + */ + [[nodiscard]] size_type max_size() const noexcept { + return packed.first().max_size(); + } + + /*! @brief Clears the container. */ + void clear() noexcept { + sparse.first().clear(); + packed.first().clear(); + rehash(0u); + } + + /** + * @brief Inserts an element into the container, if it does not exist. + * @param value An element to insert into the container. + * @return A pair consisting of an iterator to the inserted element (or to + * the element that prevented the insertion) and a bool denoting whether the + * insertion took place. + */ + std::pair insert(const value_type &value) { + return insert_or_do_nothing(value); + } + + /*! @copydoc insert */ + std::pair insert(value_type &&value) { + return insert_or_do_nothing(std::move(value)); + } + + /** + * @brief Inserts elements into the container, if they do not exist. + * @tparam It Type of input iterator. + * @param first An iterator to the first element of the range of elements. + * @param last An iterator past the last element of the range of elements. + */ + template + void insert(It first, It last) { + for(; first != last; ++first) { + insert(*first); + } + } + + /** + * @brief Constructs an element in-place, if it does not exist. + * + * The element is also constructed when the container already has the key, + * in which case the newly constructed object is destroyed immediately. + * + * @tparam Args Types of arguments to forward to the constructor of the + * element. + * @param args Arguments to forward to the constructor of the element. + * @return A pair consisting of an iterator to the inserted element (or to + * the element that prevented the insertion) and a bool denoting whether the + * insertion took place. + */ + template + std::pair emplace(Args &&...args) { + if constexpr(((sizeof...(Args) == 1u) && ... && std::is_same_v, value_type>)) { + return insert_or_do_nothing(std::forward(args)...); + } else { + auto &node = packed.first().emplace_back(std::piecewise_construct, std::make_tuple(packed.first().size()), std::forward_as_tuple(std::forward(args)...)); + const auto index = value_to_bucket(node.second); + + if(auto it = constrained_find(node.second, index); it != end()) { + packed.first().pop_back(); + return std::make_pair(it, false); + } + + std::swap(node.first, sparse.first()[index]); + rehash_if_required(); + + return std::make_pair(--end(), true); + } + } + + /** + * @brief Removes an element from a given position. + * @param pos An iterator to the element to remove. + * @return An iterator following the removed element. + */ + iterator erase(const_iterator pos) { + const auto diff = pos - cbegin(); + erase(*pos); + return begin() + diff; + } + + /** + * @brief Removes the given elements from a container. + * @param first An iterator to the first element of the range of elements. + * @param last An iterator past the last element of the range of elements. + * @return An iterator following the last removed element. + */ + iterator erase(const_iterator first, const_iterator last) { + const auto dist = first - cbegin(); + + for(auto from = last - cbegin(); from != dist; --from) { + erase(packed.first()[from - 1u].second); + } + + return (begin() + dist); + } + + /** + * @brief Removes the element associated with a given value. + * @param value Value of an element to remove. + * @return Number of elements removed (either 0 or 1). + */ + size_type erase(const value_type &value) { + for(size_type *curr = &sparse.first()[value_to_bucket(value)]; *curr != (std::numeric_limits::max)(); curr = &packed.first()[*curr].first) { + if(packed.second()(packed.first()[*curr].second, value)) { + const auto index = *curr; + *curr = packed.first()[*curr].first; + move_and_pop(index); + return 1u; + } + } + + return 0u; + } + + /** + * @brief Exchanges the contents with those of a given container. + * @param other Container to exchange the content with. + */ + void swap(dense_set &other) { + using std::swap; + swap(sparse, other.sparse); + swap(packed, other.packed); + swap(threshold, other.threshold); + } + + /** + * @brief Returns the number of elements matching a value (either 1 or 0). + * @param key Key value of an element to search for. + * @return Number of elements matching the key (either 1 or 0). + */ + [[nodiscard]] size_type count(const value_type &key) const { + return find(key) != end(); + } + + /** + * @brief Returns the number of elements matching a key (either 1 or 0). + * @tparam Other Type of the key value of an element to search for. + * @param key Key value of an element to search for. + * @return Number of elements matching the key (either 1 or 0). + */ + template + [[nodiscard]] std::enable_if_t && is_transparent_v, std::conditional_t> + count(const Other &key) const { + return find(key) != end(); + } + + /** + * @brief Finds an element with a given value. + * @param value Value of an element to search for. + * @return An iterator to an element with the given value. If no such + * element is found, a past-the-end iterator is returned. + */ + [[nodiscard]] iterator find(const value_type &value) { + return constrained_find(value, value_to_bucket(value)); + } + + /*! @copydoc find */ + [[nodiscard]] const_iterator find(const value_type &value) const { + return constrained_find(value, value_to_bucket(value)); + } + + /** + * @brief Finds an element that compares _equivalent_ to a given value. + * @tparam Other Type of an element to search for. + * @param value Value of an element to search for. + * @return An iterator to an element with the given value. If no such + * element is found, a past-the-end iterator is returned. + */ + template + [[nodiscard]] std::enable_if_t && is_transparent_v, std::conditional_t> + find(const Other &value) { + return constrained_find(value, value_to_bucket(value)); + } + + /*! @copydoc find */ + template + [[nodiscard]] std::enable_if_t && is_transparent_v, std::conditional_t> + find(const Other &value) const { + return constrained_find(value, value_to_bucket(value)); + } + + /** + * @brief Returns a range containing all elements with a given value. + * @param value Value of an element to search for. + * @return A pair of iterators pointing to the first element and past the + * last element of the range. + */ + [[nodiscard]] std::pair equal_range(const value_type &value) { + const auto it = find(value); + return {it, it + !(it == end())}; + } + + /*! @copydoc equal_range */ + [[nodiscard]] std::pair equal_range(const value_type &value) const { + const auto it = find(value); + return {it, it + !(it == cend())}; + } + + /** + * @brief Returns a range containing all elements that compare _equivalent_ + * to a given value. + * @tparam Other Type of an element to search for. + * @param value Value of an element to search for. + * @return A pair of iterators pointing to the first element and past the + * last element of the range. + */ + template + [[nodiscard]] std::enable_if_t && is_transparent_v, std::conditional_t>> + equal_range(const Other &value) { + const auto it = find(value); + return {it, it + !(it == end())}; + } + + /*! @copydoc equal_range */ + template + [[nodiscard]] std::enable_if_t && is_transparent_v, std::conditional_t>> + equal_range(const Other &value) const { + const auto it = find(value); + return {it, it + !(it == cend())}; + } + + /** + * @brief Checks if the container contains an element with a given value. + * @param value Value of an element to search for. + * @return True if there is such an element, false otherwise. + */ + [[nodiscard]] bool contains(const value_type &value) const { + return (find(value) != cend()); + } + + /** + * @brief Checks if the container contains an element that compares + * _equivalent_ to a given value. + * @tparam Other Type of an element to search for. + * @param value Value of an element to search for. + * @return True if there is such an element, false otherwise. + */ + template + [[nodiscard]] std::enable_if_t && is_transparent_v, std::conditional_t> + contains(const Other &value) const { + return (find(value) != cend()); + } + + /** + * @brief Returns an iterator to the beginning of a given bucket. + * @param index An index of a bucket to access. + * @return An iterator to the beginning of the given bucket. + */ + [[nodiscard]] const_local_iterator cbegin(const size_type index) const { + return {packed.first().begin(), sparse.first()[index]}; + } + + /** + * @brief Returns an iterator to the beginning of a given bucket. + * @param index An index of a bucket to access. + * @return An iterator to the beginning of the given bucket. + */ + [[nodiscard]] const_local_iterator begin(const size_type index) const { + return cbegin(index); + } + + /** + * @brief Returns an iterator to the beginning of a given bucket. + * @param index An index of a bucket to access. + * @return An iterator to the beginning of the given bucket. + */ + [[nodiscard]] local_iterator begin(const size_type index) { + return {packed.first().begin(), sparse.first()[index]}; + } + + /** + * @brief Returns an iterator to the end of a given bucket. + * @param index An index of a bucket to access. + * @return An iterator to the end of the given bucket. + */ + [[nodiscard]] const_local_iterator cend([[maybe_unused]] const size_type index) const { + return {packed.first().begin(), (std::numeric_limits::max)()}; + } + + /** + * @brief Returns an iterator to the end of a given bucket. + * @param index An index of a bucket to access. + * @return An iterator to the end of the given bucket. + */ + [[nodiscard]] const_local_iterator end(const size_type index) const { + return cend(index); + } + + /** + * @brief Returns an iterator to the end of a given bucket. + * @param index An index of a bucket to access. + * @return An iterator to the end of the given bucket. + */ + [[nodiscard]] local_iterator end([[maybe_unused]] const size_type index) { + return {packed.first().begin(), (std::numeric_limits::max)()}; + } + + /** + * @brief Returns the number of buckets. + * @return The number of buckets. + */ + [[nodiscard]] size_type bucket_count() const { + return sparse.first().size(); + } + + /** + * @brief Returns the maximum number of buckets. + * @return The maximum number of buckets. + */ + [[nodiscard]] size_type max_bucket_count() const { + return sparse.first().max_size(); + } + + /** + * @brief Returns the number of elements in a given bucket. + * @param index The index of the bucket to examine. + * @return The number of elements in the given bucket. + */ + [[nodiscard]] size_type bucket_size(const size_type index) const { + return static_cast(std::distance(begin(index), end(index))); + } + + /** + * @brief Returns the bucket for a given element. + * @param value The value of the element to examine. + * @return The bucket for the given element. + */ + [[nodiscard]] size_type bucket(const value_type &value) const { + return value_to_bucket(value); + } + + /** + * @brief Returns the average number of elements per bucket. + * @return The average number of elements per bucket. + */ + [[nodiscard]] float load_factor() const { + return size() / static_cast(bucket_count()); + } + + /** + * @brief Returns the maximum average number of elements per bucket. + * @return The maximum average number of elements per bucket. + */ + [[nodiscard]] float max_load_factor() const { + return threshold; + } + + /** + * @brief Sets the desired maximum average number of elements per bucket. + * @param value A desired maximum average number of elements per bucket. + */ + void max_load_factor(const float value) { + ENTT_ASSERT(value > 0.f, "Invalid load factor"); + threshold = value; + rehash(0u); + } + + /** + * @brief Reserves at least the specified number of buckets and regenerates + * the hash table. + * @param cnt New number of buckets. + */ + void rehash(const size_type cnt) { + auto value = cnt > minimum_capacity ? cnt : minimum_capacity; + const auto cap = static_cast(size() / max_load_factor()); + value = value > cap ? value : cap; + + if(const auto sz = next_power_of_two(value); sz != bucket_count()) { + sparse.first().resize(sz); + + for(auto &&elem: sparse.first()) { + elem = (std::numeric_limits::max)(); + } + + for(size_type pos{}, last = size(); pos < last; ++pos) { + const auto index = value_to_bucket(packed.first()[pos].second); + packed.first()[pos].first = std::exchange(sparse.first()[index], pos); + } + } + } + + /** + * @brief Reserves space for at least the specified number of elements and + * regenerates the hash table. + * @param cnt New number of elements. + */ + void reserve(const size_type cnt) { + packed.first().reserve(cnt); + rehash(static_cast(std::ceil(cnt / max_load_factor()))); + } + + /** + * @brief Returns the function used to hash the elements. + * @return The function used to hash the elements. + */ + [[nodiscard]] hasher hash_function() const { + return sparse.second(); + } + + /** + * @brief Returns the function used to compare elements for equality. + * @return The function used to compare elements for equality. + */ + [[nodiscard]] key_equal key_eq() const { + return packed.second(); + } + +private: + compressed_pair sparse; + compressed_pair packed; + float threshold{default_threshold}; +}; + +} // namespace entt + +#endif diff --git a/deps/include/entt/container/fwd.hpp b/deps/include/entt/container/fwd.hpp new file mode 100644 index 0000000..8b6375d --- /dev/null +++ b/deps/include/entt/container/fwd.hpp @@ -0,0 +1,38 @@ +#ifndef ENTT_CONTAINER_FWD_HPP +#define ENTT_CONTAINER_FWD_HPP + +#include +#include +#include +#include + +namespace entt { + +template< + typename Key, + typename Type, + typename = std::hash, + typename = std::equal_to<>, + typename = std::allocator>> +class dense_map; + +template< + typename Type, + typename = std::hash, + typename = std::equal_to<>, + typename = std::allocator> +class dense_set; + +template +class basic_table; + +/** + * @brief Alias declaration for the most common use case. + * @tparam Type Element types. + */ +template +using table = basic_table...>; + +} // namespace entt + +#endif diff --git a/deps/include/entt/container/table.hpp b/deps/include/entt/container/table.hpp new file mode 100644 index 0000000..3c8e777 --- /dev/null +++ b/deps/include/entt/container/table.hpp @@ -0,0 +1,460 @@ +#ifndef ENTT_CONTAINER_TABLE_HPP +#define ENTT_CONTAINER_TABLE_HPP + +#include +#include +#include +#include +#include +#include "../config/config.h" +#include "../core/iterator.hpp" +#include "fwd.hpp" + +namespace entt { + +/*! @cond TURN_OFF_DOXYGEN */ +namespace internal { + +template +class table_iterator { + template + friend class table_iterator; + +public: + using value_type = decltype(std::forward_as_tuple(*std::declval()...)); + using pointer = input_iterator_pointer; + using reference = value_type; + using difference_type = std::ptrdiff_t; + using iterator_category = std::input_iterator_tag; + using iterator_concept = std::random_access_iterator_tag; + + constexpr table_iterator() noexcept + : it{} {} + + constexpr table_iterator(It... from) noexcept + : it{from...} {} + + template && ...)>> + constexpr table_iterator(const table_iterator &other) noexcept + : table_iterator{std::get(other.it)...} {} + + constexpr table_iterator &operator++() noexcept { + return (++std::get(it), ...), *this; + } + + constexpr table_iterator operator++(int) noexcept { + table_iterator orig = *this; + return ++(*this), orig; + } + + constexpr table_iterator &operator--() noexcept { + return (--std::get(it), ...), *this; + } + + constexpr table_iterator operator--(int) noexcept { + table_iterator orig = *this; + return operator--(), orig; + } + + constexpr table_iterator &operator+=(const difference_type value) noexcept { + return ((std::get(it) += value), ...), *this; + } + + constexpr table_iterator operator+(const difference_type value) const noexcept { + table_iterator copy = *this; + return (copy += value); + } + + constexpr table_iterator &operator-=(const difference_type value) noexcept { + return (*this += -value); + } + + constexpr table_iterator operator-(const difference_type value) const noexcept { + return (*this + -value); + } + + [[nodiscard]] constexpr reference operator[](const difference_type value) const noexcept { + return std::forward_as_tuple(std::get(it)[value]...); + } + + [[nodiscard]] constexpr pointer operator->() const noexcept { + return {operator[](0)}; + } + + [[nodiscard]] constexpr reference operator*() const noexcept { + return operator[](0); + } + + template + friend constexpr std::ptrdiff_t operator-(const table_iterator &, const table_iterator &) noexcept; + + template + friend constexpr bool operator==(const table_iterator &, const table_iterator &) noexcept; + + template + friend constexpr bool operator<(const table_iterator &, const table_iterator &) noexcept; + +private: + std::tuple it; +}; + +template +[[nodiscard]] constexpr std::ptrdiff_t operator-(const table_iterator &lhs, const table_iterator &rhs) noexcept { + return std::get<0>(lhs.it) - std::get<0>(rhs.it); +} + +template +[[nodiscard]] constexpr bool operator==(const table_iterator &lhs, const table_iterator &rhs) noexcept { + return std::get<0>(lhs.it) == std::get<0>(rhs.it); +} + +template +[[nodiscard]] constexpr bool operator!=(const table_iterator &lhs, const table_iterator &rhs) noexcept { + return !(lhs == rhs); +} + +template +[[nodiscard]] constexpr bool operator<(const table_iterator &lhs, const table_iterator &rhs) noexcept { + return std::get<0>(lhs.it) < std::get<0>(rhs.it); +} + +template +[[nodiscard]] constexpr bool operator>(const table_iterator &lhs, const table_iterator &rhs) noexcept { + return rhs < lhs; +} + +template +[[nodiscard]] constexpr bool operator<=(const table_iterator &lhs, const table_iterator &rhs) noexcept { + return !(lhs > rhs); +} + +template +[[nodiscard]] constexpr bool operator>=(const table_iterator &lhs, const table_iterator &rhs) noexcept { + return !(lhs < rhs); +} + +} // namespace internal +/*! @endcond */ + +/** + * @brief Basic table implementation. + * + * Internal data structures arrange elements to maximize performance. There are + * no guarantees that objects are returned in the insertion order when iterate + * a table. Do not make assumption on the order in any case. + * + * @tparam Container Sequence container row types. + */ +template +class basic_table { + using container_type = std::tuple; + +public: + /*! @brief Unsigned integer type. */ + using size_type = std::size_t; + /*! @brief Input iterator type. */ + using iterator = internal::table_iterator; + /*! @brief Constant input iterator type. */ + using const_iterator = internal::table_iterator; + /*! @brief Reverse iterator type. */ + using reverse_iterator = internal::table_iterator; + /*! @brief Constant reverse iterator type. */ + using const_reverse_iterator = internal::table_iterator; + + /*! @brief Default constructor. */ + basic_table() + : payload{} { + } + + /** + * @brief Copy constructs the underlying containers. + * @param container The containers to copy from. + */ + explicit basic_table(const Container &...container) noexcept + : payload{container...} { + ENTT_ASSERT((((std::get(payload).size() * sizeof...(Container)) == (std::get(payload).size() + ...)) && ...), "Unexpected container size"); + } + + /** + * @brief Move constructs the underlying containers. + * @param container The containers to move from. + */ + explicit basic_table(Container &&...container) noexcept + : payload{std::move(container)...} { + ENTT_ASSERT((((std::get(payload).size() * sizeof...(Container)) == (std::get(payload).size() + ...)) && ...), "Unexpected container size"); + } + + /*! @brief Default copy constructor, deleted on purpose. */ + basic_table(const basic_table &) = delete; + + /** + * @brief Move constructor. + * @param other The instance to move from. + */ + basic_table(basic_table &&other) noexcept + : payload{std::move(other.payload)} {} + + /** + * @brief Constructs the underlying containers using a given allocator. + * @tparam Allocator Type of allocator. + * @param allocator A valid allocator. + */ + template + explicit basic_table(const Allocator &allocator) + : payload{Container{allocator}...} {} + + /** + * @brief Copy constructs the underlying containers using a given allocator. + * @tparam Allocator Type of allocator. + * @param container The containers to copy from. + * @param allocator A valid allocator. + */ + template + basic_table(const Container &...container, const Allocator &allocator) noexcept + : payload{Container{container, allocator}...} { + ENTT_ASSERT((((std::get(payload).size() * sizeof...(Container)) == (std::get(payload).size() + ...)) && ...), "Unexpected container size"); + } + + /** + * @brief Move constructs the underlying containers using a given allocator. + * @tparam Allocator Type of allocator. + * @param container The containers to move from. + * @param allocator A valid allocator. + */ + template + basic_table(Container &&...container, const Allocator &allocator) noexcept + : payload{Container{std::move(container), allocator}...} { + ENTT_ASSERT((((std::get(payload).size() * sizeof...(Container)) == (std::get(payload).size() + ...)) && ...), "Unexpected container size"); + } + + /** + * @brief Allocator-extended move constructor. + * @tparam Allocator Type of allocator. + * @param other The instance to move from. + * @param allocator The allocator to use. + */ + template + basic_table(basic_table &&other, const Allocator &allocator) + : payload{Container{std::move(std::get(other.payload)), allocator}...} {} + + /*! @brief Default destructor. */ + ~basic_table() noexcept = default; + + /** + * @brief Default copy assignment operator, deleted on purpose. + * @return This container. + */ + basic_table &operator=(const basic_table &) = delete; + + /** + * @brief Move assignment operator. + * @param other The instance to move from. + * @return This container. + */ + basic_table &operator=(basic_table &&other) noexcept { + payload = std::move(other.payload); + return *this; + } + + /** + * @brief Exchanges the contents with those of a given table. + * @param other Table to exchange the content with. + */ + void swap(basic_table &other) { + using std::swap; + swap(payload, other.payload); + } + + /** + * @brief Increases the capacity of a table. + * + * If the new capacity is greater than the current capacity, new storage is + * allocated, otherwise the method does nothing. + * + * @param cap Desired capacity. + */ + void reserve(const size_type cap) { + (std::get(payload).reserve(cap), ...); + } + + /** + * @brief Returns the number of rows that a table has currently allocated + * space for. + * @return Capacity of the table. + */ + [[nodiscard]] size_type capacity() const noexcept { + return std::get<0>(payload).capacity(); + } + + /*! @brief Requests the removal of unused capacity. */ + void shrink_to_fit() { + (std::get(payload).shrink_to_fit(), ...); + } + + /** + * @brief Returns the number of rows in a table. + * @return Number of rows. + */ + [[nodiscard]] size_type size() const noexcept { + return std::get<0>(payload).size(); + } + + /** + * @brief Checks whether a table is empty. + * @return True if the table is empty, false otherwise. + */ + [[nodiscard]] bool empty() const noexcept { + return std::get<0>(payload).empty(); + } + + /** + * @brief Returns an iterator to the beginning. + * + * If the table is empty, the returned iterator will be equal to `end()`. + * + * @return An iterator to the first row of the table. + */ + [[nodiscard]] const_iterator cbegin() const noexcept { + return {std::get(payload).cbegin()...}; + } + + /*! @copydoc cbegin */ + [[nodiscard]] const_iterator begin() const noexcept { + return cbegin(); + } + + /*! @copydoc begin */ + [[nodiscard]] iterator begin() noexcept { + return {std::get(payload).begin()...}; + } + + /** + * @brief Returns an iterator to the end. + * @return An iterator to the element following the last row of the table. + */ + [[nodiscard]] const_iterator cend() const noexcept { + return {std::get(payload).cend()...}; + } + + /*! @copydoc cend */ + [[nodiscard]] const_iterator end() const noexcept { + return cend(); + } + + /*! @copydoc end */ + [[nodiscard]] iterator end() noexcept { + return {std::get(payload).end()...}; + } + + /** + * @brief Returns a reverse iterator to the beginning. + * + * If the table is empty, the returned iterator will be equal to `rend()`. + * + * @return An iterator to the first row of the reversed table. + */ + [[nodiscard]] const_reverse_iterator crbegin() const noexcept { + return {std::get(payload).crbegin()...}; + } + + /*! @copydoc crbegin */ + [[nodiscard]] const_reverse_iterator rbegin() const noexcept { + return crbegin(); + } + + /*! @copydoc rbegin */ + [[nodiscard]] reverse_iterator rbegin() noexcept { + return {std::get(payload).rbegin()...}; + } + + /** + * @brief Returns a reverse iterator to the end. + * @return An iterator to the element following the last row of the reversed + * table. + */ + [[nodiscard]] const_reverse_iterator crend() const noexcept { + return {std::get(payload).crend()...}; + } + + /*! @copydoc crend */ + [[nodiscard]] const_reverse_iterator rend() const noexcept { + return crend(); + } + + /*! @copydoc rend */ + [[nodiscard]] reverse_iterator rend() noexcept { + return {std::get(payload).rend()...}; + } + + /** + * @brief Appends a row to the end of a table. + * @tparam Args Types of arguments to use to construct the row data. + * @param args Parameters to use to construct the row data. + * @return A reference to the newly created row data. + */ + template + std::tuple emplace(Args &&...args) { + if constexpr(sizeof...(Args) == 0u) { + return std::forward_as_tuple(std::get(payload).emplace_back()...); + } else { + return std::forward_as_tuple(std::get(payload).emplace_back(std::forward(args))...); + } + } + + /** + * @brief Removes a row from a table. + * @param pos An iterator to the row to remove. + * @return An iterator following the removed row. + */ + iterator erase(const_iterator pos) { + const auto diff = pos - begin(); + return {std::get(payload).erase(std::get(payload).begin() + diff)...}; + } + + /** + * @brief Removes a row from a table. + * @param pos Index of the row to remove. + */ + void erase(const size_type pos) { + ENTT_ASSERT(pos < size(), "Index out of bounds"); + erase(begin() + static_cast(pos)); + } + + /** + * @brief Returns the row data at specified location. + * @param pos The row for which to return the data. + * @return The row data at specified location. + */ + [[nodiscard]] std::tuple operator[](const size_type pos) const { + ENTT_ASSERT(pos < size(), "Index out of bounds"); + return std::forward_as_tuple(std::get(payload)[pos]...); + } + + /*! @copydoc operator[] */ + [[nodiscard]] std::tuple operator[](const size_type pos) { + ENTT_ASSERT(pos < size(), "Index out of bounds"); + return std::forward_as_tuple(std::get(payload)[pos]...); + } + + /*! @brief Clears a table. */ + void clear() { + (std::get(payload).clear(), ...); + } + +private: + container_type payload; +}; + +} // namespace entt + +/*! @cond TURN_OFF_DOXYGEN */ +namespace std { + +template +struct uses_allocator, Allocator> + : std::bool_constant<(std::uses_allocator_v && ...)> {}; + +} // namespace std +/*! @endcond */ + +#endif -- cgit