// this program is to benchmark different map implementations on different key
// types

#include <map>
#include <tr1/unordered_map>
#include <iwear/stopwatch.h>
//#include <iwear/avlmap.h>
#include <iwear/utility.h>
#include <iwear/debug.h>
#include <iostream>
#include <string>
#include <vector>
#include <ext/hash_map>
#include <algorithm>
#include <google/dense_hash_map>
#include <google/sparse_hash_map>

using namespace std;
using namespace std::tr1;
using namespace iwear;
using namespace __gnu_cxx;


static int stringlength = 120;

template<class Key>
Key random_insert(long inserts) 
{
    return Key(rand() % (inserts*2));
}

template<>
float random_insert( long inserts )
{
    float f = float(rand() % (inserts*2));
    cout << "F-hash: " << *(reinterpret_cast<int*>(&f)) << endl;
    return f;/*
    f = ((float(rand()) / RAND_MAX) * inserts);
    return f;
    return float(rand() % (inserts*2));
    return ((float(rand()) / RAND_MAX) * inserts);*/
}

template<>
std::string random_insert(long)
{
    string buf;
    buf.resize(stringlength);

    for( long j = 0; j < stringlength; ++j )
    {
	char w; 
	while( (w=(rand()%256)) == 0 );
	buf[j] = w;
    }
    return buf;
}

std::map<string,double> fill_timemap;
std::map<string,double> search_timemap;
std::map<string,double> search_new_timemap;

inline void save_max( double& d, double v)
{
    if( d == double() )
    {
	d = v;
    }
    else
    {
	d = min(d,v);
    }
}

// Needed to be able to hash floats, doubles and strings
namespace __gnu_cxx {
    template<>
	struct hash<std::string>
	{
	    size_t operator()(const std::string& s ) const
	    {
		return __stl_hash_string(s.c_str());
	    }
	};
    template<>
	struct hash<float>
	{
	    size_t operator()(float s ) const
	    {
		return 
		    *(reinterpret_cast<int*>(&s));
	    }
	};
    template<>
	struct hash<double>
	{
	    size_t operator()(double s ) const
	    {
		return 
		    (reinterpret_cast<int*>(&s))[0] +
		    (reinterpret_cast<int*>(&s))[1];
	    }
	};
}

template<class Map>
void reserve_and_init( Map& m, long inserts, bool reserve = false )
{
    (void)m;
    (void)inserts;
    if( reserve )
    {
    }
}

#define GOOGLE_INIT(MAP1,MAP2) \
template<> \
void reserve_and_init( MAP1,MAP2& m, long, bool ) \
{ m.set_empty_key(MAP1,MAP2::key_type()); }

GOOGLE_INIT(google::dense_hash_map<int,int>)
GOOGLE_INIT(google::dense_hash_map<long,int>)
GOOGLE_INIT(google::dense_hash_map<float,int>)
GOOGLE_INIT(google::dense_hash_map<double,int>)
GOOGLE_INIT(google::dense_hash_map<string,int>)
	
template<class Map>
void test( const std::string& type, long randseed, long inserts )
{
    typedef typename Map::mapped_type Value;
    typedef typename Map::key_type Key;

//    cout << "Testing " << typenameof(Map()) << endl;
    cout << "Testing " << type << endl;

    cout << "Pregenerating a vector<" << typenameof(Key()) << "> to insert" << endl;
    vector<Key> pres;
    pres.reserve(inserts);

    srand(randseed);
    for( long i = 0; i < inserts; ++i )
    {
	pres.push_back(random_insert<Key>(inserts));//rand() % (inserts*2));
    }

    // Testing the speed of the inserts
    Map tumap;
    reserve_and_init(tumap,inserts,false);
//    StopWatch<SW::clock> sw;
    StopWatch<SW::gettime> sw;
//    StopWatch<SW::gettimeofday> sw;
    sw.Start();
    for( long i = 0; i < inserts; ++i )
    {
	tumap.insert(make_pair(pres[i],Value(i)));
    }
    sw.Stop();
    cout << "Needed " << sw.Time() << "s for filling  a " << type << endl;

    double& d_f = fill_timemap[type];
    save_max(d_f,sw.Time());
    // Testing the speed of searches (of the same values inserted, in the same order inserted)
    sw.Start();
    for( long i = 0; i < inserts; ++i )
    {
	tumap.find(pres[i]);
    }
    sw.Stop();
    cout << "Needed " << sw.Time() << "s for searching a " << type << " in-order" << endl;

    double& d_s = search_timemap[type];
    save_max(d_s,sw.Time());

    std::random_shuffle(pres.begin(),pres.end());

    sw.Start();
    for( long i = 0; i < inserts; ++i )
    {
	tumap.find(pres[i]);
    }
    sw.Stop();
    cout << "Needed " << sw.Time() << "s for searching a " << type << " randomized in-order" << endl;

    double& d_n = search_new_timemap[type];
    save_max(d_n,sw.Time());

    cerr << type << "(" << inserts << ")" << "," << d_f << "," << d_s << "," << d_n << endl;
}

