// graph.cpp: implementation of the graph class.
//
//////////////////////////////////////////////////////////////////////

#include "graph.h"

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

graph::graph(int numVertices, int numEdges)
{
	if (!(vertices = new list<edge*>[numVertices]))
		cout << "ERROR: out of memory" << endl;
	if (!(vertexName = new string[numVertices]))
		cout << "ERROR: out of memory" << endl;	
	lastVertex = 1;

	if (!(edgeName = new string[numEdges]))
		cout << "ERROR: out of memory" << endl;	
	lastEdge = 1;

	known = 0;    //these are initialized after we know how many vertices we ended up with.
	distance = 0;
	previous = 0;

}

graph::~graph()
{
	delete [] vertices;
	delete [] vertexName;
	delete [] edgeName;
	if (known)
		delete [] known;
	if (distance)
		delete [] distance;
	if (previous)
		delete [] previous;
}

int graph::addEdge(string v1, string v2, string label)
{
	int nv1 = addVertex(v1);
	int nv2 = addVertex(v2);
	int ne = edgeNumbers[label];
	if (!(ne)){
		edgeName[lastEdge] = label;
		edgeNumbers[label] = lastEdge;
		ne = lastEdge;
		lastEdge++;
	};
	
	edge *e = new edge(nv2, ne); //and edge to nv2.
	vertices[nv1].push_front(e);
	return nv1;
}

int graph::addVertex(string s)
{
	int n = vertexNumbers[s];
//	cout << "add: " << s << endl;
	if (n){
//		cout << s << " already there" << endl;
		return n;
	};
	vertexNumbers[s] = lastVertex;
	vertexName[lastVertex] = s;
	lastVertex++;	
	return lastVertex-1;
}

//read the data file and add the appropiate edges
// We only do an addEdge for movies that have more than minVotes.
// This means that only popular movies will be added.
//Setting minVotes higher means that the graphs will be smaller
// and occupy LESS MEMORY. (if you run out of memory, set it higher).
//
//NOTE: votes is the number of people who voted.
//		rating is the average rating they gave the movie.
void graph::readGraph(istream & is, int minVotes)
{
	string word, name;
	string movieName;
	string actors[300]; //assume no more than 300 actors in movie
	int votes;
	int totalNumEdges = 0;
	double rating;
	is >> word;
	while (word == "M:") {
		name = "";
		int first=1;
		while (1) {
			is >> word;
			if (word == "R:")
				break;
			if (first){
				name = word;
				first = 0;
			}
			else
				name += " " + word;
		}
		movieName = name;
		is >> rating;  //We ignore these for this Problem Set.
		is >> word; // "V:"
		is >> votes;
		if (votes < minVotes){ //ignore unpopular movies
			is >> word;
			while (word != "M:" && word != "")
				is >> word;
			continue;
		}
		is >> word;
		int currentActor = 1;
		while (word == "A:"){
			string actorName = "";
			int first = 1;
			while (is >> word) {
				if (word == "M:" || word == "A:")
					break;
				if (first){
					actorName = word;
					first = 0;
				}
				else
					actorName += " " + word;
			};
			actors[currentActor] = actorName;
			currentActor++;
		}
		int i,j;
		for (i = 1; i < currentActor; i++){
			for (j= i+1; j< currentActor; j++){
				addEdge(actors[i], actors[j], movieName);
				addEdge(actors[j], actors[i], movieName);
				totalNumEdges+=2;
			}
		}
	}
	cout << "We added " << lastEdge << " movies, " << lastVertex << " actors, and " 
		<< totalNumEdges << " edges." << endl;
}


void graph::calculateShortestPaths(string center)
{
	int centerVertex = vertexNumbers[center];
	if (!(centerVertex)){
		cout << "Vertex " << center << " not found" << endl;
		return;
	}
	else
		cout << "Calculating distances from " << center << endl;
	queue<int> Q;
	initializeSPTable();
	distance[centerVertex] = 0;
	Q.push(centerVertex);
	while (!(Q.empty())) {
		int	v = Q.front();
		Q.pop();
		known[v] = 1; //not needed anymore
		typedef list<edge*>::const_iterator LI;
		for (LI j = vertices[v].begin(); j != vertices[v].end(); ++j){
			edge *e = *j;
			int w = e->vertex;
			if (distance[w] == -1) {
				distance[w] = distance[v] + 1;
				previous[w] = v;
				Q.push(w);
			}
		}
	}
}


void graph::initializeSPTable()
{
	int i;
	if (!(known)){
		if (!(known = new int[lastVertex]))
			cout << "ERROR: Out of memory" << endl;
	}
	if (!(distance)){
		if (!(distance = new int[lastVertex]))
			cout << "ERROR: Out of memory" << endl;
	}
	if (!(previous)){
		if (!(previous = new int[lastVertex]))
			cout << "ERROR: Out of memory" << endl;
	}
	for (i=0; i < lastVertex; i++){
		known[i] = 0;
		distance[i] = -1;
		previous[i] = 0;
	}
}

void graph::printShortestPath(string name)
{
	int v = vertexNumbers[name];
	if (!(v)){
		cout << "===" << name << " was not found (not in popular movie)." << endl;
		return;
	}
	cout << "===Finding path to " << name << endl;
	int prev;
	while (prev = previous[v]) {
		cout << vertexName[v] << " was in ";
		typedef list<edge*>::const_iterator LI;
		for (LI j = vertices[v].begin(); j != vertices[v].end(); ++j){
			edge *e = *j;
			int w = e->vertex;
//			cout << "w= " << w << "prev= " << prev << endl;
			if (w == prev){
				cout << edgeName[e->label] << " with " << vertexName[prev] << endl;
				break;
			}
		}
		v = prev;
	}
}