feeble-mundane/source/feeble_mundane/ui/ecs.hpp

#ifndef MA_POINTLESS_ENTITY_COMPONENT_SYSTEM
#define MA_POINTLESS_ENTITY_COMPONENT_SYSTEM

#include <vector>
#include <memory>
#include <numeric>
#include <limits>
#include <string>

#include "simple/support/meta.hpp"
#include "simple/support/tuple_utils.hpp"
#include "simple/support/function_utils.hpp"
#include "simple/support/rational.hpp"
#include "simple/support/algorithm/utils.hpp"


template <typename... Interfaces>
class entities;

template <typename Base, typename... Interfaces>
// TODO: enable if is_abstract<Base> && has_virtual_destructor<Base>
// and maybe is_abstract<Interfaces>, but not sure
struct object_interface
{
	static constexpr size_t type_count = 1 + sizeof...(Interfaces);
};

// TODO: parameterise std::unique_ptr and std::vector templates?? do I need that within a project or between projects, cause in a latter case can get away with using declaration in a configuration header
template <typename... Types>
class components
{
	public:

	using types = std::tuple<Types...>;

	template <typename Element, typename ...Args>
	auto& emplace(Args&&... args)
	{
		using simple::support::meta::find_t;
		using simple::support::meta::bind;
		using simple::support::meta::make_index_segment;
		using simple::support::tuple_car;
		using simple::support::tuple_car_t;
		using simple::support::tuple_tie_cdr;
		using simple::support::tie_subtuple;
		using simple::support::is_template_instance_v;

		using found = find_t<bind<is_component, size_constant<0>, Element>, types>;
		static_assert(found::value != std::tuple_size_v<types>, "Element type not found in known component list.");
		if constexpr (is_template_instance_v<object_interface, typename found::type>)
		{
			auto object_vectors = tie_subtuple(vectors,
				make_index_segment<
					found::functor::binding::value,
					found::type::type_count
				>()
			);

			auto& elements = tuple_car(object_vectors);

			auto element = std::make_unique<Element>(std::forward<Args>(args)...);
			Element& raw = *element.get();

			add_interface(raw, tuple_tie_cdr(object_vectors));

			elements.emplace_back(std::move(element)); // assuming raw pointer will not change... that's safe right?
			return raw;
		}
		else
		{
			return std::get<found::functor::binding::value>(vectors).emplace_back(std::forward<Args>(args)...);
		}
	}

	template <typename Element>
	Element& push(Element&& element)
	{ return emplace<simple::support::remove_cvref_t<Element>>(std::forward<Element>(element)); }

	// TODO: return a range ??
	template <typename Component>
	const auto& get() const noexcept
	{
		using simple::support::meta::find_v;
		return std::get<find_v<Component, flat_types>>(vectors);
	}

	std::string log_sizes() const
	{
		std::string info;
		simple::support::transform([&](auto& v){
			info += std::to_string(v.size()) + ": " + typeid(typename std::remove_reference_t<decltype(v)>::value_type).name() + '\n';
		}, vectors);
		return info;
	}

	private:

	template <typename T>
	struct flatten_object_interface { using type = std::tuple<T>; };
	template <typename Base, typename... Interfaces>
	struct flatten_object_interface<object_interface<Base, Interfaces...>>
	{ using type = std::tuple<std::unique_ptr<Base>, Interfaces*...>; };

	template <size_t i> using size_constant = std::integral_constant<size_t, i>;

	template <typename flat_index, typename T, typename Component>
	struct is_component : std::is_same<T,Component>
	{
		using binding = size_constant<flat_index{} + !is_component::value>;
	};

	template <typename flat_index, typename T, typename Base, typename... Interfaces>
	struct is_component<flat_index, T, object_interface<Base,Interfaces...>>
	{
		static constexpr bool value = std::is_base_of_v<Base, T>;
		static constexpr size_t increment =
			[](bool value)
			{
				return value
					? 0
					: object_interface<Base,Interfaces...>::type_count
				;
			}
			(is_component::value);
		using binding = size_constant<flat_index{} + increment>;
	};

	using flat_types = simple::support::meta::reconstruct_t<types,flatten_object_interface>;

	template <typename T>
	using container = std::vector<T>;

	template <typename Tuple>
	using make_containers_t = simple::support::meta::transform_t<Tuple, container>;

	template <typename T>
	using container_ref = container<T>&;

	template <typename... Ts>
	using make_container_refs_t = simple::support::meta::transform_t<std::tuple<Ts...>, container_ref>;

	template <typename T>
	using iterator  = typename std::vector<T>::const_iterator;

	using iterators = simple::support::meta::transform_t<flat_types, iterator>;

