sparse_set.hpp

#ifndef ENTT_ENTITY_SPARSE_SET_HPP
#define ENTT_ENTITY_SPARSE_SET_HPP
 
#include <cstddef>
#include <iterator>
#include <memory>
#include <type_traits>
#include <utility>
#include <vector>
#include "../config/config.h"
#include "../core/algorithm.hpp"
#include "../core/any.hpp"
#include "../core/memory.hpp"
#include "../core/type_info.hpp"
#include "entity.hpp"
#include "fwd.hpp"
 
namespace entt {
 
namespace internal {
 
template<typename Container>
struct sparse_set_iterator final {
    using value_type = typename Container::value_type;
    using pointer = typename Container::const_pointer;
    using reference = typename Container::const_reference;
    using difference_type = typename Container::difference_type;
    using iterator_category = std::random_access_iterator_tag;
 
    constexpr sparse_set_iterator() noexcept
        : packed{},
          offset{} {}
 
    constexpr sparse_set_iterator(const Container &ref, const difference_type idx) noexcept
        : packed{std::addressof(ref)},
          offset{idx} {}
 
    constexpr sparse_set_iterator &operator++() noexcept {
        return --offset, *this;
    }
 
    constexpr sparse_set_iterator operator++(int) noexcept {
        sparse_set_iterator orig = *this;
        return ++(*this), orig;
    }
 
    constexpr sparse_set_iterator &operator--() noexcept {
        return ++offset, *this;
    }
 
    constexpr sparse_set_iterator operator--(int) noexcept {
        sparse_set_iterator orig = *this;
        return operator--(), orig;
    }
 
    constexpr sparse_set_iterator &operator+=(const difference_type value) noexcept {
        offset -= value;
        return *this;
    }
 
    constexpr sparse_set_iterator operator+(const difference_type value) const noexcept {
        sparse_set_iterator copy = *this;
        return (copy += value);
    }
 
    constexpr sparse_set_iterator &operator-=(const difference_type value) noexcept {
        return (*this += -value);
    }
 
    constexpr sparse_set_iterator operator-(const difference_type value) const noexcept {
        return (*this + -value);
    }
 
    [[nodiscard]] constexpr reference operator[](const difference_type value) const noexcept {
        return packed->data()[index() - value];
    }
 
    [[nodiscard]] constexpr pointer operator->() const noexcept {
        return packed->data() + index();
    }
 
    [[nodiscard]] constexpr reference operator*() const noexcept {
        return *operator->();
    }
 
    [[nodiscard]] constexpr pointer data() const noexcept {
        return packed ? packed->data() : nullptr;
    }
 
    [[nodiscard]] constexpr difference_type index() const noexcept {
        return offset - 1;
    }
 
private:
    const Container *packed;
    difference_type offset;
};
 
template<typename Container>
[[nodiscard]] constexpr std::ptrdiff_t operator-(const sparse_set_iterator<Container> &lhs, const sparse_set_iterator<Container> &rhs) noexcept {
    return rhs.index() - lhs.index();
}
 
template<typename Container>
[[nodiscard]] constexpr bool operator==(const sparse_set_iterator<Container> &lhs, const sparse_set_iterator<Container> &rhs) noexcept {
    return lhs.index() == rhs.index();
}
 
template<typename Container>
[[nodiscard]] constexpr bool operator!=(const sparse_set_iterator<Container> &lhs, const sparse_set_iterator<Container> &rhs) noexcept {
    return !(lhs == rhs);
}
 
template<typename Container>
[[nodiscard]] constexpr bool operator<(const sparse_set_iterator<Container> &lhs, const sparse_set_iterator<Container> &rhs) noexcept {
    return lhs.index() > rhs.index();
}
 
template<typename Container>
[[nodiscard]] constexpr bool operator>(const sparse_set_iterator<Container> &lhs, const sparse_set_iterator<Container> &rhs) noexcept {
    return rhs < lhs;
}
 
template<typename Container>
[[nodiscard]] constexpr bool operator<=(const sparse_set_iterator<Container> &lhs, const sparse_set_iterator<Container> &rhs) noexcept {
    return !(lhs > rhs);
}
 
template<typename Container>
[[nodiscard]] constexpr bool operator>=(const sparse_set_iterator<Container> &lhs, const sparse_set_iterator<Container> &rhs) noexcept {
    return !(lhs < rhs);
}
 
} // namespace internal
template<typename Entity, typename Allocator>
class basic_sparse_set {
    using alloc_traits = std::allocator_traits<Allocator>;
    static_assert(std::is_same_v<typename alloc_traits::value_type, Entity>, "Invalid value type");
    using sparse_container_type = std::vector<typename alloc_traits::pointer, typename alloc_traits::template rebind_alloc<typename alloc_traits::pointer>>;
    using packed_container_type = std::vector<Entity, Allocator>;
    using underlying_type = typename entt_traits<Entity>::entity_type;
 
