#include <cstdlib>
#include <algorithm>
#include <vector>
#include <windows.h>

namespace
{
	inline unsigned __int64 sampleTicks()
	{
		unsigned __int64 result;
		QueryPerformanceCounter( (LARGE_INTEGER*)&result );
		return result;
	}
	
	inline float deltaTimeMS( unsigned __int64 stop, unsigned __int64 start )
	{
		const float diff = (float)(unsigned long)(stop - start);
		unsigned __int64 freq;
		QueryPerformanceFrequency( (LARGE_INTEGER*)&freq );	
		return diff * 1000.0f / (float)freq;
	}
}

namespace 
{ 
	enum 
	{ 
		// For each test run, generate an array of this size to sort.
		kValuesSize = 1024*1024*3
	}; 
}

static int oldStyleCompare( const void* a_, const void* b_ )
{
	const float a = *(float*)a_;
	const float b = *(float*)b_;

	if( a < b )
		return -1;
	if( a > b )
		return 1;
	return 0;
}

void doOldSort( float* begin, float* end )
{
	std::qsort((void*)begin, end-begin, sizeof(begin[0]), oldStyleCompare);
}

namespace
{
	struct NewCompare
	{
		bool operator()( const float a, const float b ) const
		{
			return a < b;
		}
		
		static bool compare( const float a, const float b );
	};
	
	bool NewCompare::compare( const float a, const float b )
	{
		return a < b;
	}
}

void doNewSort( float* begin, float* end )
{
	std::sort(begin, end, NewCompare());
}

void doOldNewSort( float* begin, float* end )
{
	std::sort(begin, end, &NewCompare::compare);
}

void fuckOverCache()
{
	std::vector< int > boo(1024*1024);
	std::fill(boo.begin(), boo.end(), 99);
}

std::vector< float > createValues( int size )
{
	std::vector< float > values(size);
	std::generate(values.begin(), values.end(), std::rand);
	return values;
}

void doTest( void (*technique)(float*, float*), const char* message )
{
	std::vector< float > values = createValues( kValuesSize );
	fuckOverCache();

	Sleep(0);
	const unsigned __int64 start = sampleTicks();
	
	technique( &values[0], &values[0] + values.size() );
	
	const unsigned __int64 stop = sampleTicks();
	std::printf( "%6.2f ms, %s \n", deltaTimeMS(stop, start), message );
}

int main( int, char** )
{
	for( int i=0; i < 10; i++ )
	{
		doTest( doOldSort, "std::qsort");
		doTest( doNewSort, "std::sort, inline functor");
		doTest( doOldNewSort, "std::sort function call");
		
		std::printf( "\n" );
	}
	return 0;
}