// Autómata de pila. El struct tiene los seis componentes de la definición
// P = (Q, Σ, Γ, δ, q0, F), con los nombres del formato .pda de code/formats.md.
// Además: leer y escribir ese formato, y simular el autómata con una búsqueda sobre sus
// configuraciones (estado, posición en la entrada, pila).
// Las funciones que leen líneas siguen el esquema de code/week-01/dfa.h.
#ifndef PDA_H
#define PDA_H

#include <algorithm>
#include <compare>
#include <cstddef>
#include <fstream>
#include <istream>
#include <map>
#include <ostream>
#include <set>
#include <sstream>
#include <stdexcept>
#include <string>
#include <tuple>
#include <vector>

// ε en una transición: no leer, no sacar o no poner. Ningún símbolo de un archivo vale '\0'.
const char EPS = '\0';

// Un elemento de δ(q, a, b): el estado de destino y lo que se pone en la pila (un símbolo o ε).
struct Move {
    std::string target;
    char push;
    bool operator==(const Move& other) const = default;
};

struct Pda {
    std::vector<std::string> states;  // Q, en el orden del archivo
    std::vector<char> alphabet;       // Σ
    std::vector<char> stack;          // Γ
    // δ : Q × Σε × Γε → P(Q × Γε). La clave es (estado, lee, saca), con EPS donde va ε.
    std::map<std::tuple<std::string, char, char>, std::vector<Move>> delta;
    std::string start;             // q0
    std::set<std::string> accept;  // F ⊆ Q
};

// Cómo se escribe un símbolo o ε en un archivo.
inline std::string symbol_name(char c) {
    return c == EPS ? "eps" : std::string(1, c);
}

// Cómo se muestra en una traza.
inline std::string symbol_shown(char c) {
    return c == EPS ? "ε" : std::string(1, c);
}

// Agrega (target, push) a δ(state, read, pop), sin repetirlo.
inline void add_move(Pda& p, const std::string& state, char read, char pop, const std::string& target, char push) {
    std::vector<Move>& moves = p.delta[{state, read, pop}];
    Move move = {target, push};
    if (std::find(moves.begin(), moves.end(), move) == moves.end()) {
        moves.push_back(move);
    }
}

// ------------------------------------------------------------
// Comprobar que la séxtupla es un PDA
// ------------------------------------------------------------

// Lanza std::runtime_error si p no cumple la definición.
inline void check_pda(const Pda& p) {
    std::set<std::string> q(p.states.begin(), p.states.end());
    std::set<char> sigma(p.alphabet.begin(), p.alphabet.end());
    std::set<char> gamma(p.stack.begin(), p.stack.end());
    if (p.states.empty()) {
        throw std::runtime_error("Q no puede ser vacío");
    }
    if (q.size() != p.states.size()) {
        throw std::runtime_error("hay un estado repetido en states");
    }
    if (sigma.size() != p.alphabet.size()) {
        throw std::runtime_error("hay un símbolo repetido en alphabet");
    }
    if (gamma.size() != p.stack.size()) {
        throw std::runtime_error("hay un símbolo repetido en stack");
    }
    if (q.count(p.start) == 0) {
        throw std::runtime_error("el estado inicial " + p.start + " no está en states");
    }
    for (const std::string& f : p.accept) {
        if (q.count(f) == 0) {
            throw std::runtime_error("el estado de aceptación " + f + " no está en states");
        }
    }
    for (const auto& [key, moves] : p.delta) {
        const auto& [state, read, pop] = key;
        if (q.count(state) == 0) {
            throw std::runtime_error("transición desde " + state + ", que no está en states");
        }
        if (read != EPS && sigma.count(read) == 0) {
            throw std::runtime_error("transición que lee " + symbol_name(read) + ", que no está en alphabet");
        }
        if (pop != EPS && gamma.count(pop) == 0) {
            throw std::runtime_error("transición que saca " + symbol_name(pop) + ", que no está en stack");
        }
        for (const Move& move : moves) {
            if (q.count(move.target) == 0) {
                throw std::runtime_error("transición hacia " + move.target + ", que no está en states");
            }
            if (move.push != EPS && gamma.count(move.push) == 0) {
                throw std::runtime_error("transición que pone " + symbol_name(move.push) + ", que no está en stack");
            }
        }
    }
}

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

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 Pda read_pda(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;
    };
    // Un símbolo de un alfabeto: un solo carácter distinto de #.
    auto symbol = [&fail](const std::string& word) {
        if (word.size() != 1 || word[0] == '#') {
            fail("un símbolo es un solo carácter distinto de #: " + word);
        }
        return word[0];
    };
    // Lo mismo, o eps.
    auto symbol_or_eps = [&symbol](const std::string& word) { return word == "eps" ? EPS : symbol(word); };

    Pda p;
    p.states = field("states");
    for (const std::string& word : field("alphabet")) {
        p.alphabet.push_back(symbol(word));
    }
    for (const std::string& word : field("stack")) {
        p.stack.push_back(symbol(word));
    }
    std::vector<std::string> start = field("start");
    if (start.size() != 1) {
        fail("start: lleva exactamente un estado");
    }
    p.start = start[0];
    for (const std::string& state : field("accept")) {
        p.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() != 6 || words[3] != "->") {
            fail("una transición se escribe: estado lee saca -> destino pone (cada uno, un símbolo o eps)");
        }
        add_move(p, words[0], symbol_or_eps(words[1]), symbol_or_eps(words[2]), words[4], symbol_or_eps(words[5]));
    }
    check_pda(p);
    return p;
}

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

