// From the software distribution accompanying the textbook
// "A Practical Introduction to Data Structures and Algorithm Analysis,
// Third Edition" by Clifford A. Shaffer, Prentice Hall, 2007.
// Source code Copyright (C) 2006 by Clifford A. Shaffer.

#include <stdio.h>
#include <ctype.h>

// Used by the mark array
#define UNVISITED 0
#define VISITED 1

#include "graph.h"

// Implementation for the adjacency matrix representation
class Graphm : public Graph {
private:
  int numVertex, numEdge; // Store number of vertices, edges
  int **matrix;           // Pointer to adjacency matrix
  int *mark;              // Pointer to mark array
public:
  Graphm(int numVert) {   // Make graph w/ numVert vertices
    int i, j;
    numVertex = numVert;
    numEdge = 0;
    mark = new int[numVert];     // Initialize mark array
    for (i=0; i<numVertex; i++)
      mark[i] = UNVISITED;
    matrix = (int**) new int*[numVertex]; // Make matrix
    for (i=0; i<numVertex; i++)
      matrix[i] = new int[numVertex];
    for (i=0; i< numVertex; i++) // Initialize to 0 weights
      for (int j=0; j<numVertex; j++)
        matrix[i][j] = 0;
  }

  ~Graphm() {       // Destructor
    delete [] mark; // Return dynamically allocated memory
    for (int i=0; i<numVertex; i++)
      delete [] matrix[i];
    delete [] matrix;
  }

  int n() { return numVertex; } // Number of vertices
  int e() { return numEdge; }   // Number of edges

  // Set edge (v1, v2) to wgt
  void setEdge(int v1, int v2, int wgt) {
    Assert(wgt>0, "Illegal weight value");
    if (matrix[v1][v2] == 0)
      numEdge++;                // Increment edge count
    matrix[v1][v2] = wgt;
  }

  void delEdge(int v1, int v2) { // Delete edge (v1, v2)
    if (matrix[v1][v2] != 0) numEdge--;
    matrix[v1][v2] = 0;
  }

  int weight(int v1, int v2) { return matrix[v1][v2]; }
  int getMark(int v) { return mark[v]; }
  void setMark(int v, int val) { mark[v] = val; }

  // Return v's first neighbor
  int first(int v) {
    for (int i=0; i<numVertex; i++)
      if (matrix[v][i] != 0)
        return i;
    return numVertex;           // Return n if none
  }

  // Return v1's next neighbor after v2
  int next(int v1, int v2) {
    for(int i=v2+1; i<numVertex; i++)
      if (matrix[v1][i] != 0)
        return i;
    return numVertex;           // Return n if none
  }

};

// Functions for creating and printing graphs

#define LINELEN 80

void Gprint(Graph* G) {
  int i, j;

  cout << "Number of vertices is " << G->n() << "\n";
  cout << "Number of edges is " << G->e() << "\n";

  cout << "Matrix is:\n";
  for (i=0; i<G->n(); i++) {
    for(j=0; j<G->n(); j++)
      cout << G->weight(i, j) << " ";
    cout << "\n";
  }
}


char* getl(char* buffer, int n, FILE* fid) {
  char* ptr;
  ptr = fgets(buffer, n, fid);
  while ((ptr != NULL) && (buffer[0] == '#'))
    ptr = fgets(buffer, n, fid);
  return ptr;
}


// Create a graph from file fid
template <class GType>
Graph* createGraph(FILE* fid) {
  char buffer[LINELEN+1]; // Line buffer for reading
  bool undirected;  // true if graph is undirected, false if directed
  int i;
  int v1, v2, dist;

  if (getl(buffer, LINELEN, fid) == NULL) // Unable to get number of vertices
{ cout << "Unable to read number of vertices\n";
    return NULL;
}

  Graph* G = new GType(atoi(buffer));

  if (getl(buffer, LINELEN, fid) == NULL) // Unable to get graph type
{ cout << "Unable to read graph type\n";
    return NULL ;
}
  if (buffer[0] == 'U')
    undirected = true;
  else if (buffer[0] == 'D')
    undirected = false;
  else {
    cout << "Bad graph type: |" << buffer << "|\n";
    return NULL;
  }

  // Read in edges
  while (getl(buffer, LINELEN, fid) != NULL) {
    v1 = atoi(buffer);
    i = 0;
    while (isdigit(buffer[i])) i++;
    while (buffer[i] == ' ') i++;
    v2 = atoi(&buffer[i]);
    while (isdigit(buffer[i])) i++;
    if (buffer[i] == ' ') { // There is a distance
      while (buffer[i] == ' ') i++;
      dist = atoi(&buffer[i]);
    }
    else dist = 1;
    G->setEdge(v1, v2, dist);
    if (undirected) // Put in edge in other direction
      G->setEdge(v2, v1, dist);
  }
  return G;
}