#pragma once

#include <psemek/util/functional.hpp>
#include <psemek/math/orientation.hpp>
#include <psemek/cg/dcel.hpp>

#include <algorithm>
#include <numeric>

namespace psemek::cg
{

	namespace detail
	{

		template <typename Index, typename RobustTag, typename Iterator, typename Callback>
		auto triangulate(RobustTag robust_tag, Iterator begin, Iterator end, Callback && callback)
		{
			using point_type = std::decay_t<decltype(*begin)>;
			static_assert(point_type::static_dimension == 2);

			Index const count = std::distance(begin, end);

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

			std::vector<Index> sweepline_events;
			sweepline_events.resize(count);
			std::iota(sweepline_events.begin(), sweepline_events.end(), Index{0});
			std::sort(sweepline_events.begin(), sweepline_events.end(), [&](auto i, auto j){ return at(i) < at(j); });

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

			dcel_type result;
			for (auto it = begin; it != end; ++it)
				result.push_point();

			auto outer_face = result.push_face();

			// handle degenerate cases
			if (sweepline_events.empty()) return result;

			if (sweepline_events.size() == 1)
				return result;

			result.points.reserve(count);
			result.edges.reserve(3 * (count - 1));
			result.faces.reserve(2 * (count - 1));

			auto it = sweepline_events.begin();

			typename dcel_type::edge_handle hull_start;

			{
				auto p0 = result.point(*it++);
				auto p1 = result.point(*it++);

				auto e01 = result.push_edge();
				auto e10 = result.push_edge();

				p0.edge(e01);
				p1.edge(e10);

				e01.origin(p0);
				e01.next(e10); e10.prev(e01);
				e01.face(outer_face);
				e01.twin(e10);
				e10.origin(p1);
				e10.next(e01); e01.prev(e10);
				e10.face(outer_face);
				e10.twin(e01);
				outer_face.edge(e01);

				hull_start = e01;
			}

			for (; it != sweepline_events.end(); ++it)
			{
				// walk along the hull clockwise

				auto cur_hull_edge = hull_start;
				auto next_hull_edge = cur_hull_edge.next();

				auto hp0 = cur_hull_edge.origin();
				auto hp1 = next_hull_edge.origin();

				auto reset_hull_edge = [&]{
					cur_hull_edge = hull_start;
					next_hull_edge = cur_hull_edge.next();
					hp0 = cur_hull_edge.origin();
					hp1 = next_hull_edge.origin();
				};

				auto move_hull_edge = [&]{
					cur_hull_edge = next_hull_edge;
					next_hull_edge = next_hull_edge.next();
					hp0 = hp1;
					hp1 = next_hull_edge.origin();
				};

				bool degenerate = false;

				// find first hull edge visible from new point
				while (orientation(robust_tag, at(*it), at(hp0.index()), at(hp1.index())) != math::sign_t::positive)
				{
					move_hull_edge();
					if (cur_hull_edge == hull_start)
					{
						degenerate = true;
						break;
					}
				}

				if (degenerate)
				{
					// the whole hull is just a sequence of points on a line
					// find the closest & connect via a single edge

					reset_hull_edge();

					auto q = cur_hull_edge.origin();

					{
						int d = (at(hp0.index())[0] == at(hp1.index())[0])
							? 1 // vertical
							: 0 // horizontal
							;

						// vertical

						while (true)
						{
							if (at(cur_hull_edge.origin().index())[d] > at(q.index())[d])
								q = cur_hull_edge.origin();

							move_hull_edge();
							if (cur_hull_edge == hull_start)
								break;
						}
					}

					auto p = result.point(*it);

					auto qnext = q.edge();
					auto qprev = qnext.twin();

					auto pnext = result.push_edge();
					auto pprev = result.push_edge();

					qprev.next(pprev); pprev.prev(qprev);

					pprev.next(pnext); pnext.prev(pprev);
					pprev.origin(q);
					pprev.twin(pnext);
					pprev.face(outer_face);

					pnext.next(qnext); qnext.prev(pnext);
					pnext.origin(p);
					pnext.twin(pprev);
					pnext.face(outer_face);

					p.edge(pnext);

					continue;
				}

				auto p = result.point(*it);

				auto mid_edge = result.push_edge();
				mid_edge.origin(hp0);
				mid_edge.face(outer_face);

				auto first_mid_edge = mid_edge;

				{
					// fix prev_hull_edge.next
					auto prev_hull_edge = cur_hull_edge.twin();

					while (prev_hull_edge.face() != outer_face)
					{
						prev_hull_edge = prev_hull_edge.next().twin();
					}
					prev_hull_edge.next(first_mid_edge); first_mid_edge.prev(prev_hull_edge);
				}

				// until current edge is visible
				while (orientation(robust_tag, at(*it), at(hp0.index()), at(hp1.index())) == math::sign_t::positive)
				{
					// fill new triangle

					auto ep0 = result.push_edge();
					auto e1p = result.push_edge();

					auto f = result.push_face();

					if (!p.edge())
					{
						p.edge(ep0);
					}

					mid_edge.twin(ep0);

					ep0.origin(p);
					ep0.next(cur_hull_edge); cur_hull_edge.prev(ep0);
					ep0.twin(mid_edge);
					ep0.face(f);

					e1p.origin(hp1);
					e1p.next(ep0); ep0.prev(e1p);
					e1p.face(f);

					cur_hull_edge.next(e1p); e1p.prev(cur_hull_edge);
					cur_hull_edge.face(f);

					f.edge(ep0);

					mid_edge = e1p;

					move_hull_edge();
				}

				auto last_mid_edge = result.push_edge();
				last_mid_edge.origin(p);
				last_mid_edge.face(outer_face);
				last_mid_edge.twin(mid_edge);
				last_mid_edge.next(cur_hull_edge); cur_hull_edge.prev(last_mid_edge);

				mid_edge.twin(last_mid_edge);

				first_mid_edge.next(last_mid_edge); last_mid_edge.prev(first_mid_edge);

				// update first hull edge

				if (hull_start.face() != outer_face)
				{
					hull_start = hull_start.next().next().twin();
					outer_face.edge(hull_start);
				}

				callback(result, p);
			}

			return result;
		}

	}

	template <typename Index = std::size_t, typename RobustTag, typename InputIterator>
	auto triangulate(RobustTag robust_tag, InputIterator begin, InputIterator end)
	{
		return detail::triangulate<Index>(robust_tag, begin, end, util::nop);
	}

	template <typename Index = std::size_t, typename InputIterator>
	auto triangulate(InputIterator begin, InputIterator end)
	{
		return triangulate<Index>(math::default_robust_tag, begin, end);
	}

}
