// Genera TODOS los árboles rojinegros válidos con las claves 1..n, y los colapsa.
// Comprueba que cada árbol 2-3-4 con t nodos de 2 claves viene de exactamente 2^t rojinegros,
// y cuenta cuántos de esos rojinegros se pueden obtener insertando en algún orden.
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <memory>
#include <numeric>
#include <set>
#include <string>
#include <vector>

#include "rb_set.h"

namespace {

struct Shape {
    int key = 0;
    bool red = false;
    std::shared_ptr<const Shape> left;
    std::shared_ptr<const Shape> right;
};
using Tree = std::shared_ptr<const Shape>;

bool is_red(const Tree& tree) { return tree != nullptr && tree->red; }

std::string text_of(const Tree& tree) {
    if (tree == nullptr) {
        return "_";
    }
    std::string text = std::to_string(tree->key) + (tree->red ? "r" : "");
    if (tree->left != nullptr || tree->right != nullptr) {
        text += "(" + text_of(tree->left) + "," + text_of(tree->right) + ")";
    }
    return text;
}

// Devuelve el texto de RedBlackSet::collapsed, y cuenta los nodos de 2 claves.
std::string collapse(const Tree& tree, int& two_keys) {
    if (tree == nullptr) {
        return "_";
    }
    std::vector<Tree> keys;
    std::vector<Tree> children;
    if (is_red(tree->left)) {
        keys.push_back(tree->left);
        children.push_back(tree->left->left);
        children.push_back(tree->left->right);
    } else {
        children.push_back(tree->left);
    }
    keys.push_back(tree);
    if (is_red(tree->right)) {
        keys.push_back(tree->right);
        children.push_back(tree->right->left);
        children.push_back(tree->right->right);
    } else {
        children.push_back(tree->right);
    }
    two_keys += keys.size() == 2 ? 1 : 0;
    std::string text = "[";
    for (std::size_t i = 0; i < keys.size(); i++) {
        text += (i > 0 ? " " : "") + std::to_string(keys[i]->key);
    }
    text += "]";
    if (children[0] != nullptr) {
        text += "(";
        for (std::size_t i = 0; i < children.size(); i++) {
            text += (i > 0 ? "," : "") + collapse(children[i], two_keys);
        }
        text += ")";
    }
    return text;
}

int height_of(const Tree& tree) {
    return tree == nullptr ? -1 : 1 + std::max(height_of(tree->left), height_of(tree->right));
}

// Todos los árboles válidos con las claves low..high, con esa cantidad de negros hasta las hojas
// nulas, cuya raíz es negra, o cualquiera de los dos colores si may_be_red.
std::vector<Tree> build_all(int low, int high, int blacks, bool may_be_red) {
    std::vector<Tree> trees;
    if (low > high) {
        if (blacks == 0) {
            trees.push_back(nullptr);
        }
        return trees;
    }
    if (blacks < 0) {
        return trees;
    }
    for (int key = low; key <= high; key++) {
        if (blacks >= 1) {
            for (const Tree& left : build_all(low, key - 1, blacks - 1, true)) {
                for (const Tree& right : build_all(key + 1, high, blacks - 1, true)) {
                    trees.push_back(std::make_shared<const Shape>(Shape{key, false, left, right}));
                }
            }
        }
        if (may_be_red) {
            for (const Tree& left : build_all(low, key - 1, blacks, false)) {
                for (const Tree& right : build_all(key + 1, high, blacks, false)) {
                    trees.push_back(std::make_shared<const Shape>(Shape{key, true, left, right}));
                }
            }
        }
    }
    return trees;
}

}  // namespace

int main() {
    std::cout << std::setw(3) << "n" << std::setw(11) << "rojinegros" << std::setw(7) << "2-3-4" << std::setw(10) << "suma.2^t"
              << std::setw(13) << "alcanzables" << std::setw(8) << "h.todos" << std::setw(7) << "h.ins" << std::setw(7) << "cota" << "\n";
    for (int n = 1; n <= 9; n++) {
        std::map<std::string, long> trees_of_group;
        std::map<std::string, int> two_keys_of_group;
        std::set<std::string> valid;
        int max_height = 0;
        for (int blacks = 1; (1 << (blacks - 1)) - 1 <= n; blacks++) {
            for (const Tree& tree : build_all(1, n, blacks, false)) {
                int two_keys = 0;
                std::string group = collapse(tree, two_keys);
                trees_of_group[group]++;
                two_keys_of_group[group] = two_keys;
                valid.insert(text_of(tree));
                max_height = std::max(max_height, height_of(tree));
            }
        }
        long total = 0;
        for (const auto& [group, count] : trees_of_group) {
            if (count != 1L << two_keys_of_group[group]) {
                std::cout << "no calza 2^t en " << group << "\n";
                return 1;
            }
            total += 1L << two_keys_of_group[group];
        }
        std::set<std::string> reachable;
        int max_inserted = 0;
        std::vector<int> keys(n);
        std::iota(keys.begin(), keys.end(), 1);
        do {
            RedBlackSet<int> tree;
            for (int key : keys) {
                tree.insert(key);
            }
            reachable.insert(tree.shape());
            max_inserted = std::max(max_inserted, tree.height());
        } while (std::next_permutation(keys.begin(), keys.end()));
        for (const std::string& shape : reachable) {
            if (valid.count(shape) == 0) {
                std::cout << "insertar dio un arbol no valido: " << shape << "\n";
                return 1;
            }
        }
        std::cout << std::setw(3) << n << std::setw(11) << valid.size() << std::setw(7) << trees_of_group.size()
                  << std::setw(10) << total << std::setw(13) << reachable.size() << std::setw(8) << max_height
                  << std::setw(7) << max_inserted << std::fixed << std::setprecision(2) << std::setw(7)
                  << 2 * std::log2(n + 1.0) - 1 << "\n";
    }
    return 0;
}