// Testing performance of std::set vs. std::vector
// By Sean Heber <sean at fifthace.com>
// http://www.bigzaphod.org/
// License: Public Domain
// December 2005

#include <iostream>
#include <vector>
#include <set>
#include <sys/time.h>

static struct _ticks_global {
        struct timeval start;
        _ticks_global() { gettimeofday(&start, NULL); }
} ticks_global;

unsigned int ticks()
{
    struct timeval now;
    gettimeofday(&now, NULL);
    return (now.tv_sec-ticks_global.start.tv_sec)*1000+(now.tv_usec-ticks_global.start.tv_usec)/1000;
}

int main( int argc, char* argv[] )
{
	const int		SIZE_OF_ARRAY = argc>1? strtol(argv[1], NULL, 10): 10;
	const int		NUMBER_OF_TESTS = argc>2? strtol(argv[2], NULL, 10): 100;
	const int		NUMBER_OF_CYCLES = argc>3? strtol(argv[3], NULL, 10): 1000;
	std::set<int>		int_set;
	std::vector<int>	int_vec;
	std::vector<int>	set_time, vec_time;
	int			blah;

	std::cout << SIZE_OF_ARRAY << " elements in each container." << std::endl;
	std::cout << "Running " << NUMBER_OF_TESTS << " tests with " << NUMBER_OF_CYCLES << " cycles each." << std::endl;

	// put initial data into the containers for fetching later
	for( int i=0; i< SIZE_OF_ARRAY; i++ ) {
		int_set.insert( i );
		int_vec.push_back( i );
	}

	// this runs the main test for the specified number of times and cycles
	// note that I'm searching between -1 and 1+SIZE_OF_ARRAY in each test
	// the idea is to fairly take into account the worst case scenerio of
	// a number not appearing in the container

	for( int z=0; z<NUMBER_OF_TESTS; z++ ) {
		int t = ticks();
		int c;
		for( c=0; c<NUMBER_OF_CYCLES; c++ ) {
			int j;
			for( j=-1; j<SIZE_OF_ARRAY+1; j++ ) {
				std::set<int>::iterator n = int_set.find( j );
				if( n != int_set.end() )
					blah = *n;
			}
			for( j=SIZE_OF_ARRAY+1; j>-1; j-- ) {
				j--;
				std::set<int>::iterator n = int_set.find( j );
				if( n != int_set.end() )
					blah = *n;
			}
		}
		set_time.push_back( ticks()-t );
		t = ticks();
		for( c=0; c<NUMBER_OF_CYCLES; c++ ) {
			int j;
			for( j=-1; j<SIZE_OF_ARRAY+1; j++ ) {
				std::vector<int>::iterator i;
				for( i=int_vec.begin(); i!=int_vec.end(); i++ )
					if( *i == j )
						break;
				if( i != int_vec.end() )
					blah = *i;
			}
			for( j=SIZE_OF_ARRAY+1; j>-1; j-- ) {
				j--;
				std::vector<int>::iterator i;
				for( i=int_vec.begin(); i!=int_vec.end(); i++ )
					if( *i == j )
						break;
				if( i != int_vec.end() )
					blah = *i;
			}
		}
		vec_time.push_back( ticks()-t );
	}

	// using blah to make sure the compiler doesn't optimize it out of the equation
	while( blah ) blah--;

	std::vector<int>::iterator i;
	double set_avg, vec_avg;
	set_avg = vec_avg = 0;

	for( i=set_time.begin(); i!=set_time.end(); i++ ) 
		set_avg += *i;
	set_avg /= (double)set_time.size();

	for( i=vec_time.begin(); i!=vec_time.end(); i++ ) 
		vec_avg += *i;
	vec_avg /= (double)vec_time.size();

	std::cout << "Average per test for SET:\t" << set_avg << " ms";
	if( set_avg < vec_avg ) std::cout << " [winner]";
	std::cout << std::endl;
	std::cout << "Average per test for VECTOR:\t" << vec_avg << " ms";
	if( vec_avg < set_avg ) std::cout << " [winner]";
	std::cout << std::endl;

	return 0;
}