#pragma once

#include <psemek/math/orientation.hpp>

#include <algorithm>
#include <numeric>
#include <vector>

namespace psemek::cg
{

	namespace detail
	{

		template <typename RobustTag, typename InIterator, typename ItIterator, typename OutIterator>
		OutIterator quick_hull_recursive_helper(RobustTag robust_tag, InIterator p1, InIterator p2, ItIterator begin, ItIterator end, OutIterator out)
		{
			if (begin == end)
				return *out++ = p1;

			// find point in [begin, end) furthest from segment (p1,p2)
			auto mid = *std::max_element(begin, end, [&](auto it1, auto it2){
				// TODO: design a robust predicate
				return orientation(robust_tag, *it2, (*it2) + ((*p2) - (*p1)), *it1) == math::sign_t::positive;
			});

			auto end1 = std::partition(begin, end, [&](auto it){ return orientation(robust_tag, *p1, *it, *mid) == math::sign_t::positive; });
			auto end2 = std::partition(end1, end, [&](auto it){ return orientation(robust_tag, *mid, *it, *p2) == math::sign_t::positive; });

			out = quick_hull_recursive_helper(robust_tag, p1, mid, begin, end1, out);
			out = quick_hull_recursive_helper(robust_tag, mid, p2, end1, end2, out);

			return out;
		}

	}

	template <typename RobustTag, typename InIterator, typename OutIterator>
	OutIterator quick_hull(RobustTag robust_tag, InIterator begin, InIterator end, OutIterator out)
	{
		// need to store iterators to move sets of points around
		std::vector<InIterator> its(end - begin);
		std::iota(its.begin(), its.end(), begin);

		// find leftmost point and move it to the beginning
		{
			auto p = std::min_element(its.begin(), its.end(), [](auto it1, auto it2){ return *it1 < *it2; });
			std::iter_swap(its.begin(), p);
		}

		// find the next hull point in clockwise order and move it to second place
		{
			auto p = std::find_if(its.begin() + 1, its.end(), [&](auto it){
				return std::all_of(its.begin() + 1, its.end(), [&](auto jt){
					return it == jt || orientation(robust_tag, *its.front(), *it, *jt) == math::sign_t::negative;
				});
			});
			std::iter_swap(its.begin() + 1, p);
		}

		// everything is set up, do the recursion
		out = detail::quick_hull_recursive_helper(robust_tag, its[0], its[1], its.begin() + 2, its.end(), out);

		return *out++ = *(its.begin() + 1);
	}

	template <typename InIterator, typename OutIterator>
	OutIterator quick_hull(InIterator begin, InIterator end, OutIterator out)
	{
		return quick_hull(math::default_robust_tag, begin, end, out);
	}

}
