// Construcción de Thompson: de una expresión regular a un NFA con transiciones ε.
// Hay una pieza por cada caso de la definición de expresión regular. Cada pieza tiene un solo
// estado inicial y un solo estado de aceptación, y por eso se pueden conectar sin mirar adentro.
#ifndef THOMPSON_H
#define THOMPSON_H

#include <stdexcept>
#include <string>
#include <vector>

#include "nfa.h"
#include "regex.h"

// Una pieza ya construida dentro del NFA: por dónde se entra y por dónde se sale.
struct Fragment {
    std::string start;
    std::string accept;
};

// Agrega un estado nuevo, con el siguiente nombre libre: q0, q1, q2…
inline std::string new_state(Nfa& n) {
    std::string name = "q" + std::to_string(n.states.size());
    n.states.push_back(name);
    return name;
}

// Construye dentro de n la pieza de r y dice cuáles son su entrada y su salida.
inline Fragment build_fragment(Nfa& n, const RegexPtr& r) {
    switch (r->kind) {
        case Kind::Empty: {
            // Dos estados sin ninguna flecha: no hay camino de la entrada a la salida.
            std::string s = new_state(n);
            std::string f = new_state(n);
            return {s, f};
        }
        case Kind::Epsilon: {
            std::string s = new_state(n);
            std::string f = new_state(n);
            n.delta[{s, EPS}].insert(f);
            return {s, f};
        }
        case Kind::Symbol: {
            std::string s = new_state(n);
            std::string f = new_state(n);
            n.delta[{s, r->symbol}].insert(f);
            return {s, f};
        }
        case Kind::Union: {
            // Una entrada nueva que elige una de las dos piezas, y una salida nueva para las dos.
            std::string s = new_state(n);
            Fragment a = build_fragment(n, r->left);
            Fragment b = build_fragment(n, r->right);
            std::string f = new_state(n);
            n.delta[{s, EPS}].insert(a.start);
            n.delta[{s, EPS}].insert(b.start);
            n.delta[{a.accept, EPS}].insert(f);
            n.delta[{b.accept, EPS}].insert(f);
            return {s, f};
        }
        case Kind::Concat: {
            // La salida de la primera pieza se une con la entrada de la segunda.
            Fragment a = build_fragment(n, r->left);
            Fragment b = build_fragment(n, r->right);
            n.delta[{a.accept, EPS}].insert(b.start);
            return {a.start, b.accept};
        }
        case Kind::Star: {
            // Entrada y salida nuevas: se puede saltar la pieza, o recorrerla y repetir.
            std::string s = new_state(n);
            Fragment a = build_fragment(n, r->left);
            std::string f = new_state(n);
            n.delta[{s, EPS}].insert(a.start);
            n.delta[{s, EPS}].insert(f);
            n.delta[{a.accept, EPS}].insert(a.start);
            n.delta[{a.accept, EPS}].insert(f);
            return {s, f};
        }
    }
    throw std::runtime_error("expresión mal formada");
}

// El NFA de Thompson de r sobre el alfabeto dado, que debe contener los símbolos de r.
inline Nfa thompson(const RegexPtr& r, const std::vector<char>& alphabet) {
    Nfa n;
    n.alphabet = alphabet;
    Fragment whole = build_fragment(n, r);
    n.start = whole.start;
    n.accept = {whole.accept};
    check_nfa(n);
    return n;
}

// Lo mismo, con el alfabeto formado por los símbolos que aparecen en r.
inline Nfa thompson(const RegexPtr& r) {
    return thompson(r, symbols_of(r));
}

#endif
