// Pruebas de la construcción de Thompson (sesión A).
// Cada expresión de los apuntes se convierte en un NFA y se compara con una función de C++
// que decide el mismo lenguaje mirando la cadena completa, sobre todas las cadenas cortas.
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <functional>
#include <map>
#include <sstream>
#include <string>
#include <vector>

#include "nfa.h"
#include "regex.h"
#include "thompson.h"
#include "words.h"

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

static int count_of(const std::string& w, char c) {
    int total = 0;
    for (char x : w) {
        total += (x == c);
    }
    return total;
}

static bool contains(const std::string& w, const std::string& piece) {
    return w.find(piece) != std::string::npos;
}

// w es una repetición de la pieza: ε, pieza, pieza pieza, …
static bool is_power_of(const std::string& w, const std::string& piece) {
    if (w.size() % piece.size() != 0) {
        return false;
    }
    for (std::size_t i = 0; i < w.size(); i++) {
        if (w[i] != piece[i % piece.size()]) {
            return false;
        }
    }
    return true;
}

// La forma del NFA de Thompson: un solo estado de aceptación, del que no sale nada; al
// inicial no entra nada; de cada estado salen a lo sumo dos flechas; y el número de estados
// es exactamente el doble del número de hojas, uniones y estrellas.
static void check_shape(const RegexPtr& r, const Nfa& n) {
    assert(n.accept.size() == 1);
    assert(n.states.size() == 2 * count_without_concat(r));
    assert(n.states.size() <= 2 * size(r));
    std::map<std::string, std::size_t> out;
    for (const auto& [key, targets] : n.delta) {
        out[key.first] += targets.size();
        assert(targets.count(n.start) == 0);
    }
    for (const std::string& q : n.states) {
        assert(out[q] <= 2);
    }
    assert(out[*n.accept.begin()] == 0);
}

// Compara L(r) con el predicado sobre todas las cadenas de longitud a lo sumo max_len.
static std::size_t check_language(const std::string& text, const std::vector<char>& alphabet, std::size_t max_len,
                                  const Predicate& in_language) {
    RegexPtr r = parse_regex(text);
    Nfa n = thompson(r, alphabet);
    check_shape(r, n);
    std::vector<std::string> words = all_strings(alphabet, max_len);
    for (const std::string& w : words) {
        assert(accepts(n, w) == in_language(w));
    }
    return words.size();
}

// Dos expresiones describen el mismo lenguaje, hasta longitud max_len.
static void check_same(const std::string& text1, const std::string& text2, const std::vector<char>& alphabet,
                       std::size_t max_len) {
    Nfa n1 = thompson(parse_regex(text1), alphabet);
    Nfa n2 = thompson(parse_regex(text2), alphabet);
    for (const std::string& w : all_strings(alphabet, max_len)) {
        assert(accepts(n1, w) == accepts(n2, w));
    }
}

