sparse_set.h

#pragma once
 
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <vector>
 
namespace pixelbullet
{
template <typename T, typename Index = uint32_t>
class SparseSet
{
public:
    static constexpr Index INVALID_INDEX = std::numeric_limits<Index>::max();
 
    bool Has(Index id) const
    {
        return id < sparse_.size() && sparse_[id] != INVALID_INDEX && sparse_[id] < dense_.size() && dense_[sparse_[id]].id == id;
    }
 
    void Insert(Index id, const T& value)
    {
        if (id >= sparse_.size())
        {
            sparse_.resize(id + 1, INVALID_INDEX);
        }
 
        if (Has(id))
        {
            dense_[sparse_[id]].data = value;
        }
        else
        {
            sparse_[id] = static_cast<Index>(dense_.size());
            dense_.push_back({ id, value });
        }
    }
 
    void Erase(Index id)
    {
        if (!Has(id))
        {
            return;
        }
 
        Index denseIdx = sparse_[id];
        auto lastIdx = static_cast<Index>(dense_.size() - 1);
 
        if (denseIdx != lastIdx)
        {
            std::swap(dense_[denseIdx], dense_[lastIdx]);
            sparse_[dense_[denseIdx].id] = denseIdx;
        }
 
        dense_.pop_back();
        sparse_[id] = INVALID_INDEX;
    }
 
    T& Get(Index id)
    {
        assert(Has(id));
        return dense_[sparse_[id]].data;
    }
 
    const T& Get(Index id) const
    {
        assert(Has(id));
        return dense_[sparse_[id]].data;
    }
 
    std::vector<T> Values() const
    {
        std::vector<T> out;
        for (const auto& pair : dense_)
        {
            out.push_back(pair.data);
        }
        return out;
    }
 
    std::vector<Index> Keys() const
    {
        std::vector<Index> out;
        for (const auto& pair : dense_)
        {
            out.push_back(pair.id);
        }
        return out;
    }
 
    void Clear()
    {
        sparse_.clear();
        dense_.clear();
    }
 
    [[nodiscard]] size_t Size() const
    {
        return dense_.size();
    }
    [[nodiscard]] bool Empty() const
    {
        return dense_.empty();
    }
 
    struct Entry
    {
        Index id;
        T data;
    };
 
    auto begin()
    {
        return dense_.begin();
    }
    auto end()
    {
        return dense_.end();
    }
    auto begin() const
    {
        return dense_.begin();
    }
    auto end() const
    {
        return dense_.end();
    }
 
private:
    std::vector<Index> sparse_;
    std::vector<Entry> dense_;
};
} // namespace pixelbullet