// Project 4 main program.

#include <iostream>
#include <sstream>
#include <fstream>
#include <limits>
#include <string>
#include <vector>

#include "graph.h"

std::string exec_name;

void
usage_error()
{
  std::cerr << "usage: " << exec_name << " datafile" << std::endl;
  exit(1);
}


// Vertices will contain the name of the city;
// edges will contain the distance between cities.

typedef std::string vertex;
typedef double edge;


// Notice that the city_graph will be complete and the mst_graph
// will be sparse, so we probably want two different representations.

typedef graph<vertex, edge> city_graph;
typedef graph<vertex, edge> mst_graph;



// Read in the data.

city_graph &
read_data(std::istream & infile)
{
  // Read in the number of cities.
  int ncities = 0;
  infile >> ncities;
  city_graph * g = new city_graph(ncities);

  // Get the city name and distance information.
  for (int current = 0; current < ncities; ++current)
  {
    // Get the name of the city.
    char city[100];
    infile.ignore(std::numeric_limits<int>::max(), '\n');
    infile.getline(city, 100);
    g->vertex(current) = std::string(city);

    // Get the distances to the other cities.
    // Remember that the distance to the city itself (zero) is missing.
    double dist;
    for (int i=0; i < ncities; ++i)
    {
      if (current == i)
	dist = 0.0;
      else
	infile >> dist;
      g->add_edge(dist, current, i);
    }
  }

  return *g;
}



// Find and return a minimum spanning tree using Prim's algorithm.

mst_graph &
find_mst(city_graph & g)
{
  mst_graph * mst = new mst_graph(g.vsize());
  // FILL IN HERE.
  return *mst;
}



// Print the edges in a min. spanning tree and its total cost.

void
print_mst(mst_graph & mst)
{
  // FILL IN HERE.
}



// Find and return a TSP tour, given a minimum spanning tree.

std::vector<int> & 
find_tour(mst_graph & mst)
{
  std::vector<int> * tour = new std::vector<int>;
  // FILL IN HERE.
  return *tour;
}



// Print the tour and its total cost.

void
print_tour(std::vector<int> & tour, city_graph & g)
{
  double total = 0;
  int last = 0;
  int n = tour.size();
  tour.push_back(last); // Add return city at end.
  while (n--)
  {
    std::cout << g.vertex(tour[last]) << std::endl;
    int next = last + 1;
    total += g.edge(tour[last], tour[next]);
    last = next;
  }
  std::cout << "Total length is " << total << std::endl;
}



// Main program.

void
main(int argc, char * argv[])
{
  exec_name = argv[0];
  if (argc != 2)
    usage_error();

  std::ifstream infile(argv[1], std::ios_base::in|std::ios_base::binary);
  if (!infile)
  {
    std::cerr << "error opening input file: " << argv[1] << std::endl;
    exit(1);
  }

  city_graph g = read_data(infile);
  mst_graph mst = find_mst(g);
  print_mst(mst);
  std::vector<int> tour = find_tour(mst);
  print_tour(tour, g);
}