#include <stdio.h>
#include <stdlib.h>
#include <assert.h>


#include "Dijkstra.h"
#include "PQ.h"

void clearPredNode (PredNode **AdjList, Vertex v) {
    // If we havent set a pred for that node yet
    if (AdjList[v] == NULL) {
        return;
    }

    PredNode *curr = AdjList[v];
    PredNode *temp = NULL;

    // If there is only 1 node in the linked list
    if (curr->next == NULL) {
        free (curr);
    } else {
        // Freeing the linked list
        temp = curr->next;
        while (temp != NULL) {
            free (curr);
            curr = temp;
            temp = temp->next;
        }
    }
}

void addPredNode (PredNode **AdjList, Vertex v, Vertex w) {
    // v = adj->v, w = edge.key
    PredNode *new = malloc (sizeof (AdjList));
    new->v = w;
    new->next = NULL;
    PredNode *curr = AdjList[v];
    // If this is the first node
    if (curr == NULL) {
        curr = new;
    } else {
        // Check if it is already in the list
        if (curr->v == w) {
            return;
        }
        while (curr->next != NULL) {
            curr = curr->next;
            if (curr->v == w) {
                return;
            }
        }
        curr->next = new;
    }
}

ShortestPaths dijkstra (Graph g, Vertex src) {
    int max = __INT_MAX__;

    // Initializing shortestpaths structure sp
    ShortestPaths sp;
    sp.numNodes = GraphNumVertices (g);
    sp.src = src;
    // Allocating memory for dist and pred
    sp.dist = malloc (sp.numNodes * sizeof (sp.dist));
    sp.pred = malloc (sp.numNodes * sizeof (PredNode *));


    // Initializing values for pred and dist
    for (int i = 0; i < sp.numNodes; i++) {
        sp.dist[i] = max;
        sp.pred[i] = NULL;
    }

    // Creating empty queue
    // Note that key is vertex and value is dist
    PQ q = PQNew ();
    // Setting dist[src]
    sp.dist[sp.src] = 0;
    // Initializing queue
    for (int j = 0; j < sp.numNodes; j++) {
        ItemPQ newEdge;
        newEdge.key = j;
        newEdge.value = sp.dist[j];
        PQAdd(q, newEdge);
    }

    // While the queue is not empty
    while (PQIsEmpty(q) == false) {
        // Dequeue edge
        ItemPQ edge = PQDequeue (q);
        AdjList adj = GraphOutIncident (g, edge.key);
        // While there are still adjacent nodes
        while (adj != NULL) {
            // Distance holds the distance from src to w
            // If we have not visited w
                // Relax along edge
                int distance = sp.dist[edge.key] + adj->weight;
                if (distance == sp.dist[adj->v]) {
                    addPredNode (sp.pred, adj->v, edge.key);
                }
                else if (distance < sp.dist[adj->v]) {
                    // Updating dist array with our new shortest distance
                    sp.dist[adj->v] = sp.dist[edge.key] + adj->weight;
                    // Update our pred array with new pred after clearing node
                    clearPredNode (sp.pred, adj->v);
                    // Update pred array
                    addPredNode (sp.pred, adj->v, edge.key);
                    // Update the PQ
                    ItemPQ updatePQ;
                    updatePQ.key = adj->v;
                    updatePQ.value = distance;
                    PQUpdate (q, updatePQ);
                }
            adj = adj->next;
        }
    }
    PQFree (q);
    return sp;

}






void showShortestPaths(ShortestPaths sps) {
    return;

}
void freeShortestPaths(ShortestPaths sps) {
    return;

}