#pragma once

#include <psemek/math/point.hpp>
#include <psemek/math/orientation.hpp>
#include <psemek/math/contains.hpp>
#include <psemek/cg/dcel.hpp>

#include <vector>

namespace psemek::cg
{

	template <typename IndexType = std::size_t, typename RobustTag, typename Iterator>
	auto ear_clipping(RobustTag robust_tag, Iterator begin, Iterator end)
	{
		IndexType const count = std::distance(begin, end);

		auto at = [begin](IndexType i){ return *(begin + i); };

		using dcel_type = dcel<util::empty, util::empty, util::empty, IndexType>;

		dcel_type result;

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

		result.faces[inner_face.index()].edge = 0;
		result.faces[outer_face.index()].edge = count;

		result.points.resize(count);
		result.edges.resize(2 * count);

		for (IndexType i = 0; i < count; ++i)
		{
			result.points[i].edge = i;

			result.edges[i].face = 1;
			result.edges[i].origin = i;
			result.edges[i].prev = (i + count - 1) % count;
			result.edges[i].next = (i + 1) % count;
			result.edges[i].twin = i + count;

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

		auto inside = [robust_tag](auto const & t, auto const & p)
		{
			return true
				&& math::orientation(robust_tag, t[0], t[1], p) == math::sign_t::positive
				&& math::orientation(robust_tag, t[1], t[2], p) == math::sign_t::positive
				&& math::orientation(robust_tag, t[2], t[0], p) == math::sign_t::positive
				;
		};

		auto edge = result.edge(0);
		for (IndexType i = 0; i + 3 < count; ++i)
		{
			for (;; edge = edge.next())
			{
				bool ear = true;

				auto next = edge.next();
				auto nnext = next.next();

				math::simplex triangle{at(edge.origin().index()), at(next.origin().index()), at(nnext.origin().index())};

				if (math::orientation(robust_tag, triangle[0], triangle[1], triangle[2]) == math::sign_t::negative)
					continue;

				for (auto k = nnext.next(); k != edge; k = k.next())
				{
					if (inside(triangle, at(k.origin().index())))
					{
						ear = false;
						break;
					}
				}

				if (!ear)
					continue;

				auto ein = result.push_edge();
				auto eout = result.push_edge();
				auto prev = edge.prev();

				auto face = result.push_face();

				face.edge(ein);
				ein.face(face);
				edge.face(face);
				next.face(face);

				ein.origin(nnext.origin());
				ein.prev(next); next.next(ein);
				ein.next(edge); edge.prev(ein);
				ein.twin(eout);

				eout.origin(edge.origin());
				eout.prev(prev); prev.next(eout);
				eout.next(nnext); nnext.prev(eout);
				eout.twin(ein);

				inner_face.edge(eout);
				eout.face(inner_face);

				edge = eout;

				break;
			}
		}

		return result;
	}

	template <typename IndexType = std::size_t, typename Iterator>
	auto ear_clipping(Iterator begin, Iterator end)
	{
		return ear_clipping<IndexType>(math::default_robust_tag, begin, end);
	}

}
