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

#ifndef ALGO_JB_H
#define ALGO_JB_H

//using namespace stl;

template <class T, class Iterator>
void mapIT(void (*f)(T&), Iterator begin, Iterator end)
{	if(begin < end)
	{	f(*begin);
		begin++;
		mapIT(f, begin, end);
	}
}

template < class T, class Iterator >
Iterator min_aux(T &v, Iterator start, Iterator last)
// PRE: non empty range required. 
{	if(start+1 == last) return start;
	T first = *start;
	Iterator rest = min_aux(v, start+1, last);
	if(first < *rest || first == *rest) return start;
	return rest;
}

template <class Iterator>
inline Iterator min_i(Iterator start, Iterator last)
{	return min_aux(*start, start, last);
}

template <class Iterator>
void partition_aux(Iterator b, Iterator& m, Iterator e)
{	Iterator J = b; ++J;
	m=b;
	while(J != e)
	{	if(*J < *b) 
		{	m++;
			swap(*m, *J);
		}
		J++;
	}
	swap(*m, *b);
}


template <class RandomAccessIterator>
void quickSort(RandomAccessIterator begin, RandomAccessIterator end)
{	if(begin < end -1)
	{	RandomAccessIterator t;
		partition_aux(begin, t, end);
		quickSort(begin, t);
		quickSort(t+1, end);
	}
}

template <class Iterator>
void median_aux(Iterator b, Iterator e, Iterator mid)
{	if(b<e-1 && mid>=b && mid<e)
	{	Iterator t;
		partition_aux(b, t, e);
		if(t<mid)
			median_aux(t+1, e, mid);
		else if(t>mid)
			median_aux(b, t, mid);
	}
}

template <class RandomAccessIterator>
inline void median(RandomAccessIterator begin, RandomAccessIterator end)
// Rearranges the range so that the median is in its proper (middle) location.
// Elements to the left of the middle are less than the median.
// Elements to the right of the middle are greater than the median.
// Does not otherwise sort.  Linear running time.
{	median_aux(begin, end, begin + (end-begin)/2);
}

template <class RandomAccessIterator>
// Rearranges the range so that the percentile requested is in its proper location.
// Elements to the left of this element are less than the it.
// Elements to the right of this element are greater than it is.
// Does not otherwise sort.  Linear running time.
// Precondition: percentile is > 0  is < 100.
inline void order_statistic(float percentile, RandomAccessIterator begin, RandomAccessIterator end)
{	median_aux(begin, end, begin + percentile * (end-begin)/100.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 RandomAccessIterator >
inline void selectionSortIT (RandomAccessIterator start, RandomAccessIterator end)
{	selectionSort_aux(start, end, &(*start));
} // the _aux function does the work. 

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

}


#endif