#include "graph.h"


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


Graph::Graph()
{
   total_cost = 0;
}


//****************************************************************************
//
// 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, peek
//
// Time Comp:  O(1)
//
// Space Com:  O(1)
//
//****************************************************************************


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

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

   if(!(fin >> num_vertices))  //must be an integer
   {
      fout << "NETWORK ERROR\n";
      exit(EXIT_FAILURE);
   }
   if(!(fin >> num_edges))  //must be an integer
   {
      fout << "NETWORK ERROR\n";
      exit(EXIT_FAILURE);
   }
   
   if(num_vertices < 1)  //must have a vertex
   {
      fout << "NETWORK ERROR\n";
      exit(EXIT_FAILURE);
   }
   if(num_edges < 0)  //can't have a negative number of edges
   {
      fout << "NETWORK ERROR\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, push_back
//
// 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 << "NETWORK ERROR\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_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;

   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);  //starting vertex

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

      getline(fin, to);  //finishing vertex

      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))  //cost of the leg of the trip
      {  //has to be a float
         fout << "NETWORK ERROR\n";
         exit(EXIT_FAILURE);
      }
      
      insert_edge(fout, from, to, the_weight);  //O(n + e) n = num vertices
      insert_edge(fout, to, from, the_weight);  //O(n + e) e = num edges

      fin.get();
   }
}


//****************************************************************************
//
// Function:   read_route
//
// Purpose:    Read in the shipping starting place and the destination
//             and the shipping leg cost
//
// 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_route(istream& fin, ostream& fout)
{
   string comments;
   string temp_node;

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

   getline(fin, temp_node);  //departure city
   departure = get_id(fout, temp_node);  //O(n) n = number of vertices

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

   getline(fin, temp_node);  //destination city
   destination = get_id(fout, temp_node);  //O(n) n = number of vertices

   if(departure == destination)  //no shipping to the same city
   {
      fout << "SHIPMENT ERROR\n";
      exit(EXIT_FAILURE);
   }

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

   if(!(fin >> num_units))  //number of units to be shipped
   {  //has to be an integer
      fout << "SHIPMENT ERROR\n";
      exit(EXIT_FAILURE);
   }
}


//****************************************************************************
//
// 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)  //can't have shipping route to yourself
   {
      fout << "NETWORK ERROR\n";
      exit(EXIT_FAILURE);
   }
   
   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)
      {
         fout << "NETWORK ERROR\n";
         exit(EXIT_FAILURE);
      }
      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 << "NETWORK ERROR\n";
   exit(EXIT_FAILURE);
}


//******************************************************************************
//
// Function:   get_length
//
// Purpose:    
//
// Parameters: Return the shipping leg cost from "from" to "to"
//
// Calls:      begin, end
//
// Time Comp:  O(e) - e = number of edges in graph
//
// Space Com:  O(1)
//
//******************************************************************************


float Graph::get_length(size_t from, size_t to)
{
   list<Node>::iterator iter;

   for(iter = array[from].begin(); iter != array[from].end(); ++iter)
   {  //O(e), toaches all edges in from one vertex
      //can be as big as n - 1 or as small as 0
      if(iter -> id == to)
      {
         return (iter -> weight);
      }
   }
   return(BIG);  //BIG is my representation of INFINITE, no connection
}


//******************************************************************************
//
// Function:   shortest_path
//
// Purpose:    Find all minimum paths from each city to every other city
//
// Parameters: fout - output file stream
//
// Calls:      get_length, choose, new, static_cast
//
// Time Comp:  O(n*n*n*e) n = num vertices, e = num edges
//
// Space Com:  O(n*n) n = num vertices
//
//******************************************************************************