	template <typename El>
	void add_interface(El&, std::tuple<>){}

	template <typename El, typename In, typename... Rest>
	// NOTE: this shorthand can't deduce the In :/
	// void add_interface(El& element, make_container_refs_t<In*, Rest...> interfaces)
	void add_interface(El& element, std::tuple<container<In*>&, container<Rest>&...> interfaces)
	{
		using simple::support::tuple_car;
		using simple::support::tuple_tie_cdr;
		if constexpr (std::is_base_of_v<In, El>)
			tuple_car(interfaces).push_back(&element);
		add_interface(element,tuple_tie_cdr(interfaces));
	}

	make_containers_t<flat_types> vectors;

	template <typename Component>
	auto& get() noexcept
	{
		using simple::support::meta::find_v;
		return std::get<find_v<Component, flat_types>>(vectors);
	}


	friend class entities<Types...>;

};

using entity_id_t = simple::support::rational<unsigned,
	  simple::support::meta_constant<unsigned, 1u << (std::numeric_limits<unsigned>::digits/2)>>;


template <typename... Components>
class entities
{
	public:
	using components_type = components<Components...>;

	entities() : _components(), offsets() {}
	entities(components_type components) :
		_components(std::move(components)),
		offsets(simple::support::from_tuple<decltype(offsets)>(simple::support::transform(
			[](auto& v) -> entity_size_t {return v.size();}, _components.vectors )))
	{}

	template <typename T>
	struct entity
	{
		public:
		T components;
		const entity_id_t id;
		entities& world;
		bool owning;

		~entity()
		{
			if(owning)
				world.erase(id);
		}

		entity(entity& other) = delete;
		entity& operator=(entity& other) = delete;
		entity& operator=(entity&& other) = delete;
		entity(entity&& other)
			: entity(other.world, std::move(other.components), other.id)
		{
			other.release();
		}

		entity& release()
		{
			owning = false;
			return *this;
		}

		private:
		entity(entities& world, T&& components, const entity_id_t& id) :
			components(std::forward<T>(components)),
			id(id),
			world(world),
			owning(true)
		{}
		friend class entities;
	};

	// TODO; emplace specific components to replace the make function below,
	// component type1, args1
	// component_type2, args2
	// ...
	// component_typeN, argsN
	//
	// maybe use a component helper template, so it looks like this:
	// entities.emplace
	// (
	//   component<Type1>(args1...),
	//   component<Type2>(args2...),
	//   component<Type3>(args3...),
	//   component<Type4>(args4...),
	// );
	// can also sfinae on this helper template.
	//
	// return a predictable entity object with references to all components and the id
	//
	// then again do you actually need to make new types of entity at runtime? entity types (which are defined by entity_sizes) should also be compile time, and also also also maybe fixed per id block
	// and when not, can still be RLE

	auto next_block_id()
	{
		return entity_id_t{} +
			(empty(entity_ids) ? 0 : unsigned(entity_ids.back()+1))
		;
	}

	template <typename Function>
	auto make(Function&& function)
	{
		return make(entity_id_t{} +
			(empty(entity_ids) ? 0 : unsigned(entity_ids.back()))
		, std::forward<Function>(function));
	}

	template <typename Function>
	entity<std::invoke_result_t<
		Function, components<Components...>&>>
	make(entity_id_t block_id, Function&& function)
	{
		using simple::support::transform;
		auto size_before = transform([](const auto& x) {return x.size(); },
			_components.vectors);

		auto&& product = std::invoke(
			std::forward<Function>(function),
			_components);

		auto [id, pos] = get_id(block_id);

		if(pos != entity_ids.end())
		{
			transform([off = pos - entity_ids.begin()]
			(auto& entity_size, auto size_before, auto& component)
			{
				auto size_pos = entity_size.begin() + off;
				std::rotate( // !
					component.begin() + std::accumulate(entity_size.begin(), size_pos, 0),
					component.begin() + size_before,
					component.end()
				);
			}, entity_sizes, size_before, _components.vectors);
		}

		transform([off = pos - entity_ids.begin()]
		(auto& entity_size, auto size_before, const auto& component)
		{
			auto size_pos = entity_size.begin() + off;
			entity_size.insert(size_pos, component.size() - size_before);
		}, entity_sizes, size_before, _components.vectors);

		entity_ids.insert(pos,id);

		return
		{
			*this,
			std::forward<decltype(product)>(product),
			id
		};
	};

	// TODO: swap for entities of same size, to allow stuff like remove erase

	// template <typename Element, typename ...Args>
	// Element& emplace(Args&&... args)
	// {
	// 	return make([&](auto& components) -> auto&
	// 	{
	// 		return
	// 			components.template emplace<Element>
	// 				(std::forward<Args>(args)...);
	// 	}).components;
	// }