    [[nodiscard]] auto sparse_ptr(const Entity entt) const {
        const auto pos = static_cast<size_type>(traits_type::to_entity(entt));
        const auto page = pos / traits_type::page_size;
        return (page < sparse.size() && sparse[page]) ? (sparse[page] + fast_mod(pos, traits_type::page_size)) : nullptr;
    }
 
    [[nodiscard]] auto &sparse_ref(const Entity entt) const {
        ENTT_ASSERT(sparse_ptr(entt), "Invalid element");
        const auto pos = static_cast<size_type>(traits_type::to_entity(entt));
        return sparse[pos / traits_type::page_size][fast_mod(pos, traits_type::page_size)];
    }
 
    [[nodiscard]] auto to_iterator(const Entity entt) const {
        return --(end() - index(entt));
    }
 
    [[nodiscard]] auto &assure_at_least(const Entity entt) {
        const auto pos = static_cast<size_type>(traits_type::to_entity(entt));
        const auto page = pos / traits_type::page_size;
 
        if(!(page < sparse.size())) {
            sparse.resize(page + 1u, nullptr);
        }
 
        if(!sparse[page]) {
            constexpr entity_type init = null;
            auto page_allocator{packed.get_allocator()};
            sparse[page] = alloc_traits::allocate(page_allocator, traits_type::page_size);
            std::uninitialized_fill(sparse[page], sparse[page] + traits_type::page_size, init);
        }
 
        return sparse[page][fast_mod(pos, traits_type::page_size)];
    }
 
    void release_sparse_pages() {
        auto page_allocator{packed.get_allocator()};
 
        for(auto &&page: sparse) {
            if(page != nullptr) {
                std::destroy(page, page + traits_type::page_size);
                alloc_traits::deallocate(page_allocator, page, traits_type::page_size);
                page = nullptr;
            }
        }
    }
 
    void swap_at(const std::size_t from, const std::size_t to) {
        auto &lhs = packed[from];
        auto &rhs = packed[to];
 
        sparse_ref(lhs) = traits_type::combine(static_cast<typename traits_type::entity_type>(to), traits_type::to_integral(lhs));
        sparse_ref(rhs) = traits_type::combine(static_cast<typename traits_type::entity_type>(from), traits_type::to_integral(rhs));
 
        std::swap(lhs, rhs);
    }
 
    underlying_type policy_to_head() {
        return traits_type::entity_mask * (mode != deletion_policy::swap_only);
    }
 
private:
    virtual const void *get_at(const std::size_t) const {
        return nullptr;
    }
 
    virtual void swap_or_move([[maybe_unused]] const std::size_t lhs, [[maybe_unused]] const std::size_t rhs) {
        ENTT_ASSERT((mode != deletion_policy::swap_only) || (((lhs < free_list()) + (rhs < free_list())) != 1u), "Cross swapping is not supported");
    }
 
protected:
    using basic_iterator = internal::sparse_set_iterator<packed_container_type>;
 
    void swap_only(const basic_iterator it) {
        ENTT_ASSERT(mode == deletion_policy::swap_only, "Deletion policy mismatch");
        const auto pos = static_cast<underlying_type>(index(*it));
        bump(traits_type::next(*it));
        swap_at(pos, static_cast<size_type>(head -= (pos < head)));
    }
 
