#include <ctime>
#include <iostream>
#include <iomanip>
#include <tr1/unordered_map>
#include <ext/hash_map>
#include <map>
#include <string>
#include "cycle.h"

template<typename T>
void timemap(const int n=10000000, const int r=7) {
	std::map<std::string,std::vector<double> > timings;
	std::cout << std::fixed << std::setprecision(2);

	for (int j=0 ; j<r ; j++) {
		ticks start;
		T hsh;

		start = getticks();
		// Insert every 2nd number in the sequence
		for (int i=0 ; i<n ; i+=2) {
			hsh[i] = i*2;
		}
		timings["1: Insert"].push_back(elapsed(getticks(), start));

		start = getticks();
		// Lookup every number in the sequence
		for (int i=0 ; i<n ; ++i) {
			hsh.find(i);
		}
		timings["2: Lookup"].push_back(elapsed(getticks(), start));

		start = getticks();
		// Iterate over the entries
		for (typename T::iterator it=hsh.begin() ; it != hsh.end() ; ++it) {
			int x = it->second;
			++x;
		}
		timings["3: Iterate"].push_back(elapsed(getticks(), start));

		start = getticks();
		// Erase the entries
		for (int i=0 ; i<n ; i+=2) {
			hsh.erase(i);
		}
		timings["4: Erase"].push_back(elapsed(getticks(), start));
	}

	for (std::map<std::string,std::vector<double> >::iterator it=timings.begin() ; it!=timings.end() ; ++it) {
		double sum = 0.0;
		std::cout << it->first << " ( ";
		for (int i=1 ; i<r ; i++) {
			sum += it->second.at(i);
			std::cout << it->second.at(i) << " ";
		}
		std::cout << ") " << sum/double(r-1) << std::endl;
	}
}

int main() {
	std::cout << "Timing std::tr1::unordered_map<int,int>" << std::endl;
	timemap<std::tr1::unordered_map<int,int> >();
	std::cout << std::endl;

	std::cout << "Timing __gnu_cxx::hash_map<int,int>" << std::endl;
	timemap<__gnu_cxx::hash_map<int,int> >();
	std::cout << std::endl;

	std::cout << "Timing std::map<int,int>" << std::endl;
	timemap<std::map<int,int> >();
	std::cout << std::endl;
}