// Autómata finito no determinista, con transiciones ε. El struct tiene los cinco componentes de
// la definición N = (Q, Σ, δ, q0, F), con los nombres del formato .nfa de code/formats.md.
// La diferencia con el Dfa está en un solo tipo: δ devuelve un conjunto de estados.
// Además: leer y escribir el formato, la clausura ε, la simulación con el conjunto de estados
// activos, la construcción de subconjuntos y las construcciones de cierre (unión,
// concatenación, estrella y reverso).
#ifndef NFA_H
#define NFA_H

#include <cstddef>
#include <fstream>
#include <istream>
#include <map>
#include <ostream>
#include <queue>
#include <set>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>

#include "dfa.h"

// ε no es un símbolo del alfabeto. En la clave de δ se representa con un carácter que ningún
// archivo puede usar como símbolo.
inline constexpr char EPS = '\0';

using StateSet = std::set<std::string>;

struct Nfa {
    std::vector<std::string> states;                         // Q, en el orden del archivo
    std::vector<char> alphabet;                              // Σ
    std::map<std::pair<std::string, char>, StateSet> delta;  // δ : Q × (Σ ∪ {ε}) → P(Q)
    std::string start;                                       // q0
    StateSet accept;                                         // F ⊆ Q
};

// ------------------------------------------------------------
// Comprobar que la quíntupla es un NFA
// ------------------------------------------------------------

// Lanza std::runtime_error si n no cumple la definición. A diferencia de check_dfa, no pide
// que δ sea total: un par sin transiciones vale ∅.
inline void check_nfa(const Nfa& n) {
    StateSet q(n.states.begin(), n.states.end());
    std::set<char> sigma(n.alphabet.begin(), n.alphabet.end());
    if (n.states.empty()) {
        throw std::runtime_error("Q no puede ser vacío");
    }
    if (q.size() != n.states.size()) {
        throw std::runtime_error("hay un estado repetido en states");
    }
    if (n.alphabet.empty()) {
        throw std::runtime_error("el alfabeto no puede ser vacío");
    }
    if (sigma.size() != n.alphabet.size()) {
        throw std::runtime_error("hay un símbolo repetido en alphabet");
    }
    if (q.count(n.start) == 0) {
        throw std::runtime_error("el estado inicial " + n.start + " no está en states");
    }
    for (const std::string& f : n.accept) {
        if (q.count(f) == 0) {
            throw std::runtime_error("el estado de aceptación " + f + " no está en states");
        }
    }
    for (const auto& [key, targets] : n.delta) {
        if (q.count(key.first) == 0) {
            throw std::runtime_error("transición desde " + key.first + ", que no está en states");
        }
        if (key.second != EPS && sigma.count(key.second) == 0) {
            throw std::runtime_error(std::string("transición con ") + key.second + ", que no está en alphabet");
        }
        for (const std::string& target : targets) {
            if (q.count(target) == 0) {
                throw std::runtime_error("transición hacia " + target + ", que no está en states");
            }
        }
    }
}

// ------------------------------------------------------------
// Leer y escribir el formato .nfa
// ------------------------------------------------------------

