// Cadenas distinguibles. Dos cadenas x, y son distinguibles respecto de un lenguaje L si
// algún sufijo z deja a xz y a yz en lados distintos de L. Con un DFA de L en la mano, eso se
// puede comprobar: basta mirar los estados a los que llegan x e y.
#ifndef DISTINGUISH_H
#define DISTINGUISH_H

#include <cstddef>
#include <map>
#include <optional>
#include <queue>
#include <string>
#include <utility>
#include <vector>

#include "dfa.h"

// Todas las cadenas sobre el alfabeto con longitud a lo sumo max_len, primero las más cortas
// y, entre las de igual longitud, en el orden del alfabeto. (Es la de languages.h, semana 1.)
inline std::vector<std::string> all_strings(const std::vector<char>& alphabet, std::size_t max_len) {
    std::vector<std::string> result = {""};
    std::size_t first = 0;  // dónde empiezan las cadenas de la longitud anterior
    for (std::size_t len = 1; len <= max_len; len++) {
        std::size_t last = result.size();
        for (std::size_t i = first; i < last; i++) {
            for (char a : alphabet) {
                result.push_back(result[i] + a);
            }
        }
        first = last;
    }
    return result;
}

// ¿El sufijo z distingue a x de y? Es decir: ¿M acepta exactamente una de xz, yz?
inline bool separates(const Dfa& m, const std::string& x, const std::string& y, const std::string& z) {
    return accepts(m, x + z) != accepts(m, y + z);
}

// Fuerza bruta, tal como dice la definición: prueba los sufijos de longitud a lo sumo max_len,
// del más corto al más largo, y devuelve el primero que distingue. tried cuenta cuántos probó.
// Si no encuentra ninguno, eso solo demuestra algo cuando max_len ≥ |Q| − 1 (ver los apuntes).
inline std::optional<std::string> brute_distinguishing_suffix(const Dfa& m, const std::string& x,
                                                              const std::string& y, std::size_t max_len,
                                                              std::size_t& tried) {
    tried = 0;
    for (const std::string& z : all_strings(m.alphabet, max_len)) {
        tried++;
        if (separates(m, x, y, z)) {
            return z;
        }
    }
    return std::nullopt;
}

// Lo mismo sin probar cadenas: el sufijo más corto z tal que exactamente uno de δ*(p, z) y
// δ*(q, z) está en F, o nada si los estados p y q son indistinguibles. Recorre a lo ancho los
// pares de estados a los que se llega desde (p, q) leyendo lo mismo; hay a lo sumo |Q|² pares.
inline std::optional<std::string> state_distinguishing_suffix(const Dfa& m, const std::string& p,
                                                              const std::string& q) {
    using Pair = std::pair<std::string, std::string>;
    std::map<Pair, std::string> reached = {{{p, q}, ""}};
    std::queue<Pair> pending;
    pending.push({p, q});
    while (!pending.empty()) {
        Pair current = pending.front();
        pending.pop();
        std::string z = reached.at(current);
        if ((m.accept.count(current.first) > 0) != (m.accept.count(current.second) > 0)) {
            return z;
        }
        for (char a : m.alphabet) {
            Pair next = {step(m, current.first, a), step(m, current.second, a)};
            if (reached.count(next) == 0) {
                reached[next] = z + a;
                pending.push(next);
            }
        }
    }
    return std::nullopt;
}

// Para dos cadenas: x e y son distinguibles respecto de L(M) si y solo si lo son los estados
// δ*(q0, x) y δ*(q0, y), y con los mismos sufijos.
inline std::optional<std::string> distinguishing_suffix(const Dfa& m, const std::string& x,
                                                        const std::string& y) {
    return state_distinguishing_suffix(m, delta_star(m, m.start, x), delta_star(m, m.start, y));
}

// ¿Las cadenas dadas son distinguibles dos a dos respecto de L(M)? Si lo son, todo DFA que
// reconozca L(M) tiene al menos strings.size() estados.
inline bool pairwise_distinguishable(const Dfa& m, const std::vector<std::string>& strings) {
    for (std::size_t i = 0; i < strings.size(); i++) {
        for (std::size_t j = i + 1; j < strings.size(); j++) {
            if (!distinguishing_suffix(m, strings[i], strings[j])) {
                return false;
            }
        }
    }
    return true;
}

// ------------------------------------------------------------
// El autómata de las clases (Myhill-Nerode)
// ------------------------------------------------------------

// Un representante por cada clase de equivalencia de L(M), y a qué clase pertenece cada
// cadena que se pregunte. Los representantes se buscan del más corto al más largo: ε primero,
// y después xa para cada representante x ya encontrado y cada símbolo a.
struct Classes {
    std::vector<std::string> representatives;
};

// El representante de la clase de w, o nada si w no es equivalente a ninguno.
inline std::optional<std::string> class_of(const Dfa& m, const Classes& classes, const std::string& w) {
    for (const std::string& r : classes.representatives) {
        if (!distinguishing_suffix(m, w, r)) {
            return r;
        }
    }
    return std::nullopt;
}

inline Classes nerode_classes(const Dfa& m) {
    Classes classes;
    classes.representatives.push_back("");
    for (std::size_t i = 0; i < classes.representatives.size(); i++) {
        for (char a : m.alphabet) {
            std::string candidate = classes.representatives[i] + a;
            if (!class_of(m, classes, candidate)) {
                classes.representatives.push_back(candidate);
            }
        }
    }
    return classes;
}

// El nombre del estado [x]. La cadena vacía se escribe ε.
inline std::string class_name(const std::string& x) {
    return "[" + (x.empty() ? std::string("ε") : x) + "]";
}

// El DFA de la demostración de Myhill-Nerode: un estado por clase, δ([x], a) = [xa], el
// inicial es [ε] y [x] es de aceptación si x ∈ L. Aquí L es L(M), y M solo se usa para
// responder dos preguntas: si una cadena está en L y si dos cadenas son distinguibles.
inline Dfa nerode_dfa(const Dfa& m) {
    Classes classes = nerode_classes(m);
    Dfa result;
    result.alphabet = m.alphabet;
    result.start = class_name("");
    for (const std::string& x : classes.representatives) {
        result.states.push_back(class_name(x));
        if (accepts(m, x)) {
            result.accept.insert(class_name(x));
        }
        for (char a : m.alphabet) {
            result.delta[{class_name(x), a}] = class_name(*class_of(m, classes, x + a));
        }
    }
    check_dfa(result);
    return result;
}

#endif
