#include "vecsortedpair.h"
#include "sarray.h"
#include "stl_vector.h"


//=======================================================================================
// explicit template instantiation for testing :

template vecsortedpair< std::vector< std::pair<int,int> > >;
template multivecsortedpair< std::vector< std::pair<int,int> > >;

//=======================================================================================

void vecsortedpair_test()
{
	struct Local
	{
	static void printintpair(const std::pair<int,int> & p)
	{
		printf("%d:%d,",p.first,p.second);
	}
	};

	{
		vecsortedpair< std::vector< std::pair<int,int> > > vsp;

		vsp.insert( std::make_pair(1,-1) );
		vsp.insert( std::make_pair(7,-7) );
		vsp.insert( std::make_pair(3,-3) );
		vsp.insert( 5,-5 );
		vsp.insert( -2,2 );
		vsp.insert( 13,-13 );

		puts("X");

		std::for_each(vsp.begin(),vsp.end(),Local::printintpair);

		puts("X");

		Local::printintpair( *( vsp.find(5) ) );
		Local::printintpair( *( vsp.find(3) ) );
		
		puts("X");
	}

	{
		vecsortedpair< sarray< std::pair<int,int> ,32> > vsp;

		vsp.insert( std::make_pair(1,-1) );
		vsp.insert( std::make_pair(7,-7) );
		vsp.insert( std::make_pair(3,-3) );
		vsp.insert( 5,-5 );
		vsp.insert( -2,2 );
		vsp.insert( 13,-13 );

		puts("X");

		std::for_each(vsp.begin(),vsp.end(),Local::printintpair);

		puts("X");

		Local::printintpair( *( vsp.find(5) ) );
		Local::printintpair( *( vsp.find(3) ) );
		
		puts("X");
	}
	
	{
	
		typedef vecsortedpair< sarray< std::pair<int,int> ,32> > t_vsp32;
		typedef vecsortedpair< sarray< std::pair<int,int> ,64> > t_vsp64;

		t_vsp32 vsp;

		vsp.insert( std::make_pair(1,-1) );
		vsp.insert( std::make_pair(7,-7) );
		vsp.insert( std::make_pair(3,-3) );
		vsp.insert( 5,-5 );
		vsp.insert( -2,2 );
		vsp.insert( 13,-13 );

		puts("X");

		std::for_each(vsp.begin(),vsp.end(),Local::printintpair);

		puts("X");

		Local::printintpair( *( vsp.find(5) ) );
		Local::printintpair( *( vsp.find(3) ) );
		
		puts("X");

		t_vsp64 vsp2(vsp.begin(),vsp.end(),vecsorted_construct::sorted);

	}
}

//=======================================================================================

#include "gString.h"
#include "gTimer.h"

#include <map>
#include <hash_map>

typedef std::multimap<int,const gString *>		t_mapIntString;
typedef multivecsortedpair< std::vector< std::pair<int,const gString *> > >	t_vecIntString;
typedef std::hash_multimap<int,const gString *>		t_hmapIntString;

void vecsortedpair_map_compare()
{
	/*
	the STLport string and hash_map both leak like seives in release mode !!
	presumably due to funky allocators !!
	*/

	const gString s_numbers[] =
	{
		gString( "zero" ),
		gString( "one" ),
		gString( "two" ),
		gString( "three" ),
		gString( "four" ),
		gString( "five" ),
		gString( "six" ),
		gString( "seven" ),
		gString( "eight" ),
		gString( "nine" ),
		gString( "ten" ),
	};

	t_vecIntString  avec;
	t_mapIntString  amap;
	t_hmapIntString ahash;

	int i;

	static const int num_add    = 100;
	static const int range_add  = 2000;
	static const int range_find = 2000;
	#ifdef _DEBUG
	static const int num_find = 10000;
	#else
	static const int num_find = 10000000;
	#endif

	for(i=0;i<num_add;i++)
	{
		int k = rand() % range_add;
		int j = k % 10;

		avec.insert( std::make_pair(k,&s_numbers[j]) );
		amap.insert( std::make_pair(k,&s_numbers[j]) );
		ahash.insert( std::make_pair(k,&s_numbers[j]) );
	}

	int foundCount;
	foundCount =0 ;
	srand(0);
	
	{
	gTimer::AutoTimer at("vec Finds");
		
		int j = 0;
		for(i=0;i<num_find;i++)
		{
			if ( ++j == range_find ) j = 0;
			t_vecIntString::const_iterator it = avec.find(j);
			if ( it != avec.end() )
				foundCount++;
		}

	}

	printf("foundCount = %d\n",foundCount);

	foundCount =0 ;
	srand(0);
	
	{
	gTimer::AutoTimer at("map Finds");
		
		int j = 0;
		for(i=0;i<num_find;i++)
		{
			if ( ++j == range_find ) j = 0;
			t_mapIntString::iterator it = amap.find(j);
			if ( it != amap.end() )
				foundCount++;
		}

	}

	printf("foundCount = %d\n",foundCount);
	foundCount =0 ;
	srand(0);

	{
	gTimer::AutoTimer at("hash Finds");
		
		int j = 0;
		for(i=0;i<num_find;i++)
		{
			if ( ++j == range_find ) j = 0;
			t_hmapIntString::iterator it = ahash.find(j);
			if ( it != ahash.end() )
				foundCount++;
		}
	}

	/**
	
	STLport 4.0 :
	8-1-01
	---------------------------------------

	num_add = 20000;
	range_add = 20000;
	range_find = 30000;

	vec Finds : 0.2427 seconds
	map Finds : 0.3032 seconds
	hash Finds : 0.2117 seconds

	num_add = 2000;
	range_add = 20000;
	range_find = 30000;

	vec Finds : 0.1688 seconds
	map Finds : 0.1500 seconds
	hash Finds : 0.1357 seconds

	num_add = 100;
	range_add = 20000;
	range_find = 30000;

	vec Finds : 0.1184 seconds
	map Finds : 0.1083 seconds
	hash Finds : 0.1218 seconds

	num_add = 1000;
	range_add = 2000;
	range_find = 2000;

	vec Finds : 0.1980 seconds
	map Finds : 0.1831 seconds
	hash Finds : 0.1375 seconds

	num_add    = 100;
	range_add  = 2000;
	range_find = 2000;

	vec Finds : 1.2547 seconds
	map Finds : 1.2118 seconds
	hash Finds : 1.2823 seconds

	**/

	printf("foundCount = %d\n",foundCount);

	puts("press a key");
	getc(stdin);
}

