#pragma once

#include <psemek/math/incircle.hpp>
#include <psemek/cg/triangulation/triangulation.hpp>

#include <queue>
#include <vector>

namespace psemek::cg
{

	template <typename Index = std::size_t, typename RobustTag, typename InputIterator>
	auto delaunay(RobustTag robust_tag, InputIterator begin, InputIterator end)
	{
		std::vector<Index> edge_queue;
		std::vector<Index> flipped_set;

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

		auto callback = [&](auto & dcel, auto p)
		{
			auto outer_face = dcel.face(0);

			// grab interior edges outgoing from p
			for (auto e = p.edge();;)
			{
				auto t = e.twin();

				if (e.face() != outer_face)
				{
					if (t.face() != outer_face)
					{
						edge_queue.push_back(e.index());
					}

					auto n = e.next();
					if (n.twin().face() != outer_face)
					{
						edge_queue.push_back(n.index());
					}
				}

				e = t.next();

				if (e == p.edge()) break;
			}

			while (!edge_queue.empty())
			{
				auto e = dcel.edge(edge_queue.back());
				edge_queue.pop_back();

				auto next = e.next();
				auto prev = next.next();
				auto twin = e.twin();
				auto tnext = twin.next();
				auto tprev = tnext.next();

				auto p0 = prev.origin();
				auto p1 = e.origin();
				auto p2 = next.origin();
				auto p3 = e.twin().next().next().origin();

				// decide if a flip is needed
				if (in_circle(robust_tag, at(p0.index()), at(p1.index()), at(p2.index()), at(p3.index())) != math::sign_t::positive) continue;

				flipped_set.insert(std::lower_bound(flipped_set.begin(), flipped_set.end(), e.index()), e.index());

				auto f0 = e.face();
				auto f1 = twin.face();

				e.origin(p0);
				e.next(tprev); tprev.prev(e);

				next.next(e); e.prev(next);

				prev.face(f1);
				prev.next(tnext); tnext.prev(prev);

				twin.origin(p3);
				twin.next(prev); prev.prev(twin);

				tnext.next(twin); twin.prev(tnext);

				tprev.face(f0);
				tprev.next(next); next.prev(tprev);

				p0.edge(prev);
				p1.edge(tnext);
				p2.edge(next);
				p3.edge(tprev);

				f0.edge(e);
				f1.edge(twin);

				auto push = [&](auto e)
				{
					if (e.twin().face() != outer_face && !std::binary_search(flipped_set.begin(), flipped_set.end(), e.index()))
						edge_queue.push_back(e.index());
				};

				push(next);
				push(prev);
				push(tnext);
				push(tprev);
			}

			flipped_set.clear();
		};
		return detail::triangulate<Index>(robust_tag, begin, end, callback);
	}

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

}
