// Minimización de un DFA por refinamiento de particiones (algoritmo de Moore), el DFA de
// "el k-ésimo símbolo desde el final es 1" y la comparación de dos DFA.
#ifndef MINIMIZE_H
#define MINIMIZE_H

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

#include "dfa.h"

// Una partición de Q: a cada estado, el número de su bloque. Los bloques se numeran desde 0
// en el orden en que aparece su primer estado en m.states.
struct Partition {
    std::map<std::string, int> block;
    int count = 0;  // cuántos bloques hay
};

inline bool operator==(const Partition& a, const Partition& b) {
    return a.count == b.count && a.block == b.block;
}

// Los bloques como listas de estados, cada una en el orden de m.states.
inline std::vector<std::vector<std::string>> blocks_of(const Dfa& m, const Partition& p) {
    std::vector<std::vector<std::string>> blocks(static_cast<std::size_t>(p.count));
    for (const std::string& state : m.states) {
        blocks[static_cast<std::size_t>(p.block.at(state))].push_back(state);
    }
    return blocks;
}

// Agrupa los estados que tienen la misma firma. Es el único lugar donde se numeran bloques.
inline Partition group_by(const Dfa& m, const std::map<std::string, std::vector<int>>& signature) {
    Partition result;
    std::map<std::vector<int>, int> number;  // firma → bloque
    for (const std::string& state : m.states) {
        const std::vector<int>& key = signature.at(state);
        auto found = number.find(key);
        if (found == number.end()) {
            found = number.insert({key, result.count}).first;
            result.count++;
        }
        result.block[state] = found->second;
    }
    return result;
}

// La partición de partida: los estados de aceptación por un lado y los demás por otro.
// Son los estados que la cadena vacía ya separa. Si F = ∅ o F = Q sale un solo bloque.
inline Partition initial_partition(const Dfa& m) {
    std::map<std::string, std::vector<int>> signature;
    for (const std::string& state : m.states) {
        signature[state] = {m.accept.count(state) > 0 ? 1 : 0};
    }
    return group_by(m, signature);
}

// Una ronda. Dos estados siguen juntos si estaban en el mismo bloque y, con cada símbolo,
// van a parar al mismo bloque. La firma de un estado es la lista
// (su bloque, el bloque de δ(q, a1), el bloque de δ(q, a2), ...).
inline Partition refine(const Dfa& m, const Partition& p) {
    std::map<std::string, std::vector<int>> signature;
    for (const std::string& state : m.states) {
        std::vector<int> key = {p.block.at(state)};
        for (char a : m.alphabet) {
            key.push_back(p.block.at(step(m, state, a)));
        }
        signature[state] = key;
    }
    return group_by(m, signature);
}

// Todas las particiones del algoritmo: P0 = {F, Q − F}, P1, P2, ... La última es la primera
// que una ronda ya no cambia. Como cada ronda solo parte bloques, basta comparar cuántos hay.
inline std::vector<Partition> moore_rounds(const Dfa& m) {
    std::vector<Partition> rounds = {initial_partition(m)};
    while (true) {
        Partition next = refine(m, rounds.back());
        if (next.count == rounds.back().count) {
            return rounds;
        }
        rounds.push_back(next);
    }
}

// El nombre de un bloque: el del estado si está solo, o {q0,q4} si son varios.
inline std::string block_name(const std::vector<std::string>& states) {
    if (states.size() == 1) {
        return states[0];
    }
    std::string name = "{";
    for (std::size_t i = 0; i < states.size(); i++) {
        name += (i > 0 ? "," : "") + states[i];
    }
    return name + "}";
}

// El autómata cociente: un estado por bloque. δ'([q], a) = [δ(q, a)], el inicial es el bloque
// de q0 y un bloque es de aceptación si sus estados lo son. Solo está bien definido si la
// partición es estable (refine ya no la cambia) y no mezcla estados de F con estados de Q − F.
inline Dfa quotient(const Dfa& m, const Partition& p) {
    std::vector<std::vector<std::string>> blocks = blocks_of(m, p);
    std::vector<std::string> names;
    for (const std::vector<std::string>& block : blocks) {
        names.push_back(block_name(block));
    }
    Dfa result;
    result.states = names;
    result.alphabet = m.alphabet;
    result.start = names[static_cast<std::size_t>(p.block.at(m.start))];
    for (std::size_t i = 0; i < blocks.size(); i++) {
        const std::string& representative = blocks[i][0];
        if (m.accept.count(representative) > 0) {
            result.accept.insert(names[i]);
        }
        for (char a : m.alphabet) {
            int target = p.block.at(step(m, representative, a));
            result.delta[{names[i], a}] = names[static_cast<std::size_t>(target)];
        }
    }
    check_dfa(result);
    return result;
}

