#pragma once

namespace glm
{
	//-----------------------------------------------------------------------------
	// NON MEMBER FUNCTIONS
	//
	// reasons :
	// - as std
	// - avoids building all methods for unused types
	// - avoid iterators const / not const issues depending on use case
	//
	// drawbacks :
	// - unbearable syntax with begin & end to give as parameters
	//-----------------------------------------------------------------------------

	//-----------------------------------------------------------------------------
	// used by quicksort algorithm
	template<class value_type>
	inline void glmSwap(value_type& first, value_type& second)
	{
		value_type temp = first;
		first = second;
		second = temp;
	}

	//-----------------------------------------------------------------------------
	template< typename InputIt>
	InputIt glmPartition(InputIt first, InputIt last)
	{
		InputIt pivot = first; // take first iter value as pivot value. pivot holds pivot "should be" position
		for (InputIt j = first + 1; j<last; j++)
		{
			if (*j < *first) // first unmodified before end
			{
				++pivot;
				glmSwap(*pivot, *j); // j is smaller than pivot, fill start of array with 
			}
		}

		glmSwap(*first, *pivot); // possibly same value if no swap occured before

		return pivot;
	}

	//-----------------------------------------------------------------------------
	template< typename InputIt, typename MirrorIt >
	void glmPartitionMirror(InputIt& pivot, MirrorIt& mirrorPivot, InputIt first, InputIt last, MirrorIt mirrorFirst)
	{
		pivot = first; // take first iter value as pivot value. pivot holds pivot "should be" position
		mirrorPivot = mirrorFirst;
		MirrorIt mJ = mirrorFirst + 1;
		for (InputIt j = first + 1; j<last; j++, mJ++)
		{
			if (*j < *first) // first unmodified before end
			{
				++pivot;
				++mirrorPivot;
				glmSwap(*pivot, *j); // j is smaller than pivot, fill start of array with 
				glmSwap(*mirrorPivot, *mJ);
			}
		}

		glmSwap(*first, *pivot); // possibly same value if no swap occured before
		glmSwap(*mirrorFirst, *mirrorPivot);
	}

	//-----------------------------------------------------------------------------
	template< typename InputIt>
	void glmQuickSort(InputIt first, InputIt last)
	{
		if (first < last)
		{
			InputIt pivotElement = glmPartition(first, last); // partitionning on [first,last)
			glmQuickSort(first, pivotElement); // sorting on [first,last), pivotElement is in place
			glmQuickSort(pivotElement + 1, last); // sorting on [first,last)
		}
	}
	
	//-----------------------------------------------------------------------------
	template< typename InputIt, typename MirrorIt >
	void glmQuickSortMirror(InputIt first, InputIt last, MirrorIt mirrorFirst)
	{
		if (first < last)
		{
			InputIt pivotElement;
			MirrorIt mirrorPivotElement;
			glmPartitionMirror(pivotElement, mirrorPivotElement, first, last, mirrorFirst); // partitionning on [first,last)
			glmQuickSortMirror(first, pivotElement, mirrorFirst); // sorting on [first,last), pivotElement is in place
			glmQuickSortMirror(pivotElement + 1, last, mirrorPivotElement + 1);
		}
	}
	
	//-----------------------------------------------------------------------------
	template< typename InputIt, typename Comparator>
	InputIt glmPartitionComp(InputIt first, InputIt last, Comparator comparator)
	{
		InputIt pivot = first; // take first iter value as pivot value. pivot holds pivot "should be" position
		for (InputIt j = first + 1; j < last; j++)
		{
			if (comparator(*j, *first)) // first unmodified before end
			{
				++pivot;
				if (j != pivot)
				{
					glmSwap(*pivot, *j); // j is smaller than pivot, fill start of array with 
				}
			}
		}

		if (first != pivot)
		{
			glmSwap(*first, *pivot); // possibly same value if no swap occured before
		}

		return pivot;
	}

	//-----------------------------------------------------------------------------
	template< typename InputIt, typename Comparator>
	void glmQuickSortComp(InputIt first, InputIt last, Comparator comparator)
	{
		if (first < last)
		{
			InputIt pivotElement = glmPartitionComp(first, last, comparator); // partitionning on [first,last)
			glmQuickSortComp(first, pivotElement, comparator); // sorting on [first,last), pivotElement is in place
			glmQuickSortComp(pivotElement + 1, last, comparator); // sorting on [first,last)
		}
	}


