// Pruebas de la sesión A: cada autómata de machines/ contra una función que decide el mismo
// lenguaje mirando la cadena completa, las ejecuciones copiadas en los apuntes, y los tres
// finales de la búsqueda (acepta, rechaza, límite).
#include <cassert>
#include <cstddef>
#include <functional>
#include <iostream>
#include <sstream>
#include <stdexcept>
#include <string>
#include <vector>

#include "cfg.h"
#include "convert.h"
#include "pda.h"
#include "predicates.h"

namespace {

// Compara el autómata con la función en todas las cadenas de longitud a lo sumo n.
std::size_t check_language(const std::string& path, const std::function<bool(const std::string&)>& expected,
                           std::size_t n) {
    Pda p = load_pda(path);
    std::size_t total = 0;
    for (const std::string& w : all_strings(p.alphabet, n)) {
        assert(accepts(p, w) == expected(w));
        total++;
    }
    return total;
}

std::vector<std::string> states_of(const std::vector<Step>& run) {
    std::vector<std::string> states;
    for (const Step& step : run) {
        states.push_back(step.config.state);
    }
    return states;
}

bool throws(const std::string& path) {
    try {
        load_pda(path);
    } catch (const std::runtime_error&) {
        return true;
    }
    return false;
}

}  // namespace

