#pragma once

#include <psemek/math/orientation.hpp>

namespace psemek::cg
{

	template <typename RobustTag, typename InIterator, typename OutIterator>
	OutIterator jarvis_convex_hull(RobustTag robust_tag, InIterator begin, InIterator end, OutIterator out)
	{
		auto first_hull_point = std::min_element(begin, end);
		auto last_hull_point = first_hull_point;

		*out++ = last_hull_point;

		while (true)
		{
			auto it = begin;
			for (; it != end; ++it)
			{
				if (it == last_hull_point) continue;

				bool is_hull_edge = true;
				for (auto jt = begin; jt != end; ++jt)
				{
					if (jt == it) continue;
					if (jt == last_hull_point) continue;

					if (orientation(robust_tag, *last_hull_point, *it, *jt) != math::sign_t::positive)
					{
						is_hull_edge = false;
						break;
					}
				}

				if (is_hull_edge)
				{
					break;
				}
			}

			if (it == first_hull_point) break;

			*out++ = it;
			last_hull_point = it;
		}

		return out;
	}

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

}
