// Pruebas de la eliminación de estados (sesión B).
// La expresión que sale de un DFA se vuelve a leer, se convierte en un NFA con la construcción
// de Thompson y se compara con el DFA original sobre todas las cadenas cortas. Así se cierra
// el triángulo: DFA → expresión → NFA, y los dos extremos deben aceptar lo mismo.
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <string>
#include <vector>

#include "dfa.h"
#include "gnfa.h"
#include "nfa.h"
#include "regex.h"
#include "thompson.h"
#include "words.h"

// La expresión, pasando por su texto: comprueba de paso que lo escrito se puede volver a leer.
static Nfa nfa_of(const RegexPtr& r, const std::vector<char>& alphabet) {
    return thompson(parse_regex(to_string(r)), alphabet);
}

static void check_equivalent(const Dfa& m, const RegexPtr& r, std::size_t max_len) {
    Nfa n = nfa_of(r, m.alphabet);
    for (const std::string& w : all_strings(m.alphabet, max_len)) {
        assert(accepts(m, w) == accepts(n, w));
    }
}

// Todos los órdenes de eliminación de m. Devuelve cuántos son.
static std::size_t check_all_orders(const std::string& path, std::size_t max_len) {
    Dfa m = load_dfa(path);
    std::vector<std::string> order = m.states;
    std::sort(order.begin(), order.end());
    std::size_t count = 0;
    do {
        check_equivalent(m, to_regex(m, order), max_len);
        count++;
    } while (std::next_permutation(order.begin(), order.end()));
    return count;
}

static Dfa multiples_of(int k) {
    Dfa m;
    m.alphabet = {'0', '1'};
    for (int i = 0; i < k; i++) {
        m.states.push_back("r" + std::to_string(i));
    }
    m.start = "r0";
    m.accept = {"r0"};
    for (int i = 0; i < k; i++) {
        m.delta[{m.states[i], '0'}] = m.states[(2 * i) % k];
        m.delta[{m.states[i], '1'}] = m.states[(2 * i + 1) % k];
    }
    check_dfa(m);
    return m;
}

static void test_gnfa_of_dfa() {
    Dfa m = load_dfa("machines/multiple_of_3.dfa");
    Gnfa g = to_gnfa(m);
    assert(g.states == (std::vector<std::string>{"ini", "r0", "r1", "r2", "fin"}));
    assert(g.arrow.size() == 8);
    assert(to_string(label(g, "ini", "r0")) == "ε");
    assert(to_string(label(g, "r0", "fin")) == "ε");
    assert(to_string(label(g, "r0", "r1")) == "1");
    assert(to_string(label(g, "r2", "r2")) == "1");
    assert(label(g, "r0", "r2")->kind == Kind::Empty);  // la flecha que no está lleva ∅
    // Al inicial no le entra nada y del de aceptación no sale nada.
    for (const auto& [key, r] : g.arrow) {
        assert(key.second != g.start && key.first != g.accept);
    }
    // Dos símbolos entre los mismos estados se juntan en una unión.
    Dfa all;
    all.states = {"q"};
    all.alphabet = {'0', '1'};
    all.start = "q";
    all.accept = {"q"};
    all.delta[{"q", '0'}] = "q";
    all.delta[{"q", '1'}] = "q";
    assert(to_string(label(to_gnfa(all), "q", "q")) == "0|1");
    assert(to_string(to_regex(all, {"q"})) == "(0|1)*");
    // Sin estados de aceptación no hay camino hasta fin: sale ∅.
    all.accept.clear();
    assert(to_regex(all, {"q"})->kind == Kind::Empty);
}

