// Pruebas de las construcciones de cierre (sesión B): cada una se compara con el predicado que
// define la operación, calculado sin autómatas. Y las dos construcciones incorrectas de los
// apuntes fallan con las cadenas que los apuntes dicen.
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <functional>
#include <random>
#include <string>
#include <vector>

#include "errors/wrong_constructions.h"
#include "nfa.h"
#include "strings.h"
#include "test_helpers.h"

using Predicate = std::function<bool(const std::string&)>;

// w ∈ AB: alguna partición w = uv tiene u ∈ A y v ∈ B.
static bool in_concat(const Predicate& in_a, const Predicate& in_b, const std::string& w) {
    for (std::size_t cut = 0; cut <= w.size(); cut++) {
        if (in_a(w.substr(0, cut)) && in_b(w.substr(cut))) {
            return true;
        }
    }
    return false;
}

// w ∈ A*: w se parte en cero o más trozos de A. splits[i] dice si el prefijo de longitud i está en A*.
static bool in_star(const Predicate& in_a, const std::string& w) {
    std::vector<bool> splits(w.size() + 1, false);
    splits[0] = true;
    for (std::size_t end = 1; end <= w.size(); end++) {
        for (std::size_t from = 0; from < end && !splits[end]; from++) {
            splits[end] = splits[from] && in_a(w.substr(from, end - from));
        }
    }
    return splits[w.size()];
}

static void test_examples_of_notes() {
    Nfa even = load_nfa("machines/even_ones.dfa");
    Nfa ends = load_nfa("machines/ends_01.dfa");
    Predicate in_even = [](const std::string& w) { return count_ones(w) % 2 == 0; };
    Predicate in_ends = [](const std::string& w) { return ends_with(w, "01"); };
    std::vector<std::string> words = all_strings({'0', '1'}, 9);

    // Unión: 1 + 2 + 3 estados, y el mismo lenguaje que el producto de la semana 1.
    Nfa either = nfa_union(even, ends);
    assert(either.states == (std::vector<std::string>{"s", "1.par", "1.impar", "2.q0", "2.q1", "2.q2"}));
    assert(delta_of(either, "s", EPS) == (StateSet{"1.par", "2.q0"}));
    assert(either.accept == (StateSet{"1.par", "2.q2"}));
    Dfa product_union = product(load_dfa("machines/even_ones.dfa"), load_dfa("machines/ends_01.dfa"), Combine::Union);
    for (const std::string& w : words) {
        assert(accepts(either, w) == (in_even(w) || in_ends(w)));
        assert(accepts(either, w) == accepts(product_union, w));
    }
    assert(run(either, "").front() == (StateSet{"s", "1.par", "2.q0"}));

    // Concatenación: termina en 01, y después una cantidad par de unos.
    Nfa both = nfa_concat(ends, even);
    assert(both.states.size() == 5 && both.start == "1.q0");
    assert(both.accept == (StateSet{"2.par"}));
    assert(delta_of(both, "1.q2", EPS) == (StateSet{"2.par"}));
    for (const std::string& w : words) {
        assert(accepts(both, w) == in_concat(in_ends, in_even, w));
    }
    // 0111 = 01 · 11 está; 011 no: después de cualquier 01 queda una cantidad impar de unos.
    assert(accepts(both, "0111") && accepts(both, "01") && !accepts(both, "011") && !accepts(both, ""));

    // Estrella de 0*1: ε y las cadenas que terminan en 1.
    Nfa one = load_nfa("machines/zeros_then_one.nfa");
    Predicate in_one = [](const std::string& w) { return !w.empty() && w.back() == '1' && count_ones(w) == 1; };
    Nfa star = nfa_star(one);
    assert(star.states == (std::vector<std::string>{"s", "q0", "q1"}));
    assert(star.start == "s" && star.accept == (StateSet{"s", "q1"}));
    assert(delta_of(star, "s", EPS) == (StateSet{"q0"}) && delta_of(star, "q1", EPS) == (StateSet{"q0"}));
    for (const std::string& w : words) {
        assert(accepts(star, w) == in_star(in_one, w));
        assert(accepts(star, w) == (w.empty() || w.back() == '1'));
    }

    // La estrella sin estado inicial nuevo acepta 0, que no está en (0*1)*: es exactamente
    // las cadenas no vacías que terminan en 0 lo que acepta de más.
    Nfa wrong = star_without_new_start(one);
    assert(accepts(wrong, "0") && !accepts(star, "0") && !in_star(in_one, "0"));
    assert(accepts(wrong, "") && accepts(wrong, "01"));
    for (const std::string& w : words) {
        assert(accepts(wrong, w));  // acepta todas las cadenas
    }

    // Reverso: de "termina en 01" a "empieza con 10", y de "tercero desde el final" a "tercero".
    Nfa backwards = nfa_reverse(ends);
    assert(backwards.states.size() == 4 && backwards.accept == (StateSet{"q0"}));
    assert(delta_of(backwards, "s", EPS) == (StateSet{"q2"}));
    Nfa third = load_nfa("machines/third_from_end.nfa");
    Nfa third_reversed = nfa_reverse(third);
    for (const std::string& w : words) {
        assert(accepts(backwards, w) == (w.size() >= 2 && w[0] == '1' && w[1] == '0'));
        assert(accepts(third_reversed, w) == (w.size() >= 3 && w[2] == '1'));
    }
    // El reverso de un DFA no es un DFA: de q1 salen tres flechas con 0 (eran q0→q1, q1→q1 y q2→q1).
    assert(delta_of(backwards, "q1", '0').size() == 3);
}

