#pragma once

#include <psemek/math/orientation.hpp>

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

namespace psemek::cg
{

	template <typename RobustTag, typename InIterator, typename OutIterator>
	OutIterator graham_convex_hull(RobustTag robust_tag, InIterator begin, InIterator end, OutIterator out)
	{
		// need to store iterators to sort them
		std::vector<InIterator> its(end - begin);
		std::iota(its.begin(), its.end(), begin);

		// find leftmost point & move its iterator to beginning
		{
			auto leftmost = std::min_element(its.begin(), its.end(), [](auto i1, auto i2){ return *i1 < *i2; });
			std::iter_swap(leftmost, its.begin());
		}

		// sort with respect to angle to leftmost point
		std::sort(its.begin() + 1, its.end(), [&](auto i1, auto i2){
			auto o = orientation(robust_tag, *its.front(), *i1, *i2);

			// carefully deal with parallel points
			if (o == math::sign_t::positive)
				return true;
			else if (o == math::sign_t::negative)
				return false;

			return *i1 < *i2;
		});

		// perform gift wrapping

		auto hull_end = its.begin() + 1;

		for (auto it = its.begin() + 1; it != its.end(); ++it)
		{
			while (hull_end - its.begin() >= 2 && orientation(robust_tag, **(hull_end - 2), **(hull_end - 1), **it) != math::sign_t::positive)
				--hull_end;

			*hull_end++ = *it;
		}

		// copy result to output
		return std::copy(its.begin(), hull_end, out);
	}

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

}