// El DFA mínimo de L(m): quitar los inalcanzables, refinar hasta que no cambie, y fusionar.
inline Dfa minimize(const Dfa& m) {
    Dfa trimmed = remove_unreachable(m);
    return quotient(trimmed, moore_rounds(trimmed).back());
}

// ------------------------------------------------------------
// Comparar dos DFA
// ------------------------------------------------------------

// ¿Son la misma máquina salvo los nombres de los estados? Si lo son, la correspondencia está
// forzada: el inicial va al inicial y, si p va a q, entonces δ1(p, a) va a δ2(q, a). Se
// recorre desde los iniciales y se comprueba que no haya contradicciones.
// Se asume que todos los estados de las dos máquinas son alcanzables.
inline bool isomorphic(const Dfa& m1, const Dfa& m2) {
    std::set<char> sigma1(m1.alphabet.begin(), m1.alphabet.end());
    std::set<char> sigma2(m2.alphabet.begin(), m2.alphabet.end());
    if (sigma1 != sigma2 || m1.states.size() != m2.states.size()) {
        return false;
    }
    std::map<std::string, std::string> to2 = {{m1.start, m2.start}};
    std::map<std::string, std::string> to1 = {{m2.start, m1.start}};
    std::queue<std::string> pending;
    pending.push(m1.start);
    while (!pending.empty()) {
        std::string p = pending.front();
        pending.pop();
        const std::string& q = to2.at(p);
        if ((m1.accept.count(p) > 0) != (m2.accept.count(q) > 0)) {
            return false;
        }
        for (char a : m1.alphabet) {
            const std::string& p_next = step(m1, p, a);
            const std::string& q_next = step(m2, q, a);
            auto seen1 = to2.find(p_next);
            auto seen2 = to1.find(q_next);
            if (seen1 == to2.end() && seen2 == to1.end()) {
                to2[p_next] = q_next;
                to1[q_next] = p_next;
                pending.push(p_next);
            } else if (seen1 == to2.end() || seen2 == to1.end() || seen1->second != q_next) {
                return false;
            }
        }
    }
    return to2.size() == m1.states.size();
}

// ¿L(m1) = L(m2)? Se minimizan los dos y se comparan: el DFA mínimo es único salvo nombres.
inline bool equivalent(const Dfa& m1, const Dfa& m2) {
    return isomorphic(minimize(m1), minimize(m2));
}

// La cadena más corta que uno acepta y el otro no, o nada si reconocen el mismo lenguaje.
// Recorre a lo ancho los pares (p, q) a los que se llega leyendo lo mismo en las dos máquinas.
inline std::optional<std::string> difference_witness(const Dfa& m1, const Dfa& m2) {
    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("para comparar dos DFA hace falta el mismo alfabeto");
    }
    using Pair = std::pair<std::string, std::string>;
    std::map<Pair, std::string> reached = {{{m1.start, m2.start}, ""}};
    std::queue<Pair> pending;
    pending.push({m1.start, m2.start});
    while (!pending.empty()) {
        Pair current = pending.front();
        pending.pop();
        std::string w = reached.at(current);
        if ((m1.accept.count(current.first) > 0) != (m2.accept.count(current.second) > 0)) {
            return w;
        }
        for (char a : m1.alphabet) {
            Pair next = {step(m1, current.first, a), step(m2, current.second, a)};
            if (reached.count(next) == 0) {
                reached[next] = w + a;
                pending.push(next);
            }
        }
    }
    return std::nullopt;
}

// ------------------------------------------------------------
// El k-ésimo símbolo desde el final es 1
// ------------------------------------------------------------

// El DFA que recuerda los últimos k símbolos leídos: 2^k estados, que se llaman como esos k
// símbolos. Antes de leer k símbolos, los que faltan cuentan como 0, así que el inicial es
// 0^k. Acepta si el más antiguo de los k es un 1. Es el autómata que da la construcción de
// subconjuntos de la semana 2 con otros nombres; aquí se construye directamente.
inline Dfa last_k_dfa(int k) {
    if (k < 1 || k > 16) {
        throw std::runtime_error("k debe estar entre 1 y 16");
    }
    Dfa m;
    m.alphabet = {'0', '1'};
    std::size_t width = static_cast<std::size_t>(k);
    m.start = std::string(width, '0');
    for (unsigned value = 0; value < (1u << k); value++) {
        std::string name(width, '0');
        for (std::size_t i = 0; i < width; i++) {
            if ((value >> (width - 1 - i)) & 1u) {
                name[i] = '1';
            }
        }
        m.states.push_back(name);
        if (name[0] == '1') {
            m.accept.insert(name);
        }
        for (char a : m.alphabet) {
            m.delta[{name, a}] = name.substr(1) + a;  // se olvida el más antiguo y entra a
        }
    }
    check_dfa(m);
    return m;
}

#endif