// Intercambiar F por Q − F en un NFA no da el complemento.
static void test_swap_accept() {
    Nfa third = load_nfa("machines/third_from_end.nfa");
    Nfa swapped = swap_accept(third);
    assert(swapped.accept == (StateSet{"q0", "q1", "q2"}));
    // 100 está en el lenguaje y el NFA intercambiado también la acepta.
    assert(accepts(third, "100") && accepts(swapped, "100"));
    // De hecho acepta todo, porque q0 siempre está activo.
    Dfa right = complement(subset_construction(third));
    for (const std::string& w : all_strings({'0', '1'}, 9)) {
        assert(accepts(swapped, w));
        assert(accepts(right, w) == !accepts(third, w));  // el camino correcto: primero el DFA
    }
    assert(!accepts(right, "100") && accepts(right, "000"));
}

// Las cuatro construcciones con NFA al azar, que tienen transiciones ε, ciclos y flechas que
// vuelven al estado inicial.
static int test_random() {
    std::mt19937 rng(40404);
    std::vector<std::string> words = all_strings({'0', '1'}, 5);
    int machines = 0;
    for (int round = 0; round < 100; round++) {
        Nfa a = random_nfa(rng, 1 + static_cast<int>(rng() % 4));
        Nfa b = random_nfa(rng, 1 + static_cast<int>(rng() % 4));
        Predicate in_a = [&a](const std::string& w) { return accepts_by_paths(a, w); };
        Predicate in_b = [&b](const std::string& w) { return accepts_by_paths(b, w); };
        Nfa either = nfa_union(a, b);
        Nfa both = nfa_concat(a, b);
        Nfa star = nfa_star(a);
        Nfa backwards = nfa_reverse(a);
        assert(either.states.size() == a.states.size() + b.states.size() + 1);
        assert(both.states.size() == a.states.size() + b.states.size());
        assert(star.states.size() == a.states.size() + 1 && backwards.states.size() == a.states.size() + 1);
        for (const std::string& w : words) {
            assert(accepts(either, w) == (in_a(w) || in_b(w)));
            assert(accepts(both, w) == in_concat(in_a, in_b, w));
            assert(accepts(star, w) == in_star(in_a, w));
            assert(accepts(backwards, w) == in_a(reversed(w)));
        }
        machines++;
    }
    return machines;
}

int main() {
    test_examples_of_notes();
    test_swap_accept();
    int machines = test_random();
    std::printf("test_closure: ok (unión, concatenación, estrella y reverso; %d pares de NFA al azar)\n", machines);
}
