#pragma once

#include <psemek/util/empty.hpp>
#include <psemek/util/ebo.hpp>
#include <psemek/math/simplex.hpp>

#include <cstddef>
#include <vector>
#include <cassert>

namespace psemek::cg
{

	namespace detail
	{

		template <typename Point, typename Index>
		struct point_rec : util::ebo_helper<Point>
		{
			Index edge;
		};

		template <typename Edge, typename Index>
		struct edge_rec : util::ebo_helper<Edge>
		{
			Index origin;
			Index prev;
			Index next;
			Index twin;
			Index face;
		};

		template <typename Face, typename Index>
		struct face_rec : util::ebo_helper<Face>
		{
			Index edge;
		};

		template <typename DCEL, typename Index, typename Tag>
		struct handle_base
		{
			handle_base()
				: owner_(nullptr)
				, i_(static_cast<Index>(-1))
			{}

			handle_base(DCEL * owner, Index i)
				: owner_(owner)
				, i_(i)
			{}

			DCEL & owner() const { return *owner_; }

			Index index() const { return i_; }

			explicit operator bool() const { return i_ != static_cast<Index>(-1); }

			friend bool operator == (handle_base const & h1, handle_base const & h2)
			{
				return h1.i_ == h2.i_;
			}

			friend bool operator != (handle_base const & h1, handle_base const & h2)
			{
				return !(h1 == h2);
			}

			friend bool operator < (handle_base const & h1, handle_base const & h2)
			{
				return h1.i_ < h2.i_;
			}

			friend bool operator > (handle_base const & h1, handle_base const & h2)
			{
				return h2 < h1;
			}

			friend bool operator <= (handle_base const & h1, handle_base const & h2)
			{
				return !(h2 < h1);
			}

			friend bool operator >= (handle_base const & h1, handle_base const & h2)
			{
				return !(h1 < h2);
			}

		protected:
			DCEL * owner_;
			Index i_;
		};

		struct point_tag{};
		struct edge_tag{};
		struct face_tag{};

	}

	template <typename Point, typename Edge = util::empty, typename Face = util::empty, typename Index = std::size_t>
	struct dcel
	{
		static constexpr Index null = static_cast<Index>(-1);

		using point_rec = detail::point_rec<Point, Index>;
		using edge_rec = detail::edge_rec<Edge, Index>;
		using face_rec = detail::face_rec<Face, Index>;

		std::vector<point_rec> points;
		std::vector<edge_rec> edges;
		std::vector<face_rec> faces;

		// TODO: iteration over handles

		struct point_handle;
		struct point_handle_const;
		struct edge_handle;
		struct edge_handle_const;
		struct face_handle;
		struct face_handle_const;

		struct point_handle : detail::handle_base<dcel, Index, detail::point_tag>
		{
			using detail::handle_base<dcel, Index, detail::point_tag>::handle_base;

			Point & data() const;

			edge_handle edge() const;

			void edge(edge_handle h) const;

		protected:
			point_rec & get() const
			{
				assert(this->owner_ != nullptr);
				assert(this->i_ < this->owner_->points.size());
				return this->owner_->points[this->i_];
			}
		};

		struct point_handle_const : detail::handle_base<dcel const, Index, detail::point_tag>
		{
			using detail::handle_base<dcel const, Index, detail::point_tag>::handle_base;

			Point const & data() const;

			edge_handle_const edge() const;

		protected:
			point_rec const & get() const
			{
				assert(this->owner_ != nullptr);
				assert(this->i_ < this->owner_->points.size());
				return this->owner_->points[this->i_];
			}
		};

		struct edge_handle : detail::handle_base<dcel, Index, detail::edge_tag>
		{
			using detail::handle_base<dcel, Index, detail::edge_tag>::handle_base;

			Edge & data() const;

			point_handle origin() const;
			edge_handle prev() const;
			edge_handle next() const;
			edge_handle twin() const;
			face_handle face() const;

			void origin(point_handle h) const;
			void prev(edge_handle h) const;
			void next(edge_handle h) const;
			void twin(edge_handle h) const;
			void face(face_handle h) const;

