#include "Dijkstra.h"

#include "PQ.h"
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

/*
ShortestPaths {
        int numNodes;    // The number of vertices in the graph

        Vertex src;      // The source vertex

        int *dist;       // An  array  of distances from the source vertex -
                         // one for each vertex (the distance  from  src  to
                         // itself is 0)
                         // dist[v] contains the distance from src to v

        PredNode **pred; // An  array  of  predecessor  lists - one for each
                         // vertex
                         // pred[v] contains the predecessor list for vertex
                         // v
}

PredNode {
        Vertex v;
        struct PredNode *next;
};
*/

static void free_pred_list(PredNode *head) {
    for (PredNode *i = head; i != NULL;) {
        PredNode *tmp = i->next;
        free(i);
        i = tmp;
    }
}

static PredNode *add_pred_back(PredNode *head, const Vertex v) {
    PredNode *ret = calloc(1, sizeof(PredNode));
    ret->v = v;
    // Empty Case.
    if (head == NULL) {
        return ret;
    }
    PredNode *last = head;
    // Find the last element in the linked list.
    for (PredNode *i = head->next; i != NULL; i = i->next) {
        last = i;
    }
    last->next = ret;
    return head;
}

// Finds the shortest path from src to all other vertices and stores this
// information in a ShortestPaths struct.
// However, if there are multiple shortest paths of the same weight, also store
// such paths as preds.
ShortestPaths dijkstra(Graph g, Vertex src) {

    // Initialise return struct ret and allocate appropriate memory.
    ShortestPaths ret;
    ret.src = src;
    const int num_nodes = GraphNumVertices(g);
    ret.numNodes = num_nodes;
    ret.dist = calloc((unsigned int)num_nodes, sizeof(int));
    ret.pred = calloc((unsigned int)num_nodes, sizeof(PredNode));

    // Set all distances as INT_MAX to represent infinity, but the src vertex
    // as 0 to ensure it is chosen first.
    for (int i = 0; i < num_nodes; ++i) {
        ret.dist[i] = INT_MAX;
    }
    ret.dist[src] = 0;

    // Initialise queue, insert itself in queue and initialise its distance
    // as 0.
    PQ queue = PQNew();
    PQInsert(queue, src, ret.dist[src]);

    // Perform Dijkstra's algorithm by looping through the queue until empty.
    while (!PQIsEmpty(queue)) {
        // Dequeue the vertex with the lowest weight.
        const Vertex vertex = PQDequeue(queue);

        // Loop through all adjacent vertices for the vertex.
        AdjList adjacents = GraphOutIncident(g, vertex);
        for (AdjList i = adjacents; i != NULL; i = i->next) {
            const int v = i->v;
            const int w = i->weight;
            const int path = ret.dist[vertex] + w;

            // Inefficient path, continue.
            if (ret.dist[v] < path) {
                continue;
            }

            // Better path than previously discovered. Free the current pred
            // list and update distance.
            if (ret.dist[v] > path) {
                ret.dist[v] = path;
                PQInsert(queue, v, ret.dist[v]);
                free_pred_list(ret.pred[v]);
                ret.pred[v] = NULL;
            }

            // Update pred list.
            ret.pred[v] = add_pred_back(ret.pred[v], vertex);
        }
    }

    // After performing the algorithm, we must set all INT_MAX distances back
    // to zero to conform to the spec.
    for (int i = 0; i < num_nodes; ++i) {
        if (ret.dist[i] == INT_MAX) {
            ret.dist[i] = 0;
        }
    }

    return ret;
}

// Prints out the ShortestPaths structure.
// Does not need to comply with any requirements.
void showShortestPaths(ShortestPaths sps) {
    printf("Shortest path\n");
    printf("\tNumNodes: %d\n", sps.numNodes);
    printf("\tsrc: %d\n", sps.src);
    printf("\tdist\n");
    for (int i = 0; i < sps.numNodes; ++i) {
        printf("\t\t%d: %d\n", i, sps.dist[i]);
    }
    printf("\tpred\n");
    for (int i = 0; i < sps.numNodes; ++i) {
        printf("\t\t%d\n", i);
        for (PredNode *j = sps.pred[i]; j != NULL; j = j->next) {
            printf("\t\t\t%d\n", j->v);
        }
    }
}

// Frees all memory associated with a ShortestPaths structure.
void freeShortestPaths(ShortestPaths sps) {
    for (int i = 0; i < sps.numNodes; ++i) {
        for (PredNode *j = sps.pred[i]; j != NULL;) {
            PredNode *next = j->next;
            free(j);
            j = next;
        }
    }
    free(sps.pred);
    free(sps.dist);
}