	////-----------------------------------------------------------------------------
	//// find for sorted arrays, binary search
	//// requires a valid comparison operator< on value_type
	//template<typename value_type>
	//bool glmInsertSortedUnique(glm::PODArray<value_type>& thisArray, const value_type& value)
	//{
	//	int last = static_cast<int>(thisArray.end() - thisArray.begin());
	//	if (last != 0) // else begin == end, empty
	//	{
	//		int first = 0;
	//		while (first <= last)
	//		{
	//			int middle = (first + last) / 2;
	//			if (*(firstIte + middle) < value)
	//			{
	//				first = middle + 1;
	//			}
	//			else if (*(firstIte + middle) > value)
	//			{
	//				last = middle - 1;					
	//			}
	//			else
	//			{
	//				return false;// doNothing, already in container.
	//			}
	//		}
	//	}
	//	// not found, insert at "first" position which should point at first value greater than "value"
	//	thisArray.insert(first, value);
	//	return true;
	//}


	//-----------------------------------------------------------------------------
	// find for sorted arrays, binary search
	// requires a valid comparison operator< and operator== on value_type
	template<class InputIt, class value_type>
	InputIt glmBinarySearch(InputIt firstIte, InputIt lastIte, const value_type& value)
	{
		if (lastIte != firstIte)
		{
			int first = 0;
			int last = static_cast<int>(lastIte - firstIte) - 1;
			while (first <= last)
			{
				int middle = (first + last) >> 1;
				if (*(firstIte + middle) < value)
				{
					first = middle + 1;
				}
				else if (*(firstIte + middle) == value) // handle == before >= to avoid having to declare > operator 
				{
					return firstIte + middle;
				}
				else
				{
					last = middle - 1;
				}
			}
		}
		return lastIte;
	}

	//-----------------------------------------------------------------------------
	// find for sorted arrays, binary search, return lower and upper bounds for a value
	// requires a valid comparison operator< and operator== on value_type
	template<class InputIt, class value_type>
	InputIt glmLowerBound(InputIt firstIte, InputIt lastIte, const value_type& value)
	{
		GLM_DEBUG_ASSERT(firstIte <= lastIte);

		if (*firstIte <= value)
		{
			if (firstIte != lastIte)
			{
				int first = 0;
				int last = static_cast<int>(lastIte - firstIte) - 1;
				while (first <= last)
				{
					int middle = (first + last) >> 1;
					if (*(firstIte + middle) <= value)
					{
						if ((firstIte + middle) == (lastIte - 1) // middle is last valid segment and still < value
							|| ((firstIte + middle + 1) != lastIte && value < *(firstIte + middle + 1))) // next segment more than value
						{
							return (firstIte + middle);
						}
						first = middle + 1;
					}
					else
					{
						last = middle - 1;
					}
				}
			}
			return firstIte; // first and only is lower bound
		}
		return lastIte; // no lower bound, value is before first element
	}

	//-----------------------------------------------------------------------------
	// find for unsorted arrays, loops on all items
	// requires a valid comparison operator== and operator!= on value_type
	template<class InputIt, class T>
	InputIt glmFind(InputIt first, InputIt last, const T& value)
	{
		for (; first != last; ++first)
		{
			if (*first == value)
			{
				return first;
			}
		}
		return last;
	}

	//-----------------------------------------------------------------------------
	// find for unsorted arrays, loops on all items
	// requires a valid comparison operator== and operator!= on value_type
	template<class InputIt, class T>
	bool glmFindIndex(InputIt first, InputIt last, const T& value, size_t& foundIndex)
	{
		size_t index = 0;
		for (; first != last; ++first, ++index)
		{
			if (*first == value)
			{
				foundIndex = index;
				return true;
			}
		}
		return false;
	}

	//-----------------------------------------------------------------------------
	// remove duplicate _neighbours_ of a list (does not work on unsorted arrays).
	template <class InputIt>
	InputIt glmUnique(InputIt first, InputIt last)
	{
		if (first == last) return last;

		InputIt result = first;
		while (++first != last)
		{
			if (!(*result == *first))  // or: if (!pred(*result,*first)) for version (2)
				*(++result) = *first;
		}
		return ++result;
	}
}
