// Pruebas de lo que los apuntes afirman sobre las máquinas de una cinta (sesión A).
// Cada máquina de machines/ se compara con una función de C++ que decide el mismo lenguaje
// mirando la cadena completa, sobre todas las cadenas hasta cierta longitud. Para las que
// deciden, se comprueba además que el límite de pasos de la prueba no se alcanza nunca.
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <functional>
#include <sstream>
#include <stdexcept>
#include <string>
#include <vector>

#include "tm.h"

static bool is_zeros_ones(const std::string& w) {
    std::size_t n = w.size() / 2;
    return w.size() % 2 == 0 && w == std::string(n, '0') + std::string(n, '1');
}

// w = x=x, con x sobre {0, 1}.
static bool is_w_sep_w(const std::string& w) {
    std::size_t n = w.size() / 2;
    return w.size() % 2 == 1 && w[n] == '=' && w.substr(0, n) == w.substr(n + 1) &&
           w.find('=') == n;
}

static bool is_anbncn(const std::string& w) {
    std::size_t n = w.size() / 3;
    return w.size() % 3 == 0 && w == std::string(n, 'a') + std::string(n, 'b') + std::string(n, 'c');
}

static bool has_one(const std::string& w) {
    return w.find('1') != std::string::npos;
}

struct Checked {
    std::size_t strings = 0;
    long long max_steps = 0;
};

// La máquina decide el lenguaje: con cada cadena se detiene antes del límite y responde bien.
static Checked check_decider(const std::string& path, std::size_t max_len,
                             const std::function<bool(const std::string&)>& in_language,
                             const std::function<long long(std::size_t)>& bound) {
    const long long limit = 100000;
    Tm m = load_tm(path);
    Checked checked;
    for (const std::string& w : all_strings(m.alphabet, max_len)) {
        Run r = run(m, w, limit);
        assert(r.outcome != Outcome::Limit);
        assert((r.outcome == Outcome::Accept) == in_language(w));
        // La cota de pasos que dan los apuntes, en función de la longitud de la entrada.
        assert(r.steps <= bound(w.size()));
        checked.max_steps = std::max(checked.max_steps, r.steps);
        checked.strings++;
    }
    assert(checked.max_steps < limit);
    return checked;
}

static void test_deciders() {
    // Las tres máquinas que tachan: a lo sumo n/2 vueltas de 2n − 1 pasos y un tramo final de n + 2.
    auto quadratic = [](std::size_t n) { return static_cast<long long>(n * n + n + 2); };
    Checked a = check_decider("machines/zeros_ones.tm", 13, is_zeros_ones, quadratic);
    Checked b = check_decider("machines/w_sep_w.tm", 9, is_w_sep_w, quadratic);
    Checked c = check_decider("machines/anbncn.tm", 9, is_anbncn, quadratic);
    Checked d = check_decider("machines/has_one.tm", 13, has_one,
                              [](std::size_t n) { return static_cast<long long>(n + 1); });
    std::printf("  zeros_ones: %zu cadenas, a lo sumo %lld pasos\n", a.strings, a.max_steps);
    std::printf("  w_sep_w:    %zu cadenas, a lo sumo %lld pasos\n", b.strings, b.max_steps);
    std::printf("  anbncn:     %zu cadenas, a lo sumo %lld pasos\n", c.strings, c.max_steps);
    std::printf("  has_one:    %zu cadenas, a lo sumo %lld pasos\n", d.strings, d.max_steps);
}

// Las cuentas exactas de los apuntes.
static void test_step_counts() {
    Tm zeros = load_tm("machines/zeros_ones.tm");
    for (long long n = 0; n <= 60; n++) {
        Run r = run(zeros, std::string(n, '0') + std::string(n, '1'), 100000);
        assert(r.outcome == Outcome::Accept);
        assert(r.steps == 2 * n * n + 2 * n + 1);
    }
    Tm abc = load_tm("machines/anbncn.tm");
    for (long long n = 1; n <= 40; n++) {
        Run r = run(abc, std::string(n, 'a') + std::string(n, 'b') + std::string(n, 'c'), 100000);
        assert(r.outcome == Outcome::Accept);
        assert(r.steps == 4 * n * n + 3 * n + 1);
    }
    Tm copy = load_tm("machines/w_sep_w.tm");
    for (long long n = 0; n <= 40; n++) {
        std::string x;
        for (long long i = 0; i < n; i++) {
            x += (i % 3 == 0) ? '1' : '0';
        }
        Run r = run(copy, x + "=" + x, 100000);
        assert(r.outcome == Outcome::Accept);
        assert(r.steps == 2 * n * n + 4 * n + 2);
    }
}

static std::vector<std::string> trace_text(const Tm& m, const std::string& w, long long limit) {
    std::vector<std::string> lines;
    for (const Config& c : trace(m, w, limit)) {
        lines.push_back(to_string(c));
    }
    return lines;
}