    void swap_and_pop(const basic_iterator it) {
        ENTT_ASSERT(mode == deletion_policy::swap_and_pop, "Deletion policy mismatch");
        auto &self = sparse_ref(*it);
        const auto entt = traits_type::to_entity(self);
        sparse_ref(packed.back()) = traits_type::combine(entt, traits_type::to_integral(packed.back()));
        packed[static_cast<size_type>(entt)] = packed.back();
        // unnecessary but it helps to detect nasty bugs
        ENTT_ASSERT((packed.back() = null, true), "");
        // lazy self-assignment guard
        self = null;
        packed.pop_back();
    }
 
    void in_place_pop(const basic_iterator it) {
        ENTT_ASSERT(mode == deletion_policy::in_place, "Deletion policy mismatch");
        const auto entt = traits_type::to_entity(std::exchange(sparse_ref(*it), null));
        packed[static_cast<size_type>(entt)] = traits_type::combine(std::exchange(head, entt), tombstone);
    }
 
protected:
    virtual void pop(basic_iterator first, basic_iterator last) {
        switch(mode) {
        case deletion_policy::swap_and_pop:
            for(; first != last; ++first) {
                swap_and_pop(first);
            }
            break;
        case deletion_policy::in_place:
            for(; first != last; ++first) {
                in_place_pop(first);
            }
            break;
        case deletion_policy::swap_only:
            for(; first != last; ++first) {
                swap_only(first);
            }
            break;
        }
    }
 
    virtual void pop_all() {
        switch(mode) {
        case deletion_policy::in_place:
            if(head != traits_type::to_entity(null)) {
                for(auto first = begin(); !(first.index() < 0); ++first) {
                    if(*first != tombstone) {
                        sparse_ref(*first) = null;
                    }
                }
                break;
            }
            [[fallthrough]];
        case deletion_policy::swap_only:
        case deletion_policy::swap_and_pop:
            for(auto first = begin(); !(first.index() < 0); ++first) {
                sparse_ref(*first) = null;
            }
            break;
        }
 
        head = policy_to_head();
        packed.clear();
    }
 
    virtual basic_iterator try_emplace(const Entity entt, const bool force_back, const void * = nullptr) {
        auto &elem = assure_at_least(entt);
        auto pos = size();
 
        switch(mode) {
        case deletion_policy::in_place:
            if(head != traits_type::to_entity(null) && !force_back) {
                pos = static_cast<size_type>(head);
                ENTT_ASSERT(elem == null, "Slot not available");
                elem = traits_type::combine(head, traits_type::to_integral(entt));
                head = traits_type::to_entity(std::exchange(packed[pos], entt));
                break;
            }
            [[fallthrough]];
        case deletion_policy::swap_and_pop:
            packed.push_back(entt);
            ENTT_ASSERT(elem == null, "Slot not available");
            elem = traits_type::combine(static_cast<typename traits_type::entity_type>(packed.size() - 1u), traits_type::to_integral(entt));
            break;
        case deletion_policy::swap_only:
            if(elem == null) {
                packed.push_back(entt);
                elem = traits_type::combine(static_cast<typename traits_type::entity_type>(packed.size() - 1u), traits_type::to_integral(entt));
            } else {
                ENTT_ASSERT(!(traits_type::to_entity(elem) < head), "Slot not available");
                bump(entt);
            }
 
            if(force_back) {
                pos = static_cast<size_type>(head++);
                swap_at(static_cast<size_type>(traits_type::to_entity(elem)), pos);
            }
 
            break;
        }
 
        return --(end() - pos);
    }
 
public:
    using traits_type = entt_traits<Entity>;
    using entity_type = typename traits_type::value_type;
    using version_type = typename traits_type::version_type;
    using size_type = std::size_t;
    using allocator_type = Allocator;
    using pointer = typename packed_container_type::const_pointer;
    using iterator = basic_iterator;
    using const_iterator = iterator;
    using reverse_iterator = std::reverse_iterator<iterator>;
    using const_reverse_iterator = std::reverse_iterator<const_iterator>;
 
    basic_sparse_set()
        : basic_sparse_set{type_id<void>()} {}
 
    explicit basic_sparse_set(const allocator_type &allocator)
        : basic_sparse_set{type_id<void>(), deletion_policy::swap_and_pop, allocator} {}
 
