// © Copyright 1997. Joseph Bergin. All rights reserved.

#ifndef SearchSort_H
#define SearchSort_H

	template<class T>
	unsigned int BinarySearch
	(	T* elements,	// Array of Ts.  
		const T& t, 	// Searching for t in elements.
		unsigned int first, 	// Starting here.
		unsigned int last		// Ending here.
	)
	{	if(first >= last) return first;
		unsigned int mid = (first + last)/2; // Middle.
		if(t == elements[mid]) return mid;
		if(elements[mid] < t ) 
			return BinarySearch(elements, t, mid + 1, last);
		else 
			return BinarySearch(elements, t, first, mid - 1);
	}

	template<class T>
	T* BinarySearch
	(	const T& t, 	// Searching for t between first, after. 
		T* first,		// Array of Ts.  
		T* after
	)
	{	if(first >= after) return first;
		T* mid = first + (after - first)/2; // Middle.
		if(t == *mid) return mid;
		if(*mid < t ) 
			return BinarySearch(t, mid + 1, after);
		else 
			return BinarySearch(t, first, mid - 1);
	}

	template < class T >
	void selectionSort(T* start, T* end)
	{	for(T* where = start ; where < end ; where++)
		{	T* loc = where;
			T small = *loc;
			for(T* inner = where + 1; inner < end; inner++)
				if(*inner < *loc)
				{	loc = inner;
					small = *loc;
				}
			*loc = *where;
			*where = small;
		}
	}
	
// The next few functions are for testing ideas only
	
	template <class T>
	inline T* value_typeIT(const T*) { return (T*)(0); }
// Define one of these for each kind of iterator also

/*
template <class T, class Distance> struct random_access_iterator {};

template <class T, class Distance> 
inline T* value_type(const random_access_iterator<T, Distance>&) {
    return (T*)(0);
}
*/

	template < class iterator, class T >
	void selectionSort_aux (iterator start, iterator end, T*)
	{	for(iterator where = start ; where < end ; where++)
		{	iterator loc = where;
			T small = *loc;
			for(iterator inner = where + 1; inner < end; inner++)
				if(*inner < *loc)
				{	loc = inner;
					small = *loc;
				}
			*loc = *where;
			*where = small;
		}
	}
	
/*	template < class iterator >
		void selectionSortIT (iterator start, iterator end)
		{	selectionSort_aux(start, end, value_typeIT(start));
		} // the _aux function does the work. 
*/
	template < class iterator >
		void selectionSortIT (iterator start, iterator end)
		{	selectionSort_aux(start, end, &(*start));
		} // the _aux function does the work. 

	template<class iterator, class T> // random access iterator with
		// value type T with operator< and operator==
	iterator BinarySearchIT
	(	const T& t, 	// Searching for t between first, after. 
		iterator first,	 
		iterator after
	)
	{	if(first >= after) return first;
		iterator mid = first + (after - first)/2; // Middle.
		if(t == *mid) return mid;
		if(*mid < t ) 
			return BinarySearch(t, mid + 1, after);
		else 
			return BinarySearch(t, first, mid /* -1 */);
	}


#endif