/********************************************************************
  Author:        Dana Vrajitoru, IUSB, CS
  Class:         C243 Data Structures
  File name:     graph.cc
  Last updated:  April 9, 2012.
  Description:   Implementation of the graph class.
*********************************************************************/

#include "graph.h"
#include <fstream>
#include <iostream>
#include <iomanip>
#include <cstring>

// A sort of hash function for the names - works only if the names are
// in sequence, all of them starting with an uppercase, and none of
// them having the same starting letter. Like, 'A', 'B', 'C', etc.
int Graph::index(const string name)
{
  return int(name[0] - 'A');
}

// Default constructor - makes an empty undirected graph.
Graph::Graph(int nv)
{
  nr_vertices = 0;
  nr_edges = 0;
  directed = false;
  if (nv>0)
    init(nv);
}

// Destructor - empty the lists and the vector.
Graph::~Graph()
{
  make_empty();
}

// Starts the graph over.
void Graph::make_empty()
{
  directed = false;
  if (nr_vertices) {
    for (int i=0; i<nr_vertices; i++) 
      vertices[i].neighbors.clear();
    vertices.erase(vertices.begin(), vertices.end());
    nr_vertices = 0;
    nr_edges = 0;
  }
}

// Tells us if the graph is directed.
bool Graph::is_directed()
{
  return directed;
}

// Set the direction flag to directed or undirected.
void Graph::set_directed()
{
  directed = true;
}

void Graph::set_undirected()
{
  directed = false;
}

// Initialize the data structure for the specified number of vertices.
void Graph::init(int nv)
{
  add_vertex(nv-1); // Last index we need
}

// Adds a vertex with the specified index. It also adds all the
// intermediate vertices from the current position to the new one. It
// creates labels with uppercase letters in order.
void Graph::add_vertex(int index)
{
  string s = "A";
  for(int i = nr_vertices; i<=index; i++) {
    s[0] = char('A' + i);
    add_vertex(s);
  }
}

// Adds a vertex with a given name.
void Graph::add_vertex(const string the_name)
{
  vertex new_vertex;
  new_vertex.name = the_name;
  vertices.push_back(new_vertex);
  nr_vertices++;
}

// Adds an edge based on vertex names. If the graph is undirected,
// it adds the edge in both directions.
void Graph::add_edge(char *name1, char *name2)
{
  int index1 = index(string(name1));
  int index2 = index(string(name2));
  if (index1 > nr_vertices)
      add_vertex(index1);
  if (index2 >= nr_vertices)
    add_vertex(index2);
  add_edge(index1, index2);
}

// Adds an edge based on vertex names. If the graph is undirected,
// it adds the edge in both directions.
void Graph::add_edge(const string name1, const string name2)
{
  int index1 = index(name1);
  int index2=index(name2);
  if (index1 >= nr_vertices)
    add_vertex(name1);
  if (index2 >= nr_vertices)
    add_vertex(name2);
  add_edge(index1, index2);
}

// Adds an edge between vertices identified by their index
void Graph::add_edge(const int index1, const int index2)
{
  vertices[index1].neighbors.push_back(index2);
  if (!directed)
    vertices[index2].neighbors.push_back(index1);
  nr_edges++;  
}

// Reads the graph from a file
void Graph::read(const char *filename)
{
  ifstream fin(filename);
  char buffer[20], buffer1[20];
  int nrv;
  fin >> buffer; // U or D
  if (buffer[0] == 'd' || buffer[0] == 'D')  
    directed=true;
  fin >> nrv;
  for (int i=0; i<nrv; i++) {
    fin >> buffer; // vertex name
    add_vertex(string(buffer));
  }
  while (!fin.eof() && fin.good()) {
    fin >> buffer;
    if (strlen(buffer) && fin.good())
      fin >> buffer1;
    if (strlen(buffer) && strlen(buffer1) && fin.good()) {
      buffer[strlen(buffer)-1]='\0'; // Deleting the ','
      add_edge(string(buffer), string(buffer1));
    }
  }
  fin.close();
}

// Simple print of the graph.
void Graph::print()
{
  int i;
  if (directed)
    cout << "The graph is directed" << endl;
  else
    cout << "The graph is undirected" << endl;
  cout << "The graph contains " << nr_vertices
       << " vertices and " << nr_edges << " edges" << endl;
  if (nr_vertices) {
    cout << "The vertex names are: ";
    for (i=0; i<nr_vertices; i++)
      cout << vertices[i].name << ' ';
    cout << endl 
	 << "The adjacency list for each vertex is:" << endl;
    for (i=0; i<nr_vertices; i++) {
      cout << "vertex " << i << ": ";
      list<int>::iterator iter;
      iter = vertices[i].neighbors.begin();
      while (iter != vertices[i].neighbors.end()) {
	cout << *iter << ' ';
	iter++;
      }
      cout << endl;
    }
  }
}

// Functions to be implemented by the students.

// Writes the graph to a file that is compatible with the function read.
void Graph::write(const char *filename)
{
  ; // The student must supply the code.
}

// Inputs a graph from the user. First it should ask for the number of
// vertices, then call the function init with the number of vertices
// to automatically generate the labels as uppercase letters, and then
// ask the use to input the edges. The user will be expected to enter
// uppercase letters to identify the edges, and anything else should
// end the input process.
void Graph::input()
{
  ; // The student must supply the code.
}

// Print the graph in depth-first and breadth-first order. Implement
// one of these two functions.
void Graph::print_df()
{
  ; // The student must supply the code.
}

void Graph::print_bf()
{
  ; // The student must supply the code.
}