// Procedimientos de decisión sobre DFA. Cada función es uno de los algoritmos de la sesión A,
// y todas terminan siempre: recorren un conjunto finito de estados o de pares de estados.
//
//   accepts (en dfa.h)       A_DFA: simular
//   shortest_accepted        E_DFA: alcanzabilidad, con una búsqueda en anchura
//   symmetric_difference     el DFA C de la demostración de EQ_DFA, con el producto completo
//   compare                  EQ_DFA: solo los pares alcanzables, y una cadena más corta que separa
#ifndef DECIDE_H
#define DECIDE_H

#include <algorithm>
#include <cstddef>
#include <map>
#include <optional>
#include <queue>
#include <set>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>

#include "dfa.h"

// E_DFA. Busca en anchura desde q0 y devuelve una cadena más corta de L(M), o nada si
// L(M) = ∅. La búsqueda visita cada estado una sola vez, así que termina.
inline std::optional<std::string> shortest_accepted(const Dfa& m) {
    // Cómo se llegó a cada estado marcado: desde qué estado y con qué símbolo.
    std::map<std::string, std::pair<std::string, char>> parent;
    std::set<std::string> marked = {m.start};
    std::queue<std::string> pending;
    pending.push(m.start);
    while (!pending.empty()) {
        std::string q = pending.front();
        pending.pop();
        if (m.accept.count(q) > 0) {
            std::string w;
            while (q != m.start) {
                w += parent.at(q).second;
                q = parent.at(q).first;
            }
            std::reverse(w.begin(), w.end());
            return w;
        }
        for (char a : m.alphabet) {
            const std::string& next = step(m, q, a);
            if (marked.insert(next).second) {
                parent[next] = {q, a};
                pending.push(next);
            }
        }
    }
    return std::nullopt;
}

// ¿L(M) = ∅? Es decir, ¿⟨M⟩ ∈ E_DFA?
inline bool is_empty(const Dfa& m) {
    return !shortest_accepted(m).has_value();
}

inline void require_same_alphabet(const Dfa& a, const Dfa& b) {
    std::set<char> sigma_a(a.alphabet.begin(), a.alphabet.end());
    std::set<char> sigma_b(b.alphabet.begin(), b.alphabet.end());
    if (sigma_a != sigma_b) {
        throw std::runtime_error("los dos DFA deben tener el mismo alfabeto");
    }
}

// El DFA C con L(C) = diferencia simétrica de L(A) y L(B): el producto completo, con todos
// los pares, y F = los pares en los que exactamente uno de los dos estados es de aceptación.
inline Dfa symmetric_difference(const Dfa& a, const Dfa& b) {
    require_same_alphabet(a, b);
    Dfa c;
    c.alphabet = a.alphabet;
    c.start = pair_name(a.start, b.start);
    for (const std::string& p : a.states) {
        for (const std::string& q : b.states) {
            std::string name = pair_name(p, q);
            c.states.push_back(name);
            if ((a.accept.count(p) > 0) != (b.accept.count(q) > 0)) {
                c.accept.insert(name);
            }
            for (char s : c.alphabet) {
                c.delta[{name, s}] = pair_name(step(a, p, s), step(b, q, s));
            }
        }
    }
    check_dfa(c);
    return c;
}

// El resultado de comparar dos DFA.
struct Comparison {
    bool equivalent = true;
    std::string witness;                                     // si no lo son: una cadena más corta que los separa
    std::vector<std::pair<std::string, std::string>> pairs;  // los pares visitados, en el orden de la búsqueda
};

// EQ_DFA sin construir el producto. Busca en anchura desde (qA, qB) y solo genera los pares
// alcanzables. Si encuentra un par con un estado de aceptación y otro que no, la cadena que
// llevó hasta él separa a los dos autómatas, y por ser búsqueda en anchura es de las más cortas.
// Termina: hay a lo sumo |QA| · |QB| pares y cada uno se visita una vez.
inline Comparison compare(const Dfa& a, const Dfa& b) {
    require_same_alphabet(a, b);
    using Pair = std::pair<std::string, std::string>;
    Comparison result;
    std::map<Pair, std::pair<Pair, char>> parent;
    std::set<Pair> marked;
    std::queue<Pair> pending;
    Pair first = {a.start, b.start};
    marked.insert(first);
    pending.push(first);
    while (!pending.empty()) {
        Pair current = pending.front();
        pending.pop();
        result.pairs.push_back(current);
        if ((a.accept.count(current.first) > 0) != (b.accept.count(current.second) > 0)) {
            result.equivalent = false;
            while (current != first) {
                result.witness += parent.at(current).second;
                current = parent.at(current).first;
            }
            std::reverse(result.witness.begin(), result.witness.end());
            return result;
        }
        for (char s : a.alphabet) {
            Pair next = {step(a, current.first, s), step(b, current.second, s)};
            if (marked.insert(next).second) {
                parent[next] = {current, s};
                pending.push(next);
            }
        }
    }
    return result;
}

// Todos los pares alcanzables desde (qA, qB), sin detenerse en el primero que separa.
inline std::size_t reachable_pairs(const Dfa& a, const Dfa& b) {
    require_same_alphabet(a, b);
    using Pair = std::pair<std::string, std::string>;
    std::set<Pair> marked = {{a.start, b.start}};
    std::queue<Pair> pending;
    pending.push({a.start, b.start});
    while (!pending.empty()) {
        Pair current = pending.front();
        pending.pop();
        for (char s : a.alphabet) {
            Pair next = {step(a, current.first, s), step(b, current.second, s)};
            if (marked.insert(next).second) {
                pending.push(next);
            }
        }
    }
    return marked.size();
}

// La cadena w como se muestra en pantalla: ε si es vacía.
inline std::string show(const std::string& w) {
    return w.empty() ? "ε" : w;
}

#endif
