// file:          ToolsetArrayComparableC.hpp
// description:   Utility class for searching and sorting arrays.
//                PÜ 31.3(4).
// author:        Karlheinz Hug
// creation date: 2005-04-28
// last update:   2012-06-21

#ifndef TOOLSET_ARRAY_COMPARABLE_C_HPP_
#define TOOLSET_ARRAY_COMPARABLE_C_HPP_

#include <cassert>
#include <vector>

	template <typename T>
	class ToolsetArrayComparable
		// Instantiation condition: T is a comparable type.
	{
		public:
			static bool sorted (const std::vector<T> & array);

			static bool has (const std::vector<T> & array, const T & item);

			static void sort (std::vector<T> & array);

		protected:
			static bool sorted_between
				(const std::vector<T> & array, int left, int right);

			static bool has_between
				(const std::vector<T> & array, const T & item, int left, int right);

			static void sort_between_e (std::vector<T> & array, int low, int high);
			static void sort_between_l (std::vector<T> & array, int low, int high);
	}; // ToolsetArrayComparable

	template <typename T>
	bool ToolsetArrayComparable<T>::sorted (const std::vector<T> & array)
	{
		int index = 0;
		while (index < (int)array.size() - 1 && array[index] <= array[index + 1])
		{
			++index;
		}
		return index >= (int)array.size() - 1;
	}

	template <typename T>
	bool ToolsetArrayComparable<T>::has
		(const std::vector<T> & array, const T & item)
	{
		assert(sorted(array)); // precondition
		return has_between(array, item, 0, array.size() - 1);
	}

	template <typename T>
	void ToolsetArrayComparable<T>::sort (std::vector<T> & array)
	{
		sort_between_l(array, 0, array.size() - 1);
		assert(sorted (array)); // postcondition
	}

	template <typename T>
	bool ToolsetArrayComparable<T>::sorted_between
		(const std::vector<T> & array, int left, int right)
	{
		assert(left >= 0);				    // precondition
		assert(right < (int)array.size());  // precondition
		while (left < right && array[left] <= array[left + 1])
		{
			++left;
		}
		return left >= right;
	}

	template <typename T>
	bool ToolsetArrayComparable<T>::has_between
		(const std::vector<T> & array, const T & item, int left, int right)
	{
		assert(left >= 0);							// precondition
		assert(right < (int)array.size());				// precondition
		assert(sorted_between(array, left, right)); // precondition
		if (left > right)
		{
			return false;
		}
		else
		{
			int mid = (left + right) / 2;
			if (item < array[mid])
			{
				return has_between(array, item, left, mid - 1);
			}
			else if (item > array[mid])
			{
				return has_between(array, item, mid + 1, right);
			}
			else
			{
				return true;
			}
		}
	}

	template <typename T>
	void ToolsetArrayComparable<T>::sort_between_e (std::vector<T> & array, int low, int high)
		// Quicksort, efficient variant.
		// Instantiation condition: T is a comparable type.
	{
		assert(0 <= low && low <= high && high < (int)array.size()); // precondition
		int	left		= low,
			right		= high;
		T	separator	= array[(low + high) / 2];
		do {
			while (array[left] < separator) {
				++left;
			}
			while (separator < array[right]) {
				--right;
			}
			if (left <= right) {
				T store = array[left];
				array[left] = array[right];
				array[right] = store;
				++left;
				--right;
			}
		} while (left <= right);
		if (low < right) {
			sort_between_e(array, low, right);
		}
		if (left < high) {
			sort_between_e(array, left, high);
		}
		assert(sorted_between (array, low, high)); // postcondition
	}

	template <typename T>
	void ToolsetArrayComparable<T>::sort_between_l (std::vector<T> & array, int low, int high)
		// Quicksort, liberal variant.
		// Instantiation condition: T is a comparable type.
	{
		assert(0 <= low && high < (int)array.size()); // precondition
		if (low < high)
		{
			int	left		= low,
				right		= high;
			T	separator	= array[(low + high) / 2];
			do {
				while (array[left] < separator) {
					++left;
				}
				while (separator < array[right]) {
					--right;
				}
				if (left <= right) {
					T store = array[left];
					array[left] = array[right];
					array[right] = store;
					++left;
					--right;
				}
			} while (left <= right);
			sort_between_l(array, low, right);
			sort_between_l(array, left, high);
		}
		assert(sorted_between (array, low, high)); // postcondition
	}

#endif // TOOLSET_ARRAY_COMPARABLE_C_HPP_