#include <array>
#include <chrono>
#include <cmath>
#include <iostream>
#include <functional>
#include <set>
#include <tuple>

using namespace std;
using namespace chrono;

const size_t SIZE = 1000;
const double lg5 = log(5) / log(2);

typedef unsigned long myint;
typedef array<myint, SIZE> myarray;

void use_set(myarray& out) {
    set<myint> s = {1};
    for (auto& x : out) {
        auto it = s.begin();
        x = *it;
        s.erase(it);
        s.insert(x * 2);
        s.insert(x * 5);
    }
}

tuple<double, int, int> incr_i(int i, int j) {
    double mindiff = 1;
    int mini = ++i, minj = j;
    double diff = mindiff;
    while (j > 0) {
        --j;
        diff -= lg5;
        while (diff < 0) {
            ++i;
            ++diff;
        }
        if (diff < mindiff) {
            mindiff = diff;
            mini = i;
            minj = j;
        }
    }
    return make_tuple(mindiff, mini, minj);
}

tuple<double, int, int> incr_j(int i, int j) {
    double mindiff = lg5;
    int mini = i, minj = ++j;
    double diff = mindiff;
    while (i > 0) {
        --i;
        diff -= 1;
        if (diff < 0) {
            ++j;
            diff += lg5;
        }
        if (diff < mindiff) {
            mindiff = diff;
            mini = i;
            minj = j;
        }
    }
    return make_tuple(mindiff, mini, minj);
}



void use_dbl(myarray& out) {
    int i = 0, j = 0;
    myarray pow2 = {1}, pow5 = {1};
    for (size_t x = 1; x < SIZE; ++x) {
        pow2[x] = pow2[x - 1] * 2;
        pow5[x] = pow5[x - 1] * 5;
    }
    for (auto& x : out) {
        x = pow2[i] * pow5[j];
        double d1, d2;
        int i1, j1, i2, j2;
        tie(d1, i1, j1) = incr_i(i, j);
        tie(d2, i2, j2) = incr_j(i, j);
        if (d1 <= d2) tie(i, j) = tie(i1, j1);
        else          tie(i, j) = tie(i2, j2);
    }
}

template<class DurationType = chrono::microseconds, class F>
typename DurationType::rep closure_time(const F& f) {
    typedef high_resolution_clock myclock;
    auto start = myclock::now();
    f();
    auto end = myclock::now();
    return duration_cast<DurationType>(end - start).count();
}

int main()
{
    cout << "Print first " << SIZE << " elements of {i,j > 0 | 2^i * 5^j}\n";

    myarray using_set;
    cout << "Using set time: ";
    cout << closure_time(bind(use_set, ref(using_set))) << endl;
    for (auto x : using_set)
        cout << x << ' ';
    cout << endl;

    myarray using_dbl;
    cout << "Using dbl time: ";
    cout << closure_time(bind(use_dbl, ref(using_dbl))) << endl;
    for (auto x : using_dbl)
        cout << x << ' ';
    cout << endl;

   return 0;
}