// Todos los caminos de un NFA con una cadena, uno por línea: paths_nfa ARCHIVO.nfa CADENA
// Es el árbol de ejecuciones, con cada rama escrita desde la raíz. Una rama termina cuando
// se acaba la cadena o cuando el estado no tiene transición con el símbolo que toca (muere).
// La cadena vacía se pasa como '' en la terminal.
#include <cstddef>
#include <iostream>
#include <set>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>

#include "nfa.h"
#include "strings.h"

struct Count {
    int finished = 0;   // caminos que leyeron toda la cadena
    int accepting = 0;  // de esos, los que terminan en F
    int dead = 0;       // caminos que murieron antes
};

// Extiende el camino text, que está en el estado q y ya leyó pos símbolos de w.
// on_path tiene los pares (estado, posición) del camino: evita dar vueltas por un ciclo de ε.
static void explore(const Nfa& n, const std::string& w, const std::string& q, std::size_t pos,
                    const std::string& text, std::set<std::pair<std::string, std::size_t>>& on_path, Count& count) {
    on_path.insert({q, pos});
    bool moved = false;
    if (pos == w.size()) {
        bool ok = n.accept.count(q) > 0;
        std::cout << "  " << text << "    termina en " << q << (ok ? ", que está en F" : ", que no está en F") << '\n';
        count.finished++;
        count.accepting += ok;
        moved = true;
    } else {
        for (const std::string& r : delta_of(n, q, w[pos])) {
            explore(n, w, r, pos + 1, text + " -" + w[pos] + "-> " + r, on_path, count);
            moved = true;
        }
    }
    for (const std::string& r : delta_of(n, q, EPS)) {
        if (on_path.count({r, pos}) == 0) {
            explore(n, w, r, pos, text + " -ε-> " + r, on_path, count);
            moved = true;
        }
    }
    if (!moved) {
        std::cout << "  " << text << "    muere: " << q << " no tiene transición con " << w[pos] << '\n';
        count.dead++;
    }
    on_path.erase({q, pos});
}

int main(int argc, char** argv) {
    if (argc != 3) {
        std::cerr << "uso: paths_nfa ARCHIVO.nfa CADENA\n";
        return 2;
    }
    try {
        Nfa n = load_nfa(argv[1]);
        std::string w = argv[2];
        std::cout << "w = " << show(w) << '\n';
        std::set<std::pair<std::string, std::size_t>> on_path;
        Count count;
        explore(n, w, n.start, 0, n.start, on_path, count);
        std::cout << "caminos que leen toda la cadena: " << count.finished << "    que mueren antes: " << count.dead
                  << "    que terminan en F: " << count.accepting << "\n"
                  << (count.accepting > 0 ? "algún camino termina en F: acepta" : "ningún camino termina en F: rechaza")
                  << '\n';
    } catch (const std::runtime_error& error) {
        std::cerr << "error: " << error.what() << '\n';
        return 1;
    }
}
