//**************************************************************************
//
//      CSE 465 Programming Assignment #3
//      By Anirudh Modi (avm105@psu.edu) on 4/14/98-Tue
//
//**************************************************************************
//	Running time of algorithm -> O[(E+V)log V]
//**************************************************************************
// 	Have implemented the following extra options ->
//		1. Hashing procedure for Vertex Names (hash.cc)
//		2. Decrease_Key operation takes O(log N) time (priqueue.cc)
//		3. There is no memory leak
//**************************************************************************
//	Also implemented :
//		1. General code so that any "source" can be specified
//		2. Prints the Heap status at every stage if desired
//		3. Undirectional graphs can also be read
//**************************************************************************
#include <iostream.h>
#include <fstream.h>
#include <string.h>
#include "vertex.h"
#include "adjlist.h"
#include "hash.h"
#include "dijkstra.h"
//**************************************************************************
#define SIZE 25000		// Max size of Hash Table and Adj List
#define BUF_SIZE 1000		// Max Size for Reading every line of Input
//**************************************************************************
#define PRINT_DIJKSTRA 1	// Flag to print the list of shortest edges
#define PRINT_VERTEX_LIST 0	// Flag to print the vertex list at start
#define PRINT_HEAP_STATUS 0	// Flag to print heap after each step
#define ASK_FOR_SOURCE 0	// Flag to ask for source vertex (else 
				// defaults to first vertex read)
#define IS_UNDIRECTIONAL 0	// Flag for undirectional graph
//**************************************************************************
void Read_Graph (char *filename,AdjList& G,HashTable& T,int is_undirectional);
int  Get_Source(HashTable& T);
void Read_Dest (int source, Vertex *V, AdjList& G, HashTable& T);
//**************************************************************************
int main (int argc, char *argv[])
{
if (argc != 2) 
	{
	 cerr << "Syntax: " << argv[0] << " <graph-file>" << endl;
	 exit(-1);
	}

HashTable T(SIZE);	// Hash Table for Vertices
AdjList   G(SIZE);	// Graph as an Adjency List representation

if (IS_UNDIRECTIONAL) 
	 cout << "Reading UNDIRECTIONAL Graph..." << endl;
else
	 cout << "Reading DIRECTIONAL Graph (digraph)..." << endl;

Read_Graph(argv[1],G,T,IS_UNDIRECTIONAL);		// Read the Graph
int vert = G.no_of_verts();
int edges = G.no_of_edges();
if (IS_UNDIRECTIONAL) edges /= 2;

if (vert == 0 || edges == 0)
	{
	 cerr << "No vertices and/or edges specified..." << endl;
	 cerr << "Invalid input file !!" << endl;
	 cerr << "Exiting....." << endl;
	 exit(-1);
	}

cout << "Number of vertices = " << vert << endl;
cout << "Number of edges = " << edges << endl << endl;

int source;

if (ASK_FOR_SOURCE)
	source = Get_Source(T);
else
	source = 1;

Vertex *V = new Vertex[vert];	// List of edges forming shortest paths

dijkstra(source,G,V,T,PRINT_HEAP_STATUS); // Call Dijkstra's routine

if (PRINT_VERTEX_LIST)
	{
	 cout << '\t' << "Vertex list" << endl;
	 cout << '\t' << "-----------" << endl;
	 for (int i=1;i<=vert;i++) 
	 	cout << '\t' << i << '\t' << T.name_of(i) << endl;
	 cout << endl;
	 cout << '\t' << "Source: " << T.name_of(source) << endl << endl;
	}

if (PRINT_DIJKSTRA)
	Print_Dijkstra(source,V,T);

Read_Dest(source,V,G,T);

delete [] V;

cout << endl << endl;
cout << "EOF character pressed ! Exiting.............." << endl;
}
//**************************************************************************
void Read_Graph (char *filename,AdjList& G,HashTable& T,int is_undirectional)
{
ifstream inp(filename);
char buf[BUF_SIZE];

if (!inp)
	{
	 cerr << "Invalid filename \"" << filename << "\" !!" << endl;
	 cerr << "Exiting........." << endl;
	 exit(-1);
	}

while (inp.getline(buf,BUF_SIZE) && inp.good() && !inp.eof())
	{
	 char *vertname2 = strpbrk(buf, " \t");
	 *vertname2++ = '\0';
	 char *buf2 = strpbrk(vertname2, " \t");
	 *buf2++ = '\0';
	 int weight = atoi(buf2);
	 int ptA = T.id_of(buf);
	 int ptB = T.id_of(vertname2);
	 G.add_Edge(ptA,ptB,weight);
	 if (is_undirectional)
	 	G.add_Edge(ptB,ptA,weight);
	}
G.setVerts(T.nodes_of());

return;
}
//**************************************************************************
int Get_Source(HashTable& T)
{
int source;
char buf[BUF_SIZE];

cout << "Source: ";
while (cin.getline(buf,BUF_SIZE) && cin.good() && !cin.eof())
	{
	 source = T.find(buf);
	 if (source) break;
	 cout 	<< endl << '\t' << "Unkown vertex \"" << buf 
		 	<< "\" !! Try again !" << endl << endl;
	 cout << "Source: ";
	}
cout << endl;
return source;
}
//**************************************************************************
void Read_Dest (int source, Vertex *V, AdjList& G, HashTable& T)
{
char buf[BUF_SIZE];

cout << "Destination: ";
while (cin.getline(buf,BUF_SIZE) && cin.good() && !cin.eof())
	{
	 int dest = T.find(buf);
	 if (dest)
	 	 Print_Path(source,dest,V,G,T);
	 else if (strlen(buf))
		 cout 	<< endl << '\t' << "Unkown vertex \"" << buf 
		 	<< "\" !! Try again !" << endl << endl;
	 cout << "Destination: ";
	}
}
//**************************************************************************