Skip to content

Instantly share code, notes, and snippets.

@Journeyman1337
Last active March 6, 2022 21:06
Show Gist options
  • Save Journeyman1337/9029f2aa691f7737ee31aaf0510d59cf to your computer and use it in GitHub Desktop.
Save Journeyman1337/9029f2aa691f7737ee31aaf0510d59cf to your computer and use it in GitHub Desktop.
/*
* 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;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment