#include "Dijkstra.h"
#include <queue>



using namespace std;

vector< vector<pair<int, int> > > Dijsktra::setup_adjList(int num) {
	vector< vector<pair<int, int> > > adjList;
	numVectors = num;
	// creating 4 vertices, so we pass in num as the # of vertices
	int i = 0;
	while (i < num)
	{
		// make a vector representing a adjacency row, and add it to the adjList
		vector<pair<int, int> > row;
		adjList.push_back(row);
		i++;
	}
	return adjList;
}
// every adjList[i] contains all the adjacent vertices of i in this format:
// <vertex of friend, edge weight>
vector< vector<pair<int, int> > > Dijsktra::fill_adjList(vector< vector<pair<int, int> > > adjList, int a, int b, int c) {

	// create our edges that will actually be in our Adj List
	// adjList[VERTEX].push_back(make_pair(EDGE, WEIGHT));
	// make_pair is used to pair the neighbor EDGE and its WEIGHT
	adjList[a].push_back(make_pair(b, c));




	// return the adjacency list, which is passed to the next fill_adjList call for the next adjList[i]
	return adjList;
}

// prints shortest paths from src to all other vertices
void Dijsktra::shortestPath(int src, vector< vector<pair<int, int> > > adjList, int num)
{
	// creates a priority queue to store vertices that are being processed
	priority_queue< pair<int, int>, vector <pair<int, int>>, greater<pair<int, int>> > priorityQueue;

	// create a vector for distances and initialize all distances as infinity (INT_MAX)
	// using num as number of verticies (number of distances we need to calculate)
	vector<int> dist(num, INT_MAX);

	// push source in priority queue and set its distance = 0
	priorityQueue.push(make_pair(0, src));
	dist[src] = 0;

	// looping till priority queue becomes empty (or all distances are not finalized)
	while (!priorityQueue.empty())
	{
		// the first vertex in the priorityQueue is the min distance vertex, pop it from the priorityQueue
		// capture int u as the label, we have to do this since the priorityQueue is sorted by distances (we'd lose the vertex label)
		int u = priorityQueue.top().second;
		priorityQueue.pop();

		// vector i is used to iterate through all adjacent vertices of a vertex
		vector< pair<int, int> >::iterator i;
		for (i = adjList[u].begin(); i != adjList[u].end(); ++i)
		{
			// capture adjacent vertex label v, and weight it's weight
			int v = (*i).first;
			int weight = (*i).second;

			// if there is a shorter path to v through u, update the distance of v
			if (dist[v] > dist[u] + weight)
			{
				dist[v] = dist[u] + weight;
				priorityQueue.push(make_pair(dist[v], v));
			}
		}
	}
	// public distVector captures dist so we do not have to pass it in to printDist()
	distVector = dist;

}
void Dijsktra::printDist() {

	// print shortest distances stored in dist[]
	char alpha[10] = { 'A','B','C','D','E','F','G','H','I','J' }; // used to coorilate vertex index to Node labels
	cout << "  Vertex    \t Distance from Source \t\n";
	for (int i = 0; i < 4; ++i)
		cout << "    " << alpha[i] << " \t\t\t " << distVector[i] << "\t" << "\n";
}