//****************************************************************************
//
// Function:   graph
//
// Purpose:    default constructor
//
// Parameters: none
//
// Calls:      none
// 
// Time Comp:  O(1)
//
// Space Com:  O(1)
//
//****************************************************************************

#include "graph.h"

Graph::Graph()
{
   spanning = false;
}


//****************************************************************************
//
// Function:   read_directed
//
// Purpose:    Read in if the graph is directed or undirected
//
// Parameters: fin - the input file stream
//             fout - the output file stream
//
// Calls:      exit
//
// Time Comp:  O(1)
//
// Space Com:  O(1)
//
//****************************************************************************


void Graph::read_directed(istream& fin, ostream& fout)
{
   string comments;
   while(fin.peek() == '%')
   {  //get rid of comments
      fin.get();
      getline(fin, comments);
   }

   string is_directed;
   fin >> is_directed;

   if(is_directed == "directed")
   {
      directed = true;
   }
   else if(is_directed == "undirected")
   {
      directed = false;
   }
   else
   {
      fout << "\nError in input file.\n\n";
      exit(EXIT_FAILURE);
   }
}


//****************************************************************************
//
// Function:   read_num_vertices
//
// Purpose:    Read in the number of verticies in the graph
//
// Parameters: fin - the input file stream
//             fout - the output file stream
//
// Calls:      exit
//
// Time Comp:  O(1)
//
// Space Com:  O(1)
//
//****************************************************************************


void Graph::read_num_vertices(istream& fin, ostream& fout)
{
   string comments;
   fin.get();
   while(fin.peek() == '%')
   {  //get rid of comments
      getline(fin, comments);
   }

   if(!(fin >> num_vertices))  //must be an integer
   {
      fout << "\nError in input file.\n";
      exit(EXIT_FAILURE);
   }
   if(num_vertices < 1)  //must have a vertex
   {
      fout << "\nError in input file.\n\n";
      exit(EXIT_FAILURE);
   }
}


//****************************************************************************
//
// Function:   read_vertices_name
//
// Purpose:    Read in the name of the verticies of the graph
//
// Parameters: fin - the input file stream
//             fout - the output file stream
//
// Calls:      get, getline, new, exit
//
// Time Comp:  O(n*n) n = number of vertices in the graph
//
// Space Com:  O(n) n = number of vertices in the graph
//
//****************************************************************************


void Graph::read_vertices_name(istream& fin, ostream& fout)
{
   array = new list<Node>[num_vertices];  //takes num_vertices space
   vector<string>::iterator iter;
   string vert_name;
   fin.get();
   string comments;

   for(int i(0); i < num_vertices; ++i)  //this runs num_vertices times
   {
      while(fin.peek() == '%')
      {  //get rid of comments
         getline(fin, comments);
      }
      getline(fin, vert_name);
      iter = names.begin();  //O(1)
      while(true)  //this runs at most num_vertices times
      {  //keeps the names in alphabetical order
         if(iter == names.end())
         {
            names.push_back(vert_name);  //O(1)
            break;
         }
         else if(*iter == vert_name)
         {  //can't have duplicate vertex names
            fout << "\nError in input file.\n\n";
            exit(EXIT_FAILURE);
         }
         else if(vert_name < *iter)
         {  //keeps in alphabetical order
            names.insert(iter, vert_name);  //O(n) = number of vertices
            break;
         }
         else
         {
            ++iter;
         }
      }
   }
}


//****************************************************************************
//
// Function:   read_num_edges
//
// Purpose:    Read the number of edges in the graph.
//
// Parameters: fin - the input file stream
//             fout - the output file stream
//
// Calls:      exit
//
// Time Comp:  O(1)
//
// Space Com:  O(1)
//
//****************************************************************************


void Graph::read_num_edges(istream& fin, ostream& fout)
{
   string comments;

   while(fin.peek() == '%')
   {  //get rid of comments
      fin.get();
      getline(fin, comments);
   }

   if(!(fin >> num_edges))  //must be an integer
   {
      fout << "\nError in input file.\n\n";
      exit(EXIT_FAILURE);
   }
   if(num_edges < 0)
   {  //can't have a negative number of edges
      fout << "\nError in input file.\n\n";
      exit(EXIT_FAILURE);
   }
}


//****************************************************************************
//
// Function:   read_edges
//
// Purpose:    Read the edges of the graph in.
//
// Parameters: fin - the input file stream
//             fout - the output file stream
//
// Calls:      get, peek, getline, insert_edge, exit
//
// Time Comp:  O(n*n or n*e)  n = num vertices, e = number of edges
//
// Space Com:  O(1)
//
//****************************************************************************


void Graph::read_edges(istream& fin, ostream& fout)
{
   string from;
   string to;
   float the_weight;
   string comments;
   fin.get();

   for(int i(0); i < num_edges; ++i)  //runs number of edges in the graph time
   {
      while(fin.peek() == '%')
      {  //get rid of comments
         fin.get();
         getline(fin, comments);
      }

      getline(fin, from);

      while(fin.peek() == '%')
      {  //get rid of commments
         fin.get();
         getline(fin, comments);
      }

      getline(fin, to);

      while(fin.peek() == '%')
      {  //get rid of comments
         fin.get();
         getline(fin, comments);
      }

      if(fin.peek() == '\n')
      {  //if you leave a blank line it counts as a weight of one
         the_weight = 1;
      }
      else if(!(fin >> the_weight))
      {  //has to be a float
         fout << "\nError in input file.\n\n";
         exit(EXIT_FAILURE);
      }
      insert_edge(fout, from, to, the_weight);  //O(n + e) n = num vertices
      if(!directed)                                       //e = num edges
      {  //put the edge in the linked list
         insert_edge(fout, to, from, the_weight);
      }
      fin.get();
   }
}


