#include <map>
#include <tuple>
#include <chrono>
#include <vector>
#include <string>
#include <cstdlib>
#include <fstream>
#include <iomanip>
#include <assert.h>
#include <iostream>
#include <unordered_map>

using namespace std ;

typedef chrono::time_point<chrono::system_clock> SystemTime ;

template <typename HashType, typename KeyType> tuple <int, int, int> hash_test(vector <KeyType> &keys)
{
    int count(0);
    int insertTime(0), fetchTime(0) ;
    {
        HashType hash ;
        {
            SystemTime start(chrono::system_clock::now());
            for(KeyType &t : keys)
                hash [t] = 1;
            SystemTime end(chrono::system_clock::now());
            insertTime = chrono::duration_cast<chrono::microseconds>(end-start).count();
        }
        {
            SystemTime start(chrono::system_clock::now());
            for(KeyType &t : keys)
                count += hash [t];
            SystemTime end(chrono::system_clock::now());
            fetchTime = chrono::duration_cast<chrono::microseconds>(end-start).count();
        }
    }
    //count is used to ensure that the compiler optimisations don't remove the hashing operations
    return tuple <int, int, int>(insertTime, fetchTime, count);
}

template <typename Key> void maptest(const char *context, vector <Key> &keys)
{
    auto uMapTimes = hash_test<unordered_map <Key, int>, Key>(keys);
    auto oMapTimes = hash_test<map <Key, int>, Key>(keys);
    cout<<context<<endl;
    cout<<setw(12)<<"unordered: "<<setw(8)<<get<0>(uMapTimes)<<setw(8)<<get<1>(uMapTimes)<<endl;
    cout<<setw(12)<<"ordered: "  <<setw(8)<<get<0>(oMapTimes)<<setw(8)<<get<1>(oMapTimes)<<endl;
}

int main()
{
    std::srand(time(0));
    
    enum { KeyCount=1024, MinStrSize=8, MaxStrSize=16 } ;
    vector <int> integerKeys(KeyCount);
    for(int i=0; i<KeyCount; i++)
        integerKeys [i] = i ;
    
    vector <string> randomStrings(KeyCount) ;
    for(int i=0; i<KeyCount; i++)
    {
        auto &str = randomStrings[i] ;
        str.resize(((MaxStrSize-MinStrSize)%std::rand()) + MinStrSize);
        for(char &c : str)
        {
            c = (('z' - 'a')%std::rand()) + 'a' ;
        }
    }
    
    //wordlist can be downloaded here: http://pastebin.com/yt3s22hf
    vector <string> wordKeys ;
    ifstream input("wordlist.txt");
    assert(input.good());
    while(!input.eof())
    {
        string s ;
        input >> s ;
        wordKeys.push_back(s);
    }
    input.close();
    
    maptest<int>(" ** Integer Keys ** ", integerKeys);
    maptest<string>(" ** Random String Keys ** ", randomStrings);
    maptest<string>(" ** Real Words Keys ** ", wordKeys);
    

    return 0 ;
}