// Header file: ToolsetArrayComparableM.hpp
// last change: 2011-06-30 Khu

#ifndef TOOLSET_ARRAY_COMPARABLE_M_HPP_
#define TOOLSET_ARRAY_COMPARABLE_M_HPP_

#include <cassert>
#include <algorithm>
#include <vector>

    namespace ToolsetArrayComparable
    {
        template <typename T>
        bool sorted_between (const std::vector<T> & array, int left, int right)
			// Instantiation condition: T is a comparable type.
		{
			assert(0 <= left);									// precondition
			assert(right < array.size());						// precondition
			while (left < right && array[left] <= array[left + 1]) {
				++left;
			}
			return left >= right;
		}
		
		template <typename T>
		bool sorted (const std::vector<T> & array)
			// Instantiation condition: T is a comparable type.
		{
			return sorted_between(array, 0, array.size() - 1);
		}
			
		template <typename T>
		bool less_before (const std::vector<T> & array, const T & item, int left)
			// Instantiation condition: T is a comparable type.
		{
			assert(left <= array.size()); // precondition
			int i = 0;
			while (i < left && array[i] < item) {
				++i;
			}
			return i >= left;
        }

		template <typename T>
		bool greater_after (const std::vector<T> & array, const T & item, int right)
			// Instantiation condition: T is a comparable type.
		{
			assert(-1 <= right); // precondition
			int i = array.size() - 1;
			while (right < i && item < array[i]) {
				--i;
			}
			return right >= i;
		}
		
		template <typename T>
		bool greaterequal_from
             (const std::vector<T> & array, const T & item, int right)
			// Instantiation condition: T is a comparable type.
		{
			assert(-1 <= right); // precondition
			int i = array.size() - 1;
			while (right <= i && item <= array[i]) {
				--i;
			}
			return right > i;
		}
		
		template <typename T>
		bool has_between_1r
             (const std::vector<T> & array, const T & item, int left, int right)
			// Instantiation condition: T is a comparable type.
		{
			assert(0 <= left);									// precondition
			assert(left <= right + 1);							// precondition
			assert(right < array.size());						// precondition
			assert(sorted_between(array, left, right));			// precondition
			assert(less_before(array, item, left));				// precondition
			assert(greater_after(array, item, right));			// precondition
			if (left > right) {
				assert(left == right + 1);
				return false;
			} else {
				assert(left <= right);
				int mid = (left + right) / 2;
				assert(left <= mid && mid <= right);
				if (item < array[mid]) {
					return has_between_1r(array, item, left, mid - 1);
				} else if (item > array[mid]) {
					return has_between_1r(array, item, mid + 1, right);
				} else {
					assert(item == array[mid]);
					return true;
				}
			}
		}
		
		template <typename T>
		bool has_1r (const std::vector<T> & array, const T & item)
			// Instantiation condition: T is a comparable type.
		{
			assert(sorted(array)); // precondition
			return has_between_1r(array, item, 0, array.size() - 1);
		}
        
		template <typename T>
		bool has_1i (const std::vector<T> & array, const T & item)
			// Instantiation condition: T is a comparable type.
		{
			assert(sorted(array)); // precondition
            int left = 0, 
                right = array.size() - 1;
			assert(0 <= left);							// loop-invariant
			assert(left <= right + 1);					// loop-invariant
			assert(right < array.size());				// loop-invariant
			assert(sorted_between(array, left, right));	// loop-invariant
			assert(less_before(array, item, left));		// loop-invariant
			assert(greater_after(array, item, right));	// loop-invariant
            while (left <= right) {
				int mid = (left + right) / 2;
				assert(left <= mid && mid <= right);
				if (item < array[mid]) {
                    right = mid - 1;
				} else if (item > array[mid]) {
                    left = mid + 1;
				} else {
					assert(item == array[mid]);
					return true;
				}
    			assert(0 <= left);							// loop-invariant
    			assert(left <= right + 1);					// loop-invariant
    			assert(right < array.size());				// loop-invariant
    			assert(sorted_between(array, left, right));	// loop-invariant
    			assert(less_before(array, item, left));		// loop-invariant
    			assert(greater_after(array, item, right));	// loop-invariant
    		}
    		assert(left == right + 1);
    		return false;
		}
        
		template <typename T>
		bool has_between_2r
             (const std::vector<T> & array, const T & item, int left, int right)
			// Instantiation condition: T is a comparable type.
		{
			assert(0 <= left);									// precondition
			assert(left <= right);			    				// precondition
			assert(right <= array.size());						// precondition
			assert(sorted_between(array, left, std::min(right, (int)array.size() - 1)));
            													// precondition
			assert(less_before(array, item, left));				// precondition
			assert(greaterequal_from(array, item, right));		// precondition
			if (left >= right) {
				assert(left == right);
				return left < array.size() && item == array[left];
			} else {
				assert(left < right);
				int mid = (left + right) / 2;
				assert(left <= mid && mid < right);
				if (item <= array[mid]) {
					return has_between_2r(array, item, left, mid);
				} else {
					assert(item > array[mid]);
					return has_between_2r(array, item, mid + 1, right);
				}
			}
		}
		
		template <typename T>
		bool has_2r (const std::vector<T> & array, const T & item)
			// Instantiation condition: T is a comparable type.
		{
			assert(sorted(array)); // precondition
			return has_between_2r(array, item, 0, array.size());
		}

		template <typename T>
		bool has_2i (const std::vector<T> & array, const T & item)
			// Instantiation condition: T is a comparable type.
		{
			assert(sorted(array)); // precondition
            int left = 0, 
                right = array.size();
			assert(0 <= left);								// loop-invariant
			assert(left <= right);			    			// loop-invariant
			assert(right <= array.size());					// loop-invariant
			assert(sorted_between(array, left, std::min(right, (int)array.size() - 1)));
            												// loop-invariant
			assert(less_before(array, item, left));			// loop-invariant
			assert(greaterequal_from(array, item, right));	// loop-invariant
            while(left < right) {
				int mid = (left + right) / 2;
				assert(left <= mid && mid < right);
				if (item <= array[mid]) {
                    right = mid;
				} else {
					assert(item > array[mid]);
					left = mid + 1;
				}
    			assert(0 <= left);							// loop-invariant
    			assert(left <= right);			    		// loop-invariant
    			assert(right <= array.size());				// loop-invariant
    			assert(sorted_between(array, left, std::min(right, (int)array.size() - 1)));
                											// loop-invariant
    			assert(less_before(array, item, left));		// loop-invariant
    			assert(greaterequal_from(array, item, right));	// loop-invariant
            }
       		assert(left == right);
  			return left < array.size() && item == array[left];
		}

        const int not_found = -1;
        
		template <typename T>
		int index_in_of_between_1r
             (const std::vector<T> & array, const T & item, int left, int right)
			// Instantiation condition: T is a comparable type.
		{
			assert(0 <= left);									// precondition
			assert(left <= right + 1);							// precondition
			assert(right < array.size());						// precondition
			assert(sorted_between(array, left, right));			// precondition
			assert(less_before(array, item, left));				// precondition
			assert(greater_after(array, item, right));			// precondition
			if (left > right) {
				assert(left == right + 1);
				return not_found;
			} else {
				assert(left <= right);
				int mid = (left + right) / 2;
				assert(left <= mid && mid <= right);
				if (item < array[mid]) {
					return index_in_of_between_1r(array, item, left, mid - 1);
				} else if (item > array[mid]) {
					return index_in_of_between_1r(array, item, mid + 1, right);
				} else {
					assert(item == array[mid]);
					return mid;
				}
			}
		}
		
		template <typename T>
		int index_in_of_1r (const std::vector<T> & array, const T & item)
			// Instantiation condition: T is a comparable type.
		{
			assert(sorted(array)); // precondition
			return index_in_of_between_1r(array, item, 0, array.size() - 1);
		}
        
		template <typename T>
		int index_in_of_1i (const std::vector<T> & array, const T & item)
			// Instantiation condition: T is a comparable type.
		{
			assert(sorted(array)); // precondition
            int left = 0, 
                right = array.size() - 1;
			assert(0 <= left);							// loop-invariant
			assert(left <= right + 1);					// loop-invariant
			assert(right < array.size());				// loop-invariant
			assert(sorted_between(array, left, right));	// loop-invariant
			assert(less_before(array, item, left));		// loop-invariant
			assert(greater_after(array, item, right));	// loop-invariant
            while (left <= right) {
				int mid = (left + right) / 2;
				assert(left <= mid && mid <= right);
				if (item < array[mid]) {
                    right = mid - 1;
				} else if (item > array[mid]) {
                    left = mid + 1;
				} else {
					assert(item == array[mid]);
					return mid;
				}
    			assert(0 <= left);							// loop-invariant
    			assert(left <= right + 1);					// loop-invariant
    			assert(right < array.size());				// loop-invariant
    			assert(sorted_between(array, left, right));	// loop-invariant
    			assert(less_before(array, item, left));		// loop-invariant
    			assert(greater_after(array, item, right));	// loop-invariant
    		}
    		assert(left == right + 1);
    		return not_found;
		}
        
		template <typename T>
		int min_index_in_of_between_2r
             (const std::vector<T> & array, const T & item, int left, int right)
			// Instantiation condition: T is a comparable type.
		{
			assert(0 <= left);									// precondition
			assert(left <= right);			    				// precondition
			assert(right <= array.size());						// precondition
			assert(sorted_between(array, left, std::min(right, (int)array.size() - 1)));
            													// precondition
			assert(less_before(array, item, left));				// precondition
			assert(greaterequal_from(array, item, right));		// precondition
			if (left >= right) {
				assert(left == right);
				return 
                    left < array.size() && item == array[left] ? left : not_found;
			} else {
				assert(left < right);
				int mid = (left + right) / 2;
				assert(left <= mid && mid < right);
				return item <= array[mid]
					? min_index_in_of_between_2r(array, item, left, mid)
				    : min_index_in_of_between_2r(array, item, mid + 1, right);
			}
		}
		
		template <typename T>
		int min_index_in_of_2r (const std::vector<T> & array, const T & item)
			// Instantiation condition: T is a comparable type.
		{
			assert(sorted(array)); // precondition
			return min_index_in_of_between_2r(array, item, 0, array.size());
		}

		template <typename T>
		int min_index_in_of_2i (const std::vector<T> & array, const T & item)
			// Instantiation condition: T is a comparable type.
		{
			assert(sorted(array)); // precondition
            int left = 0, 
                right = array.size();
			assert(0 <= left);								// loop-invariant
			assert(left <= right);			    			// loop-invariant
			assert(right <= array.size());					// loop-invariant
			assert(sorted_between(array, left, std::min(right, (int)array.size() - 1)));
            												// loop-invariant
			assert(less_before(array, item, left));			// loop-invariant
			assert(greaterequal_from(array, item, right));	// loop-invariant
            while(left < right) {
				int mid = (left + right) / 2;
				assert(left <= mid && mid < right);
				if (item <= array[mid]) {
                    right = mid;
				} else {
					assert(item > array[mid]);
					left = mid + 1;
				}
    			assert(0 <= left);							// loop-invariant
    			assert(left <= right);			    		// loop-invariant
    			assert(right <= array.size());				// loop-invariant
    			assert(sorted_between(array, left, std::min(right, (int)array.size() - 1)));
                											// loop-invariant
    			assert(less_before(array, item, left));		// loop-invariant
    			assert(greaterequal_from(array, item, right));	// loop-invariant
            }
       		assert(left == right);
  			return left < array.size() && item == array[left] ? left : not_found;
		}

		template <typename T>
		void gapsort (std::vector<T> & array) 
			// Instantiation condition: T is a comparable type.
		{
			const float shrink_factor = 1.3;
			bool swapped = true;
			int gap = array.size();
			while (swapped || gap > 1) {
				swapped = false;
				gap = std::max(int(gap / shrink_factor), 1);
				for (int index1 = 0; index1 + gap < array.size(); ++index1) {
					int index2 = index1 + gap;
					if (array[index1] > array[index2]) {
						std::swap(array[index1], array[index2]);
						swapped = true;
					};
				};
			};
			assert(sorted(array));                              // postcondition
		}

		template <typename T>
		void sort_between (std::vector<T> & array, int low, int high)
			// Instantiation condition: T is a comparable type.
		{
			assert(0 <= low && low <= high && high < 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(array, low, right);
			}
			if (left < high) {
				sort_between(array, left, high);
			}
			assert(sorted_between (array, low, high)); // postcondition
		}
		
		template <typename T>
		void quicksort (std::vector<T> & array)
		{
			sort_between(array, 0, array.size() - 1);
			assert(sorted (array)); // postcondition
		}
		  
        typedef int Comparable;
        typedef int Index;
        
    	static void sort_slice (Comparable array [], Index low, Index high) {
    		assert(low  >= 0);
    		assert(high >= 0);
    		Index			left			= low,
    					right			= high;
    		Comparable separator = array[(low + high) / 2];
    		do {
    			while (array[left] < separator) {
    				++left;
    			}
    			while (separator < array[right]) {
    				--right;
    			}
    			if (left <= right) {
    				Comparable store = array[left];
    				array[left] = array[right];
    				array[right] = store;
    				++left;
    				--right;
    			}
    		} while (left <= right);
    		if (low < right) {
    			sort_slice(array, low, right);
    		}
    		if (left < high) {
    			sort_slice(array, left, high);
    		}
    	}
    	
    	void quicksort_old (Comparable array [], Index length) {
    		assert(length > 1);
    		sort_slice(array, 0, length - 1);
    	}
	} // ToolsetArrayComparable

#endif // TOOLSET_ARRAY_COMPARABLE_M_HPP_