generational.hpp

#pragma once
#include <vector>
#include <algorithm>
#include <optional>
#include <stdexcept>
#include <utility>

template <typename T>
class Arena;

template<typename T>
class Arena
{
	template<typename T>
	class Element;
	template<typename T>
	class Gendex;
	template<typename T>
	class Iterator;
	template<typename T>
	class ConstIterator;
public:
	typedef T value_type;
	typedef T* pointer;
	typedef const T* const_pointer;
	typedef T& reference;
	typedef const T& const_reference;
	typedef T&& rvalue_reference;
	typedef ptrdiff_t difference_type;
	typedef size_t size_type;
	typedef const size_t const_size_type;
	typedef Arena<T>::Gendex<T> gendex;
	typedef Arena<T>::Gendex<T>& gendex_reference;
	typedef const Arena<T>::Gendex<T>& gendex_const_reference;
	typedef Arena<T>::Gendex<T>&& gendex_rvalue_reference;
	typedef Arena<T>::Element<T> element;
	typedef Arena<T>::Iterator<T> iterator;
	typedef Arena<T>::ConstIterator<T> const_iterator;
	typedef std::reverse_iterator<iterator> reverse_iterator;
	typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

	template<typename T>
	class Element
	{
		friend class Arena<T>;
	private:
		size_type generation;
		value_type item;

	public:
		Element() noexcept :
			generation(0),
			item()
		{}
		Element(const_size_type generation, const_reference item)
			:
			generation(generation),
			item(item)
		{}
		Element(const_size_type generation, rvalue_reference item)
			:
			generation(generation),
			item(std::move(item))
		{}
		template <class... Args>
		Element(const size_type generation, Args... args)
			:
			generation(generation),
			item(std::forward(args))
		{}
		~Element() = default;
	};

	template<typename T>
	class Gendex
	{
		friend class Arena<T>;
	private:
		size_type index;
		size_type generation;

	public:
		Gendex(const_size_type index, const_size_type generation) noexcept
			:
			index(index),
			generation(generation)
		{}
		Gendex(gendex_const_reference other) noexcept
			:
			index(other.index),
			generation(other.generation)
		{}
		Gendex(gendex_rvalue_reference other) = delete;
		gendex_reference operator=(gendex_const_reference& other) noexcept
		{
			return Gendex(other.index, other.generation);
		}
		gendex_reference operator=(gendex_rvalue_reference other) noexcept
		{
			return Gendex(other.index, other.generation);
		}
		~Gendex() = default;

		bool operator==(gendex_const_reference other)
		{
			return 
				(other.generation == this->generation) &&
				(other.index == this->index);
		}
	};

	template<typename T>
	class ConstIterator
	{

	};

	template<typename T>
	class Iterator
	{

	};

private:
	std::vector<element> data;
	std::vector<size_type> empty_data_positions;
	size_type generation_id = 1;
	size_type item_count = 0;

public:
	Arena() = default;
	Arena(const Arena& other) = delete;
	Arena(Arena&& other) = delete;
	Arena& operator=(const Arena& other) = delete;
	Arena& operator=(Arena&& other) = delete;
	~Arena() = default;

	void reserve(const_size_type capacity)
	{
		this->data.reserve(capacity);
	}

	void reserve_unused_indices(const_size_type capacity)
	{
		this->empty_data_positions.reserve(capacity);
	}

	bool contains(gendex_const_reference gendex)
	{
		if (this->data.size() <= gendex.index)
		{
			return false;
		}
		return this->data[gendex.index].generation == gendex.generation;
	}

	bool try_remove(gendex_const_reference index)
	{
		if (index.index >= this->data.size())
		{
			if (auto& cur_element = this->data[index.index])
			{
				if (cur_element.generation == index.generation)
				{
					this->data[index.index] = element();
					this->empty_data_positions.push_back(index.index);
					this->item_count--;
					return true;
				}
			}
		}
		return false;
	}

	void remove(gendex_const_reference index)
	{
		if (index.index >= this->data.size())
		{
			if (auto& cur_element = this->data[index.index])
			{
				if (cur_element.generation == index.generation)
				{
					this->data[index.index] = element();
					this->empty_data_positions.push_back(index.index);
					this->item_count--;
					return;
				}
			}
		}
		throw std::out_of_range(__func__);
	}

	reference get(gendex_const_reference index)
	{
		if (index.index >= this->data.size())
		{
			if (auto& cur_element = this->data[index.index])
			{
				if (cur_element.generation == index.generation)
				{
					return cur_element.item;
				}
			}
		}
		throw std::out_of_range(__func__);
	}

	pointer get_ptr(gendex_const_reference index) noexcept
	{
		if (index.index < this->data.size())
		{
			if (auto& cur_element = this->data[index.index])
			{
				if (cur_element.generation == index.generation)
				{
					return &cur_element.value;
				}
			}
		}
		return nullptr;
	}

	std::optional<value_type> try_get(gendex_const_reference index) const noexcept
	{
		if (index.index < this->data.size())
		{
			if (auto& cur_element = this->data[index.index])
			{
				if (cur_element.generation == index.generation)
				{
					return cur_element.item;
				}
			}
		}
		return std::nullopt;
	}

	reference operator[](gendex_const_reference index)
	{
		if (index.index < this->data.size())
		{
			if (auto& cur_element = this->data[index.index])
			{
				if (cur_element.generation == index.generation)
				{
					return cur_element.item;
				}
			}
		}
		return this->data[index.index].item;
	}

	void push(const_reference item)
	{
		if (!this->empty_data_positions.empty())
		{
			this->data[this->empty_data_positions.back()] = element(this->generation_id++, item);
			this->empty_data_positions.pop_back();
		}
		else
		{
			this->data.push_back(element(generation++, item));
		}
		this->item_count++;
	}

	gendex push(rvalue_reference item)
	{
		size_t index = 0;
		if (!this->empty_data_positions.empty())
		{
			index = this->empty_data_positions.back();
			this->data[index] = element(this->generation_id, std::move(item));
			this->empty_data_positions.pop_back();
		}
		else
		{
			index = this->data.size();
			this->data.push_back(element(this->generation_id, std::move(item)));
		}
		this->item_count++;
		return gendex(index, this->generation_id++);
	}

	template <class... Args>
	void emplace(Args... args)
	{
		if (!this->empty_data_positions.empty())
		{
			this->data[this->empty_data_positions.back()] = element(this->generation_id++, std::forward(args));
			this->empty_data_positions.pop_back();
		}
		else
		{
			this->data.emplace(this->generation_id++, std::forward(args));
		}
		this->item_count++;
	}

	size_type size()
	{
		return this->item_count;
	}

	size_type capacity()
	{
		return this->data.capacity();
	}

	size_type capcity_unused_indices()
	{
		return this->empty_data_positions.capacity();
	}

	void clear()
	{
		this->data.clear();
		this->item_count = 0;
	}

	size_type generation()
	{
		return this->generation_id;
	}

	void reset()
	{
		this->data.clear();
		this->generation = 0;
		this->item_count = 0;
	}

	bool empty()
	{
		return this->item_count == 0;
	}

	iterator begin()
	{

	}

	iterator end()
	{

	}

	reverse_iterator rbegin()
	{

	}

	reverse_iterator rend()
	{

	}

	const_iterator cbegin()
	{

	}

	const_iterator cend()
	{

	}

	const_reverse_iterator crbegin()
	{

	}

	const_reverse_iterator crend()
	{

	}
};