		protected:
			edge_rec & get() const
			{
				assert(this->owner_ != nullptr);
				assert(this->i_ < this->owner_->edges.size());
				return this->owner_->edges[this->i_];
			}
		};

		struct edge_handle_const : detail::handle_base<dcel const, Index, detail::edge_tag>
		{
			using detail::handle_base<dcel const, Index, detail::edge_tag>::handle_base;

			Edge const & data() const;

			point_handle_const origin() const;
			edge_handle_const prev() const;
			edge_handle_const next() const;
			edge_handle_const twin() const;
			face_handle_const face() const;

		protected:
			edge_rec const & get() const
			{
				assert(this->owner_ != nullptr);
				assert(this->i_ < this->owner_->edges.size());
				return this->owner_->edges[this->i_];
			}
		};

		struct face_handle : detail::handle_base<dcel, Index, detail::face_tag>
		{
			using detail::handle_base<dcel, Index, detail::face_tag>::handle_base;

			Face & data() const;

			edge_handle edge() const;

			void edge(edge_handle h) const;

		protected:
			face_rec & get() const
			{
				assert(this->owner_ != nullptr);
				assert(this->i_ < this->owner_->faces.size());
				return this->owner_->faces[this->i_];
			}
		};

		struct face_handle_const : detail::handle_base<dcel const, Index, detail::face_tag>
		{
			using detail::handle_base<dcel const, Index, detail::face_tag>::handle_base;

			Face const & data() const;

			edge_handle_const edge() const;

		protected:
			face_rec const & get() const
			{
				assert(this->owner_ != nullptr);
				assert(this->i_ < this->owner_->faces.size());
				return this->owner_->faces[this->i_];
			}
		};

		point_handle point(Index i)
		{
			return {this, i};
		}

		edge_handle edge(Index i)
		{
			return {this, i};
		}

		face_handle face(Index i)
		{
			return {this, i};
		}

		point_handle_const point(Index i) const
		{
			return {this, i};
		}

		edge_handle_const edge(Index i) const
		{
			return {this, i};
		}

		face_handle_const face(Index i) const
		{
			return {this, i};
		}

		point_handle push_point(Point data = {})
		{
			auto i = static_cast<Index>(points.size());
			points.push_back({{std::move(data)}, null});
			return point(i);
		}

		edge_handle push_edge(Edge data = {})
		{
			auto i = static_cast<Index>(edges.size());
			edges.push_back({{std::move(data)}, null, null, null, null, null});
			return edge(i);
		}

		face_handle push_face(Face data = {})
		{
			auto i = static_cast<Index>(faces.size());
			faces.push_back({{std::move(data)}, null});
			return face(i);
		}

		point_handle insert_point(Index i, Point data = {})
		{
			points.insert(points.begin() + i, {{std::move(data)}, null});
			for (auto & e : edges)
			{
				if (e.origin >= i)
					++e.origin;
			}
			return point(i);
		}

		edge_handle insert_edge(Index i, Edge data = {})
		{
			edges.insert(edges.begin() + i, {{std::move(data)}, null, null, null, null, null});
			for (auto & p : points)
			{
				if (p.edge >= i)
					++p.edge;
			}
			for (auto & e : edges)
			{
				if (e.prev >= i)
					++e.prev;
				if (e.next >= i)
					++e.next;
				if (e.twin >= i)
					++e.twin;
			}
			for (auto & f : faces)
			{
				if (f.edge >= i)
					++f.edge;
			}
			return edge(i);
		}

		face_handle insert_face(Index i, Face data = {})
		{
			faces.insert(faces.begin() + i, {{std::move(data)}, null});
			for (auto & e : edges)
			{
				if (e.face >= i)
					++e.face;
			}
			return face(i);
		}

		void remove_point(point_handle h)
		{
			points.erase(points.begin() + h.index());
			for (auto & e : edges)
			{
				if (e.origin > h.index())
					--e.origin;
			}
		}