//****************************************************************************
//
// Function:   read_start
//
// Purpose:    Read the vertex to start the bfs with.
//
// Parameters: fin - the input file stream
//             fout - the output file stream
//
// Calls:      peek, get, getline, get_id
//
// Time Comp:  O(n) n = number of vertices
//
// Space Com:  O(1)
//
//****************************************************************************


void Graph::read_start(istream& fin, ostream& fout)
{
   string comments;
   while(fin.peek() == '%')
   {  //get rid of comments
      fin.get();
      getline(fin, comments);
   }
   string start_node;
   getline(fin, start_node);
   start_vertex = get_id(fout, start_node);  //O(n) n = number of vertices
}


//****************************************************************************
//
// Function:   insert_edge
//
// Purpose:    Insert an edge into the list of from.
//
// Parameters: fout - the output file stream
//             from - beginning place of the edge
//             to - ending place of the edge
//             the_weight - the value of the edge
//
// Calls:      get_id, begin, empty, push_front, end, push_back
//
// Time Comp:  O(n + e) n = number of vertices, e = number of edges
//
// Space Com:  O(1)
//
//****************************************************************************


void Graph::insert_edge(ostream& fout, string from, string to,
                        float the_weight)
{
   size_t from_id = get_id(fout, from);  //O(n) n = num_vertices
   size_t to_id = get_id(fout, to);  //O(n)
   list<Node>::iterator iter = array[from_id].begin();  //O(1)

   if(array[from_id].empty())  //(1)
   {  //first edge in the list
      array[from_id].push_front(Node(to_id, the_weight));  //O(1)
      return;
   }

   for(iter = array[from_id].begin(); iter != array[from_id].end(); ++iter)
   {  //O(e) e = number of edges in the graph
      if(iter -> weight > the_weight)
      {  //insert edges in order of weight
         array[from_id].insert(iter, Node(to_id, the_weight));  //O(1)
         return;
      }
   }
   array[from_id].push_back(Node(to_id, the_weight));  //O(1)
}


//****************************************************************************
//
// Function:   get_id
//
// Purpose:    Returns the array index of in_name
//
// Parameters: fout - the output file stream
//             in_name - name of vertex to return the id of
//
// Calls:      begin, end, exit
//
// Time Comp:  O(n) n = number of vertices in the graph
//
// Space Com:  O(1)
//
//****************************************************************************


size_t Graph::get_id(ostream& fout, string in_name)
{
   vector<string>::iterator iter;
   size_t count(0);
   for(iter = names.begin(); iter != names.end(); ++iter)  //runs number of
   {  //find name                                         //vertices in graph
      if(*iter == in_name)
      {
         return count;
      }
      ++count;
   }
   fout << "\nError in input file.\n\n";
   exit(EXIT_FAILURE);
}


//****************************************************************************
//
// Function:   bfs
//
// Purpose:    This prints a breadth first search of the graph.
//
// Parameters: fout - the output file stream
//
// Calls:      new, push, empty, front, pop, begin, end, get_id
//
// Time Comp:  O(n*e) n = number of vertices e = number of edges
//
// Space Com:  O(n) n = number of vertices in the graph
//
//****************************************************************************


void Graph::bfs(ostream& fout)
{
   bool* visited  = new bool[num_vertices];  //num_vertices space
   for(int i(0); i < num_vertices; ++i)
   {  //initually no nodes have been visited
      visited[i] = false;
   }
   visited[start_vertex] = true;  //the start vertex has been visited
   queue<size_t> visited_nodes;  //this queue can get as big as n = num_nodes
   visited_nodes.push(start_vertex);  //O(1)
   size_t starter;
   list<Node>::iterator iter;

   while(!visited_nodes.empty())  //O(n) n = number of vertices
   {
      starter = visited_nodes.front();  //O(1)
      visited_nodes.pop();  //O(1)
      for(iter = array[starter].begin(); iter != array[starter].end(); ++iter)
      {  //O(e) e = number of edges in the graph
      	 //visit all nodes adjacent to starter
         if(!visited[iter -> get_id()])  //O(1)
         {  //if this vertices hasn't been visited yet
            fout << names[starter] <<endl;
            fout << names[iter -> get_id()] << endl;  //O(1)
            fout << iter -> weight << endl;
            visited_nodes.push(iter -> get_id());  //O(1)
            visited[iter -> get_id()] = true;  //O(1)
            spanning = true;
         }
      }
   }
   delete[] visited;
}


//****************************************************************************
//
// Function:   is_spanning
//
// Purpose:    If the graph has no spanning tree this prints that out
//
// Parameters: fout - the output file stream
//
// Calls:      none
//
// Time Comp:  O(1)
//
// Space Com:  O(1)
//
//****************************************************************************


void Graph::is_spanning(ostream& fout)
{
   if(!spanning)
   {
      fout << "\nThis graph contains no spanning tree.\n\n";
   }
}