// Árbol binario de búsqueda óptimo: los greedy que fallan, la tabla y el árbol que sale.
#include <iomanip>
#include <iostream>
#include <string>
#include <vector>

#include "interval_dp.h"

namespace {

void show(const std::vector<std::string>& names, const std::vector<long long>& f) {
    const int n = static_cast<int>(f.size());
    std::cout << "Claves y frecuencias:";
    for (int i = 0; i < n; i++) std::cout << ' ' << names[i] << '=' << f[i];
    const BstTables t = optimal_bst(f);
    std::cout << "\n  C[i][j], rango [i, j)\n  i\\j";
    for (int j = 0; j <= n; j++) std::cout << std::setw(5) << j;
    std::cout << '\n';
    for (int i = 0; i <= n; i++) {
        std::cout << std::setw(5) << i;
        for (int j = 0; j <= n; j++) {
            if (j < i) {
                std::cout << std::setw(5) << ".";
            } else {
                std::cout << std::setw(5) << t.cost[i][j];
            }
        }
        std::cout << '\n';
    }
    std::cout << "  raíz[i][j]\n  i\\j";
    for (int j = 1; j <= n; j++) std::cout << std::setw(5) << j;
    std::cout << '\n';
    for (int i = 0; i < n; i++) {
        std::cout << std::setw(5) << i;
        for (int j = 1; j <= n; j++) {
            std::cout << std::setw(5) << (j <= i ? std::string(".") : names[t.root[i][j]]);
        }
        std::cout << '\n';
    }
    std::vector<int> depth(f.size(), 0);
    bst_depths(t.root, 0, n, 1, depth);
    std::cout << "  árbol: " << bst_shape(t.root, names, 0, n) << "\n  profundidades:";
    for (int i = 0; i < n; i++) std::cout << ' ' << names[i] << '=' << depth[i];
    std::cout << "\n  costo con la definición: " << cost_from_depths(f, depth) << '\n';
    std::cout << "  por fuerza bruta: " << bst_brute(f) << '\n';
    std::cout << "  la más frecuente a la raíz: " << bst_most_frequent_root(f, 0, n, 1) << '\n';
    std::cout << "  balanceado: " << bst_balanced(f, 0, n, 1) << '\n';
}

}  // namespace

int main() {
    show({"A", "B", "C", "D"}, {2, 1, 3, 4});
}