// La técnica de fijar la entrada dentro de la máquina: de M y w se construye M_w, que con su
// entrada x primero comprueba que x = w y después corre M con w.
//   L(M_w) = {w} si M acepta w, y L(M_w) = ∅ si no.
// Es la función computable de la reducción de A_TM al complemento de E_TM.
#pragma once

#include <stdexcept>
#include <string>

#include "tm.h"

inline Tm fix_input(const Tm& m, const std::string& w) {
    const char mark = '@';   // marca la primera celda mientras se compara
    if (has_symbol(m.tape, mark)) throw std::runtime_error("la cinta de M no puede usar el símbolo @");
    initial_configuration(m, w);   // comprueba que w usa el alfabeto de entrada
    const int n = static_cast<int>(w.size());

    Tm result;
    result.alphabet = m.alphabet;
    result.tape = m.tape;
    result.tape.push_back(mark);
    // Los estados de M pasan con el prefijo m. para que no choquen con los nuevos.
    auto old = [](const std::string& q) { return "m." + q; };
    auto compare = [](int i) { return "c" + std::to_string(i); };
    for (int i = 0; i <= n; ++i) result.states.push_back(compare(i));
    result.states.push_back("back");
    for (const std::string& q : m.states) result.states.push_back(old(q));
    result.start = compare(0);
    result.accept = old(m.accept);
    result.reject = old(m.reject);

    if (n == 0) {
        // w = ε: la entrada debe ser vacía. L en la primera celda deja el cabezal en su sitio.
        result.delta[{compare(0), '_'}] = Transition{old(m.start), '_', 'L'};
    } else {
        // c_i: los primeros i símbolos de x coinciden con los de w. El primero se cambia por la marca.
        result.delta[{compare(0), w[0]}] = Transition{compare(1), mark, 'R'};
        for (int i = 1; i < n; ++i) result.delta[{compare(i), w[i]}] = Transition{compare(i + 1), w[i], 'R'};
        // c_n con un blanco: x = w. Volver a la primera celda, restaurar su símbolo y empezar M.
        result.delta[{compare(n), '_'}] = Transition{"back", '_', 'L'};
        for (char a : m.alphabet) result.delta[{"back", a}] = Transition{"back", a, 'L'};
        result.delta[{"back", mark}] = Transition{old(m.start), w[0], 'L'};
    }
    // Cualquier otro caso de la comparación no tiene transición: va a reject.
    for (const auto& [key, t] : m.delta) {
        result.delta[{old(key.first), key.second}] = Transition{old(t.next), t.write, t.move};
    }
    return result;
}
