/**
 * @file kruskal_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 <memory>
#include <algorithm>

#include "disjointsets.hpp"
#include "kruskal_algorithm.hpp"

template <class T>
float kruskal_algorithm(WGraph<T> &g, std::vector<EdgeIterator<T>> &mst) noexcept(false)
{
    assert(!g.is_directed());
    float total_distance = 0.0;

    DisjointSets sets(g.order());

    // Generate a set for each node.
    for (size_t i = 0; i < g.order(); ++i)
        sets.make_set(i);

    std::vector<EdgeIterator<T>> edges;
    for (auto v_it = g.vertices_begin(); v_it != g.vertices_end(); ++v_it) {
        for (auto e_it = g.edges_begin(v_it); e_it != g.edges_end(v_it); ++e_it) {
            if (e_it->first()->label() < e_it->second()->label()) {
                edges.push_back(e_it);
            }
        }
    }

    // Sort the edges using the comparison function.
    auto compare = [](const EdgeIterator<T> &a,
                      const EdgeIterator<T> &b) -> bool
    {
        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::sort(std::begin(edges), std::end(edges), compare);

    mst.resize(0);
    for (const auto& e : edges) {
        size_t u = e->first()->label();
        size_t v = e->second()->label();
        if (sets.find(u) != sets.find(v)) {
            sets.joint(u, v);
            mst.push_back(e);
            total_distance += e->item();
            if (mst.size() == g.order() - 1) {
                break;
            }
        }
    }

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

    assert(mst.size() == g.order() - 1);
    return total_distance;
}