// Prueba todos los órdenes de inserción de n claves, y anota lo peor que pasó en una inserción.
// También revisa los dos lados de la cota: n >= 2^negros - 1, y altura + 1 <= 2 * negros.
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <vector>

#include "rb_set.h"

int main() {
    std::cout << std::setw(3) << "n" << std::setw(8) << "ordenes" << std::setw(7) << "h.min" << std::setw(7) << "h.max"
              << std::setw(6) << "cota" << std::setw(16) << "max.rotaciones" << std::setw(16) << "max.recoloreos"
              << std::setw(9) << "cuentas" << "\n";
    for (int n = 1; n <= 9; n++) {
        std::vector<int> keys(n);
        std::iota(keys.begin(), keys.end(), 1);
        long orders = 0;
        int min_height = n;
        int max_height = -1;
        long max_rotations = 0;
        long max_recolors = 0;
        bool counts_hold = true;
        do {
            RedBlackSet<int> tree;
            for (int key : keys) {
                long rotations = tree.rotations();
                long recolors = tree.recolors();
                tree.insert(key);
                max_rotations = std::max(max_rotations, tree.rotations() - rotations);
                max_recolors = std::max(max_recolors, tree.recolors() - recolors);
            }
            int blacks = tree.black_height();
            counts_hold = counts_hold && n >= (1 << blacks) - 1 && tree.height() + 1 <= 2 * blacks;
            min_height = std::min(min_height, tree.height());
            max_height = std::max(max_height, tree.height());
            orders++;
        } while (std::next_permutation(keys.begin(), keys.end()));
        std::cout << std::setw(3) << n << std::setw(8) << orders << std::setw(7) << min_height << std::setw(7) << max_height
                  << std::fixed << std::setprecision(2) << std::setw(6) << 2 * std::log2(n + 1.0) - 1
                  << std::setw(16) << max_rotations << std::setw(16) << max_recolors
                  << std::setw(9) << (counts_hold ? "si" : "NO") << "\n";
    }
    return 0;
}