// -*- mode: c++ -*-
// $Id: hash2.g++,v 1.2 2001/06/20 03:20:02 doug Exp $
// http://www.bagley.org/~doug/shootout/

#include <ctime>
#include <cstdlib>
#include <string.h>
#include <stdio.h>
#include <iostream>
#include <tr1/unordered_map>

using namespace std;
using namespace std::tr1;

struct eqstr {
    bool operator()(const char* s1, const char* s2) const {
		return strcmp(s1, s2) == 0;
    }
};

namespace std {
	namespace tr1 {
		template<>
		struct hash<const char*> {
			std::size_t	operator()(const char* s) const {
				return _Fnv_hash<>::hash(s, strlen(s));
			}
		};
	}
}


int main(int argc, char *argv[]) {
    int n = ((argc == 2) ? atoi(argv[1]) : 1);
    clock_t start=clock();
	char buf[16];

	typedef unordered_map<const char*, int, hash<const char*>, eqstr> HM;
	//	typedef hash_map<const char*, int, hash<const char*>, eqstr> HM;
    HM hash1, hash2;

    for (int i=0; i<10000; i++) {
		sprintf(buf, "foo_%d", i);
		hash1[strdup(buf)] = i;
    }

    for (int i=0; i<n; i++) {
		for (HM::iterator k = hash1.begin(); k != hash1.end(); ++k) {
			HM::iterator it = hash2.find(k->first);
			if (it!=hash2.end()) {
				it->second += k->second;
			} else {
				hash2.insert( *k );
			}
		}
    }

    cout << hash1["foo_1"] << " " << hash1["foo_9999"] << " "
	 << hash2["foo_1"] << " " << hash2["foo_9999"] << endl;

  clock_t endt=clock(); 
  std::cout <<"Time: " << double(endt-start)/CLOCKS_PER_SEC * 1000 << " ms\n";

}