// Lee una descripción completa, hasta el final de la entrada. Si un par de estado y símbolo
// aparece en varias líneas, sus destinos se juntan.
inline Nfa read_nfa(std::istream& in) {
    int number = 0;
    auto fail = [&number](const std::string& message) {
        throw std::runtime_error("línea " + std::to_string(number) + ": " + message);
    };
    // Siguiente línea que no es comentario ni está vacía. Devuelve false al final.
    auto next_line = [&in, &number](std::vector<std::string>& words) {
        std::string line;
        while (std::getline(in, line)) {
            number++;
            if (!line.empty() && line[0] == '#') {
                continue;
            }
            words = split_words(line);
            if (!words.empty()) {
                return true;
            }
        }
        return false;
    };
    // Un campo: "nombre: valor valor ...". Devuelve los valores.
    auto field = [&next_line, &fail](const std::string& name) {
        std::vector<std::string> words;
        if (!next_line(words) || words[0] != name + ":") {
            fail("se esperaba el campo " + name + ":");
        }
        words.erase(words.begin());
        return words;
    };

    Nfa n;
    n.states = field("states");
    for (const std::string& symbol : field("alphabet")) {
        if (symbol.size() != 1 || symbol[0] == '#') {
            fail("un símbolo es un solo carácter distinto de #: " + symbol);
        }
        n.alphabet.push_back(symbol[0]);
    }
    std::vector<std::string> start = field("start");
    if (start.size() != 1) {
        fail("start: lleva exactamente un estado");
    }
    n.start = start[0];
    for (const std::string& state : field("accept")) {
        n.accept.insert(state);
    }
    if (!field("delta").empty()) {
        fail("después de delta: las transiciones van una por línea");
    }
    std::vector<std::string> words;
    while (next_line(words)) {
        // estado símbolo destino…, con eps en el lugar del símbolo para una transición ε.
        if (words.size() < 3 || (words[1] != "eps" && words[1].size() != 1)) {
            fail("una transición se escribe: estado símbolo destino… (uno o más destinos)");
        }
        char symbol = (words[1] == "eps") ? EPS : words[1][0];
        for (std::size_t i = 2; i < words.size(); i++) {
            n.delta[{words[0], symbol}].insert(words[i]);
        }
    }
    try {
        check_nfa(n);
    } catch (const std::runtime_error& error) {
        throw std::runtime_error(std::string("no es un NFA: ") + error.what());
    }
    return n;
}

inline Nfa load_nfa(const std::string& path) {
    std::ifstream file(path);
    if (!file) {
        throw std::runtime_error("no se pudo abrir " + path);
    }
    try {
        return read_nfa(file);
    } catch (const std::runtime_error& error) {
        throw std::runtime_error(path + ": " + error.what());
    }
}

// Escribe n en el formato .nfa: una línea por cada par con al menos un destino, con los
// destinos en el orden de states. Lo que escribe se puede volver a leer con read_nfa.
inline void write_nfa(std::ostream& out, const Nfa& n) {
    out << "states:";
    for (const std::string& state : n.states) {
        out << ' ' << state;
    }
    out << "\nalphabet:";
    for (char a : n.alphabet) {
        out << ' ' << a;
    }
    out << "\nstart: " << n.start << "\naccept:";
    for (const std::string& state : n.states) {
        if (n.accept.count(state) > 0) {
            out << ' ' << state;
        }
    }
    out << "\ndelta:\n";
    std::vector<char> columns = n.alphabet;
    columns.push_back(EPS);
    for (const std::string& state : n.states) {
        for (char a : columns) {
            auto it = n.delta.find({state, a});
            if (it == n.delta.end() || it->second.empty()) {
                continue;
            }
            out << state << ' ' << (a == EPS ? std::string("eps") : std::string(1, a));
            for (const std::string& target : n.states) {
                if (it->second.count(target) > 0) {
                    out << ' ' << target;
                }
            }
            out << '\n';
        }
    }
}

// ------------------------------------------------------------
// Ejecutar
// ------------------------------------------------------------

// δ(q, a), con a ∈ Σ o a = EPS. Un par sin transiciones da ∅.
inline StateSet delta_of(const Nfa& n, const std::string& q, char a) {
    auto it = n.delta.find({q, a});
    return it == n.delta.end() ? StateSet{} : it->second;
}

// Clausura ε: E(S) son los estados a los que se llega desde algún estado de S con cero o más
// transiciones ε. Es una búsqueda en el grafo que solo tiene las flechas ε.
inline StateSet eps_closure(const Nfa& n, const StateSet& s) {
    StateSet closure = s;
    std::queue<std::string> pending;
    for (const std::string& q : s) {
        pending.push(q);
    }
    while (!pending.empty()) {
        std::string q = pending.front();
        pending.pop();
        for (const std::string& r : delta_of(n, q, EPS)) {
            if (closure.insert(r).second) {
                pending.push(r);
            }
        }
    }
    return closure;
}

// Un paso con el símbolo a desde un conjunto: primero todas las flechas con a que salen de
// algún estado de S, después la clausura ε. Es E(⋃ δ(q, a)), con q en S.
inline StateSet step(const Nfa& n, const StateSet& s, char a) {
    StateSet targets;
    for (const std::string& q : s) {
        StateSet next = delta_of(n, q, a);
        targets.insert(next.begin(), next.end());
    }
    return eps_closure(n, targets);
}

