// De una fórmula cuantificada a un grafo de geografía generalizada: la reducción que muestra
// que la geografía generalizada es PSPACE-difícil.
//
// La fórmula debe tener la forma ∃x1 ∀x2 ∃x3 … ∃xk ψ, con k impar, los cuantificadores
// alternados y ψ en CNF. normalize_for_game lleva cualquier fórmula de qbf.h a esa forma.
#ifndef FORMULA_GAME_H
#define FORMULA_GAME_H

#include <cstddef>
#include <cstdlib>
#include <stdexcept>
#include <string>
#include <vector>

#include "graph.h"
#include "qbf.h"

// ¿El prefijo empieza con ∃, alterna y termina con ∃?
inline bool has_game_form(const Qbf& f) {
    if (f.variables.empty() || f.variables.size() % 2 == 0) {
        return false;
    }
    for (std::size_t i = 0; i < f.variables.size(); i++) {
        if (f.quantifiers[i] != (i % 2 == 0 ? 'E' : 'A')) {
            return false;
        }
    }
    return true;
}

// Una fórmula con el mismo valor y la forma que pide el juego. Donde el cuantificador que toca
// no es el de la variable siguiente, intercala una variable nueva, d1, d2…, que no aparece en
// ninguna cláusula: quien la elige no cambia nada.
inline Qbf normalize_for_game(const Qbf& f) {
    Qbf g;
    std::vector<int> new_index(f.variables.size(), 0);
    int dummies = 0;
    auto add_dummy = [&g, &dummies, &f]() {
        std::string name;
        bool taken = true;
        while (taken) {
            name = "d" + std::to_string(++dummies);
            taken = false;
            for (const std::string& used : f.variables) {
                taken = taken || used == name;
            }
        }
        g.quantifiers.push_back(g.variables.size() % 2 == 0 ? 'E' : 'A');
        g.variables.push_back(name);
    };
    for (std::size_t i = 0; i < f.variables.size(); i++) {
        char expected = g.variables.size() % 2 == 0 ? 'E' : 'A';
        if (f.quantifiers[i] != expected) {
            add_dummy();
        }
        g.variables.push_back(f.variables[i]);
        g.quantifiers.push_back(f.quantifiers[i]);
        new_index[i] = static_cast<int>(g.variables.size());
    }
    if (g.variables.size() % 2 == 0) {
        add_dummy();  // el último cuantificador debe ser ∃ (también si no había variables)
    }
    for (const std::vector<int>& clause : f.clauses) {
        std::vector<int> renamed;
        for (int literal : clause) {
            int index = new_index[static_cast<std::size_t>(std::abs(literal)) - 1];
            renamed.push_back(literal > 0 ? index : -index);
        }
        g.clauses.push_back(renamed);
    }
    return g;
}

// El grafo de la reducción. Por cada variable x, un rombo de cuatro nodos:
//
//     x.in → x.T → x.out        x.T: se eligió x verdadera
//     x.in → x.F → x.out        x.F: se eligió x falsa
//
// El x.out de cada rombo va al x.in del siguiente, y el último va al nodo `matrix`.
// De `matrix` sale una arista a un nodo por cláusula (cl1, cl2…); de cada cláusula, una a un
// nodo por literal (cl1/1, cl1/2…); y de cada literal, una al nodo de su rombo que lo hace
// verdadero: x.T si el literal es x, x.F si es ¬x. La partida empieza en el x.in del primer rombo.
inline Graph geography_from_formula(const Qbf& f) {
    if (!has_game_form(f)) {
        throw std::runtime_error("la fórmula no tiene la forma ∃ ∀ ∃ … ∃: pásenla antes por normalize_for_game");
    }
    Graph g;
    auto add_node = [&g](const std::string& name) {
        g.nodes.push_back(name);
        g.edges.emplace_back();
        return static_cast<int>(g.nodes.size()) - 1;
    };
    std::size_t k = f.variables.size();
    std::vector<int> in(k), when_true(k), when_false(k), out(k);
    for (std::size_t i = 0; i < k; i++) {
        in[i] = add_node(f.variables[i] + ".in");
        when_true[i] = add_node(f.variables[i] + ".T");
        when_false[i] = add_node(f.variables[i] + ".F");
        out[i] = add_node(f.variables[i] + ".out");
        g.edges[in[i]] = {when_true[i], when_false[i]};
        g.edges[when_true[i]] = {out[i]};
        g.edges[when_false[i]] = {out[i]};
        if (i > 0) {
            g.edges[out[i - 1]] = {in[i]};
        }
    }
    int matrix = add_node("matrix");
    g.edges[out[k - 1]] = {matrix};
    for (std::size_t j = 0; j < f.clauses.size(); j++) {
        std::string clause_name = "cl" + std::to_string(j + 1);
        int clause_node = add_node(clause_name);
        g.edges[matrix].push_back(clause_node);
        for (std::size_t l = 0; l < f.clauses[j].size(); l++) {
            int literal = f.clauses[j][l];
            std::size_t variable = static_cast<std::size_t>(std::abs(literal)) - 1;
            int literal_node = add_node(clause_name + "/" + std::to_string(l + 1));
            g.edges[clause_node].push_back(literal_node);
            g.edges[literal_node] = {literal > 0 ? when_true[variable] : when_false[variable]};
        }
    }
    g.start = in[0];
    return g;
}

#endif