		void remove_edge(edge_handle h)
		{
			edges.erase(edges.begin() + h.index());
			for (auto & p : points)
			{
				if (p.edge > h.index())
					--p.edge;
			}
			for (auto & e : edges)
			{
				if (e.prev > h.index())
					--e.prev;
				if (e.next > h.index())
					--e.next;
				if (e.twin > h.index())
					--e.twin;
			}
			for (auto & f : faces)
			{
				if (f.edge > h.index())
					--f.edge;
			}
		}

		void remove_face(face_handle h)
		{
			faces.erase(faces.begin() + h.index());
			for (auto & e : edges)
			{
				if (e.face > h.index())
					--e.face;
			}
		}
	};

	template <typename Point, typename Edge, typename Face, typename Index>
	Point & dcel<Point, Edge, Face, Index>::point_handle::data() const
	{
		return get().data();
	}

	template <typename Point, typename Edge, typename Face, typename Index>
	typename dcel<Point, Edge, Face, Index>::edge_handle dcel<Point, Edge, Face, Index>::point_handle::edge() const
	{
		return edge_handle{this->owner_, get().edge};
	}

	template <typename Point, typename Edge, typename Face, typename Index>
	void dcel<Point, Edge, Face, Index>::point_handle::edge(edge_handle h) const
	{
		get().edge = h.index();
	}

	template <typename Point, typename Edge, typename Face, typename Index>
	Point const & dcel<Point, Edge, Face, Index>::point_handle_const::data() const
	{
		return get().data();
	}

	template <typename Point, typename Edge, typename Face, typename Index>
	typename dcel<Point, Edge, Face, Index>::edge_handle_const dcel<Point, Edge, Face, Index>::point_handle_const::edge() const
	{
		return edge_handle_const{this->owner_, get().edge};
	}

	template <typename Point, typename Edge, typename Face, typename Index>
	Edge & dcel<Point, Edge, Face, Index>::edge_handle::data() const
	{
		return get().data();
	}

	template <typename Point, typename Edge, typename Face, typename Index>
	typename dcel<Point, Edge, Face, Index>::point_handle dcel<Point, Edge, Face, Index>::edge_handle::origin() const
	{
		return point_handle{this->owner_, get().origin};
	}

	template <typename Point, typename Edge, typename Face, typename Index>
	typename dcel<Point, Edge, Face, Index>::edge_handle dcel<Point, Edge, Face, Index>::edge_handle::prev() const
	{
		return edge_handle{this->owner_, get().prev};
	}

	template <typename Point, typename Edge, typename Face, typename Index>
	typename dcel<Point, Edge, Face, Index>::edge_handle dcel<Point, Edge, Face, Index>::edge_handle::next() const
	{
		return edge_handle{this->owner_, get().next};
	}

	template <typename Point, typename Edge, typename Face, typename Index>
	typename dcel<Point, Edge, Face, Index>::edge_handle dcel<Point, Edge, Face, Index>::edge_handle::twin() const
	{
		return edge_handle{this->owner_, get().twin};
	}

	template <typename Point, typename Edge, typename Face, typename Index>
	typename dcel<Point, Edge, Face, Index>::face_handle dcel<Point, Edge, Face, Index>::edge_handle::face() const
	{
		return face_handle{this->owner_, get().face};
	}

	template <typename Point, typename Edge, typename Face, typename Index>
	void dcel<Point, Edge, Face, Index>::edge_handle::origin(point_handle h) const
	{
		get().origin = h.index();
	}

	template <typename Point, typename Edge, typename Face, typename Index>
	void dcel<Point, Edge, Face, Index>::edge_handle::prev(edge_handle h) const
	{
		get().prev = h.index();
	}

	template <typename Point, typename Edge, typename Face, typename Index>
	void dcel<Point, Edge, Face, Index>::edge_handle::next(edge_handle h) const
	{
		get().next = h.index();
	}

	template <typename Point, typename Edge, typename Face, typename Index>
	void dcel<Point, Edge, Face, Index>::edge_handle::twin(edge_handle h) const
	{
		get().twin = h.index();
	}

