#include "graph.h"


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


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")
   {
      fout << "\nError in input file.\n\n";
      exit(EXIT_FAILURE);
   }
   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);
      }

      if(from < to)
      {
         insert_edge(fout, from, to, the_weight);  //O(n + e) n = num vertices
      }
      else
      {
         insert_edge(fout, to, from, the_weight);  //O(n + e) n = num vertices
      }
      
      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)
{
   if(from == to)
   {  //don't need any edges to yourself
      return;
   }
   
   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(from_id, 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 -> id == to_id)
      {
         if(the_weight > iter -> weight)
         {  //keep only the largest weighted edges
            iter -> weight = the_weight;
            return;
         }
         return;
      }
      if(to_id < iter -> id)
      {  //insert edges in order of id
         array[from_id].insert(iter, Node(from_id, to_id, the_weight));  //O(1)
         return;
      }


   }
   array[from_id].push_back(Node(from_id, 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:   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";
   }
}


//******************************************************************************
//
// Function:   find_network
//
// Purpose:    Searches the adjacency list to find the largest weight.
//             Then uses this as the starting vetex and adds additional
//             edges so that one vertex is already in the new network.
//
// Parameters: none
//
// Calls:      new, begin, end
//
// Time Comp:  O(n*e)
//
// Space Com:  O(n) n = number of vertices in the graph
//
//******************************************************************************


void Graph::find_network()
{
   list<Node>::iterator iter;
   list<Node>::iterator max_weight;
   bool* set = new bool[num_vertices];  //space of O(n) n = num_vertices
   bool first_node = true;
   
   for(int j(0); j < num_vertices; ++j)
   {  //this is true if a node is in the tree
      set[j] = false;
   }

   for(int j(0); j < num_vertices - 1; ++j)  //O(n)
   {
      max_weight = NULL;
      //these two for loops touch all edges in the graph O(e)
      for(int i(0); i < num_vertices - 1; ++i)
      {  //find the maximum weighted edge that doesn't create a cycle
         for(iter = array[i].begin(); iter != array[i].end(); ++iter)
         {
            if((max_weight == NULL) && (first_node))
            {
               max_weight = iter;
            }
            else
            {
               if(((max_weight == NULL) &&
                 ((set[i] && !set[iter -> id]) ||   //only one of the nodes can
                 (!set[i] && set[iter -> id]))) ||  //already be in the tree
                 ((max_weight != NULL) &&
                 (iter -> weight > max_weight -> weight) &&
                 ((set[i] && !set[iter -> id]) ||  //only one of the nodes can
                 (!set[i] && set[iter -> id]))))   //already be in the tree
               {
                  max_weight = iter;
               }
            }
         }
      }
      if(first_node)
      {
         set[max_weight -> from_id] = true;
         set[max_weight -> id] = true;
         max_weight -> in_network = true;
         first_node = false;
      }
      else
      {
         if(set[max_weight -> from_id])
         {
            set[max_weight -> id] = true;
         }
         else
         {
            set[max_weight -> from_id] = true;
         }
         max_weight -> in_network = true;
      }
   }
}


//******************************************************************************
//
// Function:   simplify
//
// Purpose:    This removes any edges that are not needed for network
//             connectivity.
// Parameters: none
//
// Calls:      begin, end, erase
//
// Time Comp:  O(e) e = number of edges
//
// Space Comp: O(1)
//
//******************************************************************************


void Graph::simplify()
{
   list<Node>::iterator iter;
   //these two for loops touch all edges in the graph O(e)
   for(int i(0); i < num_vertices - 1; ++i)
   {
      for(iter = array[i].begin(); iter != array[i].end(); ++iter)
      {
         if(!(iter -> in_network))
         {
            array[i].erase(iter);  //O(1)
            --iter;
         }
      }
   }
}


//******************************************************************************
//
// Function:   show_all
//
// Purpose:    Outputs the simplified network in alphabetical order.
//
// Parameters: fout - output file stream
//
// Calls:      begin, end, get_id
//
// Time Comp:  O(e) e = number of edges in the graph
//
// Space Com:  O(1)
//
//******************************************************************************


void Graph::show_all(ostream& fout)
{
   list<Node>::iterator iter;
   //these two for loops run through all the edges in the graph O(e)
   for(int i(0); i < num_vertices - 1; ++i)
   {
      for(iter = array[i].begin(); iter != array[i].end(); ++iter)
      {
         fout << names[i] << endl;
         fout << names[iter -> get_id()] << endl;
         fout << iter -> weight << endl;
      }
   }
}