	// TODO: reuse code from find, why is it so hard :/
	// TODO: forget() method, that will turn this into a nop (you know, the classic problem: we technically own all objects we hand out, but we pretend that the user owns them instead with owning handles. now the user's destruction pattern might not be very efficient for our arrangement, and we can do nothing about that, exceeeeept when we know we are going to be destroyed as well, then we can ignore user requests to destroy and take care of it all in one go, unfortunately if the user is following RAII diligently, everything will be destroyed before us, so we have to give them a way to indicate this doomsday scenario manually)

	template <typename Projection>
	void erase(entity_id_t first_id, entity_id_t last_id, Projection proj)
	{
		using simple::support::transform_arg;
		auto found = simple::support::range{
			lower_bound(begin(entity_ids), end(entity_ids), first_id, transform_arg{proj}),
		    upper_bound(begin(entity_ids), end(entity_ids), last_id,  transform_arg{proj})
		};
		assert(found.valid());

		using simple::support::transform;
		transform([&](auto& components, auto& sizes, auto entities_offset)
		{
			auto found_size = simple::support::map_range(found, sizes, begin(entity_ids));

			auto offset_begin = std::accumulate(begin(sizes), found_size.begin(), 0);
			auto offset_end = std::accumulate(found_size.begin(), found_size.end(), offset_begin);
			auto components_range = simple::support::get_iterator_range
				(
					components,
					simple::support::range{offset_begin, offset_end}
				) + entities_offset
			;
			components.erase(components_range.begin(), components_range.end());

			sizes.erase(found_size.begin(), found_size.end());
		}, _components.vectors, entity_sizes, offsets);

		entity_ids.erase(found.begin(), found.end());
	}

	void erase(entity_id_t first_id, entity_id_t last_id)
	{ erase(first_id, last_id, [](auto x){ return x; }); }

	void erase(entity_id_t id) { erase(id, id); }

	void erase_block(entity_id_t first_id, entity_id_t last_id)
	{ erase(first_id, last_id, [](auto x){ return unsigned(x); }); }

	void erase_block(entity_id_t id) { erase_block(id, id); }


	template <typename Component>
	decltype(auto) get_all() const noexcept
	{ return _components.template get<Component>(); }

	template <typename Component>
	auto get() const noexcept
	{
		using simple::support::make_range;
		using simple::support::meta::find_v;
		auto components = make_range(_components.template get<Component>());
		components.begin() += offsets[find_v<Component, types>];
		return components;
	}

	// TODO: support a subset of components, not just one or all
	template <typename Component = void, typename Projection = void>
	auto find(entity_id_t id, Projection proj = [](entity_id_t x) { return x; }) noexcept
	{
		using simple::support::transform_arg;
		auto block_pair = std::equal_range(begin(entity_ids), end(entity_ids), id, transform_arg{proj});
		auto block = simple::support::range{block_pair.first, block_pair.second};

		using simple::support::transform;
		using simple::support::meta::find_v;

		constexpr auto component_index = find_v<Component, types>;

		if constexpr (component_index == std::tuple_size_v<types>)
		{
			return transform([&block,this](auto& components, auto& sizes, auto offset)
			{
				// TODO: remove this->, when stupod clang 11+ stops complaining about unused this ffs
				return this->get_components(block,components,sizes,offset);
			}, _components.vectors, entity_sizes, offsets);
		}
		else
		{
			return get_components
			(
				block,
				_components.template get<Component>(),
				entity_sizes[component_index],
				offsets[component_index]
			);
		}
	}

	// TODO: support a subset of components, not just one or all
	template <typename Component = void>
	auto find_block(entity_id_t id) noexcept
	{
		return find(id, [](auto x){ return unsigned(x); });
	}

	template <typename Component, typename It, size_t Index = 0>
	class component_iterator
	{
		public:
		using iterator = It;
		using difference_type = typename std::iterator_traits<iterator>::difference_type;
		using value_type = Component;
		using pointer = Component*;
		using reference = Component&;
		using iterator_category = typename std::iterator_traits<iterator>::iterator_category;

		component_iterator(It base, entities& world) :
			base(base), world(&world)
		{}

		constexpr decltype(auto) operator*() const
		{ return *(world->find<Component>(base->id).begin() + Index); }
		constexpr auto operator->() const
		{ return world->find<Component>(base->id).begin() + Index; }
		constexpr decltype(auto) operator*()
		{ return *(world->find<Component>(base->id).begin() + Index); }
		constexpr auto operator->()
		{ return world->find<Component>(base->id).begin() + Index; }

		constexpr component_iterator& operator++()
		{
			++base;
			return *this;
		}

