// 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 this file to access Graph representation implemented using an
// Adjacency List

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

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

#include "link.ht"
#include "llist.ht"

#include "graph.h"


// Edge implementation for adjacency list
class Edge {
public:
  int vertex, weight;
  Edge() { vertex = -1; weight = -1; }
  Edge(int v, int w) { vertex = v; weight = w; }
};

// Overload for the Edge << operator
ostream& operator << (ostream& s, Edge e)
  { return(s << "(" << e.vertex << ", " << e.weight << ")"); }

// Implementation for the adjacency list representation
class Graphl : public Graph {
private:
  int numVertex, numEdge;     // Number of vertices, edges
  List<Edge>** vertex; // List headers
  int *mark;                  // Pointer to mark array
public:
  Graphl(int numVert) { // Make graph with 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;
    // Create and initialize adjacency lists
    vertex = (List<Edge>**) new List<Edge>*[numVertex];
    for (i=0; i<numVertex; i++)
      vertex[i] = new LList<Edge>();
  }

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

  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");
    Edge it(v2, wgt);
    Edge curr;
    vertex[v1]->getValue(curr);
    // If not already at v2, we must search from the start
    if (curr.vertex != v2)
      for (vertex[v1]->setStart();
           vertex[v1]->getValue(curr); vertex[v1]->next())
        if (curr.vertex >= v2) break;
    if (curr.vertex == v2)   // Edge (v1, v2) already exists
      vertex[v1]->remove(curr); // So clear out existing one
    else numEdge++;             // Otherwise, add a new edge
    vertex[v1]->insert(it);
  }

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

  void delEdge(int v1, int v2) { // Delete edge (v1, v2)
    Edge curr;
    vertex[v1]->getValue(curr);
    if (curr.vertex != v2)         // If not already at v2,
      for (vertex[v1]->setStart(); //   search for the start
           vertex[v1]->getValue(curr); vertex[v1]->next())
        if (curr.vertex >= v2) break;
    // If not at v2 now, then there is no edge (v1, v2)
    if (curr.vertex == v2) {
      vertex[v1]->remove(curr);
      numEdge--;
    }
  }

  int weight(int v1, int v2) { // Return weight of (v1, v2)
    Edge curr;
    vertex[v1]->getValue(curr);
    if (curr.vertex != v2)         // If not already at v2,
      for (vertex[v1]->setStart(); //   search for the start
           vertex[v1]->getValue(curr); vertex[v1]->next())
        if (curr.vertex >= v2) break;
    if (curr.vertex == v2)
      return curr.weight;
    else   // If not at v2 now, there is no edge (v1, v2)
      return 0; // Weight is 0 if (v1, v2) does not exist
  }

  int first(int v) { // Return first neighbor of v
    Edge it;
    vertex[v]->setStart();
    if (vertex[v]->getValue(it)) return it.vertex;
    else return numVertex;      // Return n if none
  }

  int next(int v1, int v2) { // Get v1's neighbor after v2
    Edge it;
    vertex[v1]->getValue(it);
    if (it.vertex == v2)     // Can just get next vertex
      vertex[v1]->next();
    else { // Must start from beginning of list and search
      vertex[v1]->setStart();
      while (vertex[v1]->getValue(it) && (it.vertex <= v2))
        vertex[v1]->next();
    }
    if (vertex[v1]->getValue(it)) return it.vertex;
    else 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;
}