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

// Helper class.
class Timer
{
public:
	Timer()
		: tick(0)
	{
		SetThreadAffinityMask( GetCurrentThread(), 1 );	// Tries to prevent this thread from jumping around.
		Sleep(0); // When we wake up, we're hopefully at the beginning of a timequantum.
	}
	
	void sample()
	{
		LARGE_INTEGER tick;
		QueryPerformanceCounter(&tick);
		
		this->deltaTicks = (tick.QuadPart - this->tick);
		if( this->deltaTicks < 0 )
			this->deltaTicks = 0;
		this->tick = tick.QuadPart;
	}
	
	float deltaTime() const
	{
		LARGE_INTEGER freq;
		QueryPerformanceFrequency( &freq );
		return float(double(this->deltaTicks) / double(freq.QuadPart));	// Dubious casting of the floats here...
	}
	
	__int64 tick;
	__int64 deltaTicks;
};

volatile int acc = 0;

typedef std::vector< std::pair< int, int > > Vector;

void runVectorTest( int count )
{
	Vector values;
	values.reserve(count);
	
	for( int i=0; i < count; i++ )
		values.push_back( Vector::value_type(i, rand()) );


	Vector::value_type* begin = &values[0];
	
	Timer timer;
	timer.sample();

	for( int i=0; i < count; i++ )
		acc += begin[i].second;

	//Actually slower. Generates more calls.
	//Vector::const_iterator it = values.begin();
	//Vector::const_iterator end = values.end();
	//for( ; it != end; ++it )
	//	acc += it->second;
			
	timer.sample();
	//printf( "Acc = %d\n", acc ); // prevent the compiler to discard the acc variable. Really.
	printf( "Vector iterator           %8.2f ms\n", timer.deltaTime() * 1000.0f );
}

typedef std::map< int, int > Map;
void runMapTest( int count )
{
	Map values;
	
	for( int i=0; i < count; i++ )
		values.insert( Map::value_type(i, rand()) );

	Timer timer;
	timer.sample();

	Map::const_iterator end = values.end();
	for( Map::const_iterator it = values.begin(); it != end; ++it )
		acc += it->second;
	
	timer.sample();
	//printf( "Acc = %d\n", acc ); // prevent the compiler to discard the acc variable. Really.
	printf( "Map iterator              %8.2f ms\n", timer.deltaTime() * 1000.0f );
}

struct FirstPairCompare
{
	bool operator()( const Vector::value_type& lhs, const Vector::value_type& rhs )
	{
		return lhs.first < rhs.first;
	}
};

void runVectorInsert( int count, const std::vector<int>& order )
{
	Vector values;
	values.reserve(count);
	
	Timer timer;
	timer.sample();
	
	for( int i=0; i < count; i++ )
	{
		Vector::value_type value(order[i], rand());
		std::pair<Vector::iterator, Vector::iterator> result = 
			std::equal_range( values.begin(), values.end(), value, FirstPairCompare() );
		values.insert(result.second, value);
	}
	
	timer.sample();
	printf( "Vector insert             %8.2f ms\n", timer.deltaTime() * 1000.0f );
}

void runVectorFind( int count, const std::vector<int>& order )
{
	Vector values;
	values.reserve(count);
	
	for( int i=0; i < count; i++ )
	{
		Vector::value_type value(order[i], rand());
		std::pair<Vector::iterator, Vector::iterator> result = 
			std::equal_range( values.begin(), values.end(), value, FirstPairCompare() );
		values.insert(result.second, value);
	}

	Timer timer;
	timer.sample();
	for( int i=0; i < count; i++ )
	{
		Vector::value_type value(order[i], 0);
		std::pair<Vector::iterator, Vector::iterator> result = 
			std::equal_range( values.begin(), values.end(), value, FirstPairCompare() );
		acc += result.first->second;
	}
	
	timer.sample();
	printf( "Vector find               %8.2f ms\n", timer.deltaTime() * 1000.0f );
}

void runMapInsert( int count, const std::vector<int>& order )
{
	Map values;
	
	Timer timer;
	timer.sample();
	
	for( int i=0; i < count; i++ )
	{
		Map::value_type value(order[i], rand());
		values.insert(value);
	}
	
	timer.sample();
	printf( "Map insert                %8.2f ms\n", timer.deltaTime() * 1000.0f );
}

void runVMapFind( int count, const std::vector<int>& order )
{
	Map values;
	
	for( int i=0; i < count; i++ )
	{
		Map::value_type value(order[i], rand());
		values.insert(value);
	}

	Timer timer;
	timer.sample();
	
	for( int i=0; i < count; i++ )
	{
		Map::iterator it = values.find(order[i]);
		acc += it->second;
	}
	
	timer.sample();
	printf( "Map find                  %8.2f ms\n", timer.deltaTime() * 1000.0f );
}


int __cdecl main()
{
	volatile int countTimes = 1024*50;
	
	std::vector<int> order(countTimes);
	for( int i=0; i < countTimes; i++ )
		order[i] = i;
	std::random_shuffle( order.begin(), order.end() );
	
	runVectorInsert(countTimes, order);
	runMapInsert(countTimes, order);
	runVectorFind(countTimes, order);
	runVMapFind(countTimes, order);
	
	runVectorTest(countTimes);
	runMapTest(countTimes);
}


/*
Sample results on my machine:

	Vector insert              1807.95 ms
	Map insert                   57.14 ms
	Vector find                  24.12 ms
	Map find                     27.58 ms
	Vector iterator               0.25 ms
	Map iterator                  1.90 ms

*/