int main() {
    // Cada autómata reconoce el lenguaje que dicen los apuntes.
    std::size_t strings = 0;
    strings += check_language("machines/zeros_ones.pda", is_zeros_ones, 10);
    strings += check_language("machines/zeros_ones_norm.pda", is_zeros_ones, 10);
    strings += check_language("machines/even_palindromes.pda", is_even_palindrome, 10);
    strings += check_language("machines/balanced.pda", is_balanced, 10);
    strings += check_language("machines/equal_ab.pda", has_equal_ab, 10);
    strings += check_language("machines/even_ones.pda", has_even_ones, 10);
    strings += check_language("machines/anbn_cm.pda", is_anbn_cm, 8);
    strings += check_language("machines/ij_or_jk.pda", is_ij_or_jk, 8);

    // El intento de reconocer a^n b^n c^n acepta de más: no compara las c con nada.
    Pda attempt = load_pda("machines/anbn_cm.pda");
    assert(accepts(attempt, "aabbcc"));
    assert(accepts(attempt, "aabbc"));
    assert(accepts(attempt, "aabbccccc"));
    assert(!is_anbncn("aabbc"));

    // La ejecución de 0011 que está en los apuntes: 7 configuraciones, y la pila sube y baja.
    Pda zeros_ones = load_pda("machines/zeros_ones.pda");
    Search search = simulate(zeros_ones, "0011");
    assert(search.verdict == Verdict::Accept);
    assert((states_of(search.run) == std::vector<std::string>{"q0", "q1", "q1", "q1", "q2", "q2", "q3"}));
    std::vector<std::string> stacks;
    for (const Step& step : search.run) {
        stacks.push_back(step.config.stack);
    }
    assert((stacks == std::vector<std::string>{"", "$", "0$", "00$", "0$", "$", ""}));
    assert(search.explored == 7);
    // Con ε acepta sin moverse, porque q0 está en F. Con 001 y con 10 rechaza.
    assert(simulate(zeros_ones, "").run.size() == 1);
    assert(simulate(zeros_ones, "001").verdict == Verdict::Reject);
    assert(simulate(zeros_ones, "001").explored == 5);
    assert(simulate(zeros_ones, "10").explored == 2);
    // 0011 seguido de más símbolos: llega a q3 antes de terminar de leer, y eso no es aceptar.
    assert(!accepts(zeros_ones, "00110"));
    assert(!accepts(zeros_ones, "0101"));

    // Los palíndromos: la ejecución de aceptación de 0110 adivina el medio después de dos símbolos.
    Pda palindromes = load_pda("machines/even_palindromes.pda");
    search = simulate(palindromes, "0110");
    assert(search.verdict == Verdict::Accept);
    assert((states_of(search.run) == std::vector<std::string>{"q0", "q1", "q1", "q1", "q2", "q2", "q2", "q3"}));
    assert(search.run[4].read == EPS && search.run[4].config.pos == 2);
    assert(search.explored == 15);
    assert(simulate(palindromes, "011").verdict == Verdict::Reject);
    assert(simulate(palindromes, "011").explored == 11);

    // Aceptar es por estado: la pila no tiene que estar vacía.
    Pda keeps;
    keeps.states = {"q0", "q1"};
    keeps.alphabet = {'a'};
    keeps.stack = {'x'};
    keeps.start = "q0";
    keeps.accept = {"q1"};
    add_move(keeps, "q0", 'a', EPS, "q1", 'x');
    add_move(keeps, "q1", 'a', EPS, "q1", 'x');
    search = simulate(keeps, "aaa");
    assert(search.verdict == Verdict::Accept && search.run.back().config.stack == "xxx");
    assert(!accepts(keeps, ""));

    // Un ciclo de transiciones ε que no cambia la pila: la búsqueda termina gracias al conjunto
    // de configuraciones vistas, y rechaza.
    Pda cycle;
    cycle.states = {"q0", "q1", "q2"};
    cycle.alphabet = {'a'};
    cycle.stack = {'x'};
    cycle.start = "q0";
    cycle.accept = {"q2"};
    add_move(cycle, "q0", EPS, EPS, "q1", EPS);
    add_move(cycle, "q1", EPS, EPS, "q0", EPS);
    add_move(cycle, "q1", 'a', EPS, "q2", EPS);
    search = simulate(cycle, "");
    assert(search.verdict == Verdict::Reject && search.explored == 2);
    assert(accepts(cycle, "a"));
    assert(!accepts(cycle, "aa"));

    // Un ciclo de transiciones ε que hace crecer la pila: las configuraciones no se acaban.
    Pda grows;
    grows.states = {"q0", "q1"};
    grows.alphabet = {'a'};
    grows.stack = {'x'};
    grows.start = "q0";
    grows.accept = {"q1"};
    add_move(grows, "q0", EPS, EPS, "q0", 'x');
    add_move(grows, "q0", 'a', EPS, "q1", EPS);
    search = simulate(grows, "", 1000);
    assert(search.verdict == Verdict::Limit && search.explored == 1001);
    // La búsqueda por niveles sí encuentra la aceptación, que está a un paso.
    assert(simulate(grows, "a", 1000).verdict == Verdict::Accept);
    // El PDA de la gramática de expresiones tiene uno de esos ciclos, por la regla E → E + T.
    Pda expr = cfg_to_pda(load_cfg("machines/expr.cfg"));
    assert(simulate(expr, "a+a", 5000).verdict == Verdict::Accept);
    assert(simulate(expr, "a+", 5000).verdict == Verdict::Limit);

    // Leer y escribir: lo que write_pda escribe se vuelve a leer igual.
    for (const std::string name : {"zeros_ones", "even_palindromes", "balanced", "equal_ab", "ij_or_jk"}) {
        Pda p = load_pda("machines/" + name + ".pda");
        std::stringstream text;
        write_pda(text, p);
        Pda again = read_pda(text);
        assert(again.states == p.states && again.alphabet == p.alphabet && again.stack == p.stack);
        assert(again.start == p.start && again.accept == p.accept && again.delta == p.delta);
    }
    assert(load_pda("machines/even_ones.pda").stack.empty());
    assert(count_transitions(load_pda("machines/ij_or_jk.pda")) == 14);

    // Las descripciones de errors/ no son un PDA.
    assert(throws("errors/two_symbols.pda"));
    assert(throws("errors/unknown_stack_symbol.pda"));

    std::cout << "test_pda: ok (8 autómatas, " << strings << " cadenas en total)\n";
}