// Escribe p en el formato .pda: lo que escribe se puede volver a leer con read_pda.
// Las transiciones salen agrupadas por estado, en el orden de states.
inline void write_pda(std::ostream& out, const Pda& p) {
    out << "states:";
    for (const std::string& state : p.states) {
        out << ' ' << state;
    }
    out << "\nalphabet:";
    for (char a : p.alphabet) {
        out << ' ' << a;
    }
    out << "\nstack:";
    for (char c : p.stack) {
        out << ' ' << c;
    }
    out << "\nstart: " << p.start << "\naccept:";
    for (const std::string& state : p.states) {
        if (p.accept.count(state) > 0) {
            out << ' ' << state;
        }
    }
    out << "\ndelta:\n";
    for (const std::string& state : p.states) {
        for (const auto& [key, moves] : p.delta) {
            if (std::get<0>(key) != state) {
                continue;
            }
            for (const Move& move : moves) {
                out << state << ' ' << symbol_name(std::get<1>(key)) << ' ' << symbol_name(std::get<2>(key)) << " -> "
                    << move.target << ' ' << symbol_name(move.push) << '\n';
            }
        }
    }
}

inline std::size_t count_transitions(const Pda& p) {
    std::size_t total = 0;
    for (const auto& [key, moves] : p.delta) {
        total += moves.size();
    }
    return total;
}

// ------------------------------------------------------------
// Simular
// ------------------------------------------------------------

// Una configuración: el estado, cuántos símbolos de la entrada ya se leyeron, y la pila, con la
// cima en stack[0]. La configuración inicial es (q0, 0, ε).
struct Config {
    std::string state;
    std::size_t pos = 0;
    std::string stack;
    auto operator<=>(const Config& other) const = default;
};

// Un paso de una ejecución: la transición que se usó (lee, saca → pone) y adónde llevó.
struct Step {
    char read = EPS;
    char pop = EPS;
    char push = EPS;
    Config config;
};

// Las configuraciones a las que se llega en un paso desde c, con la entrada w.
// Una transición (q, a, b) → (r, c) se puede usar si a es ε o el siguiente símbolo de w, y
// si b es ε o la cima de la pila. Con la pila vacía solo sirven las que no sacan nada.
inline std::vector<Step> successors(const Pda& p, const std::string& w, const Config& c) {
    std::vector<Step> result;
    std::vector<char> reads = {EPS};
    if (c.pos < w.size()) {
        reads.push_back(w[c.pos]);
    }
    std::vector<char> pops = {EPS};
    if (!c.stack.empty()) {
        pops.push_back(c.stack[0]);
    }
    for (char read : reads) {
        for (char pop : pops) {
            auto it = p.delta.find({c.state, read, pop});
            if (it == p.delta.end()) {
                continue;
            }
            for (const Move& move : it->second) {
                Step step;
                step.read = read;
                step.pop = pop;
                step.push = move.push;
                step.config.state = move.target;
                step.config.pos = c.pos + (read == EPS ? 0 : 1);
                step.config.stack = c.stack.substr(pop == EPS ? 0 : 1);
                if (move.push != EPS) {
                    step.config.stack.insert(step.config.stack.begin(), move.push);
                }
                result.push_back(step);
            }
        }
    }
    return result;
}

