// Mide su AvlMap: la altura, las rotaciones y el tiempo, frente al árbol sin balance.
// Las alturas y las rotaciones son conteos. 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 "avl_map.h"
#include "bench.h"
#include "fibonacci_tree.h"
#include "plain_tree.h"

namespace {

// Hasta aquí se mide el árbol sin balance con claves ordenadas: cuesta Θ(n²).
const int plain_limit = 16000;

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

struct AvlResult {
    int height = 0;
    long rotations = 0;
    double seconds = 0;
};

AvlResult run_avl(const std::vector<int>& keys) {
    AvlResult result;
    result.seconds = median_seconds(3, [&] {
        AvlMap<int, int> map;
        for (int key : keys) {
            map.insert(key, key);
        }
        result.height = map.height();
        result.rotations = map.rotations();
    });
    return result;
}

int run_plain(const std::vector<int>& keys, double& seconds) {
    int height = 0;
    seconds = median_seconds(3, [&] {
        PlainTree<int> tree;
        for (int key : keys) {
            tree.insert(key);
        }
        height = tree.height();
    });
    return height;
}

void print_avl_columns(const AvlResult& result, int n) {
    std::cout << std::setw(7) << result.height << std::setprecision(3) << std::setw(8)
              << static_cast<double>(result.rotations) / n;
}

}  // namespace

int main() {
    std::cout << "Claves ordenadas\n";
    std::cout << std::setw(9) << "n" << std::setw(7) << "log2n" << std::setw(8) << "1.44log" << std::setw(7) << "h.avl"
              << std::setw(8) << "rot/n" << std::setw(9) << "t.avl" << std::setw(9) << "h.sin" << std::setw(9) << "t.sin" << "\n";
    for (int n = 1000; n <= 1024000; n *= 4) {
        std::vector<int> keys = ascending(n);
        double log_n = std::log2(n);
        std::cout << std::setw(9) << n << std::fixed << std::setprecision(1) << std::setw(7) << log_n
                  << std::setw(8) << 1.44 * log_n;
        AvlResult avl = run_avl(keys);
        print_avl_columns(avl, n);
        std::cout << std::setprecision(4) << std::setw(9) << avl.seconds;
        if (n <= plain_limit) {
            double seconds = 0;
            int height = run_plain(keys, seconds);
            std::cout << std::setw(9) << height << std::setw(9) << seconds;
        } else {
            std::cout << std::setw(9) << "-" << std::setw(9) << "-";
        }
        std::cout << std::endl;
    }

    std::cout << "Claves al azar\n";
    std::cout << std::setw(9) << "n" << std::setw(7) << "log2n" << std::setw(8) << "1.44log" << std::setw(7) << "h.avl"
              << std::setw(8) << "rot/n" << std::setw(9) << "t.avl" << std::setw(9) << "h.sin" << std::setw(9) << "t.sin" << "\n";
    std::mt19937 random(11);
    for (int n = 1000; n <= 1024000; n *= 4) {
        std::vector<int> keys = ascending(n);
        std::shuffle(keys.begin(), keys.end(), random);
        double log_n = std::log2(n);
        std::cout << std::setw(9) << n << std::fixed << std::setprecision(1) << std::setw(7) << log_n
                  << std::setw(8) << 1.44 * log_n;
        AvlResult avl = run_avl(keys);
        print_avl_columns(avl, n);
        std::cout << std::setprecision(4) << std::setw(9) << avl.seconds;
        double seconds = 0;
        int height = run_plain(keys, seconds);
        std::cout << std::setw(9) << height << std::setw(9) << seconds << std::endl;
    }

    std::cout << "El peor caso: arboles de Fibonacci, armados insertando por niveles\n";
    std::cout << std::setw(9) << "n" << std::setw(7) << "log2n" << std::setw(8) << "1.44log" << std::setw(7) << "h.avl"
              << std::setw(8) << "rot" << std::setw(8) << "h/log2n" << "\n";
    for (int h = 4; h <= 24; h += 4) {
        std::vector<int> keys = fibonacci_keys(h);
        AvlMap<int, int> map;
        for (int key : keys) {
            map.insert(key, key);
        }
        double log_n = std::log2(static_cast<double>(keys.size()));
        std::cout << std::setw(9) << keys.size() << std::fixed << std::setprecision(1) << std::setw(7) << log_n
                  << std::setw(8) << 1.44 * log_n << std::setw(7) << map.height() << std::setw(8) << map.rotations()
                  << std::setprecision(2) << std::setw(8) << map.height() / log_n << "\n";
    }
    return 0;
}