// Fórmulas booleanas cuantificadas en forma prenex, con la parte sin cuantificadores en CNF:
//
//     φ = Q1 x1 Q2 x2 … Qm xm ψ,   con cada Qi igual a ∃ o a ∀ y ψ una conjunción de cláusulas.
//
// El struct tiene las tres partes: las variables en el orden del prefijo, el cuantificador de
// cada una y las cláusulas. Además: leer y escribir el formato .qbf de la semana y evaluar la
// fórmula con la recursión que muestra que TQBF está en PSPACE.
#ifndef QBF_H
#define QBF_H

#include <algorithm>
#include <cstddef>
#include <cstdlib>
#include <fstream>
#include <istream>
#include <map>
#include <ostream>
#include <stdexcept>
#include <string>
#include <vector>

#include "fields.h"

struct Qbf {
    std::vector<std::string> variables;     // x1 … xm, en el orden del prefijo
    std::vector<char> quantifiers;          // quantifiers[i] es 'E' (∃) o 'A' (∀), el de variables[i]
    std::vector<std::vector<int>> clauses;  // ψ: el literal xi es i (desde 1) y ¬xi es -i
};

// ------------------------------------------------------------
// Leer y escribir el formato .qbf
// ------------------------------------------------------------
//
//     # ∀x ∃y ((x ∨ y) ∧ (¬x ∨ ¬y))
//     prefix: A x E y
//     clauses:
//     x y
//     -x -y
//
// `prefix:` lleva el prefijo de izquierda a derecha: una letra, A o E, y el nombre de la variable.
// Después de `clauses:` va una cláusula por línea; un literal negado lleva un guion delante.

inline Qbf read_qbf(std::istream& in) {
    Qbf f;
    std::vector<std::string> prefix = read_field(in, "prefix");
    if (prefix.size() % 2 != 0) {
        throw std::runtime_error("prefix: lleva pares de cuantificador y variable");
    }
    std::map<std::string, int> index;
    for (std::size_t i = 0; i < prefix.size(); i += 2) {
        if (prefix[i] != "A" && prefix[i] != "E") {
            throw std::runtime_error("el cuantificador es A o E, y se leyó " + prefix[i]);
        }
        const std::string& name = prefix[i + 1];
        if (name[0] == '-') {
            throw std::runtime_error("el nombre de una variable no empieza con guion: " + name);
        }
        if (index.count(name) != 0) {
            throw std::runtime_error("la variable " + name + " está cuantificada dos veces");
        }
        f.variables.push_back(name);
        f.quantifiers.push_back(prefix[i][0]);
        index[name] = static_cast<int>(f.variables.size());
    }
    if (!read_field(in, "clauses").empty()) {
        throw std::runtime_error("después de clauses: las cláusulas van una por línea");
    }
    std::string line;
    while (next_line(in, line)) {
        std::vector<int> clause;
        for (const std::string& word : split_words(line)) {
            bool negated = word[0] == '-';
            std::string name = negated ? word.substr(1) : word;
            if (index.count(name) == 0) {
                throw std::runtime_error("la variable " + name +
                                         " no tiene cuantificador: la fórmula no está totalmente cuantificada");
            }
            clause.push_back(negated ? -index[name] : index[name]);
        }
        f.clauses.push_back(clause);
    }
    return f;
}

inline Qbf load_qbf(const std::string& path) {
    std::ifstream in(path);
    if (!in) {
        throw std::runtime_error(path + ": no se pudo abrir");
    }
    try {
        return read_qbf(in);
    } catch (const std::runtime_error& e) {
        throw std::runtime_error(path + ": " + e.what());
    }
}

inline void write_qbf(std::ostream& out, const Qbf& f) {
    out << "prefix:";
    for (std::size_t i = 0; i < f.variables.size(); i++) {
        out << ' ' << f.quantifiers[i] << ' ' << f.variables[i];
    }
    out << "\nclauses:\n";
    for (const std::vector<int>& clause : f.clauses) {
        for (std::size_t k = 0; k < clause.size(); k++) {
            int literal = clause[k];
            out << (k > 0 ? " " : "") << (literal < 0 ? "-" : "") << f.variables[std::abs(literal) - 1];
        }
        out << '\n';
    }
}

