// El AVL con menos nodos para cada altura: la recurrencia, Fibonacci, y el árbol de verdad.
#include <cassert>
#include <cmath>
#include <iomanip>
#include <iostream>

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

int main() {
    const double log_phi = std::log((1 + std::sqrt(5.0)) / 2);
    std::cout << std::setw(3) << "h" << std::setw(8) << "N(h)" << std::setw(9) << "F(h+3)-1"
              << std::setw(7) << "medida" << std::setw(5) << "rot" << std::setw(7) << "log2n"
              << std::setw(8) << "1.44log" << std::setw(8) << "cota" << "\n";
    long fib_a = 1;  // F(1)
    long fib_b = 1;  // F(2)
    long fib_c = 2;  // F(3), la que corresponde a h = 0
    for (int h = 0; h <= 24; h++) {
        long n = min_avl_nodes(h);
        AvlSet<int> tree;
        for (int key : fibonacci_keys(h)) {
            tree.insert(key);
        }
        tree.check_invariants();
        assert(static_cast<long>(tree.size()) == n);
        double log_n = std::log2(static_cast<double>(n));
        // La cota exacta, contando aristas: h < log_phi(n + 2) + log_phi(raíz de 5) - 3,
        // es decir, h < 1.4405 log2(n + 2) - 1.3277.
        double bound = std::log(static_cast<double>(n + 2)) / log_phi + std::log(std::sqrt(5.0)) / log_phi - 3;
        if (h <= 12 || h % 4 == 0) {
            std::cout << std::setw(3) << h << std::setw(8) << n << std::setw(9) << fib_c - 1
                      << std::setw(7) << tree.height() << std::setw(5) << tree.rotations()
                      << std::fixed << std::setprecision(2) << std::setw(7) << log_n
                      << std::setw(8) << 1.44 * log_n << std::setw(8) << bound << "\n";
        }
        fib_a = fib_b;
        fib_b = fib_c;
        fib_c = fib_a + fib_b;
    }
    return 0;
}