/**
 * @file floyd_algorithm_imp.hpp
 *
 * 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.
 */
#pragma once

#include <utility>
#include <limits>
#include <stack>
#include <floyd_algorithm.hpp>

template <class T>
void floyd_algorithm(WGraph<T> const &g,
                     FMatrix &D,
                     IMatrix &I)
{
    D = g.weights();
    I.resize(g.order(), g.order(), -1);

    size_t n = g.order();

    for (size_t k = 0; k < n; ++k)
        for (size_t i = 0; i < n; ++i)
            for (size_t j = 0; j < n; ++j)
            {
                if (D[i][k] < std::numeric_limits<float>::infinity() &&
                    D[k][j] < std::numeric_limits<float>::infinity())
                {
                    float new_d = D[i][k] + D[k][j];
                    if (new_d < D[i][j])
                    {
                        D.set(i, j, new_d);
                        I.set(i, j, (int)k);
                    }
                }
            }
}

std::list<size_t>
floyd_path(size_t src, size_t dst, IMatrix const &I)
{
    std::list<size_t> path;
    path.push_back(src);

    std::stack<std::pair<size_t, size_t>> stk;
    stk.push({src, dst});

    while (!stk.empty())
    {
        size_t i = stk.top().first;
        size_t j = stk.top().second;
        stk.pop();

        int k = I[i][j];
        if (k == -1)
        {
            path.push_back(j);
        }
        else
        {
            stk.push({(size_t)k, j});
            stk.push({i, (size_t)k});
        }
    }

    return path;
}