// 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)
{
//implement this
}


void graph::initializeSPTable()
{
//implement this (or don't, if you don't need it)
}

void graph::printShortestPath(string name)
{
//implement this
}