#include <queue> // I'm using the STL queue
#include <stack> // I'm using the STL stack
#include "apvector.h"
#include "listNode2.h"

typedef bool boolean ;

template <class T> graph<T>::graph(){
	myNumVertices = 0;
	myNumEdges = 0;
}
	
template <class T> void graph<T>::addVertex(const T & name){
	if(myVertices.length() == myNumVertices)
		myVertices.resize(myNumVertices*2+1);

	myVertices[myNumVertices].set_data(name);
	myVertices[myNumVertices].set_link(NULL);
	myNumVertices++;
}

template <class T> void graph<T>::addEdge(const T & name1, const T & name2){
	int i = getIndex(name1);
	int j = getIndex(name2);

	node<T> * temp;
	temp = myVertices[i].link();
	list_head_insert(temp, name2);
	myVertices[i].set_link(temp);

	temp = myVertices[j].link();
        list_head_insert(temp, name1);
        myVertices[j].set_link(temp);

	myNumEdges++;
}

template <class T> node < T > * graph<T>::getNeighbors(const T & name) const{
	node<T> * temp1;
	node<T> * temp2;
	int i = getIndex(name);

	const node<T> * temp = myVertices[i].link();
	list_copy(temp, temp1, temp2);
	return temp1;
}

template <class T> int graph<T>::numVertices() const{
	return myNumVertices;
}

template <class T> int graph<T>::numEdges() const{
	return myNumEdges;
}

template <class T> int graph<T>::getIndex(const T & name) const{
	for (int i = 0; i < myNumVertices; i++){
		if(name == myVertices[i].data())
			return i;
	}

	return -1;

}

// NEW FUNCTIONS

template <class T>
T graph<T>::getItem(int index) const{
  if(index < 0 || index >= myNumVertices){
	cerr << "Illegal Index (" << index << ") into getItem" << endl ;
	exit(EXIT_FAILURE) ;
  }//if
  return myVertices[index].data() ;
}//end of getItem

template <class T>
void graph<T>::bfs(const T & source, apvector<int> & distances, apvector<int> & parent) {
  // initialize the distances vector
  distances.resize(myNumVertices) ;
  for(int i = 0 ; i < myNumVertices ; i++) distances[i] = -1 ;

  // initialize the parent vector
  parent.resize(myNumVertices) ;
  for(int i = 0 ; i < myNumVertices ; i++) parent[i] = -1 ;

  // initialize a visited vector
  apvector<boolean> visited ;
  visited.resize(myNumVertices) ;
  for(int i = 0 ; i < myNumVertices ; i++) visited[i] = false ;

  // find info about the source
  int index = getIndex(source) ;
  if(index < 0){
    cerr << "Source for bfs not found in graph!" << endl ;
    exit(EXIT_FAILURE) ;
  }//if

  // set initial info about source
  visited[index] = true ; // i am the source!
  distances[index] = 0 ; // i am the source!
  parent[index] = -1 ;   // no parent

  // create queue to tell who we need to visit
  queue<int> q ;
  q.push(index) ; // 1st thing on q is the source!

  while(!q.empty()){
    int parent_index = q.front() ; // store 1st thing in q
    q.pop() ;           // remove it from the q

    node<T> * cur = myVertices[parent_index].link() ;    
    // check each neighbor
    while(cur != NULL){
       int neighbor_index = getIndex(cur->data()) ;
       if(!visited[neighbor_index]){
         // mark neighbor as visited
         visited[neighbor_index] = true ;

         // set neighbor's distance
         distances[neighbor_index] = distances[parent_index] + 1 ;

         // set neighbor's parent, index parent[n] = parent_index 
         parent[neighbor_index] = parent_index ; 

         // push child onto queue
         q.push(neighbor_index) ;
      }//if not visited yet
      cur = cur->link() ; // goto next neighbor
    }//while there are more neighbors
  }//while q not empty
}//end of bfs

template <class T>
void graph<T>::print(){
  node<T> * temp ;
  for(int i = 0 ; i < myNumVertices ;i++){
    temp = &myVertices[i] ;
    cout << temp->data() << " has neighbors ... " ;
    temp = temp->link() ;
    while(temp != NULL){
      cout << temp->data() << " " ;
      temp = temp->link() ;
    }//while
    cout << endl ;
  }//for
}//end of print