// El lema de bombeo, de los dos lados.
// Con un DFA: dada una cadena aceptada de longitud al menos |Q|, encontrar la división x, y, z
// que promete el lema, buscando el primer estado que se repite en la ejecución.
// Sin DFA: el juego contra el adversario para un lenguaje dado por una función que decide.
#ifndef PUMPING_H
#define PUMPING_H

#include <cstddef>
#include <functional>
#include <map>
#include <stdexcept>
#include <string>
#include <vector>

#include "dfa.h"

// Una división s = xyz.
struct Split {
    std::string x, y, z;
};

// y repetida i veces.
inline std::string repeat(const std::string& y, std::size_t i) {
    std::string result;
    for (std::size_t k = 0; k < i; k++) {
        result += y;
    }
    return result;
}

// x y^i z
inline std::string pumped(const Split& split, std::size_t i) {
    return split.x + repeat(split.y, i) + split.z;
}

// ------------------------------------------------------------
// Con un DFA: de dónde sale la división
// ------------------------------------------------------------

struct PumpSplit {
    Split split;
    std::string state;      // el estado que se repite
    std::size_t first = 0;  // se visita después de leer first símbolos...
    std::size_t second = 0; // ...y otra vez después de leer second, con first < second ≤ |Q|
};

// La demostración del lema, ejecutada. La ejecución de M con w empieza con los estados
// r0, r1, ..., rp, donde p = |Q|: son p + 1 estados y solo hay p distintos, así que dos
// coinciden. Se toma la primera repetición: x es lo leído hasta la primera visita, y lo leído
// entre las dos visitas, z el resto. Pide |w| ≥ |Q|; no pide que M acepte w.
inline PumpSplit pump_split(const Dfa& m, const std::string& w) {
    std::size_t p = m.states.size();
    if (w.size() < p) {
        throw std::runtime_error("la cadena debe tener al menos |Q| = " + std::to_string(p) + " símbolos");
    }
    std::vector<std::string> sequence = run(m, w);
    std::map<std::string, std::size_t> seen;  // estado → después de cuántos símbolos se visitó
    for (std::size_t j = 0; j <= p; j++) {
        auto earlier = seen.find(sequence[j]);
        if (earlier != seen.end()) {
            std::size_t i = earlier->second;
            PumpSplit result;
            result.split = {w.substr(0, i), w.substr(i, j - i), w.substr(j)};
            result.state = sequence[j];
            result.first = i;
            result.second = j;
            return result;
        }
        seen[sequence[j]] = j;
    }
    throw std::logic_error("imposible: p + 1 estados sin repetición");  // principio del palomar
}

// ------------------------------------------------------------
// Sin DFA: el juego
// ------------------------------------------------------------

// Todas las divisiones s = xyz que el adversario puede elegir: |y| > 0 y |xy| ≤ p.
// Si |s| ≥ p son p(p + 1)/2.
inline std::vector<Split> legal_splits(const std::string& s, std::size_t p) {
    std::vector<Split> result;
    for (std::size_t x_len = 0; x_len < s.size() && x_len < p; x_len++) {
        for (std::size_t y_len = 1; x_len + y_len <= p && x_len + y_len <= s.size(); y_len++) {
            result.push_back({s.substr(0, x_len), s.substr(x_len, y_len), s.substr(x_len + y_len)});
        }
    }
    return result;
}

// Una partida: el lenguaje, y nuestras dos jugadas. La cadena depende de p. El exponente
// puede depender de p y de la división, aunque en los ejemplos del capítulo es fijo.
struct Game {
    std::string name;         // para la línea de comandos
    std::string language;     // cómo se muestra L
    std::function<bool(const std::string&)> in_language;
    std::function<std::string(std::size_t)> choose_string;
    std::size_t exponent = 2;
};

// ¿Cuántos unos y ceros?
inline std::size_t count_symbol(const std::string& w, char a) {
    std::size_t total = 0;
    for (char c : w) {
        total += (c == a) ? 1 : 0;
    }
    return total;
}

// ¿w es de la forma a^i b^j, con a antes que b?
inline bool is_block_pair(const std::string& w, char a, char b) {
    std::size_t i = 0;
    while (i < w.size() && w[i] == a) {
        i++;
    }
    while (i < w.size() && w[i] == b) {
        i++;
    }
    return i == w.size();
}