    explicit basic_sparse_set(deletion_policy pol, const allocator_type &allocator = {})
        : basic_sparse_set{type_id<void>(), pol, allocator} {}
 
    explicit basic_sparse_set(const type_info &elem, deletion_policy pol = deletion_policy::swap_and_pop, const allocator_type &allocator = {})
        : sparse{allocator},
          packed{allocator},
          info{&elem},
          mode{pol},
          head{policy_to_head()} {}
 
    basic_sparse_set(basic_sparse_set &&other) noexcept
        : sparse{std::move(other.sparse)},
          packed{std::move(other.packed)},
          info{other.info},
          mode{other.mode},
          head{std::exchange(other.head, policy_to_head())} {}
 
    basic_sparse_set(basic_sparse_set &&other, const allocator_type &allocator) noexcept
        : sparse{std::move(other.sparse), allocator},
          packed{std::move(other.packed), allocator},
          info{other.info},
          mode{other.mode},
          head{std::exchange(other.head, policy_to_head())} {
        ENTT_ASSERT(alloc_traits::is_always_equal::value || packed.get_allocator() == other.packed.get_allocator(), "Copying a sparse set is not allowed");
    }
 
    virtual ~basic_sparse_set() {
        release_sparse_pages();
    }
 
    basic_sparse_set &operator=(basic_sparse_set &&other) noexcept {
        ENTT_ASSERT(alloc_traits::is_always_equal::value || packed.get_allocator() == other.packed.get_allocator(), "Copying a sparse set is not allowed");
 
        release_sparse_pages();
        sparse = std::move(other.sparse);
        packed = std::move(other.packed);
        info = other.info;
        mode = other.mode;
        head = std::exchange(other.head, policy_to_head());
        return *this;
    }
 
    void swap(basic_sparse_set &other) {
        using std::swap;
        swap(sparse, other.sparse);
        swap(packed, other.packed);
        swap(info, other.info);
        swap(mode, other.mode);
        swap(head, other.head);
    }
 
    [[nodiscard]] constexpr allocator_type get_allocator() const noexcept {
        return packed.get_allocator();
    }
 
    [[nodiscard]] deletion_policy policy() const noexcept {
        return mode;
    }
 
    [[nodiscard]] size_type free_list() const noexcept {
        return static_cast<size_type>(head);
    }
 
    void free_list(const size_type len) noexcept {
        ENTT_ASSERT((mode == deletion_policy::swap_only) && !(len > packed.size()), "Invalid value");
        head = static_cast<underlying_type>(len);
    }
 
    virtual void reserve(const size_type cap) {
        packed.reserve(cap);
    }
 
    [[nodiscard]] virtual size_type capacity() const noexcept {
        return packed.capacity();
    }
 
    virtual void shrink_to_fit() {
        packed.shrink_to_fit();
    }
 
    [[nodiscard]] size_type extent() const noexcept {
        return sparse.size() * traits_type::page_size;
    }
 
    [[nodiscard]] size_type size() const noexcept {
        return packed.size();
    }
 
    [[nodiscard]] bool empty() const noexcept {
        return packed.empty();
    }
 
    [[nodiscard]] bool contiguous() const noexcept {
        return (mode != deletion_policy::in_place) || (head == traits_type::to_entity(null));
    }
 
    [[nodiscard]] pointer data() const noexcept {
        return packed.data();
    }
 
    [[nodiscard]] iterator begin() const noexcept {
        const auto pos = static_cast<typename iterator::difference_type>(packed.size());
        return iterator{packed, pos};
    }
 
    [[nodiscard]] const_iterator cbegin() const noexcept {
        return begin();
    }
 
    [[nodiscard]] iterator end() const noexcept {
        return iterator{packed, {}};
    }
 
    [[nodiscard]] const_iterator cend() const noexcept {
        return end();
    }
 
    [[nodiscard]] reverse_iterator rbegin() const noexcept {
        return std::make_reverse_iterator(end());
    }
 
    [[nodiscard]] const_reverse_iterator crbegin() const noexcept {
        return rbegin();
    }
 
    [[nodiscard]] reverse_iterator rend() const noexcept {
        return std::make_reverse_iterator(begin());
    }
 
