// Pruebas de los procedimientos de decisión sobre gramáticas: E_CFG y A_CFG.
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <random>
#include <set>
#include <stdexcept>
#include <string>
#include <vector>

#include "cfg.h"

static std::vector<std::string> all_strings(const std::vector<char>& alphabet, std::size_t max_len) {
    std::vector<std::string> result = {""};
    std::size_t begin = 0;
    for (std::size_t len = 1; len <= max_len; len++) {
        std::size_t end = result.size();
        for (std::size_t i = begin; i < end; i++) {
            for (char a : alphabet) {
                result.push_back(result[i] + a);
            }
        }
        begin = end;
    }
    return result;
}

static bool is_anbn(const std::string& w) {
    std::size_t n = w.size() / 2;
    return w.size() % 2 == 0 && w == std::string(n, 'a') + std::string(n, 'b');
}

// E_CFG: las marcas de los apuntes.
static void test_marking() {
    Cfg parens = load_cfg("machines/parens.cfg");
    assert(generating(parens) == (std::set<std::string>{"S"}));
    assert(!is_empty(parens));

    Cfg anbn = load_cfg("machines/anbn_chomsky.cfg");
    std::vector<std::vector<std::string>> rounds = generating_rounds(anbn);
    assert(rounds.size() == 3);
    assert(rounds[0] == (std::vector<std::string>{"S0", "A", "B"}));
    assert(rounds[1] == (std::vector<std::string>{"S"}));
    assert(rounds[2] == (std::vector<std::string>{"T"}));
    assert(!is_empty(anbn));

    // Tiene reglas y dos variables que generan, pero S no genera nada.
    Cfg none = load_cfg("machines/no_base_case.cfg");
    assert(none.rules.size() == 7);
    assert(generating(none) == (std::set<std::string>{"A", "B"}));
    assert(is_empty(none));

    // Con una regla más para C, S pasa a generar: C → b, y entonces S → C A.
    Cfg fixed = none;
    fixed.rules.push_back({"C", {"b"}});
    assert(generating(fixed) == (std::set<std::string>{"S", "A", "B", "C"}));
    assert(!is_empty(fixed));
}

// A_CFG: las derivaciones de 2n − 1 pasos y CYK deciden lo mismo.
static void test_membership() {
    Cfg anbn = load_cfg("machines/anbn_chomsky.cfg");
    assert(is_chomsky(anbn));
    assert(cyk(anbn, "aabb") && !cyk(anbn, "abab") && cyk(anbn, "") && cyk(anbn, "ab"));
    int in_language = 0;
    for (const std::string& w : all_strings({'a', 'b'}, 10)) {
        bool expected = is_anbn(w);
        assert(cyk(anbn, w) == expected);
        assert(derives_bounded(anbn, w) == expected);
        if (expected && !w.empty()) {
            in_language++;
            // Exactamente 2n − 1 pasos: con uno menos no se llega.
            assert(derives_within(anbn, {anbn.start}, w, 2 * w.size() - 1));
            assert(!derives_within(anbn, {anbn.start}, w, 2 * w.size() - 2));
        }
    }
    assert(in_language == 5);

    // La de los paréntesis no está en forma normal de Chomsky: estos algoritmos no la aceptan.
    Cfg parens = load_cfg("machines/parens.cfg");
    assert(!is_chomsky(parens));
    bool failed = false;
    try {
        cyk(parens, "()");
    } catch (const std::runtime_error&) {
        failed = true;
    }
    assert(failed);
}

// Gramáticas al azar en forma normal de Chomsky, con variables S, A, B. El algoritmo de marcas
// dice "no vacío" si y solo si CYK encuentra alguna cadena. Si L(G) no es vacío, tiene una cadena
// con un árbol de derivación sin variables repetidas en ningún camino: a lo sumo |V| = 3
// variables por camino, y entonces a lo sumo 2^2 = 4 hojas.
static void test_emptiness_random() {
    std::mt19937 rng(4129);
    const std::vector<std::string> inner = {"A", "B"};
    int empty = 0;
    for (int round = 0; round < 500; round++) {
        Cfg g;
        g.variables = {"S", "A", "B"};
        g.terminals = {'a', 'b'};
        g.start = "S";
        int count = 1 + static_cast<int>(rng() % 6);
        for (int i = 0; i < count; i++) {
            std::string head = g.variables[rng() % 3];
            unsigned kind = rng() % 8;
            if (kind == 0) {
                std::string terminal(1, g.terminals[rng() % 2]);
                g.rules.push_back({head, {terminal}});
            } else if (kind == 1 && head == "S") {
                g.rules.push_back({head, {}});
            } else {
                std::string left = inner[rng() % 2];
                std::string right = inner[rng() % 2];
                g.rules.push_back({head, {left, right}});
            }
        }
        assert(is_chomsky(g));
        bool found = false;
        for (const std::string& w : all_strings(g.terminals, 4)) {
            if (cyk(g, w)) {
                found = true;
                break;
            }
        }
        assert(is_empty(g) == !found);
        empty += is_empty(g) ? 1 : 0;
    }
    assert(empty > 50 && empty < 450);
}

int main() {
    test_marking();
    test_membership();
    test_emptiness_random();
    std::printf("test_cfg: ok (E_CFG, A_CFG; 500 gramáticas al azar)\n");
}