	template <typename Point, typename Edge, typename Face, typename Index>
	void dcel<Point, Edge, Face, Index>::edge_handle::face(face_handle h) const
	{
		get().face = h.index();
	}

	template <typename Point, typename Edge, typename Face, typename Index>
	Edge const & dcel<Point, Edge, Face, Index>::edge_handle_const::data() const
	{
		return get().data();
	}

	template <typename Point, typename Edge, typename Face, typename Index>
	typename dcel<Point, Edge, Face, Index>::point_handle_const dcel<Point, Edge, Face, Index>::edge_handle_const::origin() const
	{
		return point_handle_const{this->owner_, get().origin};
	}

	template <typename Point, typename Edge, typename Face, typename Index>
	typename dcel<Point, Edge, Face, Index>::edge_handle_const dcel<Point, Edge, Face, Index>::edge_handle_const::prev() const
	{
		return edge_handle_const{this->owner_, get().prev};
	}

	template <typename Point, typename Edge, typename Face, typename Index>
	typename dcel<Point, Edge, Face, Index>::edge_handle_const dcel<Point, Edge, Face, Index>::edge_handle_const::next() const
	{
		return edge_handle_const{this->owner_, get().next};
	}

	template <typename Point, typename Edge, typename Face, typename Index>
	typename dcel<Point, Edge, Face, Index>::edge_handle_const dcel<Point, Edge, Face, Index>::edge_handle_const::twin() const
	{
		return edge_handle_const{this->owner_, get().twin};
	}

	template <typename Point, typename Edge, typename Face, typename Index>
	typename dcel<Point, Edge, Face, Index>::face_handle_const dcel<Point, Edge, Face, Index>::edge_handle_const::face() const
	{
		return face_handle_const{this->owner_, get().face};
	}

	template <typename Point, typename Edge, typename Face, typename Index>
	Face & dcel<Point, Edge, Face, Index>::face_handle::data() const
	{
		return get().data();
	}

	template <typename Point, typename Edge, typename Face, typename Index>
	typename dcel<Point, Edge, Face, Index>::edge_handle dcel<Point, Edge, Face, Index>::face_handle::edge() const
	{
		return edge_handle{this->owner_, get().edge};
	}

	template <typename Point, typename Edge, typename Face, typename Index>
	void dcel<Point, Edge, Face, Index>::face_handle::edge(edge_handle h) const
	{
		get().edge = h.index();
	}

	template <typename Point, typename Edge, typename Face, typename Index>
	Face const & dcel<Point, Edge, Face, Index>::face_handle_const::data() const
	{
		return get().data();
	}

	template <typename Point, typename Edge, typename Face, typename Index>
	typename dcel<Point, Edge, Face, Index>::edge_handle_const dcel<Point, Edge, Face, Index>::face_handle_const::edge() const
	{
		return edge_handle_const{this->owner_, get().edge};
	}

	template <
		typename Point2, typename Edge2 = util::empty, typename Face2 = util::empty, typename Index2 = std::size_t,
		typename Point, typename Edge, typename Face, typename Index,
		typename PointFn, typename EdgeFn, typename FaceFn>
	dcel<Point2, Edge2, Face2, Index2> map(dcel<Point, Edge, Face, Index> const & d, PointFn && point_fn, EdgeFn && edge_fn, FaceFn && face_fn)
	{
		using result_type = dcel<Point2, Edge2, Face2, Index2>;
		result_type result;

		result.points.reserve(d.points.size());
		result.edges.reserve(d.edges.size());
		result.faces.reserve(d.faces.size());

		for (auto const & p : d.points)
		{
			typename result_type::point_rec rec;
			rec.edge = static_cast<Index2>(p.edge);
			rec.data() = point_fn(p.data());
			result.points.push_back(std::move(rec));
		}

		for (auto const & e : d.edges)
		{
			typename result_type::edge_rec rec;
			rec.origin = static_cast<Index2>(e.origin);
			rec.prev = static_cast<Index2>(e.prev);
			rec.next = static_cast<Index2>(e.next);
			rec.twin = static_cast<Index2>(e.twin);
			rec.face = static_cast<Index2>(e.face);
			rec.data() = edge_fn(e.data());
			result.edges.push_back(std::move(rec));
		}

		for (auto const & f : d.faces)
		{
			typename result_type::face_rec rec;
			rec.edge = static_cast<Index2>(f.edge);
			rec.data() = face_fn(f.data());
			result.faces.push_back(std::move(rec));
		}

		return result;
	}

