// Minimización de un DFA, como en la semana 4: quitar los estados inalcanzables y fusionar los
// indistinguibles, refinando la partición {F, Q − F} hasta que no cambie.
// Aquí solo se usa para producir los autómatas de lab/dfa_equiv/machines.
#ifndef MINIMIZE_H
#define MINIMIZE_H

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

#include "dfa.h"

// Devuelve el DFA mínimo equivalente a m. Sus estados se llaman prefix0, prefix1, ...
inline Dfa minimize(const Dfa& original, const std::string& prefix = "s") {
    Dfa m = remove_unreachable(original);
    // block[q] es el número del bloque de q. Se empieza con dos bloques: F y Q − F.
    std::map<std::string, std::size_t> block;
    for (const std::string& q : m.states) {
        block[q] = m.accept.count(q) > 0 ? 1 : 0;
    }
    std::size_t count = 0;
    while (true) {
        // La firma de un estado: su bloque y el bloque de cada uno de sus destinos.
        // Dos estados siguen juntos solo si tienen la misma firma.
        std::map<std::vector<std::size_t>, std::size_t> number;
        std::map<std::string, std::size_t> refined;
        for (const std::string& q : m.states) {
            std::vector<std::size_t> signature = {block.at(q)};
            for (char a : m.alphabet) {
                signature.push_back(block.at(step(m, q, a)));
            }
            auto it = number.find(signature);
            if (it == number.end()) {
                it = number.insert({signature, number.size()}).first;
            }
            refined[q] = it->second;
        }
        bool stable = number.size() == count;
        count = number.size();
        block = refined;
        if (stable) {
            break;
        }
    }
    Dfa result;
    result.alphabet = m.alphabet;
    std::vector<bool> done(count, false);
    for (const std::string& q : m.states) {
        std::size_t b = block.at(q);
        if (done[b]) {
            continue;
        }
        done[b] = true;
        std::string name = prefix + std::to_string(b);
        result.states.push_back(name);
        if (m.accept.count(q) > 0) {
            result.accept.insert(name);
        }
        for (char a : m.alphabet) {
            result.delta[{name, a}] = prefix + std::to_string(block.at(step(m, q, a)));
        }
    }
    result.start = prefix + std::to_string(block.at(m.start));
    check_dfa(result);
    return result;
}

#endif
