/******************************************************************************
 *
 * Created by: Carla Negri Lintzmayer
 *             Maycon Sambinelli
 * To be used by our students
 *
 * CC BY-NC-ND 4.0
 * Attribution-NonCommercial-NoDerivatives 4.0 International
 * https://creativecommons.org/licenses/by-nc-nd/4.0/
 *
 *****************************************************************************/

#include "graph.h"

typedef struct {Vertex u; Vertex v; double weight;} WEdge;


WEdge wedge(Vertex u, Vertex v, double weight) {
    WEdge e = {u, v, weight};
    return e;
}

/* Função auxiliar para sort_edges()
 * Recebe edges[ini..mid] e edges[mid+1..end] já ordenados e faz com que
 * edges[ini..end] fique totalmente ordenado */
void merge_edges(WEdge *edges, int ini, int mid, int end) {
    WEdge *A = Malloc((mid-ini+1) * sizeof(*A));
    WEdge *B = Malloc((end-mid) * sizeof(*B));
    
    int i, j, k;

    for (i = ini; i <= mid; i++)
        A[i-ini] = edges[i];
    for (i = mid+1; i <= end; i++)
        B[i-mid-1] = edges[i];

    i = 0;
    j = 0;
    k = ini;
    while (i < (mid-ini+1) && j < (end-mid)) {
        if (A[i].weight < B[j].weight)
            edges[k++] = A[i++];
        else
            edges[k++] = B[j++];
    }
    while (i < (mid-ini+1))
        edges[k++] = A[i++];
    while (j < (end-mid))
        edges[k++] = B[j++];

    free(A);
    free(B);
}

/* Implementação do MergeSort para ordenar um vetor de arestas com pesos.
 * Vai ordenar o vetor edges[ini..end] (portanto o primeiro e último índices devem ser
 * elementos válidos) */
void sort_edges(WEdge *edges, int ini, int end) {
    if (ini < end) {
        int mid = (ini + end) / 2;
        sort_edges(edges, ini, mid);
        sort_edges(edges, mid+1, end);
        merge_edges(edges, ini, mid, end);
    }
}