// Autómata finito determinista. El struct tiene los cinco componentes de la definición
// M = (Q, Σ, δ, q0, F), con los nombres del formato .dfa de code/formats.md.
// Es el dfa.h de la semana 1, copiado sin cambios para que esta carpeta se pueda usar sola:
// leer y escribir el formato, la función de transición extendida, los estados alcanzables, la
// construcción del producto y el complemento. Lo nuevo de la semana 4 está en minimize.h,
// distinguish.h y pumping.h.
#ifndef DFA_H
#define DFA_H

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

struct Dfa {
    std::vector<std::string> states;                            // Q, en el orden del archivo
    std::vector<char> alphabet;                                 // Σ
    std::map<std::pair<std::string, char>, std::string> delta;  // δ : Q × Σ → Q
    std::string start;                                          // q0
    std::set<std::string> accept;                               // F ⊆ Q
};

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

// Lanza std::runtime_error si m no cumple la definición. Lo más importante: δ es total.
inline void check_dfa(const Dfa& m) {
    std::set<std::string> q(m.states.begin(), m.states.end());
    std::set<char> sigma(m.alphabet.begin(), m.alphabet.end());
    if (m.states.empty()) {
        throw std::runtime_error("Q no puede ser vacío");
    }
    if (q.size() != m.states.size()) {
        throw std::runtime_error("hay un estado repetido en states");
    }
    if (m.alphabet.empty()) {
        throw std::runtime_error("el alfabeto no puede ser vacío");
    }
    if (sigma.size() != m.alphabet.size()) {
        throw std::runtime_error("hay un símbolo repetido en alphabet");
    }
    if (q.count(m.start) == 0) {
        throw std::runtime_error("el estado inicial " + m.start + " no está en states");
    }
    for (const std::string& f : m.accept) {
        if (q.count(f) == 0) {
            throw std::runtime_error("el estado de aceptación " + f + " no está en states");
        }
    }
    for (const auto& [key, target] : m.delta) {
        if (q.count(key.first) == 0) {
            throw std::runtime_error("transición desde " + key.first + ", que no está en states");
        }
        if (sigma.count(key.second) == 0) {
            throw std::runtime_error(std::string("transición con ") + key.second + ", que no está en alphabet");
        }
        if (q.count(target) == 0) {
            throw std::runtime_error("transición hacia " + target + ", que no está en states");
        }
    }
    for (const std::string& state : m.states) {
        for (char a : m.alphabet) {
            if (m.delta.count({state, a}) == 0) {
                throw std::runtime_error("falta la transición δ(" + state + ", " + a + "): en un DFA, δ es total");
            }
        }
    }
}

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

inline std::vector<std::string> split_words(const std::string& text) {
    std::istringstream in(text);
    std::vector<std::string> words;
    std::string word;
    while (in >> word) {
        words.push_back(word);
    }
    return words;
}

// Lee una descripción completa, hasta el final de la entrada.
inline Dfa read_dfa(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;
    };

    Dfa m;
    m.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);
        }
        m.alphabet.push_back(symbol[0]);
    }
    std::vector<std::string> start = field("start");
    if (start.size() != 1) {
        fail("start: lleva exactamente un estado");
    }
    m.start = start[0];
    for (const std::string& state : field("accept")) {
        m.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)) {
        if (words.size() != 3 || words[1].size() != 1) {
            fail("una transición se escribe: estado símbolo destino");
        }
        std::pair<std::string, char> key = {words[0], words[1][0]};
        if (m.delta.count(key) > 0) {
            fail("transición repetida para δ(" + words[0] + ", " + words[1] + "): en un DFA hay una sola");
        }
        m.delta[key] = words[2];
    }
    check_dfa(m);
    return m;
}

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

// Escribe m en el formato .dfa: lo que escribe se puede volver a leer con read_dfa.
inline void write_dfa(std::ostream& out, const Dfa& m) {
    out << "states:";
    for (const std::string& state : m.states) {
        out << ' ' << state;
    }
    out << "\nalphabet:";
    for (char a : m.alphabet) {
        out << ' ' << a;
    }
    out << "\nstart: " << m.start << "\naccept:";
    for (const std::string& state : m.states) {
        if (m.accept.count(state) > 0) {
            out << ' ' << state;
        }
    }
    out << "\ndelta:\n";
    for (const std::string& state : m.states) {
        for (char a : m.alphabet) {
            out << state << ' ' << a << ' ' << m.delta.at({state, a}) << '\n';
        }
    }
}

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

