/**
 * @file dijkstra_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 <cassert>
#include <tuple>
#include <functional>
#include <limits>
#include <queue>

#include <dijkstra_algorithm.hpp>

template <class T>
void dijkstra_algorithm(WGraph<T> &g,
                        size_t source,
                        std::vector<size_t> &predecessors,
                        std::vector<float> &distances)
{
    assert(source < g.order());

    using Tuple = std::tuple<float, size_t, size_t>;

    g.reset(false);

    size_t n = g.order();
    predecessors.resize(n);
    distances.resize(n);
    for (size_t i = 0; i < n; ++i)
    {
        predecessors[i] = i;
        distances[i] = std::numeric_limits<float>::infinity();
    }
    distances[source] = 0.0f;

    std::priority_queue<Tuple, std::vector<Tuple>, std::greater<Tuple>> pq;
    pq.push({0.0f, source, source});

    while (!pq.empty())
    {
        float d    = std::get<0>(pq.top());
        size_t from = std::get<1>(pq.top());
        size_t u    = std::get<2>(pq.top());
        pq.pop();

        if (g.is_visited(u))
            continue;
        g.set_visited(u, true);
        predecessors[u] = from;
        distances[u] = d;

        auto u_it = g.vertex(u);
        for (auto e_it = g.edges_begin(u_it); e_it != g.edges_end(u_it); ++e_it)
        {
            size_t v = e_it->second()->label();
            if (!g.is_visited(v))
            {
                float new_d = d + e_it->item();
                if (new_d <= distances[v])
                {
                    distances[v] = new_d;
                    pq.push({new_d, u, v});
                }
            }
        }
    }
}

inline std::list<size_t>
dijkstra_path(size_t src, size_t dst,
              std::vector<size_t> const &predecessors)
{
    assert(src < predecessors.size());
    assert(dst < predecessors.size());
    assert(predecessors[src] == src);

    std::list<size_t> path;

    if (predecessors[dst] == dst && dst != src)
        return path;

    size_t current = dst;
    while (current != src)
    {
        path.push_front(current);
        current = predecessors[current];
    }
    path.push_front(src);

    return path;
}