	template <typename Point, typename Edge, typename Face, typename Index>
	void fill_missing_faces(dcel<Point, Edge, Face, Index> & dcel)
	{
		for (Index i = 0; i < dcel.edges.size(); ++i)
		{
			if (dcel.edges[i].face != dcel.null) continue;

			auto e = dcel.edge(i);
			auto f = dcel.push_face();
			f.edge(e);
			e.face(f);

			for (e = e.next(); e.index() != i; e = e.next())
				e.face(f);
		}
	}

	template <typename Index = std::size_t, typename Iterator>
	auto polygon_dcel(Iterator begin, Iterator end)
	{
		using point_type = std::decay_t<decltype(*begin)>;

		dcel<point_type, util::empty, util::empty, Index> result;

		auto outer_face = result.push_face();
		auto inner_face = result.push_face();

		outer_face.edge(result.edge(0));
		inner_face.edge(result.edge(1));

		for (; begin != end; ++begin)
		{
			result.push_point(*begin);
			result.push_edge();
			result.push_edge();
		}

		std::size_t const N = result.points.size();

		for (std::size_t i = 0; i < N; ++i)
		{
			result.points[i].edge = 2 * i;

			result.edges[2 * i].face = 0;
			result.edges[2 * i].prev = 2 * ((i + N - 1) % N);
			result.edges[2 * i].next = 2 * ((i + 1) % N);
			result.edges[2 * i].twin = 2 * i + 1;
			result.edges[2 * i].origin = i;

			result.edges[2 * i + 1].face = 1;
			result.edges[2 * i + 1].prev = 2 * ((i + 1) % N) + 1;
			result.edges[2 * i + 1].next = 2 * ((i + N - 1) % N) + 1;
			result.edges[2 * i + 1].twin = 2 * i;
			result.edges[2 * i + 1].origin = (i + 1) % N;
		}

		return result;
	}

	template <typename Point, typename Edge, typename Face, typename Index, typename OutputIterator>
	OutputIterator edge_mesh(dcel<Point, Edge, Face, Index> const & dcel, OutputIterator out)
	{
		std::vector<bool> visited(dcel.edges.size(), false);
		for (Index e = 0; e < dcel.edges.size(); ++e)
		{
			if (visited[e]) continue;

			auto twin = dcel.edges[e].twin;

			visited[e] = true;
			visited[twin] = true;

			auto h = dcel.edge(e);

			*out++ = math::segment<Index>{h.origin().index(), h.twin().origin().index()};
		}
		return out;
	}

	template <typename Point, typename Edge, typename Face, typename Index>
	auto edge_mesh(dcel<Point, Edge, Face, Index> const & dcel)
	{
		std::vector<math::segment<Index>> result;
		edge_mesh(dcel, std::back_inserter(result));
		return result;
	}

	template <typename Point, typename Edge, typename Face, typename Index, typename OutputIterator>
	OutputIterator triangle_mesh(dcel<Point, Edge, Face, Index> const & dcel, OutputIterator out)
	{
		for (Index f = 1; f < dcel.faces.size(); ++f)
		{
			auto h = dcel.face(f).edge();

			math::triangle<Index> t;
			t[0] = h.origin().index(); h = h.next();
			t[1] = h.origin().index(); h = h.next();
			t[2] = h.origin().index();

			*out++ = t;
		}
		return out;
	}

	template <typename Point, typename Edge, typename Face, typename Index>
	auto triangle_mesh(dcel<Point, Edge, Face, Index> const & dcel)
	{
		std::vector<math::triangle<Index>> result;
		triangle_mesh(dcel, std::back_inserter(result));
		return result;
	}

}
