sparse_set.h

#pragma once
 
#include "pixelbullet/core/assert.h"
 
#include <concepts>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <utility>
#include <vector>
 
namespace pixelbullet
{
template <typename T, std::unsigned_integral Index = std::uint32_t>
class SparseSet
{
public:
    using value_type = T;
    using index_type = Index;
 
    struct Entry
    {
        template <typename... Args>
        Entry(const Index entry_id, Args&&... args)
            : id(entry_id)
            , value(std::forward<Args>(args)...)
        {
        }
 
        Index id;
        T value;
    };
 
    [[nodiscard]] bool contains(const Index id) const
    {
        assert_valid_id(id);
 
        const std::size_t sparse_index = static_cast<std::size_t>(id);
        if (sparse_index >= sparse_.size())
        {
            return false;
        }
 
        const Index dense_index = sparse_[sparse_index];
        const std::size_t dense_position = static_cast<std::size_t>(dense_index);
        return dense_index != k_invalid_index && dense_position < dense_.size() && dense_[dense_position].id == id;
    }
 
    T& insert_or_assign(const Index id, T value)
    {
        ensure_sparse_size(id);
 
        if (contains(id))
        {
            T& existing = dense_[static_cast<std::size_t>(sparse_[static_cast<std::size_t>(id)])].value;
            existing = std::move(value);
            return existing;
        }
 
        assert_dense_index_available();
        sparse_[static_cast<std::size_t>(id)] = static_cast<Index>(dense_.size());
        dense_.emplace_back(id, std::move(value));
        return dense_.back().value;
    }
 
    template <typename... Args>
    T& emplace(const Index id, Args&&... args)
    {
        ensure_sparse_size(id);
 
        if (contains(id))
        {
            T& existing = dense_[static_cast<std::size_t>(sparse_[static_cast<std::size_t>(id)])].value;
            existing = T(std::forward<Args>(args)...);
            return existing;
        }
 
        assert_dense_index_available();
        sparse_[static_cast<std::size_t>(id)] = static_cast<Index>(dense_.size());
        dense_.emplace_back(id, std::forward<Args>(args)...);
        return dense_.back().value;
    }
 
    bool erase(const Index id)
    {
        if (!contains(id))
        {
            return false;
        }
 
        const Index dense_index = sparse_[static_cast<std::size_t>(id)];
        const auto last_index = static_cast<Index>(dense_.size() - 1);
 
        if (dense_index != last_index)
        {
            std::swap(dense_[static_cast<std::size_t>(dense_index)], dense_[static_cast<std::size_t>(last_index)]);
            sparse_[static_cast<std::size_t>(dense_[static_cast<std::size_t>(dense_index)].id)] = dense_index;
        }
 
        dense_.pop_back();
        sparse_[static_cast<std::size_t>(id)] = k_invalid_index;
        return true;
    }
 
    T& at(const Index id)
    {
        ASSERT(contains(id), "SparseSet id {} is not present", static_cast<std::size_t>(id));
        return dense_[static_cast<std::size_t>(sparse_[static_cast<std::size_t>(id)])].value;
    }
 
    const T& at(const Index id) const
    {
        ASSERT(contains(id), "SparseSet id {} is not present", static_cast<std::size_t>(id));
        return dense_[static_cast<std::size_t>(sparse_[static_cast<std::size_t>(id)])].value;
    }
 
    [[nodiscard]] std::vector<T> values() const
    {
        std::vector<T> out;
        out.reserve(dense_.size());
        for (const auto& entry : dense_)
        {
            out.push_back(entry.value);
        }
        return out;
    }
 
    [[nodiscard]] std::vector<Index> ids() const
    {
        std::vector<Index> out;
        out.reserve(dense_.size());
        for (const auto& entry : dense_)
        {
            out.push_back(entry.id);
        }
        return out;
    }
 
    void clear()
    {
        sparse_.clear();
        dense_.clear();
    }
 
    [[nodiscard]] std::size_t size() const
    {
        return dense_.size();
    }
 
    [[nodiscard]] bool empty() const
    {
        return dense_.empty();
    }
 
    auto begin()
    {
        return dense_.begin();
    }
    auto end()
    {
        return dense_.end();
    }
    auto begin() const
    {
        return dense_.begin();
    }
    auto end() const
    {
        return dense_.end();
    }
 
private:
    static constexpr Index k_invalid_index = std::numeric_limits<Index>::max();
 
    static void assert_valid_id(const Index id)
    {
        ASSERT(id != k_invalid_index, "SparseSet id {} is reserved as the invalid sentinel", static_cast<std::size_t>(id));
    }
 
    void ensure_sparse_size(const Index id)
    {
        assert_valid_id(id);
 
        const std::size_t sparse_index = static_cast<std::size_t>(id);
        if (sparse_index >= sparse_.size())
        {
            sparse_.resize(sparse_index + 1, k_invalid_index);
        }
    }
 
    void assert_dense_index_available() const
    {
        ASSERT(dense_.size() < static_cast<std::size_t>(k_invalid_index), "SparseSet dense index overflow");
    }
 
    std::vector<Index> sparse_;
    std::vector<Entry> dense_;
};
} // namespace pixelbullet