/*
 * Name        : shortestpaths
 * Author      : Christopher Tan
 * Version     : 1.0
 * Date        : 12/1/19
 * Description : Implementation of Floyd's algorithm.
 * Pledge      : I pledge my honor that I have abided by the Stevens Honor System.
 */

#include <iostream>
#include <sstream>
#include <iomanip>
#include <string>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iterator>

using namespace std;
int vertices = 0;
const long INF = numeric_limits<long>::max();
long** matrix;
long** mainMatrix;
long** pathMatrix;
long** interMatrix;


int len(int num) {
	int digits = 1;
    while(num >= 10){
       	digits++;
    	num /= 10;
    }
    return digits;
}


vector<char> backtrack(int x, int y){
	vector<char> ans;
	char c1, c2;
	if(interMatrix[x][y] == INF) {
		c1 = 'A' + x;
		c2 = 'A' + y;
		ans.push_back(c2);
		if(c1 != c2){
			ans.push_back(c1);
		}
		return ans;
	}else{
		ans = backtrack(x,interMatrix[x][y]);
		vector<char> v2 = backtrack(interMatrix[x][y],y);
		v2.insert(v2.end(),ans.begin()+1,ans.end());
		return v2;
	}
}

void display_table(long** const matrix, const string &label, const bool use_letters = false) {
	cout << label << endl;
	long max_val = 0;
	for (int i = 0; i < vertices; i++) {
		for (int j = 0; j < vertices; j++) {
			long cell = matrix[i][j];
			if (cell < INF && cell > max_val) {
				max_val = matrix[i][j];
			}
		}
	}

	int max_cell_width = use_letters ? len(max_val) : len(max(static_cast<long>(vertices), max_val));
	cout << ' ';
	for (int j = 0; j < vertices; j++) {
		cout << setw(max_cell_width + 1) << static_cast<char>(j + 'A');
	}
	cout << endl;
	for (int i = 0; i < vertices; i++) {
		cout << static_cast<char>(i + 'A');
		for (int j = 0; j < vertices; j++) {
			cout << " " << setw(max_cell_width);
			if (matrix[i][j] == INF) {
			cout << "-";
		} else if (use_letters) {
			cout << static_cast<char>(matrix[i][j] + 'A');
		} else {
			cout << matrix[i][j];
		}
	}
	cout << endl;
 }
 cout << endl;
}

void floyds_alg(long** adj_mat) {
	pathMatrix = new long*[vertices];
			 for(int x = 0; x < vertices; x++) {
				pathMatrix[x] = new long[vertices];
				for(int y = 0; y<vertices; ++y){
					pathMatrix[x][y] = adj_mat[x][y];
				}
			}
 	for(int k = 0; k < vertices; k++) {
 	    for(int i = 0; i < vertices; i++) {
 	        for(int j = 0; j < vertices; j++) {
 	            if(pathMatrix[i][k] != INF && pathMatrix[k][j] != INF && pathMatrix[i][j] > (pathMatrix[i][k] + pathMatrix[k][j])) {
	 	            	pathMatrix[i][j] = pathMatrix[i][k] + pathMatrix[k][j];
	 	            	interMatrix[i][j] = k;
 	            }
 	            if(i == j){
 	            	adj_mat[i][j] = 0;
 	            	pathMatrix[i][j] = 0;
 	            	interMatrix[i][j] = INF;
 	            }
 	        }
 	    }
 	}

	display_table(adj_mat, "Distance matrix:" , false);
 	display_table(pathMatrix, "Path lengths:", false);
 	display_table(interMatrix, "Intermediate vertices:", true);
}

void addToMatrix(char v1, char v2, int edgeWeight){
	//simple function that adds the elements to the matrix
	matrix[v1-'A'][v2-'A'] = edgeWeight;
}

int main(int argc, char *argv[]) {
	if (argc != 2) {
		cerr << "Usage: ./shortestpaths <filename>" << endl;
		return 1;
	}

	ifstream input(argv[1]);
	if (!input) {
		cerr << "Error: Cannot open file '" << argv[1] << "'." << endl;
		return 1;
	}
	string line;
	int lineNumber = 0;
	while (getline(input, line)) {
		istringstream iss;
		iss.str(line);
		if (lineNumber == 0) {
			if (!(iss >> vertices)) {
				cerr << "Error: Invalid number of vertices '" << line << "' on line 1." << endl;
				return 1;
			}
			if (vertices < 1 || vertices > 26) {
				cerr << "Error: Invalid number of vertices '" << line << "' on line 1." << endl;
				return 1;
			}
			lineNumber++;
			matrix = new long*[vertices];
			for(int i = 0; i < vertices; ++i){
				matrix[i] = new long[vertices];
				fill_n(matrix[i] , vertices , INF);
			}
			mainMatrix = new long*[vertices];
			for(int x = 0; x < vertices; x++) {
				mainMatrix[x] = new long[vertices];
				fill_n(mainMatrix[x],vertices,INF);
			}

			interMatrix = new long*[vertices];
			for(int x = 0; x < vertices; x++) {
				interMatrix[x] = new long[vertices];
				fill_n(interMatrix[x],vertices,INF);
			}
		}
		else {
			iss.str(line);
			string val1;
			string val2;
			string val3;
			lineNumber++;
			if (!(iss >> val1 >> val2 >> val3)) {
				cerr << "Error: Invalid edge data '" << line << "' on line " << lineNumber << "." << endl;
				return 1;
			}

			char char1 = val1[0];
			char char2 = val2[0];
			string alpha = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
			stringstream geek(val3);
			int geeks = 0;


			char maxLetter = alpha[vertices - 1];
			if (!(geek >> geeks) || geeks < 1) {
				cerr << "Error: Invalid edge weight '"<< val3 << "' on line " << lineNumber << "." << endl;
				return 1;
			}

			if (maxLetter < char1 || char1 < 'A' || val1.length() > 1 ) {
				cerr << "Error: Starting vertex '" << val1 << "' on line " << lineNumber << " is not among valid values A-"<< maxLetter <<"."<<endl;
				return 1;
			}
			if (maxLetter < char2 || char2 < 'A' || val1.length() > 1) {
				cerr << "Error: Ending vertex '" << val2 << "' on line " << lineNumber << " is not among valid values A-"<< maxLetter <<"."<<endl;
				return 1;
			}

		addToMatrix(char1,char2,geeks);
		}
	}
	floyds_alg(matrix);
	vector<char> path;
	//printpath
	for(int i = 0; i < vertices; i++){
		for(int j = 0; j < vertices; j++){
			path = backtrack(i,j);
			reverse(path.begin(),path.end());
			cout << static_cast<char>('A'+i) << " -> " << static_cast<char>('A'+j) << ", distance: ";
			if(pathMatrix[i][j] < INF){
				cout << pathMatrix[i][j] << ", path: ";
				cout << path.at(0);
				for(unsigned int x = 1; x < path.size(); x++){
					cout << " -> " << path.at(x);
				}
			}
			else {
				cout << "infinity, path: none";
			}
			cout << endl;
		}
	}

	input.close();
	return 0;
}