// Intervalos con pesos: los greedy que fallan y el recorrido de la tabla.
#include <iomanip>
#include <iostream>
#include <vector>

#include "weighted_intervals.h"

namespace {

void print_classes(const std::vector<WeightedInterval>& classes) {
    for (const WeightedInterval& c : classes) {
        std::cout << " [" << c.start << ',' << c.finish << ")v" << c.value;
    }
    std::cout << '\n';
}

void compare(const char* title, const std::vector<WeightedInterval>& classes) {
    std::cout << title << ":\n  clases:";
    print_classes(classes);
    std::cout << "  óptimo por fuerza bruta: " << weighted_brute(classes) << '\n';
    std::cout << "  termina antes (semana 4): " << greedy_earliest_finish(classes) << '\n';
    std::cout << "  mayor valor primero:      " << greedy_highest_value(classes) << '\n';
    std::cout << "  tabla:                    " << weighted_best(classes) << "\n\n";
}

}  // namespace

int main() {
    compare("Una clase valiosa en medio", {{0, 2, 1}, {1, 6, 10}, {5, 7, 1}});
    compare("Una clase larga que estorba", {{0, 10, 5}, {0, 3, 4}, {3, 6, 4}, {6, 10, 4}});

    std::vector<WeightedInterval> classes = {{0, 3, 2}, {1, 5, 4}, {3, 7, 4}, {4, 9, 6}, {7, 10, 2}, {8, 11, 3}};
    compare("El ejemplo del recorrido", classes);

    sort_by_finish(classes);
    const std::vector<std::size_t> p = compatible_prefix(classes);
    const std::vector<long long> best = weighted_table(classes, p);
    std::cout << "j  clase   valor  p(j)  sin ella  con ella  T[j]\n";
    std::cout << "0  -           -     -         -         -" << std::setw(6) << best[0] << '\n';
    for (std::size_t j = 1; j <= classes.size(); j++) {
        const WeightedInterval& c = classes[j - 1];
        std::cout << j << "  [" << c.start << ',' << std::setw(2) << c.finish << ")" << std::setw(7) << c.value << std::setw(6) << p[j - 1] << std::setw(10) << best[j - 1]
                  << std::setw(10) << c.value + best[p[j - 1]] << std::setw(6) << best[j] << '\n';
    }

    std::cout << "\nHacia atrás:\n";
    std::size_t j = classes.size();
    while (j > 0) {
        if (best[j] == best[j - 1]) {
            std::cout << "  T[" << j << "] = T[" << j - 1 << "] = " << best[j] << ": no hace falta la clase " << j
                      << ", j = " << j - 1 << '\n';
            j--;
        } else {
            const WeightedInterval& c = classes[j - 1];
            std::cout << "  T[" << j << "] = " << best[j] << " > T[" << j - 1 << "] = " << best[j - 1] << ": se toma ["
                      << c.start << ',' << c.finish << "), j = p(" << j << ") = " << p[j - 1] << '\n';
            j = p[j - 1];
        }
    }
    std::cout << "Elegidas:";
    for (std::size_t i : weighted_choose(classes, p, best)) {
        std::cout << " [" << classes[i].start << ',' << classes[i].finish << ")";
    }
    std::cout << ", valor " << best.back() << '\n';

    std::cout << "\nSi el borde contara como cruce (lower_bound en vez de upper_bound):\n";
    const std::vector<std::size_t> closed = compatible_prefix_closed(classes);
    std::cout << "  p:";
    for (std::size_t value : closed) std::cout << ' ' << value;
    std::cout << "\n  valor: " << weighted_table(classes, closed).back() << " en vez de " << best.back() << '\n';
}