// Un paso: δ(q, a).
inline const std::string& step(const Dfa& m, const std::string& q, char a) {
    auto it = m.delta.find({q, a});
    if (it == m.delta.end()) {
        throw std::runtime_error("δ(" + q + ", " + a + ") no está definida");
    }
    return it->second;
}

// La función de transición extendida: δ*(q, ε) = q y δ*(q, wa) = δ(δ*(q, w), a).
// El ciclo aplica la segunda línea de la definición una vez por símbolo, de izquierda a derecha.
inline std::string delta_star(const Dfa& m, std::string q, const std::string& w) {
    for (char a : w) {
        q = step(m, q, a);
    }
    return q;
}

// M acepta w si δ*(q0, w) ∈ F.
inline bool accepts(const Dfa& m, const std::string& w) {
    return m.accept.count(delta_star(m, m.start, w)) > 0;
}

// La ejecución de M con w: los estados r0, r1, …, rn, con r0 = q0 y r(i+1) = δ(r(i), w(i+1)).
inline std::vector<std::string> run(const Dfa& m, const std::string& w) {
    std::vector<std::string> sequence = {m.start};
    for (char a : w) {
        sequence.push_back(step(m, sequence.back(), a));
    }
    return sequence;
}

// Los estados a los que se llega desde q0 con alguna cadena.
inline std::set<std::string> reachable(const Dfa& m) {
    std::set<std::string> seen = {m.start};
    std::queue<std::string> pending;
    pending.push(m.start);
    while (!pending.empty()) {
        std::string q = pending.front();
        pending.pop();
        for (char a : m.alphabet) {
            const std::string& next = step(m, q, a);
            if (seen.insert(next).second) {
                pending.push(next);
            }
        }
    }
    return seen;
}

// ------------------------------------------------------------
// Construcciones
// ------------------------------------------------------------

enum class Combine { Intersection, Union };

// El nombre del estado (p, q) del producto. Los nombres del formato no llevan espacios.
inline std::string pair_name(const std::string& p, const std::string& q) {
    return "(" + p + "," + q + ")";
}

// Construcción del producto: Q = Q1 × Q2, δ((p, q), a) = (δ1(p, a), δ2(q, a)), q0 = (q1, q2).
// Para la intersección, F = F1 × F2. Para la unión, F = (F1 × Q2) ∪ (Q1 × F2).
inline Dfa product(const Dfa& m1, const Dfa& m2, Combine mode) {
    std::set<char> sigma1(m1.alphabet.begin(), m1.alphabet.end());
    std::set<char> sigma2(m2.alphabet.begin(), m2.alphabet.end());
    if (sigma1 != sigma2) {
        throw std::runtime_error("el producto necesita dos DFA con el mismo alfabeto");
    }
    Dfa m;
    m.alphabet = m1.alphabet;
    m.start = pair_name(m1.start, m2.start);
    for (const std::string& p : m1.states) {
        for (const std::string& q : m2.states) {
            std::string name = pair_name(p, q);
            m.states.push_back(name);
            bool in1 = m1.accept.count(p) > 0;
            bool in2 = m2.accept.count(q) > 0;
            bool accepting = (mode == Combine::Intersection) ? (in1 && in2) : (in1 || in2);
            if (accepting) {
                m.accept.insert(name);
            }
            for (char a : m.alphabet) {
                m.delta[{name, a}] = pair_name(step(m1, p, a), step(m2, q, a));
            }
        }
    }
    check_dfa(m);  // también detecta dos pares con el mismo nombre, si los nombres traían comas
    return m;
}

// Complemento: la misma máquina con F cambiado por Q − F.
inline Dfa complement(const Dfa& m) {
    Dfa result = m;
    result.accept.clear();
    for (const std::string& state : m.states) {
        if (m.accept.count(state) == 0) {
            result.accept.insert(state);
        }
    }
    return result;
}

// La misma máquina sin los estados inalcanzables. Reconoce el mismo lenguaje.
inline Dfa remove_unreachable(const Dfa& m) {
    std::set<std::string> keep = reachable(m);
    Dfa result;
    result.alphabet = m.alphabet;
    result.start = m.start;
    for (const std::string& state : m.states) {
        if (keep.count(state) == 0) {
            continue;
        }
        result.states.push_back(state);
        if (m.accept.count(state) > 0) {
            result.accept.insert(state);
        }
        for (char a : m.alphabet) {
            result.delta[{state, a}] = step(m, state, a);
        }
    }
    return result;
}

#endif
