#include "Queue.h"
#include <iostream>
#include <fstream>
#include <string>
#include <deque>

using namespace std;
using namespace cop4530;

int search(int* graph, int size, int s, int d);

//This is the airline program: it uses the queue class to create
//a breadth-first search.
int main(int argc, char* argv[])
{
	ifstream infile;
	int size;
	int* graph;
	int s, d, sum;
	string* citynames;
	string selection = "y";
	string source;
	string destination;
	deque<int> path;

	//Checks to see if there was a file passed in. If so, open it
	if(argc != 2)
	{
		cout << "Usage: project2 airline_file";
		return 0;
	}
	else
	{
		//Opens the file, gets everything out of it, closes it.
		infile.open(argv[1]);
		infile >> size;
		cout << size << " cities:" << endl;

		//Gets rid of any left over whitespace; there somethimes is
		while(infile.peek() == '\n' || infile.peek() == ' ')
			infile.get();

		//Creates an array for names and cost matrix, stored as a 1-d array
		graph = new int[size*size];
		citynames = new string[size];

		for(int i = 0; i < size; i++)
		{//gets city names
			getline(infile, citynames[i], '\n');
			cout << "    " << citynames[i] << endl;
		}

		for(int i = 0; i < size*size; i++)//gets graph, puts it into 1-d matrix
			infile >> graph[i];

		//Outputs the flight things...
		cout << "\nDirect flights between cities:\n" << "------------------------\n";
		for(int i = 0; i < size; i++)
		{
			cout << citynames[i] << ":" << endl;
			for(int j = 0; j < size; j++)
				if(graph[i*size + j] > 0)
					cout << "    " << citynames[j] << ", $" << graph[i*size + j] << endl;
		}
		cout << "-----------------------\n";

		infile.close();
	}

	//Main Program loop
	while(selection != "n" && selection != "N")
	{
		path.clear();	//Clears the path so that it does not conflict with future queries
		cout << "\nSource City : ";
		getline(cin,source, '\n');
		cout << "Destination City : ";
		getline(cin,destination, '\n');
		cout << "finding min_hop route...\n";

		s = -1;			//Sets both destination and source to be non-true, then checks for truth
		d = -1;
		for(int i = 0; i < size; i++)
		{
			if(citynames[i] == source)
				s = i;
			if(citynames[i] == destination)
				d = i;
		}

		//If destination or source is not a city, say so
		if(s == -1)
			cout << "\tpath not found, source city, " << source << ", not on map";
		else if(d == -1)
			cout << "\tpath not found, destination city, " << destination << ", not on map";

		//If both destination and source are a city, then look for a path using a path finding function search
		if(s != -1 && d != -1)
		{
			//If source is destination, put only it on the deque
			if (s == d)
				path.push_back(s);
			else	//puts the destination on the back
				path.push_back(d);

			//Search returns the node pointing to the destination given, so if you call it over and over
			//with that pointing node as the new destination, it will give you the path. Not even close to
			//an efficient way of doing it but it works....plus I don't have to save EVERY SINGLE PATH i've
			//ever used in memory.
			while(s != d && d != -1)
			{
				d = search(graph, size, s, d);
				path.push_front(d);
			}
			if(d == -1)
				cout << "There is no path from " << source << " to " << destination;
			else
			{//Whole next segment shows the path and crap if there is one
				cout << "\n   ";
				sum = 0;
				for(unsigned int i = 0; i < path.size(); i++)
				{//Ouputs the path and price of path
					if(i > 0)
						sum = sum + graph[path[i -1]*size + path[i]];
					cout << citynames[path[i]];
					if(i < path.size() - 1)
						cout << " -> ";
					else
						cout << ", $" << sum;
				}
			}
		}

		do{//Repeats until user puts a correct choice
		cout << "\n\nSearch another route? (Y/N): ";
		cin >> selection;
		}while(selection != "y" && selection != "Y" && selection != "n" && selection != "N");

		cin.get();	//Gets the somehow leftover newline at the end...
	}

	delete graph;
	//delete citynames;

	return 0;
}

//Search using breadth first, returns the second to last element on the path
int search(int* graph, int size, int s, int d)
{
	//Base case, if source is destination, send it back
	if(s == d)
		return d;

	//element is the node that is currently being visited
	int element;
	bool* visited = new bool[size];
	for(int i = 0; i < size; i++)
		visited[i] = 0;

	//Path is the queue that performs the breadth first search.
	//Track keeps track of the second to last node that was visited on the path
	Queue<int> path;
	deque<int> track;
	track.clear();

	//Adds source city to queue and marks as visited
	path.push(s);
	visited[s] = 1;

	//Breadth first search based off of what we did in class
	while(!(path.empty()))
	{
		element = path.front();
		track.push_back(element);	//Adds node to track, pops off after neighbors are visited

		for(int i = 0; i < size; i++)
		{//Finds neighbors of current node, adds them to queue
			if(graph[element*size + i] > 0 && visited[i] == 0)
			{//If there is an unvisited node that is a neighbor, add it to queue and count it as visited
				visited[i] = 1;
				path.push(i);

				if(i == d)
				{//If destination is found, return track that holds previous node
					path.pop();
					return track[track.size() - 1];
					//track.push_back(i);
					//break;
				}
			}
		}
		track.pop_back();
		path.pop();
	}
	return -1;
}