/**
 * @file alphabet_soup_solver.cpp
 *
 * CopyRight F. J. Madrid-Cuevas <fjmadrid@uco.es>
 *
 * Sólo se permite el uso de este código en la docencia de las asignaturas sobre
 * Estructuras de Datos de la Universidad de Córdoba.
 *
 * Está prohibido su uso para cualquier otro objetivo.
 */

#include <trie.hpp>
#include "alphabet_soup_solver.hpp"

/**
 * @brief scan a cell looking for the next letter of a word.
 * @param row and
 * @param col are the current cell coordinates.
 * @param dy and
 * @param dx are direction vector to follow the next letter.
 * @param soup is the alphabet soup where looking for.
 * @param trie is the current subtrie.
 * @param scan_result save the current chain. Is a pair of <word, cells_coordinates [row,col]>
 *
 */
void scan_cell(int row, int col, int dy, int dx, AlphabetSoup const &soup,
               Trie &trie, ScanResult &scan_result)
{
    // Si el prefijo acumulado en el trie ES una clave, hemos encontrado una palabra completa.
    // Guardamos la palabra y salimos: la pila de coordenadas se rellena al volver de la recursión.
    if (trie.is_key()) {
        scan_result.first = trie.prefix();
        return;
    }

    // Comprobamos límites DESPUÉS de step 1: step 1 no accede a la celda,
    // así que se puede detectar la palabra aunque la siguiente celda esté fuera del tablero.
    if (row < 0 || row >= soup.rows() || col < 0 || col >= soup.cols())
        return;

    // Obtenemos el subárbol correspondiente a consumir la letra de la celda actual.
    // Si no existe esa rama en el trie, esta celda no puede pertenecer a ninguna palabra buscada.
    Trie sub_trie = trie.child(soup.cell(row, col));
    if (sub_trie.is_empty())
        return;

    if (dx == 0 && dy == 0) {
        // Primera letra de la palabra: probamos las 8 direcciones posibles del vecindario 3x3.
        // En cuanto encontremos la palabra en una dirección, apilamos esta celda y salimos.
        for (int ndy = -1; ndy <= 1; ++ndy) {
            for (int ndx = -1; ndx <= 1; ++ndx) {
                if (ndy == 0 && ndx == 0) continue; // descartamos la celda actual (sin movimiento)
                scan_cell(row + ndy, col + ndx, ndy, ndx, soup, sub_trie, scan_result);
                if (scan_result.first != "") {
                    // Palabra encontrada: apilamos las coordenadas de esta celda (primera letra)
                    scan_result.second.push({row, col});
                    return;
                }
            }
        }
    } else {
        // Letra intermedia: seguimos en la misma dirección (dy, dx).
        // Si la recursión confirma que la palabra está completa, apilamos esta celda.
        scan_cell(row + dy, col + dx, dy, dx, soup, sub_trie, scan_result);
        if (scan_result.first != "")
            scan_result.second.push({row, col});
    }
}

std::vector<ScanResult>
alphabet_soup_solver(AlphabetSoup &soup, std::vector<std::string> const &words)
{
    std::vector<ScanResult> results;
    Trie trie;

    // Generate a trie with the words to be found as keys.
    for (size_t i = 0; i < words.size(); ++i)
        trie.insert(words[i]);

    // We scan all the soup to find a first letter of any key.
    for (int row = 0; row < soup.rows(); ++row)
    {
        for (int col = 0; col < soup.cols(); ++col)
        {
            auto scan_result = std::make_pair(std::string(""),
                                              std::stack<std::pair<int, int>>());
            // Scan from this cell. This is the first letter so dx==dy==0.
            scan_cell(row, col, 0, 0, soup, trie, scan_result);
            if (scan_result.first != "")
                // A word was found so save it into the results.
                results.push_back(scan_result);
        }
    }
    return results;
}