#pragma once

#include <psemek/math/orientation.hpp>

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

namespace psemek::cg
{

	template <typename RobustTag, typename InIterator, typename OutIterator>
	OutIterator andrew_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);

		// sort lexicographically
		std::sort(its.begin(), its.end(), [](auto i1, auto i2){ return *i1 < *i2; });

		std::vector<InIterator> hull;
		hull.push_back(its.front());

		// find lower half of the hull
		for (auto it = its.begin() + 1; it != its.end(); ++it)
		{
			while (hull.size() >= 2 && orientation(robust_tag, **(hull.end() - 2), **(hull.end() - 1), **it) != math::sign_t::positive)
				hull.pop_back();

			hull.push_back(*it);
		}

		// find upper half of the hull
		for (auto it = its.rbegin() + 1; it != its.rend(); ++it)
		{
			if (*it == *(hull.end() - 2))
				continue;

			while (hull.size() >= 2 && orientation(robust_tag, **(hull.end() - 2), **(hull.end() - 1), **it) != math::sign_t::positive)
				hull.pop_back();

			hull.push_back(*it);
		}

		// the last upper part point is the first lower part point - remove it
		hull.pop_back();

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

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

}