    [[nodiscard]] const_reverse_iterator crend() const noexcept {
        return rend();
    }
 
    [[nodiscard]] iterator begin(int) const noexcept {
        return (mode == deletion_policy::swap_only) ? (end() - static_cast<typename iterator::difference_type>(head)) : begin();
    }
 
    [[nodiscard]] const_iterator cbegin(int) const noexcept {
        return begin(0);
    }
 
    [[nodiscard]] iterator end(int) const noexcept {
        return end();
    }
 
    [[nodiscard]] const_iterator cend(int) const noexcept {
        return end(0);
    }
 
    [[nodiscard]] reverse_iterator rbegin(int) const noexcept {
        return std::make_reverse_iterator(end(0));
    }
 
    [[nodiscard]] const_reverse_iterator crbegin(int) const noexcept {
        return rbegin(0);
    }
 
    [[nodiscard]] reverse_iterator rend(int) const noexcept {
        return std::make_reverse_iterator(begin(0));
    }
 
    [[nodiscard]] const_reverse_iterator crend(int) const noexcept {
        return rend(0);
    }
 
    [[nodiscard]] const_iterator find(const entity_type entt) const noexcept {
        return contains(entt) ? to_iterator(entt) : end();
    }
 
    [[nodiscard]] bool contains(const entity_type entt) const noexcept {
        const auto elem = sparse_ptr(entt);
        constexpr auto cap = traits_type::entity_mask;
        constexpr auto mask = traits_type::to_integral(null) & ~cap;
        // testing versions permits to avoid accessing the packed array
        return elem && (((mask & traits_type::to_integral(entt)) ^ traits_type::to_integral(*elem)) < cap);
    }
 
    [[nodiscard]] version_type current(const entity_type entt) const noexcept {
        const auto elem = sparse_ptr(entt);
        constexpr auto fallback = traits_type::to_version(tombstone);
        return elem ? traits_type::to_version(*elem) : fallback;
    }
 
    [[nodiscard]] size_type index(const entity_type entt) const noexcept {
        ENTT_ASSERT(contains(entt), "Set does not contain entity");
        return static_cast<size_type>(traits_type::to_entity(sparse_ref(entt)));
    }
 
    [[deprecated("use .begin()[pos] instead")]] [[nodiscard]] entity_type at(const size_type pos) const noexcept {
        return pos < packed.size() ? packed[pos] : null;
    }
 
    [[nodiscard]] entity_type operator[](const size_type pos) const noexcept {
        ENTT_ASSERT(pos < packed.size(), "Position is out of bounds");
        return packed[pos];
    }
 
    [[nodiscard]] const void *value(const entity_type entt) const noexcept {
        return get_at(index(entt));
    }
 
    [[nodiscard]] void *value(const entity_type entt) noexcept {
        return const_cast<void *>(std::as_const(*this).value(entt));
    }
 
    iterator push(const entity_type entt, const void *elem = nullptr) {
        return try_emplace(entt, (mode == deletion_policy::swap_only), elem);
    }
 
    template<typename It>
    iterator push(It first, It last) {
        for(auto it = first; it != last; ++it) {
            try_emplace(*it, true);
        }
 
        return first == last ? end() : find(*first);
    }
 
    version_type bump(const entity_type entt) {
        auto &entity = sparse_ref(entt);
        ENTT_ASSERT(entt != tombstone && entity != null, "Cannot set the required version");
        entity = traits_type::combine(traits_type::to_integral(entity), traits_type::to_integral(entt));
        packed[static_cast<size_type>(traits_type::to_entity(entity))] = entt;
        return traits_type::to_version(entt);
    }
 
    void erase(const entity_type entt) {
        const auto it = to_iterator(entt);
        pop(it, it + 1u);
    }
 
    template<typename It>
    void erase(It first, It last) {
        if constexpr(std::is_same_v<It, basic_iterator>) {
            pop(first, last);
        } else {
            for(; first != last; ++first) {
                erase(*first);
            }
        }
    }
 
    bool remove(const entity_type entt) {
        return contains(entt) && (erase(entt), true);
    }
 