inline bool in_zeros_ones(const std::string& w) {  // { 0^n 1^n }
    return is_block_pair(w, '0', '1') && count_symbol(w, '0') == count_symbol(w, '1');
}

inline bool in_equal(const std::string& w) {  // tantos ceros como unos, en cualquier orden
    return count_symbol(w, '0') + count_symbol(w, '1') == w.size() &&
           count_symbol(w, '0') == count_symbol(w, '1');
}

inline bool in_ww(const std::string& s) {  // { ww }
    std::size_t half = s.size() / 2;
    return s.size() % 2 == 0 && s.substr(0, half) == s.substr(half);
}

inline bool in_squares(const std::string& w) {  // { 0^(n²) }
    if (count_symbol(w, '0') != w.size()) {
        return false;
    }
    std::size_t n = 0;
    while (n * n < w.size()) {
        n++;
    }
    return n * n == w.size();
}

inline bool in_more_zeros(const std::string& w) {  // { 0^i 1^j : i > j }
    return is_block_pair(w, '0', '1') && count_symbol(w, '0') > count_symbol(w, '1');
}

// { a^i b^j c^k : si i = 1 entonces j = k }. No es regular y aun así cumple el lema con p = 2.
inline bool in_trap(const std::string& w) {
    std::size_t pos = 0;
    std::size_t counts[3] = {0, 0, 0};
    for (int letter = 0; letter < 3; letter++) {
        while (pos < w.size() && w[pos] == static_cast<char>('a' + letter)) {
            counts[letter]++;
            pos++;
        }
    }
    return pos == w.size() && (counts[0] != 1 || counts[1] == counts[2]);
}

// La división con la que el adversario gana siempre en el lenguaje anterior, para |s| ≥ 2:
// y es la primera letra, salvo si s empieza con exactamente dos a, en cuyo caso y = aa.
inline Split trap_split(const std::string& s) {
    bool two_a = s.size() >= 2 && s[0] == 'a' && s[1] == 'a' && (s.size() == 2 || s[2] != 'a');
    std::size_t y_len = two_a ? 2 : 1;
    return {"", s.substr(0, y_len), s.substr(y_len)};
}

// Las partidas del capítulo. Las que terminan en -mal usan una cadena o un exponente mal
// elegidos: el adversario tiene una división que resiste.
inline std::vector<Game> chapter_games() {
    auto zeros_ones = [](std::size_t p) { return std::string(p, '0') + std::string(p, '1'); };
    return {
        {"0n1n", "{ 0^n 1^n : n ≥ 0 }", in_zeros_ones, zeros_ones, 2},
        {"iguales", "{ w : w tiene tantos 0 como 1 }", in_equal, zeros_ones, 2},
        {"iguales-mal", "{ w : w tiene tantos 0 como 1 }", in_equal,
         [](std::size_t p) { return repeat("01", p); }, 2},
        {"ww", "{ ww : w ∈ {0,1}* }", in_ww,
         [](std::size_t p) { return std::string(p, '0') + "1" + std::string(p, '0') + "1"; }, 2},
        {"ww-mal", "{ ww : w ∈ {0,1}* }", in_ww, [](std::size_t p) { return std::string(2 * p, '0'); }, 2},
        {"cuadrados", "{ 0^(n²) : n ≥ 0 }", in_squares, [](std::size_t p) { return std::string(p * p, '0'); }, 2},
        {"mas-ceros", "{ 0^i 1^j : i > j }", in_more_zeros,
         [](std::size_t p) { return std::string(p + 1, '0') + std::string(p, '1'); }, 0},
        {"mas-ceros-mal", "{ 0^i 1^j : i > j }", in_more_zeros,
         [](std::size_t p) { return std::string(p + 1, '0') + std::string(p, '1'); }, 2},
    };
}

// Las divisiones con las que el adversario resiste nuestro exponente: x y^i z sigue en L.
inline std::vector<Split> surviving_splits(const Game& game, std::size_t p) {
    std::vector<Split> result;
    for (const Split& split : legal_splits(game.choose_string(p), p)) {
        if (game.in_language(pumped(split, game.exponent))) {
            result.push_back(split);
        }
    }
    return result;
}

#endif
