#include "graph.h"


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


Graph::Graph()
{
}


//******************************************************************************
//
// Function:   ~graph
//
// Purpose:    destructor
//
// Parameters: none
//
// Calls:      none
//
// Time Comp:  O(n)
//
// Space Com:  O(1)
//
//*****************************************************************************


Graph::~Graph()
{
   for(int i(0); i < num_vertices; ++i)
   {
      delete [] cost_of_link[i];
      delete [] travel_time[i];
      delete [] demand[i];
      delete [] existing_links[i];
      delete [] where_from[i];
   }
   delete cost_of_link;
   delete travel_time;
   delete demand;
   delete existing_links;
   delete where_from;
}


//****************************************************************************
//
// 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 << "Error in input file.\n";
      exit(EXIT_FAILURE);
   }
   
   if(num_vertices < 1)  //must have a vertex
   {
      fout << "Error in input file.\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
      {
         if(iter == names.end())
         {
            names.push_back(vert_name);  //O(1)
            break;
         }
         else if(*iter == vert_name)
         {  //can't have duplicate vertex names
            fout << "Error in input file.\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_travel_time
//
// Purpose:    Read in the name of the 
//
// Parameters: fin - the input file stream
//             fout - the output file stream
//
// Calls:      getline, new, peek
//
// Time Comp:  O(n*n) n = number of vertices in the graph
//
// Space Com:  O(n*n) n = number of vertices in the graph
//
//****************************************************************************


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

   while(fin.peek() == '%')
   {  //get rid of comments
      getline(fin, comments);
   }
   
   travel_time = new double*[num_vertices];
   for(int i(0); i < num_vertices; ++i)
   {
      travel_time[i] = new double[num_vertices];
   }

   for(int i(0); i < num_vertices; ++i)
   {
      for(int j(0); j < num_vertices; ++j)
      {
         fin >> travel_time[i][j];
      }
   }
}


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


void Graph::read_existing_links(istream& fin, ostream& fout)
{
   string comments;
   fin.get();

   while(fin.peek() == '%')
   {  //get rid of comments
      getline(fin, comments);
   }
   
   existing_links = new size_t*[num_vertices];
   for(int i(0); i < num_vertices; ++i)
   {
      existing_links[i] = new size_t[num_vertices];
   }
   
   for(int i(0); i < num_vertices; ++i)
   {
      for(int j(0); j < num_vertices; ++j)
      {
         fin >> existing_links[i][j];
      }
   }
}


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


void Graph::read_demand(istream& fin, ostream& fout)
{
   string comments;
   fin.get();

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

   demand = new size_t*[num_vertices];
   for(int i(0); i < num_vertices; ++i)
   {
      demand[i] = new size_t[num_vertices];
   }

   for(int i(0); i < num_vertices; ++i)
   {
      for(int j(0); j < num_vertices; ++j)
      {
         fin >> demand[i][j];
      }
   }
}


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


void Graph::read_cost_of_link(istream& fin, ostream& fout)
{
   string comments;
   fin.get();

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

   cost_of_link = new double*[num_vertices];
   for(int i(0); i < num_vertices; ++i)
   {
      cost_of_link[i] = new double[num_vertices];
   }

   for(int i(0); i < num_vertices; ++i)  //O(n)
   {
      for(int j(0); j < num_vertices; ++j)  //O(n)
      {
         if(!(fin >> cost_of_link[i][j]))
         {
            fout << "Error in input file.\n";
            exit(EXIT_FAILURE);
         }
         
         if(existing_links[i][j] == 0)
         {  //keep a list of all the unmade connections
            cheapest_edges.push_back(Node(i, j, cost_of_link[i][j]));
         }
      }
   }
   //order the list in order of increasing cost
   cheapest_edges.sort();  //O(nlogn)
}


//****************************************************************************
//
// Function:   read_funds_reamining
//
// Purpose:    Read in the name of the
//
// Parameters: fin - the input file stream
//             fout - the output file stream
//
// Calls:      get, getline, new, peek
//
// Time Comp:  O(1)
//
// Space Com:  O(1)
//
//****************************************************************************


void Graph::read_funds_remaining(istream& fin, ostream& fout)
{
   string comments;
   fin.get();

   while(fin.peek() == '%')
   {  //get rid of comments
      getline(fin, comments);
   }
   
   if(!(fin >> funds_remaining))
   {
      fout << "Error in input file.\n";
      exit(EXIT_FAILURE);
   }
}


//******************************************************************************
//
// Function:   get_length
//
// Purpose:    Return the travel time from "from" to "to"
//
// Parameters: from - origin of trip
//             to - destination of trip
//
// Calls:      none
//
// Time Comp:  O(1)
//
// Space Com:  O(1)
//
//******************************************************************************


float Graph::get_length(size_t from, size_t to)
{
   if(existing_links[from][to] == 1)
   {
      return travel_time[from][to];  //return people mins
   }
   else
   {
      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
//
// Time Comp:  O(n*n*n) n = num vertices
//
// 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)
   {  //creat a two diminsional array
      where_from[i] = new size_t[num_vertices];
   }
   
   for(int v(0); v < num_vertices; ++v)  //O(n) runs num_vertices times
   {  //find the shortest path from each vetex to every other one
      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(1)
               {  //this is a shorter path than before
                  dist[w] = dist[u] + get_length(u, w);  //O(1)
                  where_from[v][w] = u;
               }
            }
         }
      }
   }
}


