// Compara dos maneras de decidir si una gramática en forma normal de Chomsky genera una cadena:
// probar derivaciones por la izquierda con backtracking, y CYK.
//   search_cost ARCHIVO.cfg CADENA...
// Cuenta trabajo, no tiempo: pasos de derivación probados contra comprobaciones de CYK.
#include <cstddef>
#include <iomanip>
#include <iostream>
#include <stdexcept>
#include <string>

#include "cfg.h"
#include "chomsky.h"

int main(int argc, char** argv) {
    if (argc < 3) {
        std::cerr << "uso: search_cost ARCHIVO.cfg CADENA...\n";
        return 2;
    }
    try {
        std::string path = argv[1];
        Cfg g = (path == "-") ? read_cfg(std::cin) : load_cfg(path);
        std::cout << "  n   respuesta    pasos probados   comprobaciones de CYK   cadena\n";
        for (int i = 2; i < argc; i++) {
            std::string w = argv[i];
            CykTable table = cyk(g, w);
            // En forma normal de Chomsky una derivación de w tiene 2|w| − 1 pasos: ese tope no corta nada.
            // La búsqueda para en la primera derivación que encuentra. Si la cadena no se genera, las agota todas.
            DerivationSearch search = leftmost_derivations(g, w, 2 * w.size() + 1, 1);
            bool generated = cyk_accepts(g, table);
            if (generated != !search.found.empty()) {
                throw std::runtime_error("las dos búsquedas no coinciden");
            }
            std::cout << std::setw(3) << w.size() << "   " << std::left << std::setw(13)
                      << (generated ? "genera" : "no genera") << std::right << std::setw(14) << search.explored
                      << std::setw(24) << table.checks << "   " << (w.empty() ? "ε" : w) << '\n';
        }
    } catch (const std::exception& error) {
        std::cerr << "error: " << error.what() << '\n';
        return 1;
    }
}