		constexpr component_iterator operator++(int)
		{
			component_iterator ret = *this;
			++(*this);
			return ret;
		}

		constexpr component_iterator& operator+=(difference_type d)
		{
			base += d;
			return *this;
		}
		constexpr component_iterator& operator-=(difference_type d)
		{
			base -= d;
			return *this;
		}

		constexpr friend component_iterator operator+(const component_iterator& one, difference_type d)
		{
			return component_iterator(one) += d;
		}
		constexpr friend component_iterator operator+(difference_type d, const component_iterator& one)
		{
			return component_iterator(one) += d;
		}

		constexpr friend component_iterator operator-(const component_iterator& one, difference_type d)
		{
			return component_iterator(one) -= d;
		}
		constexpr friend component_iterator operator-(difference_type d, const component_iterator& one)
		{
			return component_iterator(one) -= d;
		}

		constexpr friend difference_type operator-(const component_iterator& one, const component_iterator& other)
		{
			return one.base - other.base;
		}

		constexpr friend bool operator==(const component_iterator& one, const component_iterator& other)
		{
			return one.base == other.base && one.world == other.world;
		}
		constexpr friend bool operator!=(const component_iterator& one, const component_iterator& other)
		{
			return !(one == other);
		}

		private:
		iterator base;
		entities* world;
	};

	// template <typename Component, typename It>
	// class iterator
	// {
	// 	public:
	// 	using difference_type =  entity id difference
	// 	using value_type = tuple of assignable ranges
	// 	using pointer = ???
	// 	using reference = value_type???
	// 	using iterator_category = bidirectional, could be random access if limited to a block and if block is guaranteed to be all same entity type then we can store single element size for whole block and use multiplication yay... now go do it
    //
	// 	iterator(entities& world) :
	// 		world(&world)
	// 	{}
    //
	// 	iterator(entity_id_t id, entities& world) :
	// 		base(base), world(&world)
	// 	{}
    //
	// 	private:
	// 	entities* world;
	// };

	template <typename Component, size_t Index = 0, typename EntityIt = entity_id_t*>
	auto get_component_iterator(EntityIt i)
	{
		return component_iterator<Component,EntityIt, Index>{i, *this};
	}

	std::string log_sizes() const
	{
		// TODO: entity ids, entity_sizes, offsets
		return _components.log_sizes();
	}

	private:

	using entity_size_t = unsigned short;

	template <typename ComponentVector>
	auto get_components
	(
		simple::support::range<std::vector<entity_id_t>::const_iterator> block,
		ComponentVector& components,
		const std::vector<entity_size_t>& sizes,
		const entity_size_t entities_offset
	)
	{
		auto found_size = simple::support::map_range(block, sizes, begin(entity_ids));

		auto offset_begin = std::accumulate(begin(sizes), found_size.begin(), 0);
		auto offset_end = std::accumulate(found_size.begin(), found_size.end(), offset_begin);

		return simple::support::get_iterator_range(
			components,
			simple::support::range{offset_begin, offset_end}
		) + entities_offset;
	};

	std::pair<entity_id_t, std::vector<entity_id_t>::iterator> get_id(entity_id_t block_id)
	{

		using simple::support::transform_arg;
		auto block_end = std::upper_bound
		(
			begin(entity_ids),
			end(entity_ids),
			block_id,
			transform_arg{[](entity_id_t id) { return unsigned(id); }}
		);

		if(block_end == begin(entity_ids))
			return {block_id, block_end}; // block is empty, block id also is the first id

		entity_id_t last_in_block = *(block_end - 1);
		if(unsigned(last_in_block) != unsigned(block_id))
			return {block_id, block_end}; // last element is not from this block, so again it's empty

		using simple::support::next;
		auto next_id = next(last_in_block);
		if(next_id == block_id + 1) // overflew into next block
		{
			// scramble to find a free id
			auto hole = std::adjacent_find(std::reverse_iterator(block_end), entity_ids.rend(),
				[block_id](auto next_id, auto prev_id)
				{
					return next(prev_id) != next_id || unsigned(prev_id) != unsigned(block_id);
				}
			);
			assert(hole != entity_ids.rend() && *hole == block_id); // gulp
			auto next_pos = std::next(hole).base();
			return {next(*std::prev(next_pos)), next_pos};
		}
		return {next_id, block_end};
	}

	using components_t = components<Components...>;
	using types = typename components_t::flat_types;

	components_t _components;
	std::vector<entity_id_t> entity_ids;
	std::array<
		std::vector<entity_size_t>,
		std::tuple_size_v<types>
	> entity_sizes;
	std::array<
		entity_size_t,
		std::tuple_size_v<types>
	> offsets;
};


#endif /* end of include guard */