// Pruebas de lo que los apuntes afirman sobre los NFA del capítulo (sesión A).
// Cada autómata de machines/ se compara con una función de C++ que decide el mismo lenguaje
// mirando la cadena completa, y la simulación con conjuntos de estados activos se compara
// con la definición: existe un camino que termina en un estado de aceptación.
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <functional>
#include <random>
#include <sstream>
#include <stdexcept>
#include <string>
#include <vector>

#include "kth.h"
#include "nfa.h"
#include "strings.h"
#include "test_helpers.h"

// Compara N con el predicado y con la definición por caminos. Devuelve cuántas cadenas revisó.
static std::size_t check_language(const std::string& path, std::size_t max_len,
                                  const std::function<bool(const std::string&)>& in_language) {
    Nfa n = load_nfa(path);
    std::vector<std::string> words = all_strings(n.alphabet, max_len);
    for (const std::string& w : words) {
        assert(accepts(n, w) == in_language(w));
        assert(accepts_by_paths(n, w) == in_language(w));
    }
    return words.size();
}

static bool third_from_end_is_one(const std::string& w) {
    return w.size() >= 3 && w[w.size() - 3] == '1';
}

// a*b*c*: la cadena está ordenada.
static bool in_blocks(const std::string& w) {
    for (std::size_t i = 1; i < w.size(); i++) {
        if (w[i - 1] > w[i]) {
            return false;
        }
    }
    return true;
}

static std::size_t test_languages_of_machines() {
    std::size_t total = 0;
    total += check_language("machines/third_from_end.nfa", 10, third_from_end_is_one);
    total += check_language("machines/contains_101_or_11.nfa", 10,
                            [](const std::string& w) { return contains(w, "101") || contains(w, "11"); });
    total += check_language("machines/abc_blocks.nfa", 7, in_blocks);
    total += check_language("machines/ends_01.nfa", 10, [](const std::string& w) { return ends_with(w, "01"); });
    total += check_language("machines/zeros_then_one.nfa", 10, [](const std::string& w) {
        return !w.empty() && w.back() == '1' && count_ones(w) == 1;
    });
    // Todo archivo .dfa es un .nfa válido, y como NFA acepta lo mismo.
    total += check_language("machines/even_ones.dfa", 10, [](const std::string& w) { return count_ones(w) % 2 == 0; });
    total += check_language("machines/ends_01.dfa", 10, [](const std::string& w) { return ends_with(w, "01"); });
    return total;
}

static void test_runs_of_notes() {
    Nfa third = load_nfa("machines/third_from_end.nfa");
    // El conjunto de estados activos después de cada símbolo, como lo imprime run_nfa.
    assert(run(third, "0110") == (std::vector<StateSet>{{"q0"}, {"q0"}, {"q0", "q1"}, {"q0", "q1", "q2"},
                                                        {"q0", "q2", "q3"}}));
    assert(accepts(third, "0110") && accepts(third, "100") && !accepts(third, "") && !accepts(third, "011"));
    assert(run(third, "100").back() == (StateSet{"q0", "q3"}));
    // Sin transiciones ε, la clausura no agrega nada.
    assert(eps_closure(third, {"q0", "q2"}) == (StateSet{"q0", "q2"}));
    // De q3 no sale ninguna flecha: δ(q3, 0) = ∅.
    assert(delta_of(third, "q3", '0').empty() && delta_of(third, "q3", EPS).empty());
    assert(delta_of(third, "q0", '1') == (StateSet{"q0", "q1"}));

    Nfa either = load_nfa("machines/contains_101_or_11.nfa");
    assert(eps_closure(either, {"q1"}) == (StateSet{"q1", "q2"}));
    assert(eps_closure(either, {"q0"}) == (StateSet{"q0"}));
    assert(run(either, "01011") ==
           (std::vector<StateSet>{{"q0"}, {"q0"}, {"q0", "q1", "q2"}, {"q0", "q2"}, {"q0", "q1", "q2", "q3"},
                                  {"q0", "q1", "q2", "q3"}}));
    assert(run(either, "0100").back() == (StateSet{"q0"}));
    assert(accepts(either, "01011") && !accepts(either, "0100") && accepts(either, "11") && !accepts(either, "10"));

    Nfa blocks = load_nfa("machines/abc_blocks.nfa");
    // La clausura sigue varias transiciones ε seguidas, y el estado inicial ya llega activo a qc.
    assert(eps_closure(blocks, {"qa"}) == (StateSet{"qa", "qb", "qc"}));
    assert(eps_closure(blocks, {"qb"}) == (StateSet{"qb", "qc"}));
    assert(eps_closure(blocks, {}).empty());
    assert(accepts(blocks, "") && accepts(blocks, "aacc") && accepts(blocks, "b") && !accepts(blocks, "ba"));
    assert(run(blocks, "abca") ==
           (std::vector<StateSet>{{"qa", "qb", "qc"}, {"qa", "qb", "qc"}, {"qb", "qc"}, {"qc"}, {}}));
}