static void test_steps_of_the_notes() {
    // El ejemplo de dos estados, en los dos órdenes.
    Dfa parity = load_dfa("machines/even_ones.dfa");
    Gnfa g = eliminate(to_gnfa(parity), "impar");
    assert(g.arrow.size() == 3);
    assert(to_string(label(g, "par", "par")) == "0|10*1");
    assert(to_string(to_regex(parity, {"impar", "par"})) == "(0|10*1)*");
    Gnfa h = eliminate(to_gnfa(parity), "par");
    assert(to_string(label(h, "ini", "impar")) == "0*1");
    assert(to_string(label(h, "ini", "fin")) == "0*");
    assert(to_string(label(h, "impar", "impar")) == "0|10*1");
    assert(to_string(label(h, "impar", "fin")) == "10*");
    assert(to_string(to_regex(parity, {"par", "impar"})) == "0*|0*1(0|10*1)*10*");

    // El ejemplo completo de tres estados: r2, r1, r0.
    Dfa three = load_dfa("machines/multiple_of_3.dfa");
    Gnfa a = eliminate(to_gnfa(three), "r2");
    assert(a.arrow.size() == 6);
    assert(to_string(label(a, "r1", "r1")) == "01*0");
    assert(to_string(label(a, "r0", "r1")) == "1" && to_string(label(a, "r1", "r0")) == "1");
    Gnfa b = eliminate(a, "r1");
    assert(b.arrow.size() == 3);
    assert(to_string(label(b, "r0", "r0")) == "0|1(01*0)*1");
    assert(to_string(to_regex(three, {"r2", "r1", "r0"})) == "(0|1(01*0)*1)*");
    assert(size(to_regex(three, {"r2", "r1", "r0"})) == 14);
    assert(to_string(to_regex(three, {"r1", "r2", "r0"})) == "(0|11|10(1|00)*01)*");
    assert(size(to_regex(three, {"r0", "r1", "r2"})) == 65);
    // La de 14 nodos y la de 65 describen el mismo lenguaje: los múltiplos de 3.
    Nfa small = nfa_of(to_regex(three, {"r2", "r1", "r0"}), three.alphabet);
    Nfa large = nfa_of(to_regex(three, {"r0", "r1", "r2"}), three.alphabet);
    for (const std::string& w : all_strings(three.alphabet, 9)) {
        bool multiple = w.empty() || std::stoul(w, nullptr, 2) % 3 == 0;
        assert(accepts(small, w) == multiple && accepts(large, w) == multiple);
    }
    // Termina en 01.
    Dfa ends = load_dfa("machines/ends_01.dfa");
    assert(to_string(to_regex(ends, {"q2", "q0", "q1"})) == "1*0(0|10|111*0)*1");
    // No es la más corta: (0|1)*01 describe lo mismo que el autómata.
    check_equivalent(ends, parse_regex("(0|1)*01"), 9);
    // Sin 11: la eliminación devuelve la expresión que la sesión A escribió a mano.
    Dfa no_11 = load_dfa("machines/no_11.dfa");
    assert(to_string(to_regex(no_11, {"q2", "q1", "q0"})) == "(0|10)*(ε|1)");
    assert(to_string(to_regex(no_11, {"q0", "q1", "q2"})) == "0*|0*1(00*1)*(ε|00*)");
}

static void test_growth_table() {
    // La tabla de growth: nodos de la expresión con r0 primero y con r0 al final.
    std::vector<std::vector<std::size_t>> expected = {{2, 22, 9}, {3, 65, 14}, {4, 110, 27}, {5, 314, 52}};
    for (const std::vector<std::size_t>& row : expected) {
        Dfa m = multiples_of(static_cast<int>(row[0]));
        std::vector<std::string> backward(m.states.rbegin(), m.states.rend());
        RegexPtr first = to_regex(m, m.states);
        RegexPtr last = to_regex(m, backward);
        assert(size(first) == row[1] && size(last) == row[2]);
        check_equivalent(m, first, 6);
        check_equivalent(m, last, 6);
    }
}

int main() {
    test_gnfa_of_dfa();
    test_steps_of_the_notes();
    std::size_t orders = 0;
    orders += check_all_orders("machines/even_ones.dfa", 8);
    orders += check_all_orders("machines/multiple_of_3.dfa", 8);
    orders += check_all_orders("machines/ends_01.dfa", 8);
    orders += check_all_orders("machines/no_11.dfa", 8);
    test_growth_table();
    std::printf("test_elimination: ok (4 autómatas, %zu órdenes de eliminación, 511 cadenas cada uno)\n", orders);
}