static std::size_t test_examples() {
    std::vector<char> binary = {'0', '1'};
    std::size_t count = 0;
    auto check = [&](const std::string& text, const Predicate& in_language) {
        check_language(text, binary, 9, in_language);
        count++;
    };
    // Las tres expresiones que se leen en la sesión A.
    check("(0|1)*1", [](const std::string& w) { return !w.empty() && w.back() == '1'; });
    check("((0|1)(0|1))*", [](const std::string& w) { return w.size() % 2 == 0; });
    check("0*10*10*", [](const std::string& w) { return count_of(w, '1') == 2; });
    // Las que se escriben: número par de ceros, sin 11.
    check("1*(01*01*)*", [](const std::string& w) { return count_of(w, '0') % 2 == 0; });
    check("(1|01*0)*", [](const std::string& w) { return count_of(w, '0') % 2 == 0; });
    check("(0|10)*(%|1)", [](const std::string& w) { return !contains(w, "11"); });
    // Los dos intentos fallidos de "sin 11": uno describe de menos y el otro de más.
    check("(0|10)*", [](const std::string& w) { return !contains(w, "11") && (w.empty() || w.back() == '0'); });
    check("(0|10)*1*", [](const std::string& w) {
        // Sin 11 antes de la cola final de unos: quitando esa cola, queda vacío o termina en 0 sin 11.
        std::size_t end = w.size();
        while (end > 0 && w[end - 1] == '1') {
            end--;
        }
        return !contains(w.substr(0, end), "11");
    });
    // Las de las preguntas de repaso de la guía.
    check("(0|%)1*", [](const std::string& w) { return !contains(w.substr(w.empty() ? 0 : 1), "0"); });
    check("(01)*|(10)*", [](const std::string& w) { return is_power_of(w, "01") || is_power_of(w, "10"); });
    check("(1|01*01*0)*", [](const std::string& w) { return count_of(w, '0') % 3 == 0; });
    // Σ*, y las cadenas que contienen 101.
    check("(0|1)*", [](const std::string&) { return true; });
    check("(0|1)*101(0|1)*", [](const std::string& w) { return contains(w, "101"); });
    // (ab ∪ a)*: no empieza con b y no tiene bb.
    check_language("(ab|a)*", {'a', 'b'}, 9,
                   [](const std::string& w) { return (w.empty() || w[0] == 'a') && !contains(w, "bb"); });
    count++;
    // Los enteros sin ceros a la izquierda, sobre los diez dígitos.
    check_language("0|(1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*",
                   {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'}, 3,
                   [](const std::string& w) { return w == "0" || (!w.empty() && w[0] != '0'); });
    count++;
    return count;
}

static void test_cases_of_the_definition() {
    std::vector<char> binary = {'0', '1'};
    check_language("@", binary, 6, [](const std::string&) { return false; });
    check_language("%", binary, 6, [](const std::string& w) { return w.empty(); });
    check_language("0", binary, 6, [](const std::string& w) { return w == "0"; });
    check_language("0|1", binary, 6, [](const std::string& w) { return w == "0" || w == "1"; });
    check_language("01", binary, 6, [](const std::string& w) { return w == "01"; });
    check_language("0*", binary, 6, [](const std::string& w) { return count_of(w, '1') == 0; });
}

static void test_identities() {
    std::vector<char> binary = {'0', '1'};
    std::vector<std::string> some = {"0", "(0|1)*1", "0*10*10*", "(01)*|(10)*", "%", "@"};
    for (const std::string& r : some) {
        std::string p = "(" + r + ")";
        check_same(p + "|@", r, binary, 6);   // R ∪ ∅ = R
        check_same(p + "@", "@", binary, 6);  // R∅ = ∅
        check_same("@" + p, "@", binary, 6);  // ∅R = ∅
        check_same(p + "%", r, binary, 6);    // Rε = R
        check_same("%" + p, r, binary, 6);    // εR = R
        check_same(p + "|" + p, r, binary, 6);       // R ∪ R = R
        check_same(p + "**", p + "*", binary, 6);    // (R*)* = R*
    }
    // ∅* = {ε}: la estrella de ∅ no es ∅.
    check_same("@*", "%", binary, 6);
    check_same("%*", "%", binary, 6);
    // Las dos trampas: R ∪ ε no es R, y Rε no es ∅.
    Nfa with_eps = thompson(parse_regex("0|%"), binary);
    assert(accepts(with_eps, "") && accepts(with_eps, "0"));
    assert(!accepts(thompson(parse_regex("0"), binary), ""));
    // Otras igualdades que se usan en los apuntes.
    check_same("(0|1)*", "(0*1*)*", binary, 9);
    check_same("1*(01*01*)*", "(1|01*0)*", binary, 9);
    check_same("(0|10)*(%|1)", "(%|1)(0|01)*", binary, 9);
    // Las abreviaturas de las herramientas, escritas con las tres operaciones.
    check_language("00*", binary, 7, [](const std::string& w) { return !w.empty() && count_of(w, '1') == 0; });
    check_language("(01)(01)((01)|%)", binary, 7, [](const std::string& w) { return w == "0101" || w == "010101"; });
}

static void test_run() {
    // La ejecución que copian los apuntes: (0|1)*1 con 011.
    RegexPtr r = parse_regex("(0|1)*1");
    Nfa n = thompson(r);
    assert(n.states.size() == 10);
    assert(n.start == "q0" && n.accept == StateSet{"q9"});
    std::vector<StateSet> sets = run(n, "011");
    assert(sets.size() == 4);
    assert(show_set(n, sets[0]) == "{q0, q1, q2, q4, q7, q8}");
    assert(show_set(n, sets[1]) == "{q1, q2, q3, q4, q6, q7, q8}");
    assert(show_set(n, sets[2]) == "{q1, q2, q4, q5, q6, q7, q8, q9}");
    assert(show_set(n, sets[3]) == "{q1, q2, q4, q5, q6, q7, q8, q9}");
    assert(accepts(n, "011") && !accepts(n, "010") && !accepts(n, ""));
    // El archivo de machines/ es lo que escribe la construcción, y se vuelve a leer igual.
    Nfa from_file = load_nfa("machines/ends_in_1.nfa");
    std::ostringstream written;
    std::ostringstream built;
    write_nfa(written, from_file);
    write_nfa(built, n);
    assert(written.str() == built.str());
    // (ab ∪ a)*, el de las preguntas de repaso.
    Nfa second = load_nfa("machines/ab_or_a_star.nfa");
    std::ostringstream written2;
    std::ostringstream built2;
    write_nfa(written2, second);
    write_nfa(built2, thompson(parse_regex("(ab|a)*")));
    assert(written2.str() == built2.str());
    assert(second.states.size() == 10);
    // Todo .dfa es un .nfa válido.
    Nfa from_dfa = load_nfa("machines/even_ones.dfa");
    for (const std::string& w : all_strings({'0', '1'}, 8)) {
        assert(accepts(from_dfa, w) == (count_of(w, '1') % 2 == 0));
    }
}

static void test_closure_with_cycles() {
    // (a*)* tiene un ciclo de transiciones ε: la clausura debe terminar.
    Nfa n = thompson(parse_regex("(a*)*b"), {'a', 'b'});
    for (const std::string& w : all_strings({'a', 'b'}, 8)) {
        bool expected = !w.empty() && w.back() == 'b' && count_of(w, 'b') == 1;
        assert(accepts(n, w) == expected);
    }
}

int main() {
    test_cases_of_the_definition();
    std::size_t examples = test_examples();
    test_identities();
    test_run();
    test_closure_with_cycles();
    std::printf("test_thompson: ok (%zu expresiones contra su predicado)\n", examples);
}
