// Pruebas de las construcciones: el PDA de una gramática acepta exactamente lo que la gramática
// genera; la gramática de un PDA genera exactamente lo que el PDA acepta; normalizar no cambia
// el lenguaje; y las construcciones de cierre.
#include <cassert>
#include <cstddef>
#include <functional>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>

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

namespace {

// Las cadenas de longitud a lo sumo n que el autómata acepta.
std::set<std::string> accepted_up_to(const Pda& p, std::size_t n) {
    std::set<std::string> result;
    for (const std::string& w : all_strings(p.alphabet, n)) {
        if (accepts(p, w)) {
            result.insert(w);
        }
    }
    return result;
}

// Las cadenas de longitud a lo sumo n que cumplen la función.
std::set<std::string> filter(const std::vector<char>& sigma, std::size_t n,
                             const std::function<bool(const std::string&)>& expected) {
    std::set<std::string> result;
    for (const std::string& w : all_strings(sigma, n)) {
        if (expected(w)) {
            result.insert(w);
        }
    }
    return result;
}

std::set<std::string> intersect(const std::set<std::string>& a, const std::set<std::string>& b) {
    std::set<std::string> result;
    for (const std::string& w : a) {
        if (b.count(w) > 0) {
            result.insert(w);
        }
    }
    return result;
}

}  // namespace

