#include<iostream> //File input/ouput include files
#include<fstream>
#include<iomanip>
#include<set>
#include<list>
 
 
 
using namespace std; //C++ standard libraries
const int NUMARCS = 16; //Need to use const ints for array declaration
const int NUMNODES = 8;
int i;
int main() //Main function
{
	ifstream readin("fstarin.txt", ios::in); //open input file
	ofstream readout("hw5out.txt", ios::out); //open output file
	if (!readin) {
		cerr << "File could not be opened" << endl; //Make sure file opens
		exit(1);
	}
	//declare arrays to be used
	int tail[NUMARCS+1], head[NUMARCS+1], cost[NUMARCS+1], cap[NUMARCS+1];
	//Initilize point[i] = 0... this will be a useful condition later
	int point[NUMNODES+2] = {0};
	int i = 1;
	/*This is a fairly concise loop to read the input file and assign
	the input stream to the arrays created. This same loop outputs the
	arrays as well. Note that setw() is for formatting output*/
	while (readin >> tail[i] >> head[i] >> cost[i] >> cap[i])
	i++;
	readout << setiosflags(ios::left) << setw(7) << "Arc #" << setw(7) << "Tail"<< setw(7)<< "Head"	<< setw(7)<< "Cost"	<< "Capacity" << endl;
	for (i = 1; i <= NUMARCS; i++) 
	{
		readout << setiosflags(ios::left) << setw(7) << i << setw(7) << tail[i]
		<< setw(7) << head[i]
		<< setw(7) << cost[i]
		<< cap[i] << endl;
	}
	/*Now I use a loop to assign the point vector to the first arc in the
	forward star having the same tail node. Note that nodes with no
	emanating arcs will still have point[i] = 0*/
	for (i = 1; i<= NUMARCS+1; i++) 
	{
		if (point[tail[i]] == 0) 
		{
			point[tail[i]] = i;
		}
	}
	//Now I clean up those nodes with no emanating arcs
	for (i = 1; i<=NUMNODES; i++) 
	{
		if (point[i] == 0) 
			{
				point[i] = point[i+1];
			}
	}
	/*Lastly, we can set the pointer for the n+1 node, we can do it this
	simply wlog becasue this condition will hold for all forward star
	representations*/
	point[NUMNODES+1] = NUMARCS +1;
 
	//Output the pointer vector
	readout << endl;
	readout << "The point vector is: [";
	for (i = 1; i <= NUMNODES+1; i++) 
	{
		readout << point[i] << " ";
	}
	readout << "]";
	readout << endl;
	readout << endl;
	/*This is the initialization phase of Dijkstra's: we need to construct the
	temporary and permenently labeled node sets. The Perm set is initially empty,
	the temporary initially contains all nodes. We then declare and initialize
	the label and predecessor vector*/
	//There are containers called sets with predefined operations that are useful
	//in this context
	set<int> Perm;
	set<int> Temp;
	set<int>::iterator it;
	for (i = 1; i <= NUMNODES; i++) 
	{
 
		Temp.insert(i);
	}
	int label[NUMNODES+1], pred[NUMNODES+1], lownode, lowlabel;
	for (i = 1; i <=NUMNODES; i++) 
	{ 
		label[i] = 1000; 
	}
	label[1] = 0;
	pred[1] = 0;
	/*We enter the main loop, checking that not all nodes are permanently labeled*/
	while (Perm.size() < NUMNODES) 
	{
		lownode = 0;
		lowlabel = 100000;
		/*The first loop now checks for the lowest temporary distance label. This is
		an easy, loop-based check*/
		for (it = Temp.begin(); it != Temp.end() ; it++) 
		{
			if (label[*it] < lowlabel) 
			{
				lowlabel = label[*it];
				lownode = *it;
			}
		}
		//Remove the node from the temp set, add it to the permanent set
		Temp.erase(lownode);
		Perm.insert (Perm.end(),lownode);
		/*Now, using the forward star, identify those arcs emanating from our newly
		permanently labeled noede and update distance labels and pred vector as
		appropriate*/
		for (i= point[lownode]; i < point[lownode+1]; i++) 
		{
			if (label[head[i]] > label[lownode] + cost[i]) 
			{
				label[head[i]] = label[lownode] + cost[i];
				pred[head[i]] = lownode;
			}
		}
	}
		//Output the distance labels and predecessor vector
		readout << "The optimal distance labels are:" << "[";
		for (i = 1; i <=NUMNODES; i++) 
		{
			readout << " " << label[i];
		}
	readout << "]" << endl << endl;
	readout << "The predecessor vector is:" << "[";
	for (i = 1; i <=NUMNODES; i++) 
	{
		readout << " " << pred[i];
	}
	readout << "]" << endl << endl;
	/*Now we can identify the shortest path from 1 to all. Use the list container
	as lists do not automatically sort the contents*/
	list<int> path;
	list<int>::iterator iter;
	for (i = 2; i <=NUMNODES; i++) 
	{
		readout << "The shortest path from node 1 to node " << i << " is: 1";
		int current = i;
		path.erase(path.begin(), path.end());
		while (pred[current] != 0 ) 
		{
			path.insert(path.begin(), current);
			current = pred[current];
		}
		for (iter = path.begin(); iter !=path.end(); iter++) 
		{
			readout << "-" << *iter;
		}
		readout << endl;
	}
	return 0;
}