#pragma once

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

namespace psemek::cg
{

	// TODO: this was written for Voronoi and is known to fail in some cases
	template <typename T, typename Edge, typename Face, typename Index>
	void clip(dcel<math::point<T, 2>, Edge, Face, Index> & dcel, math::vector<T, 3> const & eq)
	{
		auto outer_face = dcel.face(0);

		auto inside = [eq](auto const & p){
			return p[0] * eq[0] + p[1] * eq[1] + eq[2] >= 0.f;
		};

		auto cross = [&inside](auto edge){
			return !inside(edge.origin().data()) && inside(edge.next().origin().data());
		};

		auto split_edge = [&dcel, eq](auto edge)
		{
			auto q0 = edge.origin().data();
			auto q1 = edge.next().origin().data();

			float t = - (eq[0] * q0[0] + eq[1] * q0[1] + eq[2]) / (eq[0] * (q1[0] - q0[0]) + eq[1] * (q1[1] - q0[1]));
			auto q = q0 + t * (q1 - q0);

			auto e = dcel.push_edge();
			auto twin = dcel.push_edge();
			auto p = dcel.push_point(q);

			auto ctwin = edge.twin();

			p.edge(e);

			e.origin(p);
			e.next(edge.next());
			e.twin(ctwin);
			e.face(edge.face());

			twin.origin(p);
			twin.next(ctwin.next());
			twin.twin(edge);
			twin.face(ctwin.face());

			edge.next(e);
			edge.twin(twin);

			ctwin.next(twin);
			ctwin.twin(e);
		};

		auto prev_edge = [](auto edge)
		{
			auto e = edge;
			while (true)
			{
				e = e.twin();
				if (e.next() == edge) return e;
				e = e.next();
			}
		};

		auto merge_edge = [&](auto edge)
		{
			auto dcel_copy = dcel;

			auto next = edge.next();
			auto twin = edge.twin();
			auto ntwin = next.twin();

			assert(ntwin.next() == twin);
			assert(next.origin() == twin.origin());

			edge.next(next.next());
			edge.twin(ntwin);

			ntwin.next(twin.next());
			ntwin.twin(edge);

			edge.face().edge(edge);
			ntwin.face().edge(ntwin);

			auto face = edge.face();
			auto p = next.origin();
			if (next > twin)
			{
				dcel.remove_edge(next);
				dcel.remove_edge(twin);
			}
			else
			{
				dcel.remove_edge(twin);
				dcel.remove_edge(next);
			}
			dcel.remove_point(p);

			return face.edge();
		};

		auto current_edge = outer_face.edge();

		bool no_intersection = true;

		while (true)
		{
			if (cross(current_edge)) {
				no_intersection = false;
				break;
			}

			current_edge = current_edge.next();
			if (current_edge == outer_face.edge())
				break;
		}

		if (no_intersection)
			return;

		split_edge(current_edge);

		while (true)
		{
			bool end = false;
			while (true)
			{
				auto prev = current_edge.twin().next().twin();

				if (prev.face() != outer_face) break;

				if (cross(prev.twin()))
				{
					end = true;
					split_edge(prev.twin());
					current_edge = merge_edge(prev.next());

					break;
				}

				current_edge = merge_edge(prev);
			}

			if (end) break;

			for (bool finished = false; !finished;)
			{
				auto n = current_edge.twin().next();

				if (cross(n))
				{
					finished = true;
					split_edge(n);
				}

				auto prev = prev_edge(current_edge);

				prev.next(n);
				n.face().edge(n.next());
				n.face(outer_face);
				current_edge.origin(n.next().origin());
				current_edge.twin().next(n.next());
				n.next(current_edge);
				n.origin().edge(n);
			}

			current_edge = prev_edge(current_edge);
		}
	}

}
