#include "graph3.h"
#include <cstdlib>
#include <queue>

graph::graph(){
	// Nothing needs to be done except set the number of nodes to zero
	myNumberNodes = 0;
}

void graph::operator +=(const node & x){
	// First check if the node already exists in the graph
	if(getIndex(x) >= 0){
		cout << "Node " << x.getName() << " already exists" << endl;
		return;
	}
	
	// If the vector of nodes is full, resize it and resize the adjacency 
	// matrix. We'll make sure thet the length of the node vector always
	// equals the dimensions of the adjacency matrix
	if(myNumberNodes == myNodes.length()){
		myNodes.resize(2*myNumberNodes+1);
		myMatrix.resize(2*myNumberNodes+1);
		for(int i = 0; i <= 2*myNumberNodes; i++)
			myMatrix[i].resize(2*myNumberNodes+1);
	}

	// Insert the new node at the end
	myNodes[myNumberNodes] = x;

	// Since the new node has no neighbors to start with, set the
	// corresponding row and column to false
	for(int i = 0; i <= myNumberNodes; i++){
		myMatrix[myNumberNodes][i] = false;
		myMatrix[i][myNumberNodes] = false;
	}

	myNumberNodes++;

}

void graph::operator -=(const node & x){
	// get the index of the given node x
	int i = getIndex(x);	

	// Check if node exists in the graph; otherwise produce error message
	if (i < 0){
		cout << "Node " << x.getName() << " is not in the graph" << endl;
		return;
	}

	// we copy the last node into the ith slot
	myNodes[i] = myNodes[myNumberNodes-1];

	// we adjust the entries of the matrix appropriately;
	// move the last row to row i and the last column to column i
	for(int j = 0; j < myNumberNodes; j++){
		myMatrix[i][j] = myMatrix[myNumberNodes-1][j];
		myMatrix[j][i] = myMatrix[j][myNumberNodes-1];
	}
	myMatrix[i][i] = false;	

	// Reduce the number of nodes
	myNumberNodes--;


	// Shrink the myNodes vector and myMatrix, if they are more
	// than twice the number of nodes
	if (2*myNumberNodes < myNodes.length()){
		myNodes.resize(myNumberNodes);
		myMatrix.resize(myNumberNodes);
		for(int j = 0; j < myNumberNodes; j++)
			myMatrix[j].resize(myNumberNodes);
	} 

}


void graph::operator +=(const edge & x){
	// Get the indices of the two endpoints of the edge in the vector of nodes
	int i = getIndex(x.getNode1());
	int j = getIndex(x.getNode2());

	// Check if either of the endpoints are non-existant and produce error
	// message, if necessary
	if (i < 0){
		cout << "Node " << (x.getNode1()).getName() << " is not in the graph" << endl;
		return;
	}
	if (j < 0){
		cout << "Node " << (x.getNode2()).getName() << " is not in the graph" << endl;
		return;
	}

	
	// Check if edge already exists
	if (myMatrix[i][j]){
		cout << "Edge already exists" << endl;
		return;
	}	

	// Use these indices to turn on the corresponding elements in the 
	// adjacency matrix
	myMatrix[i][j] = myMatrix[j][i] = true;
}


void graph::operator -=(const edge & x){
	// Get the indices of the two endpoints of the edge in the vector of nodes
	int i = getIndex(x.getNode1());
	int j = getIndex(x.getNode2());

	// Check if either of the endpoints are non-existant and produce error
	// message, if necessary
	if (i < 0){
		cout << "Node " << (x.getNode1()).getName() << " is not in the graph" << endl;
		return;
	}
	if (j < 0){
		cout << "Node " << (x.getNode2()).getName() << " is not in the graph" << endl;
		return;
	}

	if(!myMatrix[i][j]){
		cout << "Edge does not exist in the graph" << endl;
		return;
	}

	// Use these indices to turn off the corresponding elements in the 
	// adjacency matrix
	myMatrix[i][j] = myMatrix[j][i] = false;
}

apvector<node> graph::get_neighbors(const node & x){
	// Set up a vector for the list of neighbors
	apvector<node> neighbors;	

	// Get the index of the node	
	int i = getIndex(x);
	
	// Check if node exists in the graph
	if(i < 0){
		cout << "Node " << x.getName() << " is not in the graph" << endl;
		return neighbors;
	}

	get_neighbors(i, neighbors);
	return neighbors;
}


void graph::get_neighbors(int i, apvector<node> & neighbors){
	// Scan the row i in the adjacency matrix and pick up neighboring nodes
	for(int j = 0; j < myNumberNodes; j++)
               if(myMatrix[i][j])
                        neighbors.push_back(myNodes[j]);
}

bool graph::bfs(const node & source, apvector<int> & distances){

	// Get index of source node
	int index = getIndex(source);

	// Check if source is in the graph
	if (index < 0)
		return false;

	// Initialization of the distances
	distances.resize(myNumberNodes);
	for(int i = 0; i < myNumberNodes; i++)
		distances[i] = -1;

	distances[index] = 0;

	// Initialization of the visited array
	apvector<bool> visited(myNumberNodes, false);
	visited[index] = true;

	// Initialization of queue
	queue<int> Q;
	Q.push(index);

	// Main bfs loop
	while(!Q.empty()){
		
		// Get the front of the queue
		int current = Q.front();
		Q.pop();	

		// Get the neighbors of current
		apvector<node> neighbors;
		get_neighbors(current, neighbors);

		// Scan the neighbors
		for(int i = 0; i < neighbors.length(); i++){
			int neighborIndex = getIndex(neighbors[i]);

			// If neighbor has not been visited, mark as visited and enqueue
			if(!visited[neighborIndex]){
				visited[neighborIndex] = true;
				Q.push(neighborIndex);
				distances[neighborIndex] = distances[current]+1;
			} // end of if
		} // end of for

	} // end of while

	return true;
} // end of function

int graph::getIndex(const node & x){
	for(int i = 0; i < myNumberNodes; i++)
		if(x == myNodes[i])
			return i;	
	return -1;
}