/**
 * @file prim_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 <exception>
#include <limits>

#include "prim_algorithm.hpp"
#include <priority_queue.hpp>

template <class T>
float prim_algorithm(WGraph<T> &g,
                     size_t start_vertex,
                     std::vector<EdgeIterator<T>> &mst) noexcept(false)
{
    assert(!g.is_directed());

    float total_distance = 0.0;
    g.reset(false);
    g.set_visited(start_vertex, true);

    auto comp = [](EdgeIterator<T> const& a, EdgeIterator<T> const& b) {
        float w_a = a->item();
        float w_b = b->item();
        if (w_a != w_b) {
            return w_a < w_b;
        }
        auto u_a = a->first()->item().key();
        auto v_a = a->second()->item().key();
        if (v_a < u_a) std::swap(u_a, v_a);

        auto u_b = b->first()->item().key();
        auto v_b = b->second()->item().key();
        if (v_b < u_b) std::swap(u_b, v_b);

        if (u_a != u_b) {
            return u_a < u_b;
        }
        return v_a < v_b;
    };
    std::vector<EdgeIterator<T>> queue_buffer;
    PriorityQueue<EdgeIterator<T>> pq(queue_buffer, comp);

    auto v_start = g.vertex(start_vertex);
    for (auto e_it = g.edges_begin(v_start); e_it != g.edges_end(v_start); ++e_it) {
        pq.enqueue(e_it);
    }

    while (!pq.is_empty() && mst.size() < g.order() - 1) {
        auto e = pq.front();
        pq.dequeue();

        size_t u = e->first()->label();
        size_t v = e->second()->label();

        bool u_visited = g.is_visited(u);
        bool v_visited = g.is_visited(v);

        if (u_visited && v_visited) {
            continue;
        }

        size_t next_v = u_visited ? v : u;
        g.set_visited(next_v, true);
        mst.push_back(e);
        total_distance += e->item();

        auto v_next = g.vertex(next_v);
        for (auto e_it = g.edges_begin(v_next); e_it != g.edges_end(v_next); ++e_it) {
            size_t dest = e_it->other(next_v);
            if (!g.is_visited(dest)) {
                pq.enqueue(e_it);
            }
        }
    }

    if (mst.size() < g.order() - 1) {
        throw std::runtime_error("It is an unconnected graph.");
    }
    return total_distance;
}