//******************************************************************************
//
// 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:   compute_people_minutes
//
// Purpose:    Computes the people minutes for the railroad network
//
// Parameters: fout - output file stream
//
// Calls:      compute_people_minutes
//
// Time Comp:  O(n*n)
//
// Space Com:  O(n)
//
//******************************************************************************


void Graph::compute_people_minutes(ostream& fout)
{
   people_minutes = 0;
   for(int i(0); i < num_vertices; ++i)
   {
      for(int j(0); j < num_vertices; ++j)
      {  //compute the people minutes for entire network
         people_minutes += (compute_people_minutes(fout, i, j) * demand[i][j]);
      }
   }
}


//******************************************************************************
//
// Function:   compute_people_minutes
//
// Purpose:    Sum all the travel times to get from 1 vertex to all others
//
// Parameters: fout - output file stream
//             from - origin of link
//             to - destination of link
//
// Calls:      compute_people_minutes
//
// Time Comp:  O(n)
//
// Space Com:  O(n) n = number of vertices in the graph
//
//******************************************************************************


double Graph::compute_people_minutes(ostream& fout, size_t from, size_t to)
{
   if(to != from)
   {  //travel time plus travel time from how you got here
      return (travel_time[where_from[from][to]][to] +
              compute_people_minutes(fout, from, where_from[from][to]));
   }
   else
   {  //travel time is zero to yourself
      return 0;
   }
}


//******************************************************************************
//
// Function:   choose_new_connections
//
// Purpose:    Find all the new railroad tracks that you can afford that
//             minimize passenger travel times the most.
//
// Parameters: fin - the input file stream
//             fout - the output file stream
//
// Calls:      shortest_path, compute_people_minutes, front, end, pop_back,
//             begin, static_cast, erase
//
// Time Comp:  O(n*n*n*u) n = number of cities, u = number of links that don't
//                                                  exist; 1 <= u <= n*n
//
// Space com:  O(n*n)
//
//******************************************************************************


void Graph::choose_new_connections(istream& fin, ostream& fout)
{
   shortest_path(cout);  //O(n*n*n)
   compute_people_minutes(cout);  //O(n*n)
   list<Node>::iterator iter;
   list<Node>::iterator min;
   double original_people_minutes = people_minutes;
   double min_people_minutes = people_minutes;
   
   if(cheapest_edges.empty())
   {
      return;
   }
   
   while(funds_remaining >= cheapest_edges.front().cost)
   {
      min = NULL;
      if(cheapest_edges.empty())
      {
         return;
      }
      iter = cheapest_edges.end();
      --iter;
      while(iter -> cost > funds_remaining)
      {  //remove all edges that cost too much
         cheapest_edges.pop_back();  //O(1)
         --iter;
         if(cheapest_edges.empty())
         {
            return;
         }
      }

      for(iter = cheapest_edges.begin(); iter != cheapest_edges.end(); ++iter)
      {  //this for loop runs for however many unmade links between cites
         //there are
         existing_links[iter -> from][iter -> to] = 1;
     
         shortest_path(fout);  //O(n*n*n)
         compute_people_minutes(cout);  //O(n*n)
         
         if(people_minutes < original_people_minutes)
         {
            if(people_minutes < min_people_minutes)
            {
               min_people_minutes = people_minutes;
               min = iter;
            }
         }
         existing_links[iter -> from][iter -> to] = 0;
      }
      
      if(min == NULL)
      {
         return;
      }
      existing_links[min -> from][min -> to] = 1;
      //update the funds_remaining
      funds_remaining -= static_cast<int>(cost_of_link[min -> from][min -> to]);
      //update the shortest path to all cities
      shortest_path(cout);  //O(n*n*n)
      //update the people_minutes
      compute_people_minutes(cout);  //O(n*n)
      original_people_minutes = min_people_minutes = people_minutes;
      
      fout << "Add link from " << names[min -> from] << " to "
           << names[min -> to] << endl << "People minutes:  "
           << people_minutes << "  Remaining Budget:  $" << funds_remaining
           << endl << endl;
           
      cheapest_edges.erase(min);  //O(1)
   }
}