// Subsecuencia creciente más larga: la tabla, el arreglo de finales paso a paso y la reconstrucción.
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <string>
#include <vector>

#include "lis.h"

namespace {

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

void show_quadratic(const std::vector<int>& a) {
    const LisTable t = lis_quadratic(a);
    std::cout << "   i:";
    for (std::size_t i = 0; i < a.size(); i++) std::cout << std::setw(3) << i;
    std::cout << "\na[i]:";
    for (int x : a) std::cout << std::setw(3) << x;
    std::cout << "\nE[i]:";
    for (int e : t.ending) std::cout << std::setw(3) << e;
    std::cout << "\npred:";
    for (int p : t.pred) std::cout << std::setw(3) << p;
    std::cout << '\n';
}

void show_tails(const std::vector<int>& a) {
    std::vector<int> tails;
    std::vector<int> tail_index;
    std::vector<int> pred(a.size(), -1);
    std::cout << " i  x  posición  finales después        índices    pred[i]\n";
    for (int i = 0; i < static_cast<int>(a.size()); i++) {
        const auto it = std::lower_bound(tails.begin(), tails.end(), a[i]);
        const std::size_t position = static_cast<std::size_t>(it - tails.begin());
        if (position > 0) pred[i] = tail_index[position - 1];
        if (it == tails.end()) {
            tails.push_back(a[i]);
            tail_index.push_back(i);
        } else {
            *it = a[i];
            tail_index[position] = i;
        }
        std::cout << std::setw(2) << i << std::setw(3) << a[i] << std::setw(10) << position << "  ";
        std::string text;
        for (int x : tails) text += std::to_string(x) + " ";
        std::cout << std::left << std::setw(23) << text;
        text.clear();
        for (int x : tail_index) text += std::to_string(x) + " ";
        std::cout << std::setw(11) << text << std::right << std::setw(4) << pred[i] << '\n';
    }
}

}  // namespace

int main() {
    const std::vector<int> a = {3, 1, 4, 1, 5, 9, 2, 6};
    std::cout << "Arreglo: ";
    print_values(a);
    std::cout << "\n\nLa tabla cuadrática\n";
    show_quadratic(a);
    std::cout << "Largo: " << lis_length_quadratic(a) << "\nCon pred, desde la primera casilla con ese largo:";
    {
        const LisTable t = lis_quadratic(a);
        std::vector<int> walk;
        for (int i = static_cast<int>(std::max_element(t.ending.begin(), t.ending.end()) - t.ending.begin()); i != -1; i = t.pred[i]) {
            walk.push_back(a[i]);
        }
        for (std::size_t k = walk.size(); k-- > 0;) std::cout << ' ' << walk[k];
    }
    std::cout << "\n\nEl arreglo de finales, con lower_bound\n";
    show_tails(a);
    std::cout << "Largo: " << lis_length_tails(a) << "\nReconstruida:";
    for (int i : lis_indices(a)) std::cout << ' ' << a[i];

    std::cout << "\n\nTomar todo lo que sea mayor que lo último tomado\n";
    for (const std::vector<int>& b : {std::vector<int>{5, 1, 2, 3}, std::vector<int>{1, 7, 2, 3, 4}}) {
        std::cout << "  ";
        print_values(b);
        std::cout << ": greedy " << lis_greedy_take(b) << ", óptimo " << lis_length_tails(b) << '\n';
    }

    const std::vector<int> c = {2, 5, 3, 7, 1};
    std::cout << "\nLos finales no son una subsecuencia\n  arreglo: ";
    print_values(c);
    std::cout << "\n  finales: ";
    print_values(final_tails(c));
    std::cout << "\n  reconstruida:";
    for (int i : lis_indices(c)) std::cout << ' ' << c[i];
    std::cout << '\n';

    std::cout << "\nlower_bound y upper_bound\n";
    for (const std::vector<int>& d : {std::vector<int>{2, 2, 2}, std::vector<int>{1, 3, 3, 5}}) {
        std::cout << "  ";
        print_values(d);
        std::cout << ": con lower_bound " << lis_length_tails(d) << ", con upper_bound "
                  << non_decreasing_length_tails(d) << '\n';
    }
}