// La fórmula como se escribe en la pizarra: ∀x ∃y ((x ∨ y) ∧ (¬x ∨ ¬y)).
inline std::string to_text(const Qbf& f) {
    std::string text;
    for (std::size_t i = 0; i < f.variables.size(); i++) {
        text += (f.quantifiers[i] == 'E' ? "∃" : "∀") + f.variables[i] + " ";
    }
    if (f.clauses.empty()) {
        return text + "(verdadero)";
    }
    text += "(";
    for (std::size_t j = 0; j < f.clauses.size(); j++) {
        text += (j > 0 ? " ∧ (" : "(");
        for (std::size_t k = 0; k < f.clauses[j].size(); k++) {
            int literal = f.clauses[j][k];
            text += (k > 0 ? " ∨ " : "");
            text += (literal < 0 ? "¬" : "") + f.variables[std::abs(literal) - 1];
        }
        text += ")";
    }
    return text + ")";
}

// ------------------------------------------------------------
// Evaluar
// ------------------------------------------------------------

// ψ con una asignación completa: todas las cláusulas tienen algún literal verdadero.
inline bool matrix_value(const Qbf& f, const std::vector<bool>& values) {
    for (const std::vector<int>& clause : f.clauses) {
        bool satisfied = false;
        for (int literal : clause) {
            bool value = values[std::abs(literal) - 1];
            satisfied = satisfied || (literal > 0 ? value : !value);
        }
        if (!satisfied) {
            return false;
        }
    }
    return true;
}

// Lo que se mide de una evaluación.
struct EvalStats {
    long long calls = 0;   // llamadas a evaluate: el tiempo
    int max_depth = 0;     // llamadas activas a la vez, como máximo: el espacio
};

// El valor de Qi xi … Qm xm ψ cuando x1 … x(i-1) ya tienen los valores de `values`.
// Prueba xi = 0 y xi = 1 en el mismo vector: la segunda prueba reutiliza el espacio de la primera.
inline bool evaluate(const Qbf& f, std::vector<bool>& values, std::size_t i, EvalStats& stats) {
    stats.calls++;
    stats.max_depth = std::max(stats.max_depth, static_cast<int>(i) + 1);
    if (i == f.variables.size()) {
        return matrix_value(f, values);
    }
    values[i] = false;
    bool with_false = evaluate(f, values, i + 1, stats);
    if (f.quantifiers[i] == 'E' && with_false) {
        return true;   // ∃: basta un valor
    }
    if (f.quantifiers[i] == 'A' && !with_false) {
        return false;  // ∀: basta un valor que falle
    }
    values[i] = true;
    return evaluate(f, values, i + 1, stats);
}

inline bool is_true(const Qbf& f, EvalStats& stats) {
    std::vector<bool> values(f.variables.size(), false);
    return evaluate(f, values, 0, stats);
}

inline bool is_true(const Qbf& f) {
    EvalStats stats;
    return is_true(f, stats);
}

// El mismo valor por otro camino, para las pruebas: la tabla con el valor de ψ en las 2^m
// asignaciones, que se pliega de la última variable a la primera (∃ es "o", ∀ es "y").
// Guarda 2^m valores: es justo el espacio que la recursión evita.
inline bool is_true_by_table(const Qbf& f) {
    std::size_t m = f.variables.size();
    std::vector<bool> table(std::size_t{1} << m);
    std::vector<bool> values(m);
    for (std::size_t row = 0; row < table.size(); row++) {
        for (std::size_t i = 0; i < m; i++) {
            values[i] = ((row >> (m - 1 - i)) & 1) != 0;  // x1 es el bit más alto
        }
        table[row] = matrix_value(f, values);
    }
    for (std::size_t i = m; i-- > 0;) {
        std::vector<bool> folded(table.size() / 2);
        for (std::size_t row = 0; row < folded.size(); row++) {
            bool a = table[2 * row];
            bool b = table[2 * row + 1];
            folded[row] = f.quantifiers[i] == 'E' ? (a || b) : (a && b);
        }
        table = folded;
    }
    return table[0];
}

#endif