//=======================================================================================

void vecsortedpair_map_compare2()
{
	/*

	many small maps :

	*/

	static const int num_maps = 100;
	static const int num_map_finds = 50;
	static const int num_add = 30;
	static const int range_add = 50;
	static const int range_find = 50;

	#ifdef _DEBUG
	static const int num_find = 100;
	#else
	static const int num_find = 100000;
	#endif

	const gString s_numbers[] =
	{
		gString( "zero" ),
		gString( "one" ),
		gString( "two" ),
		gString( "three" ),
		gString( "four" ),
		gString( "five" ),
		gString( "six" ),
		gString( "seven" ),
		gString( "eight" ),
		gString( "nine" ),
		gString( "ten" ),
	};

	t_vecIntString akey[num_maps];
	t_mapIntString  amap[num_maps];
	t_hmapIntString	ahash[num_maps];

	int i,nmap;


	for(nmap = 0;nmap<num_maps;nmap++)
	{
		for(i=0;i<num_add;i++)
		{
			int k = rand() % range_add;
			int j = k % 10;

			akey[nmap].insert(  std::make_pair(k,&s_numbers[j]) );
			amap[nmap].insert(  std::make_pair(k,&s_numbers[j]) );
			ahash[nmap].insert( std::make_pair(k,&s_numbers[j]) );
		}
	}

	int foundCount;
	foundCount =0 ;
	srand(0);
	
	{
	gTimer::AutoTimer at("vec Finds");
		
		int j = 0;
		for(i=0;i<num_find;i++)
		{
			j += 13; if ( j >= range_find ) j -= range_find;

			int nmap = 0;
			for(int imap=0;imap<num_map_finds;imap++)
			{
				nmap += 17; if ( nmap >= num_maps ) nmap -= num_maps;

				t_vecIntString::const_iterator it = akey[nmap].find(j);
				if ( it != akey[nmap].end() )
					foundCount++;
			}
		}
	}

	printf("foundCount = %d\n",foundCount);

	foundCount =0 ;
	srand(0);
	
	{
	gTimer::AutoTimer at("map Finds");
		
		int j = 0;
		for(i=0;i<num_find;i++)
		{
			j += 13; if ( j >= range_find ) j -= range_find;

			int nmap = 0;
			for(int imap=0;imap<num_map_finds;imap++)
			{
				nmap += 17; if ( nmap >= num_maps ) nmap -= num_maps;

				t_mapIntString::iterator it = amap[nmap].find(j);
				if ( it != amap[nmap].end() )
					foundCount++;
			}
		}
	}

	printf("foundCount = %d\n",foundCount);
	foundCount =0 ;
	srand(0);

	{
	gTimer::AutoTimer at("hash Finds");
		
		int j = 0;
		for(i=0;i<num_find;i++)
		{
			j += 13; if ( j >= range_find ) j -= range_find;

			int nmap = 0;
			for(int imap=0;imap<num_map_finds;imap++)
			{
				nmap += 17; if ( nmap >= num_maps ) nmap -= num_maps;

				t_hmapIntString::iterator it = ahash[nmap].find(j);
				if ( it != ahash[nmap].end() )
					foundCount++;
			}
		}
	}

	printf("foundCount = %d\n",foundCount);

	/**

	STLport 4.0 :
	8-1-01
	---------------------------------------

	num_maps = 1000;
	num_map_finds = 500;
	num_add = 10;
	range_add = 20;
	range_find = 30;

	vec Finds : 0.5277 seconds
	map Finds : 0.7630 seconds
	hash Finds : 0.6697 seconds

	num_maps = 100;
	num_map_finds = 500;
	num_add = 10;
	range_add = 20;
	range_find = 30;

	vec Finds : 0.4990 seconds
	map Finds : 0.5496 seconds
	hash Finds : 0.5102 seconds

	num_maps = 100;
	num_map_finds = 50;
	num_add = 100;
	range_add = 200;
	range_find = 300;

	vec Finds : 0.8190 seconds
	map Finds : 1.0017 seconds
	hash Finds : 0.5914 seconds

	num_maps = 100;
	num_map_finds = 50;
	num_add = 30;
	range_add = 50;
	range_find = 50;

	vec Finds : 0.7281 seconds
	map Finds : 0.7850 seconds
	hash Finds : 0.5774 seconds

	**/

	puts("press a key");
	getc(stdin);
}

//=======================================================================================