// Las secuencias de configuraciones que los apuntes muestran.
static void test_traces() {
    Tm zeros = load_tm("machines/zeros_ones.tm");
    assert(trace_text(zeros, "0011", 100) ==
           (std::vector<std::string>{"q0 0011", "X q1 011", "X0 q1 11", "X q2 0Y1", "q2 X0Y1", "X q0 0Y1", "XX q1 Y1",
                                     "XXY q1 1", "XX q2 YY", "X q2 XYY", "XX q0 YY", "XXY q3 Y", "XXYY q3 _",
                                     "XXYY_ q_accept _"}));
    assert(trace_text(zeros, "", 100) == (std::vector<std::string>{"q0 _", "_ q_accept _"}));
    // Un par sin transición: δ(q3, 0) no está escrita, y la máquina pasa a q_reject.
    assert(zeros.delta.count({"q3", '0'}) == 0);
    assert(trace_text(zeros, "010", 100) ==
           (std::vector<std::string>{"q0 010", "X q1 10", "q2 XY0", "X q0 Y0", "XY q3 0", "XY0 q_reject _"}));

    Tm copy = load_tm("machines/w_sep_w.tm");
    std::vector<std::string> lines = trace_text(copy, "01=01", 100);
    assert(lines.size() == 19);
    assert(lines[3] == "X1= q3 01" && lines[4] == "X1 q5 =X1" && lines[7] == "X q0 1=X1");
    assert(lines[14] == "XX q0 =XX" && lines[18] == "XX=XX_ q_accept _");
    assert(trace_text(copy, "=", 100) == (std::vector<std::string>{"q0 =", "= q7 _", "=_ q_accept _"}));
    assert(run(copy, "", 100).outcome == Outcome::Reject);
    assert(run(copy, "01=0", 100).outcome == Outcome::Reject);
    assert(run(copy, "01=011", 100).outcome == Outcome::Reject);
    assert(run(copy, "01=01=01", 100).outcome == Outcome::Reject);

    Tm abc = load_tm("machines/anbncn.tm");
    assert(trace_text(abc, "abc", 100) ==
           (std::vector<std::string>{"q0 abc", "X q1 bc", "XY q2 c", "X q3 YZ", "q3 XYZ", "X q0 YZ", "XY q4 Z",
                                     "XYZ q5 _", "XYZ_ q_accept _"}));
    assert(run(abc, "aabbcc", 1000).steps == 23);
    assert(run(abc, "aabbc", 1000).outcome == Outcome::Reject);
    assert(run(abc, "abcabc", 1000).outcome == Outcome::Reject);
}

// La máquina que reconoce y no decide: acepta exactamente las cadenas con algún 1, y con las
// demás no se detiene.
static void test_recognizer_that_loops() {
    Tm loops = load_tm("machines/has_one_loops.tm");
    for (const std::string& w : all_strings(loops.alphabet, 12)) {
        Run r = run(loops, w, 1000);
        if (has_one(w)) {
            assert(r.outcome == Outcome::Accept);
            assert(r.steps == static_cast<long long>(w.find('1')) + 1);
        } else {
            // Después de t pasos, la configuración es 0^n seguido de blancos, con q0 en la celda t.
            assert(r.outcome == Outcome::Limit);
            assert(r.last.state == "q0" && r.last.head == 1000);
        }
    }
    // Con la entrada 000 pasa de un millón de pasos sin detenerse.
    const long long million = 1000000;
    Run r = run(loops, "000", million);
    assert(r.outcome == Outcome::Limit && r.steps == million);
    assert(r.last.state == "q0" && r.last.head == static_cast<std::size_t>(million));
    assert(r.last.cells.substr(0, 3) == "000");
    assert(r.last.cells.find_first_not_of(BLANK, 3) == std::string::npos);
    assert(trace_text(loops, "00", 5) ==
           (std::vector<std::string>{"q0 00", "0 q0 0", "00 q0 _", "00_ q0 _", "00__ q0 _", "00___ q0 _"}));
}

// El borde izquierdo de la cinta: un movimiento L en la primera celda no mueve el cabezal.
static void test_left_end() {
    Tm m = load_tm("machines/left_end.tm");
    std::vector<std::string> lines = trace_text(m, "01", 12);
    assert(lines.size() == 13);
    assert(lines[2] == "01 q0 _" && lines[3] == "0 q1 1" && lines[4] == "q1 01");
    for (std::size_t i = 4; i < lines.size(); i++) {
        assert(lines[i] == "q1 01");
    }
    for (const std::string& w : all_strings(m.alphabet, 6)) {
        Run r = run(m, w, 500);
        assert(r.outcome == Outcome::Limit && r.last.head == 0 && r.last.state == "q1");
    }
}

static void test_to_string() {
    assert(to_string({"q0", "", 0}) == "q0 _");
    assert(to_string({"q1", "ab", 0}) == "q1 ab");
    assert(to_string({"q1", "ab", 2}) == "ab q1 _");
    assert(to_string({"q1", "ab", 4}) == "ab__ q1 _");
    assert(to_string({"q1", "a_b__", 1}) == "a q1 _b");
}

static bool fails_to_load(const std::string& path) {
    try {
        load_tm(path);
    } catch (const std::runtime_error&) {
        return true;
    }
    return false;
}

static void test_errors() {
    assert(fails_to_load("errors/two_transitions.tm"));
    assert(fails_to_load("errors/moves_after_halting.tm"));
    assert(fails_to_load("errors/symbol_not_in_tape.tm"));
    assert(fails_to_load("errors/same_accept_reject.tm"));
    assert(fails_to_load("machines/nondet_branch.tm"));  // no determinista: se lee con ntm.h
    assert(fails_to_load("machines/no_such_file.tm"));
    std::istringstream blank_in_alphabet(
        "states: q0 a r\nalphabet: 0 _\ntape: 0 _\nstart: q0\naccept: a\nreject: r\ndelta:\n");
    bool failed = false;
    try {
        read_tm(blank_in_alphabet);
    } catch (const std::runtime_error&) {
        failed = true;
    }
    assert(failed);
}

int main() {
    std::printf("test_tm:\n");
    test_deciders();
    test_step_counts();
    test_traces();
    test_recognizer_that_loops();
    test_left_end();
    test_to_string();
    test_errors();
    std::printf("test_tm: ok\n");
}