enum class Verdict { Accept, Reject, Limit };

struct Search {
    Verdict verdict = Verdict::Reject;
    std::vector<Step> run;     // si acepta: una ejecución de aceptación, desde la configuración inicial
    std::size_t explored = 0;  // configuraciones distintas que la búsqueda llegó a descubrir
};

// Sin tope de altura de pila.
const std::size_t NO_STACK_BOUND = static_cast<std::size_t>(-1);

// Decide si p acepta w con una búsqueda por niveles sobre las configuraciones.
//  - Accept: se llegó a una configuración con toda la entrada leída y el estado en F.
//    run es una ejecución de aceptación con la menor cantidad de pasos.
//  - Reject: se exploraron todas las configuraciones alcanzables y ninguna es de aceptación.
//  - Limit: se descubrieron más de max_configs configuraciones distintas sin aceptar. Pasa
//    con los autómatas que tienen ciclos de transiciones ε que hacen crecer la pila.
// El conjunto seen evita explorar dos veces la misma configuración: sin él, un ciclo de
// transiciones ε que no cambia la pila no terminaría nunca.
// Si max_stack no es NO_STACK_BOUND, se descartan las configuraciones con una pila más alta.
// Eso solo es correcto cuando se sabe que ninguna ejecución de aceptación las necesita.
inline Search simulate(const Pda& p, const std::string& w, std::size_t max_configs = 100000,
                       std::size_t max_stack = NO_STACK_BOUND) {
    auto accepting = [&p, &w](const Config& c) { return c.pos == w.size() && p.accept.count(c.state) > 0; };

    std::vector<Step> found;          // found[i]: la configuración i y la transición que la descubrió
    std::vector<std::size_t> parent;  // de cuál se llegó a la configuración i
    std::set<Config> seen;

    // Reconstruye la ejecución que termina en la configuración i.
    auto path_to = [&found, &parent](std::size_t i) {
        std::vector<Step> run;
        while (true) {
            run.push_back(found[i]);
            if (parent[i] == i) {
                break;
            }
            i = parent[i];
        }
        std::reverse(run.begin(), run.end());
        return run;
    };

    Step first;
    first.config.state = p.start;
    found.push_back(first);
    parent.push_back(0);
    seen.insert(first.config);

    Search search;
    if (accepting(first.config)) {
        search.verdict = Verdict::Accept;
        search.run = path_to(0);
        search.explored = 1;
        return search;
    }
    for (std::size_t head = 0; head < found.size(); head++) {
        Config current = found[head].config;
        for (const Step& step : successors(p, w, current)) {
            if (max_stack != NO_STACK_BOUND && step.config.stack.size() > max_stack) {
                continue;
            }
            if (!seen.insert(step.config).second) {
                continue;
            }
            found.push_back(step);
            parent.push_back(head);
            if (accepting(step.config)) {
                search.verdict = Verdict::Accept;
                search.run = path_to(found.size() - 1);
                search.explored = found.size();
                return search;
            }
            if (found.size() > max_configs) {
                search.verdict = Verdict::Limit;
                search.explored = found.size();
                return search;
            }
        }
    }
    search.verdict = Verdict::Reject;
    search.explored = found.size();
    return search;
}

// p acepta w. Lanza si la búsqueda llega al límite: quien llama debe saber que no pasará.
inline bool accepts(const Pda& p, const std::string& w, std::size_t max_configs = 100000) {
    Search search = simulate(p, w, max_configs);
    if (search.verdict == Verdict::Limit) {
        throw std::runtime_error("la búsqueda llegó al límite de configuraciones con la cadena " + w);
    }
    return search.verdict == Verdict::Accept;
}

// Todas las cadenas sobre sigma de longitud a lo sumo n, primero las más cortas.
inline std::vector<std::string> all_strings(const std::vector<char>& sigma, std::size_t n) {
    std::vector<std::string> result = {""};
    std::size_t begin = 0;
    for (std::size_t length = 1; length <= n; length++) {
        std::size_t end = result.size();
        for (std::size_t i = begin; i < end; i++) {
            for (char a : sigma) {
                result.push_back(result[i] + a);
            }
        }
        begin = end;
    }
    return result;
}

#endif
