// Pruebas de los procedimientos de decisión sobre DFA y NFA: A_DFA, A_NFA, E_DFA y EQ_DFA.
// Comprueban lo que los apuntes afirman sobre los autómatas de machines/ y los del laboratorio.
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <optional>
#include <random>
#include <string>
#include <vector>

#include "decide.h"
#include "dfa.h"
#include "minimize.h"
#include "nfa.h"

// Todas las cadenas sobre el alfabeto de longitud a lo sumo max_len, las más cortas primero.
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 const std::vector<char> BINARY = {'0', '1'};

static bool ends_in_01(const std::string& w) {
    return w.size() >= 2 && w.substr(w.size() - 2) == "01";
}

static bool kth_from_end_is_1(const std::string& w, std::size_t k) {
    return w.size() >= k && w[w.size() - k] == '1';
}

// A_DFA y A_NFA: simular, y convertir y simular.
static void test_acceptance() {
    Dfa ends = load_dfa("machines/ends_01.dfa");
    assert(run(ends, "0101") == (std::vector<std::string>{"q0", "q1", "q2", "q1", "q2"}));
    assert(accepts(ends, "0101") && !accepts(ends, ""));
    for (const std::string& w : all_strings(BINARY, 12)) {
        assert(run(ends, w).size() == w.size() + 1);  // |w| pasos, siempre termina
        assert(accepts(ends, w) == ends_in_01(w));
    }

    Nfa third = load_nfa("machines/third_from_end.nfa");
    Dfa d = subset_construction(third);
    assert(third.states.size() == 4 && d.states.size() == 8);
    assert(subset_construction(third, true).states.size() == 16);
    assert(run(d, "0100") == (std::vector<std::string>{"{q0}", "{q0}", "{q0,q1}", "{q0,q2}", "{q0,q3}"}));
    for (const std::string& w : all_strings(BINARY, 12)) {
        assert(accepts(d, w) == kth_from_end_is_1(w, 3));
    }
    assert(accepts(d, "0100") && !accepts(d, "0010"));
}

// E_DFA: alcanzabilidad.
static void test_emptiness() {
    Dfa ends = load_dfa("machines/ends_01.dfa");
    assert(!is_empty(ends));
    assert(shortest_accepted(ends) == std::optional<std::string>("01"));

    // Tiene un estado de aceptación, pero inalcanzable.
    Dfa unreachable = load_dfa("machines/unreachable_accept.dfa");
    assert(unreachable.accept.size() == 1 && reachable(unreachable).size() == 2);
    assert(is_empty(unreachable));
    for (const std::string& w : all_strings(BINARY, 12)) {
        assert(!accepts(unreachable, w));
    }

    // F = ∅: vacío. F = Q: no vacío, y la cadena más corta es ε.
    Dfa none = ends;
    none.accept.clear();
    assert(is_empty(none));
    Dfa everything = complement(none);
    assert(shortest_accepted(everything) == std::optional<std::string>(""));

    // L(M) = ∅ si y solo si el complemento acepta todo... y un lenguaje y su complemento no son vacíos a la vez.
    assert(!is_empty(complement(ends)));
    assert(shortest_accepted(complement(ends)) == std::optional<std::string>(""));
}

// EQ_DFA con los autómatas de los apuntes.
static void test_equivalence_of_notes() {
    Dfa ends = load_dfa("machines/ends_01.dfa");
    Dfa history = load_dfa("machines/ends_01_history.dfa");
    Dfa wrong = load_dfa("machines/ends_01_wrong.dfa");
    Dfa even = load_dfa("machines/even_ones.dfa");

    // El de 3 estados y el de 7 son equivalentes: 7 pares alcanzables de 21.
    Comparison same = compare(ends, history);
    assert(same.equivalent && same.witness.empty());
    assert(same.pairs.size() == 7 && reachable_pairs(ends, history) == 7);
    Dfa c = symmetric_difference(ends, history);
    assert(c.states.size() == 21 && c.accept.size() == 8 && reachable(c).size() == 7);
    assert(is_empty(c));
    for (const std::string& w : all_strings(BINARY, 12)) {
        assert(accepts(ends, w) == accepts(history, w));
    }

    // El equivocado se separa con 0101, y con ninguna cadena más corta.
    Comparison differ = compare(ends, wrong);
    assert(!differ.equivalent && differ.witness == "0101" && differ.pairs.size() == 5);
    assert(differ.pairs.back() == (std::pair<std::string, std::string>{"q2", "q0"}));
    assert(accepts(ends, "0101") && !accepts(wrong, "0101"));
    for (const std::string& w : all_strings(BINARY, 3)) {
        assert(accepts(ends, w) == accepts(wrong, w));
    }
    Dfa c2 = symmetric_difference(ends, wrong);
    assert(c2.states.size() == 9 && c2.accept.size() == 4 && reachable(c2).size() == 5);
    assert(shortest_accepted(c2) == std::optional<std::string>("0101"));
    // L(C) es la diferencia simétrica: C acepta w si y solo si exactamente uno de los dos la acepta.
    for (const std::string& w : all_strings(BINARY, 12)) {
        assert(accepts(c2, w) == (accepts(ends, w) != accepts(wrong, w)));
    }

    // Dos lenguajes que no tienen nada que ver: los separa ε.
    Comparison other = compare(ends, even);
    assert(!other.equivalent && other.witness.empty() && other.pairs.size() == 1);

    // Todo DFA es equivalente a sí mismo y a su versión mínima; no a su complemento.
    for (const Dfa& m : {ends, history, wrong, even}) {
        assert(compare(m, m).equivalent);
        assert(compare(m, minimize(m)).equivalent);
        assert(!compare(m, complement(m)).equivalent);
    }
    assert(minimize(history).states.size() == 3);
}

