// Pruebas de lo que los apuntes afirman sobre los DFA del capítulo (sesión B).
// Cada autómata de machines/ se compara con una función de C++ que decide el mismo lenguaje
// mirando la cadena completa, sobre todas las cadenas de longitud a lo sumo 12.
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <functional>
#include <sstream>
#include <stdexcept>
#include <string>
#include <vector>

#include "dfa.h"
#include "languages.h"

static bool ends_with(const std::string& w, const std::string& tail) {
    return w.size() >= tail.size() && w.compare(w.size() - tail.size(), tail.size(), tail) == 0;
}

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

static int count_ones(const std::string& w) {
    int ones = 0;
    for (char c : w) {
        ones += (c == '1');
    }
    return ones;
}

// El valor de w como número en base 2. La cadena vacía vale 0.
static unsigned long binary_value(const std::string& w) {
    return w.empty() ? 0 : std::stoul(w, nullptr, 2);
}

// Cuántas cadenas de longitud a lo sumo 12 se revisaron con cada máquina.
static std::size_t check_language(const std::string& path, const std::vector<char>& alphabet,
                                  const std::function<bool(const std::string&)>& in_language) {
    Dfa m = load_dfa(path);
    std::vector<std::string> words = all_strings(alphabet, 12);
    for (const std::string& w : words) {
        assert(accepts(m, w) == in_language(w));
    }
    return words.size();
}

static std::size_t test_languages_of_machines() {
    std::vector<char> binary = {'0', '1'};
    std::size_t n = 0;
    n = check_language("machines/even_ones.dfa", binary, [](const std::string& w) { return count_ones(w) % 2 == 0; });
    n = check_language("machines/ends_01.dfa", binary, [](const std::string& w) { return ends_with(w, "01"); });
    n = check_language("machines/contains_101.dfa", binary, [](const std::string& w) { return contains(w, "101"); });
    n = check_language("machines/multiple_of_3.dfa", binary,
                       [](const std::string& w) { return binary_value(w) % 3 == 0; });
    n = check_language("machines/starts_with_1.dfa", binary,
                       [](const std::string& w) { return !w.empty() && w[0] == '1'; });
    // El torniquete queda bloqueado si no pasó nada o si lo último fue un empujón.
    n = check_language("machines/turnstile.dfa", {'m', 'e'},
                       [](const std::string& w) { return w.empty() || w.back() == 'e'; });
    return n;
}

// La afirmación de cada estado: en qué estado queda la máquina dice un hecho sobre lo leído.
static void test_state_claims() {
    std::vector<std::string> words = all_strings({'0', '1'}, 12);

    Dfa even = load_dfa("machines/even_ones.dfa");
    for (const std::string& w : words) {
        assert(delta_star(even, even.start, w) == (count_ones(w) % 2 == 0 ? "par" : "impar"));
    }

    Dfa ends = load_dfa("machines/ends_01.dfa");
    for (const std::string& w : words) {
        std::string expected = ends_with(w, "01") ? "q2" : ends_with(w, "0") ? "q1" : "q0";
        assert(delta_star(ends, ends.start, w) == expected);
    }

    Dfa has = load_dfa("machines/contains_101.dfa");
    for (const std::string& w : words) {
        std::string expected = contains(w, "101") ? "q3" : ends_with(w, "10") ? "q2" : ends_with(w, "1") ? "q1" : "q0";
        assert(delta_star(has, has.start, w) == expected);
    }

    Dfa three = load_dfa("machines/multiple_of_3.dfa");
    for (const std::string& w : words) {
        assert(delta_star(three, three.start, w) == "r" + std::to_string(binary_value(w) % 3));
    }
    // val(wb) = 2·val(w) + b, la cuenta de la que sale δ.
    for (const std::string& w : all_strings({'0', '1'}, 10)) {
        assert(binary_value(w + "0") == 2 * binary_value(w));
        assert(binary_value(w + "1") == 2 * binary_value(w) + 1);
    }
}