#define BASIC_RUNS 1
int main ( void )
{
    const long inserts = 5000;
    const long randseed = 1234567890;

    for( int i = 0; i < BASIC_RUNS; ++i )
    {
#define DOTEST(tm,t1,t2) test<tm<t1,t2> >(""#tm"<"#t1","#t2">",randseed,inserts)
// TODO: change the benchmark so that we benchmark behaviour on no-collisions, 50% collisions, random distributed collisions
	DOTEST(std::map,int,int);
	DOTEST(std::map,long,int);
	DOTEST(std::map,float,int);
	DOTEST(std::map,double,int);
	DOTEST(std::map,string,int);

	DOTEST(tr1::unordered_map,int,int);
	DOTEST(tr1::unordered_map,long,int);
	DOTEST(tr1::unordered_map,float,int);
	DOTEST(tr1::unordered_map,double,int);
	DOTEST(tr1::unordered_map,string,int);

	DOTEST(__gnu_cxx::hash_map,int,int);
	DOTEST(__gnu_cxx::hash_map,long,int);
	DOTEST(__gnu_cxx::hash_map,float,int);
	DOTEST(__gnu_cxx::hash_map,double,int);
	DOTEST(__gnu_cxx::hash_map,string,int);

	DOTEST(google::dense_hash_map,int,int);
	DOTEST(google::dense_hash_map,long,int);
	DOTEST(google::dense_hash_map,float,int);
	DOTEST(google::dense_hash_map,double,int);
	DOTEST(google::dense_hash_map,string,int);

	DOTEST(google::sparse_hash_map,int,int);
	DOTEST(google::sparse_hash_map,long,int);
	DOTEST(google::sparse_hash_map,float,int);
	DOTEST(google::sparse_hash_map,double,int);
	DOTEST(google::sparse_hash_map,string,int);
	
    }
    
    std::map<string,double>::const_iterator fi = fill_timemap.begin();
    std::map<string,double>::const_iterator si = search_timemap.begin();
    std::map<string,double>::const_iterator ni = search_new_timemap.begin();
   
    double factor_base_fill   = 0.10;
    double factor_base_search = 0.10;
    double factor_base_new    = 0.10;
    cout << "Container\t\t\t| Fill\t\t| Fill %\t| Search\t| Search %\t" << endl;
    cout << "--------------------------------+---------------+---------------+---------------+---------------+---------------+----------" << endl;
    for(; fi != fill_timemap.end();++fi,si++,ni++ )
    {
	cout << fi->first;
	int tbs = 4-(fi->first.length() / 8);
	for( int i = 0;i<tbs;i++) cout << "\t";
	cout << "| " << fi->second << "s\t| " << 100.0*(factor_base_fill/fi->second) << "%";
	cout << "\t| " << si->second << "s\t| " << 100.0*(factor_base_search/si->second) << "%";
	cout << "\t| " << ni->second << "s\t| " << 100.0*(factor_base_new/ni->second) << "%";

	cout << endl;
    }
//    test_int();
}