// Cuántas reparaciones y rotaciones hace cada operación: conteos, no tiempos. Semilla fija.
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <random>
#include <vector>

#include "avl_set.h"
#include "fibonacci_tree.h"

namespace {

struct Totals {
    long operations = 0;
    long repairs = 0;
    long rotations = 0;
    std::size_t max_repairs = 0;
};

void print_row(const char* name, int n, const Totals& totals, int bound) {
    std::cout << std::setw(14) << name << std::setw(9) << n << std::fixed << std::setprecision(3)
              << std::setw(10) << static_cast<double>(totals.repairs) / totals.operations
              << std::setw(10) << static_cast<double>(totals.rotations) / totals.operations
              << std::setw(6) << totals.max_repairs << std::setw(7) << bound << "\n";
}

void insert_all(AvlSet<int>& tree, const std::vector<int>& keys, Totals& totals) {
    for (int key : keys) {
        long before = tree.rotations();
        tree.insert(key);
        totals.operations++;
        totals.repairs += static_cast<long>(tree.last_repairs().size());
        totals.rotations += tree.rotations() - before;
        totals.max_repairs = std::max(totals.max_repairs, tree.last_repairs().size());
    }
}

// Borra todas las claves, y anota la mayor cantidad de reparaciones permitida por h / 2.
void erase_all(AvlSet<int>& tree, const std::vector<int>& keys, Totals& totals, int& worst_bound) {
    worst_bound = tree.height() / 2;
    for (int key : keys) {
        int height_before = tree.height();
        long before = tree.rotations();
        tree.erase(key);
        totals.operations++;
        totals.repairs += static_cast<long>(tree.last_repairs().size());
        totals.rotations += tree.rotations() - before;
        totals.max_repairs = std::max(totals.max_repairs, tree.last_repairs().size());
        if (static_cast<int>(tree.last_repairs().size()) > height_before / 2) {
            std::cout << "se paso de h / 2\n";
        }
    }
}

}  // namespace

int main() {
    std::cout << std::setw(14) << "operacion" << std::setw(9) << "n" << std::setw(10) << "rep/op"
              << std::setw(10) << "rot/op" << std::setw(6) << "max" << std::setw(7) << "h/2" << "\n";
    std::mt19937 random(2026);
    for (int n : {1000, 32000, 1024000}) {
        std::vector<int> sorted(n);
        std::iota(sorted.begin(), sorted.end(), 0);
        std::vector<int> shuffled = sorted;
        std::shuffle(shuffled.begin(), shuffled.end(), random);
        std::vector<int> erase_order = sorted;
        std::shuffle(erase_order.begin(), erase_order.end(), random);
        {
            AvlSet<int> tree;
            Totals insert_totals;
            insert_all(tree, sorted, insert_totals);
            print_row("insertar orden", n, insert_totals, tree.height() / 2);
        }
        AvlSet<int> tree;
        Totals insert_totals;
        insert_all(tree, shuffled, insert_totals);
        print_row("insertar azar", n, insert_totals, tree.height() / 2);
        Totals erase_totals;
        int bound = 0;
        erase_all(tree, erase_order, erase_totals, bound);
        print_row("borrar azar", n, erase_totals, bound);
    }
    std::cout << "Borrar la clave mayor de un arbol de Fibonacci\n";
    std::cout << std::setw(3) << "h" << std::setw(9) << "n" << std::setw(13) << "reparaciones"
              << std::setw(11) << "rotaciones" << std::setw(7) << "h/2" << std::setw(11) << "h despues" << "\n";
    for (int h = 2; h <= 26; h += (h < 10 ? 1 : 4)) {
        std::vector<int> keys = fibonacci_keys(h);
        AvlSet<int> tree;
        for (int key : keys) {
            tree.insert(key);
        }
        long before = tree.rotations();
        tree.erase(static_cast<int>(keys.size()));
        tree.check_invariants();
        std::cout << std::setw(3) << h << std::setw(9) << keys.size() << std::setw(13) << tree.last_repairs().size()
                  << std::setw(11) << tree.rotations() - before << std::setw(7) << h / 2 << std::setw(11) << tree.height() << "\n";
    }
    return 0;
}