#include <cstdlib>
#include <ctime>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <set>
#ifdef HAVE_BOOST
    #include <boost/unordered_set.hpp>
    #define hash_set boost::unordered_set
#else
    #ifdef _MSC_VER
        #include <unordered_set>
        #define hash_set std::unordered_set
    #else
        #include <tr1/unordered_set>
        #define hash_set std::tr1::unordered_set
    #endif
#endif
#include "cycle.h"

void PrintStats(std::vector<double> timings) {
    std::cout << std::fixed << std::setprecision(2);
    std::cout << "[";
    for (size_t i = 1 ; i<timings.size()-1 ; ++i) {
        std::cout << timings[i] << ",";
    }
    std::cout << timings.back();
    std::cout << "]";

    double sum = 0.0;
    for (size_t i = 1 ; i<timings.size() ; ++i) {
        sum += timings[i];
    }
    double avg = sum / double(timings.size()-1);

    sum = 0.0;
    for (size_t i = 1 ; i<timings.size() ; ++i) {
        timings[i] = pow(timings[i]-avg, 2);
        sum += timings[i];
    }
    double var = sum/(timings.size()-2);
    double sdv = sqrt(var);

    std::cout << " with average " << avg << ", stddev " << sdv;
}

void SortUniq(std::vector<int>& invec, size_t n=7) {
    std::vector<double> timings;
    timings.reserve(n);

    for (size_t i=0 ; i<n ; ++i) {
        std::vector<int> vec(invec);
        ticks start = getticks();

        std::sort(vec.begin(), vec.end());
        vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
        
        ticks end = getticks();
        double timed = elapsed(end, start);
        timings.push_back(timed);
    }

    std::cout << "SortUniq(" << invec.size() << "," << n << "): ";
    PrintStats(timings);
    std::cout << std::endl;
}

void Set(std::vector<int>& invec, size_t n=7) {
    std::vector<double> timings;
    timings.reserve(n);

    for (size_t i=0 ; i<n ; ++i) {
        std::vector<int> vec(invec);
        std::set<int> st;
        ticks start = getticks();

        st.insert(vec.begin(), vec.end());

        ticks end = getticks();
        double timed = elapsed(end, start);
        timings.push_back(timed);
    }

    std::cout << "Set(" << invec.size() << "," << n << "): ";
    PrintStats(timings);
    std::cout << std::endl;
}

void HashSet(std::vector<int>& invec, size_t n=7) {
    std::vector<double> timings;
    timings.reserve(n);

    for (size_t i=0 ; i<n ; ++i) {
        std::vector<int> vec(invec);
        hash_set<int> st;
        std::set<int> sh;
        ticks start = getticks();

        st.insert(vec.begin(), vec.end());
        sh.insert(st.begin(), st.end());

        ticks end = getticks();
        double timed = elapsed(end, start);
        timings.push_back(timed);
    }

    std::cout << "HashSet(" << invec.size() << "," << n << "): ";
    PrintStats(timings);
    std::cout << std::endl;
}

int main() {
    srand(static_cast<unsigned int>(time(0)));

    std::vector<int> vec;
    vec.reserve(10000000);

    vec.clear();
    for (size_t i = 0 ; i<10000 ; ++i) {
        vec.push_back(rand()%1000);
    }
    SortUniq(vec);
    Set(vec);
    HashSet(vec);
    std::cout << std::endl;

    vec.clear();
    for (size_t i = 0 ; i<100000 ; ++i) {
        vec.push_back(rand()%1000);
    }
    SortUniq(vec);
    Set(vec);
    HashSet(vec);
    std::cout << std::endl;

    vec.clear();
    for (size_t i = 0 ; i<1000000 ; ++i) {
        vec.push_back(rand()%1000);
    }
    SortUniq(vec);
    Set(vec);
    HashSet(vec);
    std::cout << std::endl;

    vec.clear();
    for (size_t i = 0 ; i<10000000 ; ++i) {
        vec.push_back(rand()%1000);
    }
    SortUniq(vec);
    Set(vec);
    HashSet(vec);
    std::cout << std::endl;
}