// Propiedades de la clausura ε: contiene a S, aplicarla dos veces no cambia nada, y crece con S.
static void test_closure_properties() {
    std::mt19937 rng(20202);
    for (int round = 0; round < 300; round++) {
        Nfa n = random_nfa(rng, 1 + static_cast<int>(rng() % 6));
        StateSet small;
        StateSet big;
        for (const std::string& state : n.states) {
            unsigned coin = rng() % 3;
            if (coin == 0) {
                small.insert(state);
            }
            if (coin <= 1) {
                big.insert(state);
            }
        }
        StateSet closed = eps_closure(n, small);
        assert(std::includes(closed.begin(), closed.end(), small.begin(), small.end()));
        assert(eps_closure(n, closed) == closed);
        StateSet closed_big = eps_closure(n, big);
        assert(std::includes(closed_big.begin(), closed_big.end(), closed.begin(), closed.end()));
    }
}

// El lema de los estados activos: la simulación con conjuntos acepta exactamente cuando la
// definición dice que hay un camino. Con NFA al azar, que tienen ciclos de ε y caminos que mueren.
static int test_active_sets_against_paths() {
    std::mt19937 rng(10102);
    int machines = 0;
    for (int round = 0; round < 200; round++) {
        Nfa n = random_nfa(rng, 1 + static_cast<int>(rng() % 6));
        check_nfa(n);
        for (const std::string& w : all_strings(n.alphabet, 6)) {
            assert(accepts(n, w) == accepts_by_paths(n, w));
        }
        machines++;
    }
    return machines;
}

static void test_format() {
    // Leer, escribir y volver a leer da la misma máquina.
    for (const char* path : {"machines/third_from_end.nfa", "machines/contains_101_or_11.nfa",
                             "machines/abc_blocks.nfa", "machines/ends_01.dfa"}) {
        Nfa n = load_nfa(path);
        std::ostringstream text;
        write_nfa(text, n);
        std::istringstream again(text.str());
        Nfa copy = read_nfa(again);
        assert(copy.states == n.states && copy.alphabet == n.alphabet && copy.delta == n.delta);
        assert(copy.start == n.start && copy.accept == n.accept);
    }
    // Un par de estado y símbolo puede estar en varias líneas: los destinos se juntan.
    std::istringstream split("states: a b\nalphabet: 0\nstart: a\naccept: b\ndelta:\na 0 a\n# otra\na 0 b a\na eps b\n");
    Nfa joined = read_nfa(split);
    assert(delta_of(joined, "a", '0') == (StateSet{"a", "b"}) && delta_of(joined, "a", EPS) == (StateSet{"b"}));

    // kth_from_end(3) es la máquina del archivo.
    Nfa third = load_nfa("machines/third_from_end.nfa");
    Nfa built = kth_from_end(3);
    assert(built.states == third.states && built.delta == third.delta && built.accept == third.accept);

    // Un DFA visto como NFA: δ(q, a) tiene exactamente un estado y no hay transiciones ε.
    Nfa even = to_nfa(load_dfa("machines/even_ones.dfa"));
    for (const std::string& state : even.states) {
        assert(delta_of(even, state, '0').size() == 1 && delta_of(even, state, '1').size() == 1);
        assert(delta_of(even, state, EPS).empty());
    }

    // Un NFA no suele ser un archivo .dfa válido.
    bool failed = false;
    try {
        load_dfa("machines/third_from_end.nfa");
    } catch (const std::runtime_error&) {
        failed = true;
    }
    assert(failed);
    for (const char* path : {"errors/unknown_state.nfa", "errors/eps_as_target.nfa"}) {
        failed = false;
        try {
            load_nfa(path);
        } catch (const std::runtime_error&) {
            failed = true;
        }
        assert(failed);
    }
}

int main() {
    std::size_t words = test_languages_of_machines();
    test_runs_of_notes();
    test_closure_properties();
    int machines = test_active_sets_against_paths();
    test_format();
    std::printf("test_nfa: ok (7 autómatas, %zu cadenas en total; %d NFA al azar contra la definición)\n", words,
                machines);
}
