#ifndef LIBCATBOY_ECS_SPARSE_SET_HPP
#define LIBCATBOY_ECS_SPARSE_SET_HPP

#include <span>
#include <type_traits>
#include <utility>
#include <vector>

namespace libcatboy {
namespace ecs {

class isparse_set {
public:
    isparse_set()          = default;
    virtual ~isparse_set() = default;

    isparse_set(isparse_set&&) noexcept            = default;
    isparse_set& operator=(isparse_set&&) noexcept = default;
    isparse_set(const isparse_set&)                = default;
    isparse_set& operator=(const isparse_set&)     = default;
public:
    virtual bool                   contains(std::size_t key) const noexcept = 0;
    virtual void                   erase(std::size_t key) noexcept          = 0;
    virtual std::size_t            size() const noexcept                    = 0;
    virtual std::size_t            sparse_size() const noexcept             = 0;
    virtual std::span<std::size_t> dense_map() noexcept               = 0;
};

template <typename T>
class sparse_set : public isparse_set {
public:
    using value_type      = T;
    using reference       = T&;
    using const_reference = const T&;
    using pointer         = T*;
    using const_pointer   = const T*;

    static constexpr std::size_t TOMBSTONE = -1;
public:
    void insert(std::size_t key, const T& value) { emplace(key, value); }
    void insert(std::size_t key, T&& value) { emplace(key, std::move(value)); }

    template <typename... Args, typename = std::enable_if_t<std::is_constructible_v<T, Args...>>>
    T& emplace(std::size_t key, Args&&... args) {
        std::size_t index = get_index(key);
        if (index == TOMBSTONE) {
            index = m_dense.size();
            set_index(key, index);
            m_reverseMap.push_back(key);
            return m_dense.emplace_back(std::forward<Args>(args)...);
        }
        m_reverseMap[index] = key;
        return *m_dense.emplace(m_dense.cbegin() + index, std::forward<Args>(args)...);
    }
public:
    T&       operator[](std::size_t key) { return m_dense[get_index(key)]; }
    const T& operator[](std::size_t key) const { return m_dense[get_index(key)]; }

    T&       at(std::size_t key) { return m_dense.at(get_index(key)); }
    const T& at(std::size_t key) const { return m_dense.at(get_index(key)); }

    bool contains(std::size_t key) const noexcept override { return get_index(key) != TOMBSTONE; }
public:
    void erase(std::size_t key) noexcept override {
        std::size_t index = get_index(key);
        if (index == TOMBSTONE) return;
        if (index != m_dense.size() - 1) {
            set_index(m_reverseMap.back(), index);
            std::swap(m_dense[index], m_dense.back());
            std::swap(m_reverseMap[index], m_reverseMap.back());
        }

        m_dense.pop_back();
        m_reverseMap.pop_back();
        set_index(key, TOMBSTONE);
    }
public:
    std::size_t size() const noexcept override { return m_dense.size(); }

    std::size_t sparse_size() const noexcept override { return m_map.size(); }

    std::span<std::size_t> dense_map() noexcept override {
        return m_reverseMap;
    }
private:
    void set_index(std::size_t key, std::size_t dense) {
        if (key >= m_map.size()) m_map.resize(key + 1, TOMBSTONE);
        m_map[key] = dense;
    }

    std::size_t get_index(std::size_t key) const { return key >= m_map.size() ? TOMBSTONE : m_map[key]; }
private:
    std::vector<std::size_t> m_map;
    std::vector<std::size_t> m_reverseMap;
    std::vector<T>           m_dense;
};

} // namespace ecs
} // namespace libcatboy

#endif // LIBCATBOY_ECS_SPARSE_SET_HPP