SparseSet.hpp

#pragma once
 
#include <cassert>
#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 < m_Sparse.size() && m_Sparse[id] != INVALID_INDEX && m_Sparse[id] < m_Dense.size() &&
                   m_Dense[m_Sparse[id]].id == id;
        }
 
        void Insert(Index id, const T& value)
        {
            if (id >= m_Sparse.size())
            {
                m_Sparse.resize(id + 1, INVALID_INDEX);
            }
 
            if (Has(id))
            {
                m_Dense[m_Sparse[id]].data = value;
            }
            else
            {
                m_Sparse[id] = static_cast<Index>(m_Dense.size());
                m_Dense.push_back({ id, value });
            }
        }
 
        void Erase(Index id)
        {
            if (!Has(id))
            {
                return;
            }
 
            Index denseIdx = m_Sparse[id];
            auto lastIdx = static_cast<Index>(m_Dense.size() - 1);
 
            if (denseIdx != lastIdx)
            {
                std::swap(m_Dense[denseIdx], m_Dense[lastIdx]);
                m_Sparse[m_Dense[denseIdx].id] = denseIdx;
            }
 
            m_Dense.pop_back();
            m_Sparse[id] = INVALID_INDEX;
        }
 
        T& Get(Index id)
        {
            assert(Has(id));
            return m_Dense[m_Sparse[id]].data;
        }
 
        const T& Get(Index id) const
        {
            assert(Has(id));
            return m_Dense[m_Sparse[id]].data;
        }
 
        std::vector<T> Values() const
        {
            std::vector<T> out;
            for (const auto& pair : m_Dense)
            {
                out.push_back(pair.data);
            }
            return out;
        }
 
        std::vector<Index> Keys() const
        {
            std::vector<Index> out;
            for (const auto& pair : m_Dense)
            {
                out.push_back(pair.id);
            }
            return out;
        }
 
        void Clear()
        {
            m_Sparse.clear();
            m_Dense.clear();
        }
 
        [[nodiscard]] size_t Size() const
        {
            return m_Dense.size();
        }
        [[nodiscard]] bool Empty() const
        {
            return m_Dense.empty();
        }
 
        struct Entry
        {
            Index id;
            T data;
        };
 
        auto begin()
        {
            return m_Dense.begin();
        }
        auto end()
        {
            return m_Dense.end();
        }
        auto begin() const
        {
            return m_Dense.begin();
        }
        auto end() const
        {
            return m_Dense.end();
        }
 
    private:
        std::vector<Index> m_Sparse;
        std::vector<Entry> m_Dense;
    };
} // namespace PixelBullet