#pragma once

#include <memory>
#include <cstdint>

namespace psemek::util
{

	template <typename T, typename Handle = std::size_t>
	struct flat_list
	{
		using handle_type = Handle;

		static constexpr Handle null = static_cast<Handle>(-1);

		flat_list() = default;
		flat_list(flat_list &&) noexcept;
		flat_list(flat_list const &) = delete;

		flat_list & operator = (flat_list &&) noexcept;
		flat_list & operator = (flat_list const &) = delete;

		~flat_list();

		Handle insert(T const & value);
		Handle insert(T && value);

		void erase(Handle handle);

		T & operator[] (Handle handle) { return nodes_[handle].value; }
		T const & operator[] (Handle handle) const { return nodes_[handle].value; }

		std::size_t size() const { return size_; }
		std::size_t capacity() const { return capacity_; }
		bool empty() const { return size_ == 0; }

		T * data()
		{
			static_assert(sizeof(node) == sizeof(T));
			return reinterpret_cast<T *>(nodes_.get());
		}

		T const * data() const
		{
			static_assert(sizeof(node) == sizeof(T));
			return reinterpret_cast<T *>(nodes_.get());
		}

		T * begin() { return data(); }
		T const * begin() const { return data(); }

		T * end() { return begin() + capacity(); }
		T const * end() const { return begin() + capacity(); }

		void reserve(std::size_t size);
		void clear();

		void swap(flat_list & other);

	private:
		union node
		{
			Handle next;
			T value;

			node()
				: next{null}
			{}

			node(Handle next)
				: next{next}
			{}

			~node() {}
		};

		std::unique_ptr<node[]> nodes_;
		std::size_t capacity_ = 0;
		std::size_t size_ = 0;
		Handle first_ = null;

		void expand();
	};

	template <typename T, typename Handle>
	flat_list<T, Handle>::flat_list(flat_list && other) noexcept
		: nodes_(std::move(other.nodes_))
		, capacity_(other.capacity_)
		, size_(other.size_)
		, first_(other.first_)
	{
		other.capacity_ = 0;
		other.size_ = 0;
		other.first_ = null;
	}

	template <typename T, typename Handle>
	flat_list<T, Handle> & flat_list<T, Handle>::operator = (flat_list && other) noexcept
	{
		flat_list(std::move(other)).swap(*this);
		return *this;
	}

	template <typename T, typename Handle>
	flat_list<T, Handle>::~flat_list()
	{
		clear();
	}

	template <typename T, typename Handle>
	Handle flat_list<T, Handle>::insert(T const & value)
	{
		if (first_ == null)
			expand();

		auto handle = first_;
		auto next = nodes_[first_].next;
		new (&nodes_[first_].value) T{value};
		first_ = next;
		++size_;
		return handle;
	}

	template <typename T, typename Handle>
	Handle flat_list<T, Handle>::insert(T && value)
	{
		if (first_ == null)
			expand();

		auto handle = first_;
		auto next = nodes_[first_].next;
		new (&nodes_[first_].value) T{std::move(value)};
		first_ = next;
		++size_;
		return handle;
	}

	template <typename T, typename Handle>
	void flat_list<T, Handle>::erase(Handle handle)
	{
		nodes_[handle].value.~T();
		nodes_[handle].next = first_;
		first_ = handle;
		--size_;
	}

	template <typename T, typename Handle>
	void flat_list<T, Handle>::reserve(std::size_t size)
	{
		if (size <= capacity_) return;

		bool const fast_reserve = (size_ == capacity_);

		std::unique_ptr<node[]> new_nodes(new node[size]);
		for (Handle h = first_; h != null;)
		{
			auto next = nodes_[h].next;
			new_nodes[h].next = (next == null) ? static_cast<Handle>(capacity_) : next;
			h = next;
		}
		for (std::size_t i = capacity_; i + 1 < size; ++i)
			new_nodes[i].next = static_cast<Handle>(i + 1);
		new_nodes[size - 1].next = null;

		for (std::size_t i = 0; i < capacity_; ++i)
		{
			// optimized for the case of full container
			if (!fast_reserve && (new_nodes[i].next == null)) continue;
			new (&new_nodes[i].value) T{std::move(nodes_[i].value)};
			nodes_[i].value.~T();
		}

		if (first_ == null)
			first_ = static_cast<Handle>(capacity_);

		capacity_ = size;
		nodes_ = std::move(new_nodes);
	}

	template <typename T, typename Handle>
	void flat_list<T, Handle>::clear()
	{
		if constexpr (std::is_trivially_destructible_v<T>)
		{
			nodes_.reset();
			capacity_ = 0;
			first_ = null;
			size_ = 0;
			return;
		}
		else
		{
			if (size_ == 0)
			{
				nodes_.reset();
				capacity_ = 0;
				first_ = null;
				return;
			}

			for (Handle h = first_; h != null;)
			{
				auto next = nodes_[h].next;
				new (&nodes_[h].value) T;
				h = next;
			}

			for (std::size_t i = 0; i < capacity_; ++i)
				nodes_[i].value.~T();

			nodes_.reset();
			capacity_ = 0;
			size_ = 0;
			first_ = null;
		}
	}

	template <typename T, typename Handle>
	void flat_list<T, Handle>::swap(flat_list & other)
	{
		std::swap(nodes_, other.nodes_);
		std::swap(capacity_, other.capacity_);
		std::swap(size_, other.size_);
		std::swap(first_, other.first_);
	}

	template <typename T, typename Handle>
	void flat_list<T, Handle>::expand()
	{
		if (capacity_ == 0)
			reserve(16);
		else
			reserve(2 * capacity_);
	}

}
