// Compara un árbol rojinegro colapsado con un árbol 2-3-4 armado con las mismas claves.
// Para cada orden de inserción y cada política de división, compara la forma completa:
// las claves de cada nodo y el orden de sus hijos.
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <random>
#include <string>
#include <vector>

#include "rb_set.h"
#include "tree_234.h"

namespace {

struct Policy {
    const char* name;
    SplitPolicy value;
    std::vector<int> first_difference;
};

// Compara al final, y también revisa las cuentas de la política que debe calzar.
bool same_shape(const std::vector<int>& keys, SplitPolicy policy) {
    RedBlackSet<int> red_black;
    Tree234<int> tree(policy);
    for (int key : keys) {
        red_black.insert(key);
        tree.insert(key);
    }
    return red_black.collapsed() == tree.shape();
}

// Tras cada inserción: la misma forma, tantas divisiones como recoloreos, y tantos niveles como negros.
bool matches_step_by_step(const std::vector<int>& keys) {
    RedBlackSet<int> red_black;
    Tree234<int> tree(SplitPolicy::old_middle);
    for (int key : keys) {
        red_black.insert(key);
        tree.insert(key);
        if (red_black.collapsed() != tree.shape() || red_black.recolors() != tree.splits()
            || red_black.black_height() != tree.levels()) {
            return false;
        }
    }
    return true;
}

void print_keys(const std::vector<int>& keys) {
    for (std::size_t i = 0; i < keys.size(); i++) {
        std::cout << (i > 0 ? " " : "") << keys[i];
    }
}

}  // namespace

int main() {
    std::vector<Policy> policies = {
        {"al hacer overflow, sube la del medio de las 3", SplitPolicy::old_middle, {}},
        {"al hacer overflow, sube siempre la segunda de las 4", SplitPolicy::fixed_second, {}},
        {"al bajar, se divide todo nodo lleno", SplitPolicy::top_down, {}},
    };
    std::cout << std::setw(3) << "n" << std::setw(8) << "ordenes" << std::setw(9) << "medio" << std::setw(9) << "segunda"
              << std::setw(9) << "al.bajar" << "\n";
    for (int n = 1; n <= 9; n++) {
        std::vector<int> keys(n);
        std::iota(keys.begin(), keys.end(), 1);
        long orders = 0;
        std::vector<long> different(policies.size(), 0);
        do {
            orders++;
            for (std::size_t p = 0; p < policies.size(); p++) {
                if (!same_shape(keys, policies[p].value)) {
                    different[p]++;
                    if (policies[p].first_difference.empty()) {
                        policies[p].first_difference = keys;
                    }
                }
            }
            if (n <= 8 && !matches_step_by_step(keys)) {
                std::cout << "no calza paso a paso\n";
                return 1;
            }
        } while (std::next_permutation(keys.begin(), keys.end()));
        std::cout << std::setw(3) << n << std::setw(8) << orders;
        for (long count : different) {
            std::cout << std::setw(9) << count;
        }
        std::cout << "\n";
    }
    std::cout << "Primer orden en que no calza\n";
    for (const Policy& policy : policies) {
        std::cout << "  " << policy.name << ": ";
        if (policy.first_difference.empty()) {
            std::cout << "ninguno\n";
            continue;
        }
        print_keys(policy.first_difference);
        std::cout << "\n";
        RedBlackSet<int> red_black;
        Tree234<int> tree(policy.value);
        for (int key : policy.first_difference) {
            red_black.insert(key);
            tree.insert(key);
        }
        std::cout << "    rojinegro: " << red_black.collapsed() << "\n";
        std::cout << "    2-3-4:     " << tree.shape() << "\n";
    }
    std::cout << "Claves al azar, tres semillas, comparando tras cada insercion\n";
    for (unsigned seed : {12u, 13u, 14u}) {
        std::vector<int> keys(3000);
        std::iota(keys.begin(), keys.end(), 0);
        std::mt19937 random(seed);
        std::shuffle(keys.begin(), keys.end(), random);
        std::cout << "  semilla " << seed << ": " << (matches_step_by_step(keys) ? "calza" : "no calza") << "\n";
    }
    return 0;
}