void Graph::shortest_path(ostream& fout)
{
   where_from = new size_t*[num_vertices];  //space O(n*n)
   float* dist = new float[num_vertices];  //space O(n)
   bool* set = new bool[num_vertices];    //space O(n)
   
   for(int i(0); i < num_vertices; ++i)
   {
      where_from[i] = new size_t[num_vertices];
   }
   
   for(int v(0); v < num_vertices; ++v)  //O(n) runs num_vertices times
   {
      for(int i(0); i < num_vertices; ++i)  //O(n)
      {  //initialize for each vertex
         set[i] = false;
         dist[i] = get_length(v, i);
         where_from[v][i] = v;
      }
      set[v] = true;
      dist[v] = 0;
      
      for(int j(0); j < num_vertices - 2; ++j)  //O(n)
      {
         size_t u = choose(dist, set);  //O(n)
         set[u] = true;
         
         for(int w(0); w < num_vertices; ++w)  //O(n)
         {
            if(!set[w])
            {
               if(dist[u] + get_length(u, w) < dist[w])  //O(n)
               {
                  dist[w] = dist[u] + get_length(u, w);  //O(n)
                  where_from[v][w] = u;
               }
            }
         }
      }
      if(v == static_cast<int>(departure))
      {
         if(dist[destination] >= BIG)
         {
            fout << "NO CONNECTION\n";
            exit(EXIT_FAILURE);
         }
      }
   }
}


//******************************************************************************
//
// Function:   choose
//
// Purpose:    Find the shortest distance to another vertex that hasn't
//             been used yet
//
// Parameters: dist - distance from a vertex to all vertices
//             set - true if vertex has already been used
//
// Calls:      none
//
// Time Comp:  O(n) n = number of vertices
//
// Space Com:  O(1)
//
//******************************************************************************


size_t Graph::choose(const float dist[], const bool set[])
{
   bool first_node = true;
   size_t holder;

   for(int i(0); i < num_vertices; ++i)  //O(n)
   {  //finds smallest distance that is not already used
      if(!set[i] && first_node)
      {
         holder = i;
         first_node = false;
      }
      else if(!set[i] && (dist[i] < dist[holder]))
      {
         holder = i;
      }
   }
   return holder;
}


//******************************************************************************
//
// Function:   show_path
//
// Purpose:    Output the starting vertex, call work horse function that
//             prints out the rest of the vertices, then print out the final
//             cost.
//
// Parameters: fout - output file stream
//
// Calls:      show_path, precision, fixed, showpoint
//
// Time Comp:  O(n)
//
// Space Com:  O(n)
//
//******************************************************************************


void Graph::show_path(ostream& fout)
{
   fout << names[departure] << endl;  //start city
   show_path(fout, destination);  //space and time complexity of O(n)
   fout << "TOTAL COST IS $";
   fout.setf(ios::fixed);
   fout.setf(ios::showpoint);
   fout.precision(2);
   fout << total_cost << endl;  //the total cost for the trip
}


//******************************************************************************
//
// Function:   show_path
//
// Purpose:    Output the vertices you must visit and compute total cost
//
// Parameters: fout - output file stream
//             index - vertex that you just came from
//
// Calls:      show_path
//
// Time Comp:  O(n)
//
// Space Com:  O(n) n = number of vertices in the graph
//
//******************************************************************************


void Graph::show_path(ostream& fout, size_t index)
{
   if(index != departure)
   {
      show_path(fout, where_from[departure][index]);  //O(n) space & time
      fout << names[index] << endl;
      total_cost +=  //total_cost = summation(num_units * shipping leg cost)
         (num_units * get_weight(where_from[departure][index], index));
   }
}


//******************************************************************************
//
// Function:   get_weight
//
// Purpose:    Find the cost of the shipping leg between from and to
//
// Parameters: from - start vertex
//             to - end vertex
//
// Calls:      begin, end
//
// Time Comp:  O(n)
//
// Space com:  O(n) 
//
//******************************************************************************


float Graph::get_weight(size_t from, size_t to)
{
   list<Node>::iterator iter;
   for(iter = array[from].begin(); iter != array[from].end(); ++iter)  //O(n)
   {
      if(iter -> id == to)
      {
         return iter -> weight;
      }
   }
   return(EXIT_FAILURE);
}