// La función extendida sobre conjuntos: δ*(S, ε) = E(S) y δ*(S, xa) = E(⋃ δ(q, a)), con q en δ*(S, x).
// δ*({q0}, w) es el conjunto de estados activos después de leer w.
inline StateSet delta_star(const Nfa& n, const StateSet& s, const std::string& w) {
    StateSet active = eps_closure(n, s);
    for (char a : w) {
        active = step(n, active, a);
    }
    return active;
}

// ¿S tiene algún estado de aceptación?
inline bool has_accept(const Nfa& n, const StateSet& s) {
    for (const std::string& q : s) {
        if (n.accept.count(q) > 0) {
            return true;
        }
    }
    return false;
}

// N acepta w si algún estado activo al final es de aceptación.
inline bool accepts(const Nfa& n, const std::string& w) {
    return has_accept(n, delta_star(n, {n.start}, w));
}

// Los conjuntos de estados activos: antes de leer nada y después de cada símbolo de w.
inline std::vector<StateSet> run(const Nfa& n, const std::string& w) {
    std::vector<StateSet> sequence = {eps_closure(n, {n.start})};
    for (char a : w) {
        sequence.push_back(step(n, sequence.back(), a));
    }
    return sequence;
}

// Un conjunto de estados escrito como {q0,q1}, en el orden de states y sin espacios, para que
// sirva de nombre de un estado en un archivo .dfa. El conjunto vacío es {}.
inline std::string set_name(const Nfa& n, const StateSet& s) {
    std::string name = "{";
    for (const std::string& q : n.states) {
        if (s.count(q) > 0) {
            name += (name.size() > 1 ? "," : "") + q;
        }
    }
    return name + "}";
}

// ------------------------------------------------------------
// De DFA a NFA y de NFA a DFA
// ------------------------------------------------------------

// Todo DFA es un NFA: la misma máquina, con δ(q, a) = {el único destino} y sin transiciones ε.
inline Nfa to_nfa(const Dfa& m) {
    Nfa n;
    n.states = m.states;
    n.alphabet = m.alphabet;
    n.start = m.start;
    n.accept = m.accept;
    for (const auto& [key, target] : m.delta) {
        n.delta[key] = {target};
    }
    return n;
}

// Construcción de subconjuntos. El DFA tiene un estado por cada conjunto de estados del NFA
// que se alcanza desde E({q0}):
//   inicial      E({q0})
//   transición   δ_D(S, a) = E(⋃ δ(q, a)), con q en S
//   aceptación   los S que contienen algún estado de F
// Solo genera los subconjuntos alcanzables, con una cola, en el orden en que aparecen.
// Si subsets no es nulo, deja ahí el conjunto que corresponde a cada estado del DFA.
inline Dfa subset_construction(const Nfa& n, std::vector<StateSet>* subsets = nullptr) {
    Dfa d;
    d.alphabet = n.alphabet;
    StateSet first = eps_closure(n, {n.start});
    d.start = set_name(n, first);

    std::vector<StateSet> found = {first};  // found[i] es el conjunto del estado d.states[i]
    std::set<StateSet> seen = {first};
    std::queue<StateSet> pending;
    pending.push(first);
    d.states.push_back(d.start);
    while (!pending.empty()) {
        StateSet s = pending.front();
        pending.pop();
        std::string name = set_name(n, s);
        if (has_accept(n, s)) {
            d.accept.insert(name);
        }
        for (char a : n.alphabet) {
            StateSet t = step(n, s, a);
            d.delta[{name, a}] = set_name(n, t);
            if (seen.insert(t).second) {
                found.push_back(t);
                d.states.push_back(set_name(n, t));
                pending.push(t);
            }
        }
    }
    check_dfa(d);
    if (subsets != nullptr) {
        *subsets = found;
    }
    return d;
}

// ------------------------------------------------------------
// Construcciones de cierre
// ------------------------------------------------------------

// Un nombre que no esté en used: name, o name con apóstrofos hasta que no choque.
inline std::string fresh_name(const std::vector<std::string>& used, std::string name) {
    StateSet taken(used.begin(), used.end());
    while (taken.count(name) > 0) {
        name += "'";
    }
    return name;
}

