#define _SECURE_SCL 1

#include <ctime>
#include <iostream>
#include <iomanip>
#include <unordered_map>
#include <hash_map>
#include <vector>
#include <map>
#include <sstream>
#include <string>
#include <boost/unordered_map.hpp>
#include "cycle.h"

std::vector<std::string> strings;

template<typename T>
void timemap(const int n, 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[strings[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(strings[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(strings[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() {
	int n = 1000000;
	strings.reserve(n);
	strings.resize(n);
	std::stringstream ss;
	for (int i=0 ; i<n ; ++i) {
		ss.str("");
		ss.clear();
		ss << i;
		ss >> strings[i];
	}

	std::cout << "Timing boost::unordered_map<std::string,int>" << std::endl;
	timemap<boost::unordered_map<std::string,int> >(n);
	std::cout << std::endl;

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

	std::cout << "Timing stdext::hash_map<std::string,int>" << std::endl;
	timemap<stdext::hash_map<std::string,int> >(n);
	std::cout << std::endl;

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