// © Copyright 1995, Joseph Bergin. All rights reserved.

#include "Array.h"

// Require class T to have < and <= defined.  

template <class T>
class SortableArray: public Array<T>
{	public:
		SortableArray(unsigned int size = ArrayDefaultLength)
		:	Array<T>(size)
		{
		}
		
		SortableArray(unsigned int size, T t)
		:	Array<T>(size,t)
		{
		}
		
		SortableArray(const Array<T> &a) {copy(a);} // copy constructor
			// We can create a sortable array from an ordinary array,
			// but, of course they must have the same element type. 
			
		SortableArray<T> & operator = (const Array<T> &a) // Copy semantics. 
			// We can assign an ordinary array to a sortable array,
			// but, of course they must have the same element type. 
			
		{	Array<T>::operator=(a);
			return *this; 
		}

		void selectionSort()
		{	unsigned int len = length();
			for(int i = 0; i < len - 1; ++i)
			{	int s = i;
				T small = _elements[s];
				for(unsigned j = i + 1; j < len; ++j)
					if(_elements[j] < small)
					{	s = j;
						small = _elements[s];
					}
				_elements[s] = _elements[i];
				_elements[i] = small;
			}
		}
		
		void quickSort(unsigned int first, unsigned int last)
		{	if(last >= length()) userERROR("Subscript error in QuickSort");
			if(first < last)
			{	T t = _elements[first];
				unsigned lastLow = first;
				for (unsigned i = first + 1; i <= last; i++)
					if(_elements[i] < t)
					{	++lastLow;
						swap(lastLow, i);
					}
				swap(first, lastLow);
				if(lastLow != 0) quickSort(first, lastLow - 1);
				quickSort(lastLow + 1,last);
			}
		}
		
		unsigned int binarySearch(const T& t, unsigned int first, unsigned int last)
		{	if(first >= last) return first;
			unsigned int mid = (first + last)/2;
			if(t == _elements[mid]) return mid;
			if(t > _elements[mid]) return binarySearch(t, mid + 1, last);
			else return binarySearch(t, first, mid - 1);
		}
		
	private:

};

// To add. 	SortableArray<T> merge(SortableArray<T>); // Assume both sorted
//			T minimum(); // Don't assume sorted.
//			A minimum over a range would be even better.//Default the entire array.
//			T maximum(); // Don't assume sorted.
//			unsigned int search(T);  // Don't assume sorted.
				// Returns length+1 if not found.
//			unsigned int binarySearch(T); // Assume sorted. 
				// Returns length+1 if not found.