int main() {
    // --- De gramática a PDA -------------------------------------------------------------
    struct Case {
        std::string name;
        std::function<bool(const std::string&)> expected;
        std::size_t n;
    };
    std::vector<Case> grammars = {
        {"zeros_ones", is_zeros_ones, 10},      {"balanced", is_balanced, 10}, {"even_palindromes", is_even_palindrome, 10},
        {"equal_ab", has_equal_ab, 8},          {"anbn_cm", is_anbn_cm, 7},    {"am_bncn", is_am_bncn, 7},
    };
    for (const Case& c : grammars) {
        Cfg g = load_cfg("machines/" + c.name + ".cfg");
        std::set<std::string> generated = strings_up_to(g, c.n);
        // La gramática genera el lenguaje que dicen los apuntes…
        assert(generated == filter(g.terminals, c.n, c.expected));
        // … y el PDA construido acepta exactamente las mismas cadenas.
        Pda p = cfg_to_pda(g);
        assert(accepted_up_to(p, c.n) == generated);
        // Cuatro estados fijos, y k − 1 intermedios por cada regla con k ≥ 2 símbolos a la derecha.
        std::size_t states = 4;
        for (const Rule& rule : g.rules) {
            states += rule.body.size() >= 2 ? rule.body.size() - 1 : 0;
        }
        assert(p.states.size() == states);
    }
    // El ejemplo de los apuntes: la gramática de los paréntesis da 7 estados y 10 transiciones,
    // y la ejecución de aceptación de () tiene 12 configuraciones.
    Pda balanced = cfg_to_pda(load_cfg("machines/balanced.cfg"));
    assert(balanced.states.size() == 7 && count_transitions(balanced) == 10);
    Search search = simulate(balanced, "()");
    assert(search.verdict == Verdict::Accept && search.run.size() == 12);
    assert(search.run[6].config.stack == "(S)S$" && search.run[6].config.state == "q_loop");
    assert(simulate(balanced, "(()").verdict == Verdict::Reject);

    // La gramática de expresiones es recursiva por la izquierda: el PDA tiene configuraciones
    // sin fin, y la búsqueda sin tope no puede rechazar. Como la gramática no tiene reglas ε,
    // cada símbolo de la pila genera al menos un terminal, y una ejecución de aceptación nunca
    // tiene más de |w| + 1 símbolos en la pila (el + 1 es por $). Con ese tope la búsqueda decide.
    Cfg expr = load_cfg("machines/expr.cfg");
    Pda expr_pda = cfg_to_pda(expr);
    assert(expr_pda.states.size() == 10);
    std::set<std::string> expressions = strings_up_to(expr, 5);
    assert(expressions.size() == 15);
    for (const std::string& w : all_strings(expr.terminals, 5)) {
        Search bounded = simulate(expr_pda, w, 100000, w.size() + 1);
        assert(bounded.verdict != Verdict::Limit);
        assert((bounded.verdict == Verdict::Accept) == (expressions.count(w) > 0));
    }

    // --- Normalizar, y de PDA a gramática --------------------------------------------------
    std::vector<std::string> machines = {"zeros_ones", "zeros_ones_norm", "even_palindromes", "balanced",
                                         "equal_ab",   "even_ones",       "anbn_cm",          "ij_or_jk"};
    for (const std::string& name : machines) {
        Pda p = load_pda("machines/" + name + ".pda");
        std::size_t n = p.alphabet.size() == 2 ? 6 : 5;
        std::set<std::string> language = accepted_up_to(p, n);
        Pda normal = normalize_pda(p);
        assert(has_normal_shape(normal));
        for (const std::string& w : all_strings(p.alphabet, n)) {
            Search run = simulate(normal, w);
            assert(run.verdict != Verdict::Limit);
            assert((run.verdict == Verdict::Accept) == (language.count(w) > 0));
            // Al aceptar, la pila está vacía.
            assert(run.verdict != Verdict::Accept || run.run.back().config.stack.empty());
        }
        Cfg g = pda_to_cfg(normal);
        assert(g.variables.size() == normal.states.size() * normal.states.size());
        assert(strings_up_to(remove_useless(g), n) == language);
    }
    // El ejemplo de los apuntes, sin pasar por normalize_pda porque ya está normalizado.
    Pda small = load_pda("machines/zeros_ones_norm.pda");
    assert(has_normal_shape(small));
    assert(!has_normal_shape(load_pda("machines/zeros_ones.pda")));
    Cfg from_small = pda_to_cfg(small);
    assert(from_small.variables.size() == 16 && from_small.rules.size() == 72);
    Cfg useful = remove_useless(from_small);
    assert(useful.variables.size() == 6 && useful.rules.size() == 16);
    assert(from_small.start == "A(q0,q3)");
    // Sin limpiar genera lo mismo: quitar las variables que no sirven no cambia el lenguaje.
    assert(strings_up_to(from_small, 10) == filter(small.alphabet, 10, is_zeros_ones));
    assert(strings_up_to(useful, 10) == filter(small.alphabet, 10, is_zeros_ones));
    // Lo que cada variable genera, como dice la demostración: A(q1,q2) son las cadenas 0^n 1^n con n ≥ 1.
    std::map<std::string, std::set<std::string>> table = languages_up_to(from_small, 8);
    assert((table["A(q1,q2)"] == std::set<std::string>{"01", "0011", "000111", "00001111"}));
    assert(table["A(q1,q1)"] == std::set<std::string>{""});
    assert(table["A(q2,q1)"].empty());

    // --- Cierre ----------------------------------------------------------------------------
    Cfg first = load_cfg("machines/anbn_cm.cfg");
    Cfg second = load_cfg("machines/am_bncn.cfg");
    std::size_t n = 7;
    std::set<std::string> a = strings_up_to(first, n);
    std::set<std::string> b = strings_up_to(second, n);
    // Unión.
    std::set<std::string> both = a;
    both.insert(b.begin(), b.end());
    assert(strings_up_to(cfg_union(first, second), n) == both);
    assert(both == filter(first.terminals, n, is_ij_or_jk));
    // Concatenación.
    std::set<std::string> products;
    for (const std::string& u : a) {
        for (const std::string& v : b) {
            if (u.size() + v.size() <= n) {
                products.insert(u + v);
            }
        }
    }
    assert(strings_up_to(cfg_concat(first, second), n) == products);
    // Estrella, con { 0^n 1^n }: las concatenaciones de cero o más cadenas del lenguaje.
    Cfg zeros_ones = load_cfg("machines/zeros_ones.cfg");
    std::set<std::string> base = strings_up_to(zeros_ones, 8);
    std::set<std::string> star = {""};
    for (bool grew = true; grew;) {
        grew = false;
        for (const std::string& u : std::set<std::string>(star)) {
            for (const std::string& v : base) {
                if (u.size() + v.size() <= 8 && star.insert(u + v).second) {
                    grew = true;
                }
            }
        }
    }
    assert(strings_up_to(cfg_star(zeros_ones), 8) == star);
    assert(star.count("0101") > 0 && star.count("010011") > 0 && star.count("0110") == 0);
    // La intersección de los dos lenguajes libres de contexto es { a^n b^n c^n }.
    assert(intersect(a, b) == filter(first.terminals, n, is_anbncn));
    assert(intersect(a, b) == (std::set<std::string>{"", "abc", "aabbcc"}));

    std::cout << "test_convert: ok (7 gramáticas a PDA, 8 autómatas normalizados y pasados a gramática)\n";
}
