#include <stdio.h>
#include <math.h>
#include <time.h>
#include <map>

#define RANDOM 1

int main()
{
    std::map<unsigned, double> ht;
    double insertDurationMeas[10];
    double insertDurationSum = 0.0;
    time_t begin, end; 

    for(int n=10000000; n>0; n--) {

        time(&begin);
        ht.clear();
        unsigned lfsr = 1;
        for(int i=10; i>0; i--) {

            lfsr = (lfsr >> 1) ^ (unsigned int)(0 - (lfsr & 1u) & 0xd0000001u); 
#ifdef RANDOM
            ht[lfsr] = (double)(i+n);
#else
            ht[i] = (double)(i+n);
#endif
        }
        time(&end);
        double duration = difftime(end, begin);
        insertDurationSum += duration;
        insertDurationMeas[n-1] = duration;
        printf("%.1f\n", ht[42]);
    }

    // random lookups
    time(&begin);
    unsigned lfsr = 1;
    double x = 0.0;
    for(int i=10000000; i>0; i--) {

        lfsr = (lfsr >> 1) ^ (unsigned int)(0 - (lfsr & 1u) & 0xd0000001u);
        x += ht[lfsr];
    }
    time(&end);
    double lookupDuration = difftime(end, begin);

    // report on timing
    double mean = insertDurationSum/10.0;
    double durationVar = 0.0;
    for(int i=0; i<10; i++)
        durationVar += (insertDurationMeas[i]-mean)*(insertDurationMeas[i]-mean);

    double stdv = sqrt(durationVar/10.0);
    printf("insert timing in seconds: mean %.3f, stdv %.3f\n",mean,stdv);
    printf("lookup timing in seconds: %.3f\n",lookupDuration);
    return 0;
}