// El mismo NFA con prefix delante del nombre de cada estado. Sirve para que dos máquinas no
// compartan nombres: las construcciones necesitan Q1 ∩ Q2 = ∅.
inline Nfa with_prefix(const Nfa& n, const std::string& prefix) {
    Nfa result;
    result.alphabet = n.alphabet;
    result.start = prefix + n.start;
    for (const std::string& state : n.states) {
        result.states.push_back(prefix + state);
    }
    for (const std::string& state : n.accept) {
        result.accept.insert(prefix + state);
    }
    for (const auto& [key, targets] : n.delta) {
        for (const std::string& target : targets) {
            result.delta[{prefix + key.first, key.second}].insert(prefix + target);
        }
    }
    return result;
}

inline void require_same_alphabet(const Nfa& n1, const Nfa& n2) {
    std::set<char> sigma1(n1.alphabet.begin(), n1.alphabet.end());
    std::set<char> sigma2(n2.alphabet.begin(), n2.alphabet.end());
    if (sigma1 != sigma2) {
        throw std::runtime_error("la construcción necesita dos NFA con el mismo alfabeto");
    }
}

// Unión: un estado inicial nuevo s, con transiciones ε a los iniciales de N1 y de N2.
// F = F1 ∪ F2. Los estados de N1 pasan a llamarse 1.q y los de N2, 2.q.
inline Nfa nfa_union(const Nfa& first, const Nfa& second) {
    require_same_alphabet(first, second);
    Nfa n1 = with_prefix(first, "1.");
    Nfa n2 = with_prefix(second, "2.");
    Nfa n;
    n.alphabet = n1.alphabet;
    n.start = "s";
    n.states = {n.start};
    n.states.insert(n.states.end(), n1.states.begin(), n1.states.end());
    n.states.insert(n.states.end(), n2.states.begin(), n2.states.end());
    n.delta = n1.delta;
    n.delta.insert(n2.delta.begin(), n2.delta.end());
    n.delta[{n.start, EPS}] = {n1.start, n2.start};
    n.accept = n1.accept;
    n.accept.insert(n2.accept.begin(), n2.accept.end());
    check_nfa(n);
    return n;
}

// Concatenación: se empieza en N1, y de cada estado de aceptación de N1 sale una transición ε
// al inicial de N2. F = F2.
inline Nfa nfa_concat(const Nfa& first, const Nfa& second) {
    require_same_alphabet(first, second);
    Nfa n1 = with_prefix(first, "1.");
    Nfa n2 = with_prefix(second, "2.");
    Nfa n;
    n.alphabet = n1.alphabet;
    n.start = n1.start;
    n.states = n1.states;
    n.states.insert(n.states.end(), n2.states.begin(), n2.states.end());
    n.delta = n1.delta;
    n.delta.insert(n2.delta.begin(), n2.delta.end());
    for (const std::string& f : n1.accept) {
        n.delta[{f, EPS}].insert(n2.start);
    }
    n.accept = n2.accept;
    check_nfa(n);
    return n;
}

// Estrella: un estado inicial nuevo s, que es de aceptación, con una transición ε al inicial
// anterior. De cada estado de aceptación sale una transición ε al inicial anterior.
// F = F1 ∪ {s}.
inline Nfa nfa_star(const Nfa& n1) {
    Nfa n = n1;
    n.start = fresh_name(n1.states, "s");
    n.states.insert(n.states.begin(), n.start);
    n.delta[{n.start, EPS}] = {n1.start};
    for (const std::string& f : n1.accept) {
        n.delta[{f, EPS}].insert(n1.start);
    }
    n.accept.insert(n.start);
    check_nfa(n);
    return n;
}

// Reverso: todas las flechas al revés, un estado inicial nuevo s con transiciones ε a los que
// eran de aceptación, y un solo estado de aceptación: el que era inicial.
inline Nfa nfa_reverse(const Nfa& n1) {
    Nfa n;
    n.alphabet = n1.alphabet;
    n.start = fresh_name(n1.states, "s");
    n.states = {n.start};
    n.states.insert(n.states.end(), n1.states.begin(), n1.states.end());
    for (const auto& [key, targets] : n1.delta) {
        for (const std::string& target : targets) {
            n.delta[{target, key.second}].insert(key.first);
        }
    }
    if (!n1.accept.empty()) {
        n.delta[{n.start, EPS}] = n1.accept;
    }
    n.accept = {n1.start};
    check_nfa(n);
    return n;
}

#endif
