// Aren Jansen
// HW7 BFS Solution code
// breadth first search example in a directed graph

#include <iostream>
#include <cstring>

using namespace std;

class node;
typedef node *NP;
class edge;
typedef edge *EP;
void bfs( NP start );
ostream& operator << ( ostream & os, node & n );

class node{    // nodes for a graph
   public:
      char* name;
      bool visited; // three items used in traversal
      int dist;

      EP adjList;  // adjacency list

      node( char n[] )
	 : visited(false), adjList(0), dist(0)
      { 
	 name = new char[strlen(n)+1];
	 strcpy(name,n);
      }

      ~node(){ delete[] name; }

      void edge2( NP to );
};

class edge{ // elements for an edge list 
   public:    // also used to make a queue
      const NP terminus;
      EP next;
      edge( const NP to, EP nn  )
	 : terminus( to ), next(nn){}
};

void node::edge2( NP to )
{ // insert a new edge
   EP newedge = new edge( to, adjList );
   adjList = newedge;
}

class nodeQueue{
      // uses edges to build a queue of nodes
   public:
      EP head, tail;

      void push( const NP newNP )
      {  // put a new node in the queue
	 // insert at tail	 	 
	 EP newedge = new edge( newNP, 0 );
	 
	 if ( !head )
	 {		  
	    head = tail = newedge;
	    tail->next = 0;
	 }
	 else
	 {
	    tail->next = newedge;
	    tail = newedge;
	    tail->next = 0;
	 }
      }

      void pop()
      {// remove head of queue
	 
	 if ( head )
	 {
	    if ( head == tail )
	    {
	       tail = 0;
	    }

	    EP next = head->next;
	    delete head;
	    head = next;	    
	    
	    return;
	 }
      }

      NP front()
      {// return head of queue
	 return head->terminus;
      }

      bool empty()
      { 
	 if ( !head )
	 {
	    return true;
	 }
	 else
	 {
	    return false;
	 }
      }

      nodeQueue()
	 :head(0), tail(0) {}

      ~nodeQueue()
      { 
	 while( head )
	 {
	    pop();
	 }
      }
};

void bfs( NP start )
{// breadth first search of the nodes reachable from start
   nodeQueue nq;

   nq.push(start);

   while ( !nq.empty() )
   {
      NP currentNode = nq.front();

      for ( EP iter = currentNode->adjList;
	    iter; iter = iter->next )
      {	  
	 if ( !iter->terminus->visited )
	 {
	    iter->terminus->dist = currentNode->dist + 1;
	    nq.push(iter->terminus);
	 }
      }
      
      if ( !currentNode->visited )
	 cout << *currentNode;

      currentNode->visited = true;      

      nq.pop();
   }
}

ostream& operator << ( ostream & os, node & n )
{
   cout << "Node " << n.name << " is at distance "
	<< n.dist << " from the start\n";
}

int main()
{// test of dfs code
   
/*
  Test Graph
  
         4<-----5
         |      ^
         |      |
         V      V
         0----->1<---->7----->8
         |      |      ^
         |      |      |
         V      V      V
         2<---->3----->9<---->6
*/

   NP np[10];
   np[0] = new node("node 0");
   np[1] = new node("node 1");
   np[2] = new node("node 2");
   np[3] = new node("node 3");
   np[4] = new node("node 4");
   np[5] = new node("node 5");
   np[6] = new node("node 6");
   np[7] = new node("node 7");
   np[8] = new node("node 8");
   np[9] = new node("node 9");

   np[0]->edge2( np[1] );    // 0->1
   np[0]->edge2( np[2] );    // 0->2
   np[1]->edge2( np[3] );    // 1->3
   np[1]->edge2( np[7] );    // 1->7
   np[1]->edge2( np[5] );    // 1->5
   np[2]->edge2( np[3] );    // 2->3
   np[3]->edge2( np[9] );    // 3->9
   np[3]->edge2( np[2] );    // 3->2
   np[4]->edge2( np[0] );    // 4->0
   np[5]->edge2( np[4] );    // 5->4
   np[5]->edge2( np[1] );    // 5->1
   np[6]->edge2( np[9] );    // 6->9
   np[7]->edge2( np[8] );    // 7->8
   np[9]->edge2( np[6] );    // 9->6
   np[9]->edge2( np[7] );    // 9->7

   cout << "Starting from node 0 we get\n";
   bfs( np[0] );

   for( int i=0; i<10; i++ )
   {
      np[i]->visited = false;
      np[i]->dist = 0;
   }

   cout << "\nStarting from node 6 we get\n";
   bfs( np[6] );

   np[7]->edge2( np[1] );    // 7->1
   for( int i=0; i<10; i++ )
   {
      np[i]->visited = false;
      np[i]->dist = 0;
   }

   cout << "\nStarting from node 6 after inserting 7->1 we get\n";
   bfs( np[6] );


  return 0;
}