// Tiempo de insertar y de buscar n claves, al azar y ordenadas. Compilar con -O2 y sin sanitizers.
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <random>
#include <vector>

#include "bench.h"
#include "bst_set.h"

namespace {

double insert_seconds(const std::vector<int>& keys) {
    return median_seconds(5, [&] {
        BstSet<int> tree;
        for (int key : keys) {
            tree.insert(key);
        }
        keep(tree.size());
    });
}

}  // namespace

int main() {
    std::cout << std::setw(9) << "n" << std::setw(11) << "azar(s)" << std::setw(10) << "x" << std::setw(12) << "orden(s)"
              << std::setw(10) << "x" << "\n";
    std::mt19937 random(10);
    double last_random = 0;
    double last_sorted = 0;
    for (int n = 1000; n <= 32000; n *= 2) {
        std::vector<int> keys(n);
        std::iota(keys.begin(), keys.end(), 0);
        double sorted_time = insert_seconds(keys);
        std::shuffle(keys.begin(), keys.end(), random);
        double random_time = insert_seconds(keys);
        std::cout << std::setw(9) << n << std::fixed << std::setprecision(5) << std::setw(11) << random_time
                  << std::setprecision(1) << std::setw(10) << (last_random > 0 ? random_time / last_random : 0)
                  << std::setprecision(5) << std::setw(12) << sorted_time
                  << std::setprecision(1) << std::setw(10) << (last_sorted > 0 ? sorted_time / last_sorted : 0) << "\n";
        last_random = random_time;
        last_sorted = sorted_time;
    }
    return 0;
}