// Ayudas compartidas por las pruebas: predicados sobre cadenas, la aceptación de un NFA
// calculada directamente con la definición (buscando un camino) y NFA al azar con semilla fija.
#ifndef TEST_HELPERS_H
#define TEST_HELPERS_H

#include <algorithm>
#include <cstddef>
#include <random>
#include <set>
#include <string>
#include <utility>
#include <vector>

#include "nfa.h"

inline bool ends_with(const std::string& w, const std::string& tail) {
    return w.size() >= tail.size() && w.compare(w.size() - tail.size(), tail.size(), tail) == 0;
}

inline bool contains(const std::string& w, const std::string& piece) {
    return w.find(piece) != std::string::npos;
}

inline int count_ones(const std::string& w) {
    return static_cast<int>(std::count(w.begin(), w.end(), '1'));
}

inline std::string reversed(const std::string& w) {
    return std::string(w.rbegin(), w.rend());
}

// ¿Hay un camino desde q, habiendo leído pos símbolos de w, que termine en F con toda la cadena leída?
// Es la definición de aceptación, sin conjuntos de estados activos. on_path evita los ciclos de ε.
inline bool path_exists(const Nfa& n, const std::string& w, const std::string& q, std::size_t pos,
                        std::set<std::pair<std::string, std::size_t>>& on_path) {
    if (pos == w.size() && n.accept.count(q) > 0) {
        return true;
    }
    if (!on_path.insert({q, pos}).second) {
        return false;
    }
    bool found = false;
    if (pos < w.size()) {
        for (const std::string& r : delta_of(n, q, w[pos])) {
            found = found || path_exists(n, w, r, pos + 1, on_path);
        }
    }
    for (const std::string& r : delta_of(n, q, EPS)) {
        found = found || path_exists(n, w, r, pos, on_path);
    }
    on_path.erase({q, pos});
    return found;
}

inline bool accepts_by_paths(const Nfa& n, const std::string& w) {
    std::set<std::pair<std::string, std::size_t>> on_path;
    return path_exists(n, w, n.start, 0, on_path);
}

// Un NFA al azar con size estados sobre {0, 1}, con transiciones ε (también ciclos de ε),
// pares sin transición y estados inalcanzables. Solo usa rng() y restos, para que salga igual
// en cualquier plataforma.
inline Nfa random_nfa(std::mt19937& rng, int size) {
    Nfa n;
    n.alphabet = {'0', '1'};
    for (int i = 0; i < size; i++) {
        n.states.push_back("p" + std::to_string(i));
    }
    n.start = n.states[rng() % size];
    for (const std::string& state : n.states) {
        if (rng() % 3 == 0) {
            n.accept.insert(state);
        }
        for (char a : {'0', '1', EPS}) {
            // Pocas transiciones ε, para que no todo quede conectado con todo.
            unsigned arrows = (a == EPS) ? (rng() % 4 == 0 ? 1 : 0) : rng() % 3;
            for (unsigned k = 0; k < arrows; k++) {
                n.delta[{state, a}].insert(n.states[rng() % size]);
            }
        }
    }
    return n;
}

#endif
