generational_arena.hpp

/*
 * MIT License
 *
 * Copyright (c) 2022 Daniel Valcour
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */
 
 #pragma once

#include <cstddef>
#include <vector>
#include <optional>
#include <algorithm>
#include <iterator>


// this is simillar to std::optional, but allows passing by reference
template<typename T>
class optional_reference
{
private:
	T* value_ptr = nullptr;

public:
	constexpr opref() noexcept = default;
	constexpr opref(T& value) noexcept
		: value_ptr(&value)
	{}

	constexpr inline bool has_value() const noexcept
	{
		return value_ptr != nullptr;
	}

	constexpr inline T& value() noexcept
	{
		return *value_ptr;
	}
};

template<typename T>
class generational_arena
{
private:
	struct element
	{
	public:
		std::size_t generation = 0;
		T value = T();

		constexpr element() noexcept = default;
		constexpr element(const std::size_t generation, T&& value) noexcept
			: generation(generation)
			, value(value)
		{}
	};

public:
	class index
	{
		friend class generational_arena<T>;
	private:
		std::size_t position = 0;
		std::size_t generation = 0;

	public:
		constexpr index() noexcept = default;
		constexpr index(const std::size_t position, const std::size_t generation) noexcept
			: position(position)
			, generation(generation)
		{}
	};

	class iterator
	{
		using iterator_category = std::bidirectional_iterator_tag;
		using difference_type = std::ptrdiff_t;
		using value_type = T;
		using pointer = T*;
		using reference = T&

	private:
		generational_arena<T>::element* element;

	public:

		iterator(generational_arena<T>::element* element)
			: element(element)
		{}

		constexpr inline T& operator*() const  
		{
			return element->value; 
		}

		constexpr inline T* operator->() const
		{
			return *element->value;
		}

		constexpr inline iterator& operator++()
		{
			do this->element++; while (this->element->generation == 0);
			return *this;
		}

		constexpr inline iterator operator++(int)
		{
			iterator tmp = *this;
			(*this)++;
			return tmp;
		}

		constexpr inline iterator& operator--()
		{
			do this->element--; while (this->element->generation == 0);
			return *this;
		}

		constexpr inline iterator operator--(int)
		{
			iterator tmp = *this;
			(*this)--;
			return tmp;
		}

		friend constexpr inline bool operator==(const iterator& a, const iterator& b) noexcept
		{
			return a.element == b.element;
		};
		
		friend constexpr inline bool operator!=(const iterator& a, const iterator& b) noexcept
		{
			return a.element != b.element;
		};
	};
private:
	std::size_t first_position = 0;
	std::size_t last_position = 0;
	std::size_t item_count = 0;
	std::size_t generation = 1;
	std::vector<bool> free_positions = std::vector<bool>();
	std::vector<element> items = std::vector<element>();

public:
	constexpr generational_arena() noexcept = default;

	constexpr generational_arena(const std::size_t item_count, const std::size_t free_position_count)
		: items(item_count)
		, free_positions(free_position_count)
	{}

	constexpr inline void reserve(std::size_t item_count, std::size_t free_position_count) noexcept
	{
		items.reserve(item_count);
		free_positions.reserve(free_position_count);
	}

	constexpr inline generational_arena<T>::index add(T&& value) noexcept
	{
		const std::size_t generation = this->generation++;
		this->item_count++;
		if (free_positions.size() > 0)
		{
			const std::size_t position = this->free_positions[free_positions.size() - 1];
			this->free_positions.pop_back();
			auto& item = this->items[position];
			item.value = std::move(value);
			item.generation = generation;
			if (position > this->last_position)
			{
				this->last_position = position;
			}
			if (position < this->first_position)
			{
				this->first_position = position;
			}
			return generational_arena<T>::index(position, generation);
		}
		else
		{
			const std::size_t position = this->items.size();
			this->items.push_back(element(generation, std::move(value)));
			this->last_position = position;
			return generational_arena<T>::index(position, generation);
		}
	}

	constexpr inline bool contains(const generational_arena<T>::index& gendex) const noexcept
	{
		return this->items.size() > gendex.position && this->items[gendex.position].generation == gendex.generation;
	}

	constexpr inline bool try_remove(const generational_arena<T>::index& gendex) noexcept
	{
		if (this->contains(gendex))
		{
			this->items[gendex.position].generation = 0;
			this->free_positions.push_back(gendex.position);
			this->item_count--;
			if (this->item_count == 0)
			{
				this->first_position = 0;
				this->last_position = 0;
			}
			else
			{
				if (this->first_position == gendex.position)
				{
					while (this->items[++this->first_position].generation == 0);
				}
				if (this->last_position == gendex.position)
				{
					while (this->items[--this->last_position].generation == 0);
				}
			}
			return true;
		}	
		return false;
	}

	constexpr inline optional_reference<T> operator[](const generational_arena<T>::index& gendex) noexcept
	{
		if (this->contains(gendex))
		{
			return optional_reference<T>(items[gendex.position].value);
		}
		return optional_reference<T>();
	}

	constexpr inline iterator begin() 
	{
		return iterator(&this->items[this->first_position]);
	}

	constexpr inline iterator end()
	{
		return iterator(&this->items.data()[this->last_position+1]);
	}
};

template<typename T>
using gendex = generational_arena<T>::index;