#pragma once

#if !defined(MIJIN_CONTAINER_CACHED_ARRAY_HPP_INCLUDED)
#define MIJIN_CONTAINER_CACHED_ARRAY_HPP_INCLUDED 1

#include <algorithm>
#include <array>
#include <cstddef>
#include <limits>
#include <optional>
#include <vector>
#include "../debug/assert.hpp"

namespace mijin
{

//
// public defines
//

//
// public constants
//

//
// public types
//

template<typename T, std::size_t cacheSize = 32>
class CachedArray
{
public:
    using element_type = T;
    using value_type = std::remove_cv_t<T>;
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;
    using pointer = T*;
    using const_pointer = const T*;
    using reference = T&;
    using const_reference = const T&;
    using iterator = T*;
    using const_iterator = const T*;

    static constexpr std::size_t INVALID_INDEX = std::numeric_limits<size_type>::max();
private:
    struct CacheEntry
    {
        size_type index = INVALID_INDEX;
        std::size_t useIndex = 0;
        std::optional<T> value;
    };
    mutable std::array<CacheEntry, cacheSize> cache_;
    std::vector<std::optional<T>> backbuffer_;
    std::size_t nextUseIndex_ = 1;
public:
    [[nodiscard]] reference at(size_type index);
    [[nodiscard]] const_reference at(size_type index) const;
    [[nodiscard]] size_type size() const { return backbuffer_.size(); }
    void resize(size_type newSize);
    void reserve(size_type elements);

    // TODO: make iterable (not that easy if we move from the backbuffer!)
    // [[nodiscard]] iterator begin() { return &backbuffer_[0]; }
    // [[nodiscard]] const_iterator begin() const { return &backbuffer_[0]; }
    // [[nodiscard]] const_iterator cbegin() const { return &backbuffer_[0]; }
    // [[nodiscard]] iterator end() { return begin() + size(); }
    // [[nodiscard]] const_iterator end() const { return begin() + size(); }
    // [[nodiscard]] const_iterator cend() const { return begin() + size(); }

    [[nodiscard]] reference operator[](size_type index) { return at(index); }
    [[nodiscard]] const_reference operator[](size_type index) const { return at(index); }
private:
    // TODO: use deducing this once it is available
    template<typename TSelf>
    static auto atImpl(TSelf&& self, std::size_t index);
};

//
// public functions
//

template<typename T, std::size_t cacheSize>
auto CachedArray<T, cacheSize>::at(std::size_t index) -> reference
{
    return atImpl(*this, index);
}

template<typename T, std::size_t cacheSize>
auto CachedArray<T, cacheSize>::at(std::size_t index) const -> const_reference
{
    return atImpl(*this, index);
}

template<typename T, std::size_t cacheSize>
void CachedArray<T, cacheSize>::resize(size_type newSize)
{
    if (newSize < size())
    {
        // invalidate any cache entries that shouldn't exist anymore
        for (CacheEntry& entry : cache_)
        {
            if (entry.index < newSize)
            {
                entry.value = std::nullopt;
                entry.useIndex = 0;
            }
        }
    }
    backbuffer_.resize(newSize);
}

template<typename T, std::size_t cacheSize>
template<typename TSelf>
auto CachedArray<T, cacheSize>::atImpl(TSelf&& self, std::size_t index)
{
    MIJIN_ASSERT(index < size(), "CachedArray::at(): Attempting to access index out of range.");
    // first try the cache
    for (CacheEntry& entry : self.cache_)
    {
        if (entry.index == index)
        {
            entry.useIndex = self.nextUseIndex_++;
            return *entry.value;
        }
    }

    // otherwise copy from backbuffer to cache
    auto itCache = std::min_element(self.cache_.begin(), self.cache_.end(), [](const CacheEntry& left, const CacheEntry& right) {
        return left.useIndex < right.useIndex;
    });
    if (itCache->index != INVALID_INDEX)
    {
        // move back to the backbuffer
        self.backbuffer_[itCache->index] = std::move(itCache->value);
    }
    itCache->index = index;
    itCache->value = std::move(self.backbuffer_.at(index));
    itCache->useIndex = self.nextUseIndex_++;
    return *itCache->value;
}

} // namespace mijin

#endif // !defined(MIJIN_CONTAINER_CACHED_ARRAY_HPP_INCLUDED)