// Dijkstra's Algorithm in C using a heap with the best S vertex for
// every T vertex.
// See CSE 2320 Notes 14

#include <iostream>
#include <stdlib.h>
#include "minHeap.h"

using namespace std;

// For getrusage()
#include <sys/time.h>
#include <sys/resource.h>

// Basic Definitions

#define oo (1000000000)

// Declarations

int numVertices,numEdges;
struct edge {
  int tail,head,weight;
  int next;  // subscript of next edge with same tail 
};
typedef struct edge edgeType;
edgeType *edgeTab;
int *firstEdge;  // Table indicating first edge for a tail

float CPUtime()
{
struct rusage rusage;

getrusage(RUSAGE_SELF,&rusage);
return rusage.ru_utime.tv_sec+rusage.ru_utime.tv_usec/1000000.0
       + rusage.ru_stime.tv_sec+rusage.ru_stime.tv_usec/1000000.0;
}

void read_input_file()
{
// Reads a file with a weighted, directed graph and
// stores as unordered adjacency lists.
int tail,head,weight,i,j,workingEdges;

// read number of nodes and edges
cin >> numVertices >> numEdges;

firstEdge=(int*) malloc(numVertices*sizeof(int));
edgeTab=(edgeType*) malloc(numEdges*sizeof(edgeType));
if (!firstEdge || !edgeTab)
{
  cout << "edgeTab malloc failed " << __LINE__ << "\n";
  exit(0);
}

// Initially, all adjacency lists are empty
for (i=0;i<numVertices;i++)
  firstEdge[i]=(-1);

// read edges, each with a weight
workingEdges=0;
for (i=0; i<numEdges; i++)
{
  cin >> tail >> head >> weight;
  // Test for illegal edge.
  if (tail<0 || tail>numVertices-1 || head<0
  || head>numVertices-1 || weight<=0)
  {
    cout << "Invalid input " << tail << head << weight << " at " <<
      __LINE__ << "\n";
    exit(0);
  }
  // Save input edge and insert in adjacency list
  edgeTab[workingEdges].tail=tail;
  edgeTab[workingEdges].head=head;
  edgeTab[workingEdges].weight=weight;
  edgeTab[workingEdges].next=firstEdge[tail];
  firstEdge[tail]=workingEdges;
  workingEdges++;
}
}

void dijkstra()
{
typedef enum {s,t} stType;

int i,j,SPedgeCount=0;
stType *flag;
heapEntryType smallest,changing;
int *priority,*bestSneighbor;

flag=(stType*) malloc(numVertices*sizeof(stType));
priority=(int*) malloc(numVertices*sizeof(int));
bestSneighbor=(int*) malloc(numVertices*sizeof(int));

if (!flag || ! priority || !bestSneighbor)
{
  cout << "malloc failed " << __LINE__ << "\n";
  exit(0);
}
// Vertex 0 starts in S.  Other vertices start in T.
flag[0]=s;
for (i=1;i<numVertices;i++)
  flag[i]=t;

// Some T vertices might not have an edge from vertex 0.
priority[0]=0;  // Dummy entry for vertex 0
for (i=1;i<numVertices;i++)
  priority[i]=oo;

// Initialize T-heap with edges from vertex 0.
for (i=firstEdge[0];
     i!=(-1);
     i=edgeTab[i].next)
{
  priority[edgeTab[i].head]=edgeTab[i].weight;
  bestSneighbor[edgeTab[i].head]=0;
}

// Constructor does BuildMinHeap
minHeap heap(numVertices,priority,numVertices);
free(priority);

// Remove dummy entry from heap
smallest=heap.extractMin();
if (smallest.id!=0)
{
  cout << "Heap problem " << __LINE__ << "\n";
  exit(0);
}

// Each iteration finds another shortest-path tree edge
for (SPedgeCount=0;SPedgeCount<numVertices-1;SPedgeCount++)
{
  // Get minimum weight edge from S to T.
  smallest=heap.extractMin();
  if (smallest.priority==oo) // no edges remain that bridge S & T
    break;

  cout << "Include edge from " << bestSneighbor[smallest.id] <<
       " to " << smallest.id << " to give distance " << 
       smallest.priority << "\n";
  flag[smallest.id]=s;

  // Scan adjacency list looking for improvements
  for (j=firstEdge[smallest.id];
       j!=(-1);
       j=edgeTab[j].next)
    if (flag[edgeTab[j].head]==t
    && smallest.priority+edgeTab[j].weight
       <heap.getPriority(edgeTab[j].head))
    {
      changing.id=edgeTab[j].head;
      changing.priority=smallest.priority+edgeTab[j].weight;
      heap.changePriority(changing);
      bestSneighbor[edgeTab[j].head]=smallest.id;
    }
}
if (SPedgeCount<numVertices-1)
  for (i=1;i<numVertices;i++)
    if (flag[i]==t)
      cout << "Vertex " << i << " is not reachable from vertex 0\n";
free(flag);
free(bestSneighbor);
}

int main ()
{
int i,j;
float startCPU,stopCPU;

read_input_file();
startCPU=CPUtime();
dijkstra();
stopCPU=CPUtime();
cout << "Heap-based Dijkstra's time " << stopCPU-startCPU << "\n";
free(edgeTab);
free(firstEdge);
}