// El lema de bombeo para lenguajes libres de contexto, como un juego que se puede jugar
// completo cuando la cadena es corta: se listan todas las divisiones s = uvxyz que el
// adversario puede elegir, y para cada una se busca un exponente que saque la cadena del lenguaje.
#ifndef PUMPING_H
#define PUMPING_H

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

// Una división s = uvxyz, dada por las longitudes de u, v, x e y. Lo que sobra es z.
struct Division {
    std::size_t u = 0;
    std::size_t v = 0;
    std::size_t x = 0;
    std::size_t y = 0;
};

// La cadena u v^i x y^i z.
inline std::string pump(const std::string& s, const Division& d, std::size_t i) {
    std::string u = s.substr(0, d.u);
    std::string v = s.substr(d.u, d.v);
    std::string x = s.substr(d.u + d.v, d.x);
    std::string y = s.substr(d.u + d.v + d.x, d.y);
    std::string z = s.substr(d.u + d.v + d.x + d.y);
    std::string result = u;
    for (std::size_t k = 0; k < i; k++) {
        result += v;
    }
    result += x;
    for (std::size_t k = 0; k < i; k++) {
        result += y;
    }
    return result + z;
}

// Todas las divisiones de s que cumplen las condiciones del lema: |vy| > 0 y |vxy| ≤ p.
inline std::vector<Division> divisions(const std::string& s, std::size_t p) {
    std::vector<Division> result;
    for (std::size_t u = 0; u <= s.size(); u++) {
        for (std::size_t v = 0; u + v <= s.size() && v <= p; v++) {
            for (std::size_t x = 0; u + v + x <= s.size() && v + x <= p; x++) {
                for (std::size_t y = 0; u + v + x + y <= s.size() && v + x + y <= p; y++) {
                    if (v + y > 0) {
                        result.push_back({u, v, x, y});
                    }
                }
            }
        }
    }
    return result;
}

// Cómo le va a cada división de s contra el lenguaje.
struct PumpReport {
    std::size_t total = 0;       // divisiones que el adversario puede elegir
    std::size_t out_with_2 = 0;  // u v² x y² z ya no está en el lenguaje
    std::size_t out_with_0 = 0;  // con i = 2 sigue en el lenguaje, pero u x z no está
    std::size_t survive = 0;     // sigue en el lenguaje con todos los i de 0 a max_i
    Division example;            // una de las que sobreviven, si hay
};

inline PumpReport pump_report(const std::function<bool(const std::string&)>& in_language, const std::string& s,
                              std::size_t p, std::size_t max_i = 4) {
    PumpReport report;
    for (const Division& d : divisions(s, p)) {
        report.total++;
        if (!in_language(pump(s, d, 2))) {
            report.out_with_2++;
            continue;
        }
        if (!in_language(pump(s, d, 0))) {
            report.out_with_0++;
            continue;
        }
        bool all = true;
        for (std::size_t i = 0; i <= max_i; i++) {
            all = all && in_language(pump(s, d, i));
        }
        if (all) {
            if (report.survive == 0) {
                report.example = d;
            }
            report.survive++;
        }
    }
    return report;
}

// ------------------------------------------------------------
// Los lenguajes de los ejemplos, como funciones que miran la cadena completa
// ------------------------------------------------------------

// Cuenta un bloque de símbolos c a partir de la posición i, y avanza i.
inline std::size_t block(const std::string& w, std::size_t& i, char c) {
    std::size_t count = 0;
    while (i < w.size() && w[i] == c) {
        i++;
        count++;
    }
    return count;
}

// { 0^n 1^n : n ≥ 0 }
inline bool is_zeros_ones(const std::string& w) {
    std::size_t i = 0;
    std::size_t zeros = block(w, i, '0');
    std::size_t ones = block(w, i, '1');
    return i == w.size() && zeros == ones;
}

// { a^n b^n c^n : n ≥ 0 }
inline bool is_anbncn(const std::string& w) {
    std::size_t i = 0;
    std::size_t a = block(w, i, 'a');
    std::size_t b = block(w, i, 'b');
    std::size_t c = block(w, i, 'c');
    return i == w.size() && a == b && b == c;
}

// { a^i b^j c^k : i ≤ j ≤ k }
inline bool is_ordered_abc(const std::string& w) {
    std::size_t i = 0;
    std::size_t a = block(w, i, 'a');
    std::size_t b = block(w, i, 'b');
    std::size_t c = block(w, i, 'c');
    return i == w.size() && a <= b && b <= c;
}

// { ww : w es cualquier cadena }
inline bool is_ww(const std::string& w) {
    if (w.size() % 2 != 0) {
        return false;
    }
    std::size_t half = w.size() / 2;
    return w.substr(0, half) == w.substr(half);
}

#endif