// Las trazas que los apuntes muestran.
static void test_traces() {
    Dfa even = load_dfa("machines/even_ones.dfa");
    assert(run(even, "1101") == (std::vector<std::string>{"par", "impar", "par", "par", "impar"}));
    assert(run(even, "") == (std::vector<std::string>{"par"}));
    assert(!accepts(even, "1101") && accepts(even, "") && accepts(even, "0110"));

    Dfa ends = load_dfa("machines/ends_01.dfa");
    assert(run(ends, "110101") == (std::vector<std::string>{"q0", "q0", "q0", "q1", "q2", "q1", "q2"}));
    assert(accepts(ends, "01") && !accepts(ends, "1") && !accepts(ends, "") && !accepts(ends, "010"));

    Dfa has = load_dfa("machines/contains_101.dfa");
    assert(run(has, "1100101") ==
           (std::vector<std::string>{"q0", "q1", "q1", "q2", "q0", "q1", "q2", "q3"}));
    assert(run(has, "11011") == (std::vector<std::string>{"q0", "q1", "q1", "q2", "q3", "q3"}));
    assert(!accepts(has, "110011"));

    Dfa three = load_dfa("machines/multiple_of_3.dfa");
    assert(run(three, "10101") == (std::vector<std::string>{"r0", "r1", "r2", "r2", "r1", "r0"}));  // 21
    assert(run(three, "1101") == (std::vector<std::string>{"r0", "r1", "r0", "r0", "r1"}));  // 13
    assert(accepts(three, "") && accepts(three, "0") && accepts(three, "0011") && !accepts(three, "0100"));

    Dfa turnstile = load_dfa("machines/turnstile.dfa");
    assert(run(turnstile, "emme") ==
           (std::vector<std::string>{"bloqueado", "bloqueado", "libre", "libre", "bloqueado"}));
}

// δ*(q, uv) = δ*(δ*(q, u), v), para todo estado y todas las cadenas cortas.
static void test_delta_star() {
    Dfa has = load_dfa("machines/contains_101.dfa");
    std::vector<std::string> words = all_strings({'0', '1'}, 5);
    for (const std::string& q : has.states) {
        assert(delta_star(has, q, "") == q);
        for (const std::string& u : words) {
            for (const std::string& v : words) {
                assert(delta_star(has, q, u + v) == delta_star(has, delta_star(has, q, u), v));
            }
        }
    }
    // La secuencia de estados termina en δ*(q0, w) y tiene |w| + 1 estados.
    for (const std::string& w : words) {
        std::vector<std::string> sequence = run(has, w);
        assert(sequence.size() == w.size() + 1);
        assert(sequence.back() == delta_star(has, has.start, w));
    }
}

static bool fails_with(const std::string& path, const std::string& piece) {
    try {
        load_dfa(path);
    } catch (const std::runtime_error& error) {
        return std::string(error.what()).find(piece) != std::string::npos;
    }
    return false;
}

static void test_reader() {
    // Lo que no es un DFA no se carga.
    assert(fails_with("errors/missing_trap.dfa", "falta la transición δ(q0, 0)"));
    assert(fails_with("errors/two_transitions.dfa", "transición repetida para δ(q0, 0)"));
    assert(fails_with("errors/unknown_state.dfa", "pares"));
    assert(fails_with("machines/no_existe.dfa", "no se pudo abrir"));

    // Lo que write_dfa escribe, read_dfa lo lee igual.
    for (const char* path : {"machines/even_ones.dfa", "machines/ends_01.dfa", "machines/contains_101.dfa",
                             "machines/multiple_of_3.dfa", "machines/starts_with_1.dfa", "machines/turnstile.dfa"}) {
        Dfa m = load_dfa(path);
        std::stringstream text;
        write_dfa(text, m);
        Dfa again = read_dfa(text);
        assert(again.states == m.states && again.alphabet == m.alphabet && again.delta == m.delta);
        assert(again.start == m.start && again.accept == m.accept);
        assert(m.delta.size() == m.states.size() * m.alphabet.size());  // δ es total
        assert(reachable(m).size() == m.states.size());  // en estos seis, todo estado se alcanza
    }

    // accept: puede quedar vacío. Con F = ∅ no se acepta nada, y con F = Q se acepta todo.
    std::istringstream nothing("states: a b\nalphabet: 0 1\nstart: a\naccept:\ndelta:\na 0 b\na 1 a\nb 0 a\nb 1 b\n");
    Dfa none = read_dfa(nothing);
    Dfa all = none;
    all.accept = {"a", "b"};
    for (const std::string& w : all_strings({'0', '1'}, 8)) {
        assert(!accepts(none, w) && accepts(all, w));
    }
}

int main() {
    std::size_t n = test_languages_of_machines();
    test_state_claims();
    test_traces();
    test_delta_star();
    test_reader();
    std::printf("test_dfa: ok (6 autómatas, %zu cadenas cada uno)\n", n);
}
