// Mide su BstMap: altura y tiempo de insertar n claves, al azar y ordenadas.
// El caso ordenado se detiene cuando una corrida pasa de limit_seconds: hasta ahí aguantó.
// Los tiempos dependen de la máquina. Compilar con -O2 y sin sanitizers.
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <random>
#include <vector>

#include "bench.h"
#include "bst_map.h"

namespace {

const double limit_seconds = 1.0;

std::vector<int> ascending(int n) {
    std::vector<int> keys(n);
    std::iota(keys.begin(), keys.end(), 0);
    return keys;
}

// Inserta las claves, deja la altura en height y devuelve la mediana de 3 corridas.
double insert_all(const std::vector<int>& keys, int& height) {
    return median_seconds(3, [&] {
        BstMap<int, int> map;
        for (int key : keys) {
            map.insert(key, key);
        }
        height = map.height();
        keep(map.size());
    });
}

}  // namespace

int main() {
    std::cout << std::setw(9) << "n" << std::setw(7) << "log2n"
              << std::setw(7) << "h.azar" << std::setw(8) << "h/log2n" << std::setw(9) << "t.azar"
              << std::setw(9) << "h.orden" << std::setw(9) << "t.orden" << "\n";
    std::mt19937 random(10);
    bool sorted_alive = true;
    for (int n = 1000; n <= 1024000; n *= 2) {
        std::vector<int> keys = ascending(n);
        std::vector<int> shuffled = keys;
        std::shuffle(shuffled.begin(), shuffled.end(), random);
        // Primero el caso ordenado: los bloques que libera una corrida al azar quedan en otro
        // orden, y si se reusan, los nodos de la cadena ya no estarían seguidos en la memoria.
        int sorted_height = 0;
        double sorted_time = 0;
        if (sorted_alive) {
            sorted_time = insert_all(keys, sorted_height);
        }
        int random_height = 0;
        double random_time = insert_all(shuffled, random_height);
        double log_n = std::log2(n);
        std::cout << std::setw(9) << n << std::fixed << std::setprecision(1) << std::setw(7) << log_n
                  << std::setw(7) << random_height << std::setprecision(2) << std::setw(8) << random_height / log_n
                  << std::setprecision(4) << std::setw(9) << random_time;
        if (sorted_alive) {
            std::cout << std::setw(9) << sorted_height << std::setw(9) << sorted_time;
            sorted_alive = sorted_time < limit_seconds;
        } else {
            std::cout << std::setw(9) << "-" << std::setw(9) << "-";
        }
        std::cout << std::endl;
    }
    return 0;
}