/*
This program follows the science and technology promotion license of Zhikai Wang/www.heteroclinic.net.
Due to the nature or creation of this program, you can do anything with this program.
*/
#include <deque>
#include <math.h>
#include <iostream>
#include <map>
#include <time.h>
#include <ctime>

//#include <hash_map>
#ifdef __GNUC__
#include <ext/hash_map>
#else
#include <hash_map>
#endif
#define _DEFINE_DEPRECATED_HASH_CLASSES 0


namespace std
{
 using namespace __gnu_cxx;
}


int main ()
{
    srand(time(NULL));
    std::deque<int> dq;
	int e = 25;
    //std::cout<<"2^30 is "<<(2^30)<<std::endl;
    std::cout<<"pow(2,"<<e<<") is  "<<pow(2,e)<<std::endl;
    int l =  pow(2,e);
    int step =  pow(2,(e-5));
    std::cout<<"l  "<<l<<std::endl;

    std::hash_map<int,int> hm;
    std::cout<<"hm.max_size() "<<hm.max_size()<<std::endl;

    int c = 0;
    int tmptries =0;
    int trythresh =0;

clock_t start;
  double diff;

    clock_t endd = std::clock();

    start = std::clock();
    for (; hm.size()<l; ) {

        //std::cout<<"hm.size() : "<<hm.size()<<std::endl;
        tmptries =0;
        //hm.insert(std::make_pair(i,i));
        int v = rand() % l +1;
        while ( hm.find( (const int )v)  != hm.end()) {
           //std::cout<<"v : "<<v <<"\t hm.size() "<<hm.size()<<std::endl;
           tmptries++;
           v = rand() % l +1;
        }
        if (tmptries > trythresh) trythresh= tmptries;
        hm.insert(std::make_pair(v,v));
       if (((hm.size())%(step))==0) {
           std::cout<<"step : "<<++c<<"\t"<<"Thresh : "<< trythresh<<"\t"<< "elapse : "<< ( ( std::clock()- start ) / (double)CLOCKS_PER_SEC )<<std::endl;
       }
    }

    std::cout<<"hm.size() : "<<hm.size()<<std::endl;
    endd = std::clock();
    diff = ( endd - start ) / (double)CLOCKS_PER_SEC;

    std::cout<<"It took  "<<diff <<" seconds." <<std::endl;
	// to verify smaller values of e.
	//std::hash_map<int,int> ::const_iterator it = hm.begin();
	//std::hash_map<int,int> ::const_iterator ie = hm.end();
	//for( ; it != ie ; ++it ) {
    //    std::cout << it->first << " -> " << it->second  << std::endl;
    //}
    return 0;
}