// Un DFA al azar con n estados sobre {0, 1}.
static Dfa random_dfa(std::mt19937& rng, std::size_t n, const std::string& prefix) {
    Dfa m;
    m.alphabet = BINARY;
    for (std::size_t i = 0; i < n; i++) {
        m.states.push_back(prefix + std::to_string(i));
    }
    m.start = m.states[0];
    for (const std::string& q : m.states) {
        if (rng() % 3 == 0) {
            m.accept.insert(q);
        }
        for (char a : m.alphabet) {
            m.delta[{q, a}] = m.states[rng() % n];
        }
    }
    return m;
}

// Las dos maneras de decidir EQ_DFA coinciden, y la cadena que devuelven es de las más cortas.
// Si dos DFA son distintos, alguna cadena de longitud menor que |QA| · |QB| los separa: basta
// probar esas para comparar con la fuerza bruta.
static void test_equivalence_random() {
    std::mt19937 rng(90210);
    int different = 0;
    for (int round = 0; round < 400; round++) {
        std::size_t na = 1 + rng() % 3;
        std::size_t nb = 1 + rng() % 3;
        Dfa a = random_dfa(rng, na, "p");
        Dfa b = (round % 5 == 0) ? minimize(a, "m") : random_dfa(rng, nb, "r");
        nb = b.states.size();
        Comparison result = compare(a, b);
        Dfa c = symmetric_difference(a, b);
        std::optional<std::string> from_product = shortest_accepted(c);
        assert(result.equivalent == !from_product.has_value());
        assert(result.pairs.size() <= na * nb);

        std::optional<std::string> brute;
        for (const std::string& w : all_strings(BINARY, na * nb - 1)) {
            if (accepts(a, w) != accepts(b, w)) {
                brute = w;
                break;  // all_strings va de las más cortas a las más largas
            }
        }
        assert(result.equivalent == !brute.has_value());
        if (!result.equivalent) {
            different++;
            assert(accepts(a, result.witness) != accepts(b, result.witness));
            assert(result.witness.size() == brute->size());
            assert(result.witness.size() == from_product->size());
            assert(result.witness.size() < na * nb);
            assert(result.witness.size() + 2 <= na + nb);  // la cota fina del ejercicio 5
        }
    }
    assert(different > 100 && different < 400);
}

// Los autómatas de lab/dfa_equiv/machines, que escribe make_kth.
static void test_kth_machines() {
    const std::string dir = "lab/dfa_equiv/machines/";
    Nfa n = load_nfa(dir + "kth6.nfa");
    Dfa subsets = load_dfa(dir + "kth6_subsets.dfa");
    Dfa all = load_dfa(dir + "kth6_all.dfa");
    Dfa history = load_dfa(dir + "kth6_history.dfa");
    Dfa minimal = load_dfa(dir + "kth6_min.dfa");
    Dfa wrong = load_dfa(dir + "kth6_wrong.dfa");

    assert(n.states.size() == 7);
    assert(subsets.states.size() == 64 && reachable(subsets).size() == 64);
    assert(all.states.size() == 128 && reachable(all).size() == 64);
    assert(history.states.size() == 127 && reachable(history).size() == 127);
    assert(minimal.states.size() == 64);
    assert(wrong.states.size() == 63);
    // Los archivos son lo que la construcción produce.
    assert(subset_construction(n).delta == subsets.delta);
    // El de subconjuntos ya es mínimo: minimizar no le quita nada.
    assert(minimize(subsets).states.size() == 64 && minimize(all).states.size() == 64);
    assert(minimize(history).states.size() == 64);

    for (const std::string& w : all_strings(BINARY, 12)) {
        bool expected = kth_from_end_is_1(w, 6);
        assert(accepts(subsets, w) == expected && accepts(all, w) == expected);
        assert(accepts(history, w) == expected && accepts(minimal, w) == expected);
    }
    assert(compare(subsets, minimal).equivalent && compare(subsets, minimal).pairs.size() == 64);
    assert(compare(all, history).equivalent && compare(all, history).pairs.size() == 127);
    assert(compare(history, minimal).equivalent && compare(all, minimal).equivalent);

    Comparison broken = compare(minimal, wrong);
    assert(!broken.equivalent && broken.witness == "1100000");
    for (const std::string& w : all_strings(BINARY, 6)) {
        assert(accepts(minimal, w) == accepts(wrong, w));
    }
}

int main() {
    test_acceptance();
    test_emptiness();
    test_equivalence_of_notes();
    test_equivalence_random();
    test_kth_machines();
    std::printf("test_dfa: ok (A_DFA, A_NFA, E_DFA, EQ_DFA; 400 pares de DFA al azar)\n");
}
