/*
    Copyright 2007-2008 Adobe Systems Incorporated
    Distributed under the MIT License (see accompanying file LICENSE_1_0_0.txt
    or a copy at http://stlab.adobe.com/licenses.html )
	

	This test file started life as 
		ISO/IEC TR 18015:2006(E) Appendix D.4


Goals:
	
	Compare the performance of function pointers, functors, inline functors,
		standard functors, and native comparison operators

	Also compare the performance of qsort(), quicksort template, and std::sort


Assumptions:
	
	1) inline functors, standard functors and inlined native
		comparisons will perform similarly
	
	2) using functors is faster than using function pointers
	
	3) inline functors are as fast or faster than out of line functors
	
	4) a template is at least as fast as a hard coded function of
		the same algorithm, sometimes faster
	
	5) std::sort is faster than qsort()
	
	6) std::sort is faster than a naive quicksort template using the same functor


Since qsort's comparison function must return int (less than 0, 0, greater than 0)
	and std::sort's must return a bool, it is not possible to test them with each
	other's comparator.

*/


/******************************************************************************/

#include <functional>
#include <algorithm>
#include <cstdlib>
#include "benchmark_results.h"
#include "benchmark_timer.h"

using namespace std;

/******************************************************************************/

template <class Iterator>
void verify_sorted(Iterator first, Iterator last) {
	Iterator prev = first;
	first++;
	while (first != last) {
		if (*first++ < *prev++) {
			printf("test %i failed\n", current_test);
			break;
		}
	}
}

/******************************************************************************/
// --------- helper functions --------------------------------------------

// qsort passes void * arguments to its comparison function,
// which must return negative, 0, or positive value
int
less_than_function1( const void * lhs, const void * rhs )
	{
	if( *(const double *) lhs < *(const double *) rhs ) return -1;
	if( *(const double *) lhs > *(const double *) rhs ) return 1;
	return 0;
	}

// std::sort, on the other hand, needs a comparator that returns true or false
bool
less_than_function2( const double lhs, const double rhs )
	{
	return( lhs < rhs? true : false );
	}

// the comparison operator in the following functor is defined out of line
struct less_than_functor
{
	bool operator()( const double& lhs, const double& rhs ) const;
};

bool
less_than_functor::operator()( const double& lhs, const double& rhs ) const
	{
	return( lhs < rhs? true : false );
	}

// the comparison operator in the following functor is defined inline
struct inline_less_than_functor
{
	inline bool operator()( const double& lhs, const double& rhs ) const
		{
		return( lhs < rhs? true : false );
		}
};

/******************************************************************************/

// hard coded comparison function
template<class Iterator>
void quicksort(Iterator begin, Iterator end)
{
	// this only works for pointers and STL iterators
	typedef typename iterator_traits<Iterator>::value_type T;
	
	if ( (end - begin) > 1 ) {

		T middleValue = *begin;
		Iterator left = begin;
		Iterator right = end;

		for(;;) {

			while ( middleValue < *(--right) );
			if ( !(left < right ) ) break;
			
			while ( *(left) < middleValue )
				++left;
			if ( !(left < right ) ) break;

			// swap
			T temp = *right;
			*right = *left;
			*left = temp;
		}
		
		quicksort( begin, right + 1 );
		quicksort( right + 1, end );
	}
}

/******************************************************************************/

// comparison function passed in as a functor
template<class Iterator, typename Comparator>
void quicksort(Iterator begin, Iterator end, Comparator compare)
{
	// this only works for pointers and STL iterators
	typedef typename iterator_traits<Iterator>::value_type T;
	
	if ( (end - begin) > 1 ) {

		T middleValue = *begin;
		Iterator left = begin;
		Iterator right = end;

		for(;;) {

			while ( compare( middleValue, *(--right) ) );
			if ( !(left < right ) ) break;
			while ( compare( *(left), middleValue ) )
				++left;
			if ( !(left < right ) ) break;

			// swap
			T temp = *right;
			*right = *left;
			*left = temp;
		}
		
		quicksort( begin, right + 1, compare );
		quicksort( right + 1, end, compare );
	}
}

/******************************************************************************/

typedef bool comparator_function( const double x, const double y );

// use a pointer to function as a template parameter
// exact function is known at compile time, and can be inlined
template<class Iterator, comparator_function compare>
void quicksort(Iterator begin, Iterator end)
{
	// this only works for pointers and STL iterators
	typedef typename iterator_traits<Iterator>::value_type T;
	
	if ( (end - begin) > 1 ) {

		T middleValue = *begin;
		Iterator left = begin;
		Iterator right = end;

		for(;;) {

			while ( compare( middleValue, *(--right) ) );
			if ( !(left < right ) ) break;
			while ( compare( *(left), middleValue ) )
				++left;
			if ( !(left < right ) ) break;

			// swap
			T temp = *right;
			*right = *left;
			*left = temp;
		}
		
		quicksort( begin, right + 1, compare );
		quicksort( right + 1, end, compare );
	}
}