    template<typename It>
    size_type remove(It first, It last) {
        size_type count{};
 
        if constexpr(std::is_same_v<It, basic_iterator>) {
            while(first != last) {
                while(first != last && !contains(*first)) {
                    ++first;
                }
 
                const auto it = first;
 
                while(first != last && contains(*first)) {
                    ++first;
                }
 
                count += std::distance(it, first);
                erase(it, first);
            }
        } else {
            for(; first != last; ++first) {
                count += remove(*first);
            }
        }
 
        return count;
    }
 
    void compact() {
        if(mode == deletion_policy::in_place) {
            size_type from = packed.size();
            for(; from && packed[from - 1u] == tombstone; --from) {}
            underlying_type pos = std::exchange(head, traits_type::entity_mask);
 
            while(pos != traits_type::to_entity(null)) {
                if(const auto to = static_cast<size_type>(std::exchange(pos, traits_type::to_entity(packed[pos]))); to < from) {
                    --from;
                    swap_or_move(from, to);
 
                    packed[to] = packed[from];
                    const auto entity = static_cast<typename traits_type::entity_type>(to);
                    sparse_ref(packed[to]) = traits_type::combine(entity, traits_type::to_integral(packed[to]));
 
                    for(; from && packed[from - 1u] == tombstone; --from) {}
                }
            }
 
            packed.erase(packed.begin() + from, packed.end());
        }
    }
 
    void swap_elements(const entity_type lhs, const entity_type rhs) {
        const auto from = index(lhs);
        const auto to = index(rhs);
 
        // basic no-leak guarantee if swapping throws
        swap_or_move(from, to);
        swap_at(from, to);
    }
 
    template<typename Compare, typename Sort = std_sort, typename... Args>
    void sort_n(const size_type length, Compare compare, Sort algo = Sort{}, Args &&...args) {
        ENTT_ASSERT((mode != deletion_policy::in_place) || (head == traits_type::to_entity(null)), "Sorting with tombstones not allowed");
        ENTT_ASSERT(!(length > packed.size()), "Length exceeds the number of elements");
 
        algo(packed.rend() - length, packed.rend(), std::move(compare), std::forward<Args>(args)...);
 
        for(size_type pos{}; pos < length; ++pos) {
            auto curr = pos;
            auto next = index(packed[curr]);
 
            while(curr != next) {
                const auto idx = index(packed[next]);
                const auto entt = packed[curr];
 
                swap_or_move(next, idx);
                const auto entity = static_cast<typename traits_type::entity_type>(curr);
                sparse_ref(entt) = traits_type::combine(entity, traits_type::to_integral(packed[curr]));
                curr = std::exchange(next, idx);
            }
        }
    }
 
    template<typename Compare, typename Sort = std_sort, typename... Args>
    void sort(Compare compare, Sort algo = Sort{}, Args &&...args) {
        sort_n(static_cast<size_type>(end(0) - begin(0)), std::move(compare), std::move(algo), std::forward<Args>(args)...);
    }
 
    template<typename It>
    void sort_as(It first, It last) {
        ENTT_ASSERT((mode != deletion_policy::in_place) || (head == traits_type::to_entity(null)), "Sorting with tombstones not allowed");
 
        for(auto it = begin(0); it.index() && first != last; ++first) {
            if(const auto curr = *first; contains(curr)) {
                if(const auto entt = *it; entt != curr) {
                    // basic no-leak guarantee (with invalid state) if swapping throws
                    swap_elements(entt, curr);
                }
 
                ++it;
            }
        }
    }
 
    [[deprecated("use iterator based sort_as instead")]] void sort_as(const basic_sparse_set &other) {
        sort_as(other.begin(), other.end());
    }
 
    void clear() {
        pop_all();
        // sanity check to avoid subtle issues due to storage classes
        ENTT_ASSERT((compact(), size()) == 0u, "Non-empty set");
        head = policy_to_head();
        packed.clear();
    }
 
    const type_info &type() const noexcept {
        return *info;
    }
 
    virtual void bind(any) noexcept {}
 
private:
    sparse_container_type sparse;
    packed_container_type packed;
    const type_info *info;
    deletion_policy mode;
    underlying_type head;
};
 
} // namespace entt
 
#endif