// Pruebas de CYK (sesión B): responde lo mismo que las otras dos maneras de saber si una
// gramática genera una cadena, la tabla del ejemplo es la de los apuntes, y el árbol que
// recupera es un árbol de derivación de la cadena.
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <functional>
#include <set>
#include <sstream>
#include <stdexcept>
#include <string>
#include <vector>

#include "cfg.h"
#include "chomsky.h"
#include "predicates.h"

struct Case {
    const char* path;
    std::size_t max_length;
    std::function<bool(const std::string&)> in_language;
};

static std::size_t binary_rules(const Cfg& g) {
    std::size_t total = 0;
    for (const Rule& rule : g.rules) {
        total += (rule.body.size() == 2);
    }
    return total;
}

// Para todas las cadenas hasta una longitud: CYK con la gramática convertida responde lo mismo
// que el predicado y que el cálculo de L(G) con la gramática original.
static std::size_t test_agreement() {
    std::vector<Case> cases = {
        {"machines/zeros_ones.cfg", 9, is_zeros_ones},     {"machines/palindromes.cfg", 8, is_palindrome},
        {"machines/parens.cfg", 9, is_balanced},           {"machines/parens_ss.cfg", 8, is_balanced},
        {"machines/equal_ab.cfg", 8, has_equal_ab},        {"machines/even_ones.cfg", 8, has_even_ones},
        {"machines/blocks.cfg", 9, is_block_list},         {"machines/abc_union.cfg", 6, is_abc_union},
        {"machines/expr_ambiguous.cfg", 5, is_expression}, {"machines/expr_precedence.cfg", 4, is_expression},
        {"machines/dangling_else.cfg", 6, is_if_else},     {"machines/dangling_else_fixed.cfg", 6, is_if_else},
    };
    std::size_t total = 0;
    for (const Case& c : cases) {
        Cfg original = load_cfg(c.path);
        Cfg g = to_chomsky(original);
        std::set<std::string> generated = generated_strings(original, c.max_length);
        for (const std::string& w : all_strings(original.terminals, c.max_length)) {
            CykTable table = cyk(g, w);
            bool answer = cyk_accepts(g, table);
            assert(answer == c.in_language(w));
            assert(answer == (generated.count(w) > 0));
            // El costo: (n³ − n)/6 pares de celdas, por la cantidad de reglas A → BC.
            std::size_t n = w.size();
            assert(static_cast<std::size_t>(table.checks) == (n * n * n - n) / 6 * binary_rules(g));
            if (answer) {
                Tree tree = cyk_tree(g, table, w);
                assert(is_parse_tree(g, tree) && yield_of(tree) == w);
                assert(count_inner(tree) == (n == 0 ? 1 : 2 * n - 1));
                assert(count_trees(g, w) >= 1);
            } else {
                assert(count_trees(g, w) == 0);
            }
            total++;
        }
    }
    return total;
}

static std::string cell_text(const Cfg& g, const CykTable& table, std::size_t i, std::size_t j) {
    std::string text;
    for (const std::string& name : g.variables) {
        if (table.cell[i][j].count(name) > 0) {
            text += (text.empty() ? "" : ",") + name;
        }
    }
    return text;
}

// La tabla de a+a*a con la gramática ambigua convertida, celda por celda, como en los apuntes.
static void test_table_of_the_notes() {
    Cfg g = load_cfg("machines/expr_ambiguous_chomsky.cfg");
    // El archivo guardado es lo que produce la conversión.
    Cfg converted = to_chomsky(load_cfg("machines/expr_ambiguous.cfg"));
    assert(g.variables == converted.variables && g.start == converted.start);
    assert(g.rules.size() == converted.rules.size());
    for (const Rule& rule : converted.rules) {
        assert(std::find(g.rules.begin(), g.rules.end(), rule) != g.rules.end());
    }
    assert(g.variables.size() == 12 && g.rules.size() == 18 && binary_rules(g) == 12);

    std::string w = "a+a*a";
    CykTable table = cyk(g, w);
    std::vector<std::vector<std::string>> expected = {
        {"E0,E", "", "E0,E", "", "E0,E"},
        {"", "U_+", "E0_1,E_1", "", "E0_1,E_1"},
        {"", "", "E0,E", "", "E0,E"},
        {"", "", "", "U_*", "E0_2,E_2"},
        {"", "", "", "", "E0,E"},
    };
    for (std::size_t i = 0; i < 5; i++) {
        for (std::size_t j = i; j < 5; j++) {
            assert(cell_text(g, table, i, j) == expected[i][j]);
        }
    }
    assert(table.checks == 240);
    assert(cyk_accepts(g, table));
    Tree tree = cyk_tree(g, table, w);
    assert(bracket_text(tree) == "[E0 [E a] [E0_1 [U_+ +] [E [E a] [E_2 [U_* *] [E a]]]]]");
    // Dos árboles, como las dos derivaciones por la izquierda de la gramática original.
    assert(count_trees(g, w) == 2);
    assert(leftmost_derivations(g, w, 9, 1000).found.size() == 2);
    assert(count_trees(to_chomsky(load_cfg("machines/expr_precedence.cfg")), w) == 1);
    // a+a+a+a tiene 5 árboles: los números de Catalan.
    assert(count_trees(g, "a+a+a+a") == 5);
    assert(count_trees(g, "a+a+a+a+a") == 14);
    assert(!cyk_accepts(g, "a+"));
    assert(!cyk_accepts(g, ""));
}

// El conteo de árboles de CYK coincide con el número de derivaciones por la izquierda.
static void test_tree_counts() {
    for (const char* path : {"machines/parens_ss.cfg", "machines/equal_ab.cfg", "machines/abc_union.cfg",
                             "machines/dangling_else.cfg"}) {
        Cfg g = to_chomsky(load_cfg(path));
        for (const std::string& w : generated_strings(g, 6)) {
            DerivationSearch search = leftmost_derivations(g, w, 1000, 100000);
            assert(search.complete);
            assert(count_trees(g, w) == search.found.size());
        }
    }
}

static void test_edge_cases() {
    // CYK rechaza una gramática que no está en forma normal de Chomsky.
    Cfg parens = load_cfg("machines/parens.cfg");
    bool thrown = false;
    try {
        cyk(parens, "()");
    } catch (const std::runtime_error&) {
        thrown = true;
    }
    assert(thrown);
    // La cadena vacía: depende solo de la regla S0 → ε.
    assert(cyk_accepts(to_chomsky(parens), ""));
    assert(!cyk_accepts(to_chomsky(load_cfg("machines/two_derivations.cfg")), ""));
    // Una gramática que no genera nada: B no termina nunca. Y C no tiene reglas.
    std::istringstream text("variables: S A B C\nterminals: a\nstart: S\nrules:\nS -> A B | A C\nA -> a\nB -> B B\n");
    Cfg nothing = read_cfg(text);
    assert(is_chomsky(nothing));
    assert(generated_strings(nothing, 8).empty());
    for (const std::string& w : all_strings(nothing.terminals, 8)) {
        assert(!cyk_accepts(nothing, w));
    }
}

int main() {
    std::size_t total = test_agreement();
    test_table_of_the_notes();
    test_tree_counts();
    test_edge_cases();
    std::printf("test_cyk: ok (12 gramáticas, %zu cadenas)\n", total);
}