/******************************************************************************/

// use a function pointer
// most compilers will not inline the function argument
void quicksort_function(double* begin, double* end, comparator_function compare)
{
	if ( (end - begin) > 1 ) {

		double middleValue = *begin;
		double* left = begin;
		double* right = end;

		for(;;) {

			while ( compare( middleValue, *(--right) ) );
			if ( !(left < right ) ) break;
			while ( compare( *(left), middleValue ) )
				++left;
			if ( !(left < right ) ) break;

			// swap
			double temp = *right;
			*right = *left;
			*left = temp;
		}
		
		quicksort( begin, right + 1, compare );
		quicksort( right + 1, end, compare );
	}
}

/******************************************************************************/

int main(int argc, char* argv[])
{
	int i;
#ifdef SMALL_PROBLEM_SIZE
	int iterations = (1 < argc) ? atoi(argv[1]) : 30; // number of iterations
#else
	int iterations = (1 < argc) ? atoi(argv[1]) : 300; // number of iterations
#endif
	int tablesize = (2 < argc) ? atoi(argv[2]) : 10000; // size of array
	
	
	// seed the random number generator, so we get repeatable results
	srand( tablesize + 123 );
	
	
	// initialize the table to sort
	double * master_table = new double[tablesize];
	for( int n = 0; n < tablesize; ++n )
		{
		master_table[n] = static_cast<double>( rand() );
		}
	
	double * table = new double[tablesize]; // working copy
	
	
	// here is where the timing starts
	
	for (i = 0; i < iterations; ++i)
		{
		copy(master_table, master_table+tablesize, table);
		qsort( table, tablesize, sizeof(double), less_than_function1 );
		verify_sorted( table, table + tablesize );
		}
	
	for (i = 0; i < iterations; ++i)
		{
		copy(master_table, master_table+tablesize, table);
		quicksort_function( table, table + tablesize, less_than_function2 );
		verify_sorted( table, table + tablesize );
		}
	
	for (i = 0; i < iterations; ++i)
		{
		copy(master_table, master_table+tablesize, table);
		quicksort( table, table + tablesize, less_than_function2 );
		verify_sorted( table, table + tablesize );
		}
	
	for (i = 0; i < iterations; ++i)
		{
		copy(master_table, master_table+tablesize, table);
		quicksort<double *, less_than_function2 >( table, table + tablesize  );
		verify_sorted( table, table + tablesize );
		}

	for (i = 0; i < iterations; ++i)
		{
		copy(master_table, master_table+tablesize, table);
		sort( table, table + tablesize, less_than_function2 );
		verify_sorted( table, table + tablesize );
		}

	for (i = 0; i < iterations; ++i)
		{
		copy(master_table, master_table+tablesize, table);
		quicksort( table, table + tablesize, less_than_functor() );
		verify_sorted( table, table + tablesize );
		}
	
	for (i = 0; i < iterations; ++i)
		{
		sort( table, table + tablesize, less_than_functor() );
		verify_sorted( table, table + tablesize );
		copy(master_table, master_table+tablesize, table);
		}

	for (i = 0; i < iterations; ++i)
		{
		copy(master_table, master_table+tablesize, table);
		quicksort( table, table + tablesize, inline_less_than_functor() );
		verify_sorted( table, table + tablesize );
		}
	
	for (i = 0; i < iterations; ++i)
		{
		copy(master_table, master_table+tablesize, table);
		sort( table, table + tablesize, inline_less_than_functor() );
		verify_sorted( table, table + tablesize );
		}
	
	for (i = 0; i < iterations; ++i)
		{
		copy(master_table, master_table+tablesize, table);
		quicksort( table, table + tablesize, less<double>() );
		verify_sorted( table, table + tablesize );
		}
	
	for (i = 0; i < iterations; ++i)
		{
		copy(master_table, master_table+tablesize, table);
		sort( table, table + tablesize, less<double>() );
		verify_sorted( table, table + tablesize );
		}
	
	for (i = 0; i < iterations; ++i)
		{
		copy(master_table, master_table+tablesize, table);
		quicksort( table, table + tablesize );
		verify_sorted( table, table + tablesize );
		}

	for (i = 0; i < iterations; ++i)
		{
		copy( master_table, master_table+tablesize, table );
		sort( table, table + tablesize );
		verify_sorted( table, table + tablesize );
		}
	
	
	delete[] table;
	delete[] master_table;
	
	return 0;
}