#include "Graph.h"
#include <iostream>
#include <fstream>
#include <sstream>

typedef std::ifstream     ifstream;
typedef std::ofstream     ofstream;
typedef std::stringstream sstream;
typedef std::exception    exception;

class graphm : public Graph {
  private:
    int numVertex, numEdge, *edge, *mark;

    int calcEdge(int v1, int v2) {
      int e = (v1 > v2) ? v1 * (v1 - 1) / 2 + v2 : v2 * (v2 - 1) / 2 + v1;
      return e;
    }

  public:
    graphm(int numVert) {
      Init(numVert);
    }

    ~graphm() {
      delete[] edge;
      delete[] mark;
    }

    void Init(int n) {
      int i, e;

      numVertex = n;
      numEdge   = 0;

      // Use negative weight to represent no edge for Kruskal's algorithm
      e    = n * (n - 1) / 2;
      edge = new int[e];
      for (i = 0; i < e; i++) {
        edge[i] = -1;
      }

      // Use -1 to represent UNVISITED
      mark = new int[n];
      for (i = 0; i < n; i++) {
        mark[i] = -1;
      }
    }

    int n() {
      return numVertex;
    }

    int e() {
      return numEdge;
    }

    int first(int v) {
      int i, e;

      for (i = 0; i < numVertex; i++) {
        if (i == v) {
          continue;
        }

        e = calcEdge(v, i);

        if (edge[e] != -1) {
          return i;
        }
      }

      return numVertex;
    }

    int next(int v, int w) {
      int i, e;

      for (i = w + 1; i < numVertex; i++) {
        if (i == v) {
          continue;
        }

        e = calcEdge(v, i);

        if (edge[e] != -1) {
          return i;
        }
      }

      return numVertex;
    }

    void setEdge(int v1, int v2, int wt) {
      if (!(wt > -1)) {
        std::cerr << "Illegal weight value" << std::endl;
        exit(1);
      }

      if (v1 == v2) {
        return;
      }

      int e = calcEdge(v1, v2);

      if (edge[e] == -1) {
        numEdge++;
      }
      edge[e] = wt;
    }

    void delEdge(int v1, int v2) {
      if (v1 == v2) {
        return;
      }

      int e = calcEdge(v1, v2);

      if (edge[e] != -1) {
        numEdge--;
      }
      edge[e] = -1;
    }

    bool isEdge(int i, int j) {
      if (i == j) {
        return false;
      }
      return edge[calcEdge(i, j)] != -1;
    }

    int weight(int v1, int v2) {
      if (v1 == v2) {
        return -1;
      }
      return edge[calcEdge(v1, v2)];
    }

    int getMark(int v) {
      return mark[v];
    }

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

/*
*   File format:
*     numVertex
*     list of all weights in order (0,0) ... (n,n), separated by spaces
*     list of all marks in order 0 ... n, separated by spaces
*
*   Example:
*     5
*     -1 3 -1 -1 -1 3 -1 -1 1 1 -1 -1 -1 -1 0 -1 1 -1 -1 -1 -1 1 0 -1 -1
*     -1 -1 -1 -1 -1
*/

Graph *create_graph()   // creates empty graph (to be later initialized with Init method)
{
    Graph *x = new graphm(0);
    return x;
}

Graph* read_graph(string filename) {
  try {
    int      i, j, w;
    ifstream ifs;
    string   s;
    graphm*  g;
    sstream  ss1, ss2;

    ifs.open(filename);

    // Read in the number of vertices
    getline(ifs, s);
    g = new graphm(std::stoi(s));

    // Read in the list of weights and parse to set edges
    getline(ifs, s);
    ss1.str(s);
    for (i = 0; i < g->n(); i++) {
      for (j = 0; j < g->n(); j++) {
        ss1 >> s;
        w = std::stoi(s);
        if (w == -1) {
          continue;
        }
        g->setEdge(i, j, w);
      }
    }

    // Read in the list of marks and parse to set marks
    getline(ifs, s);
    ss2.str(s);
    for (i = 0; i < g->n(); i++) {
      ss2 >> s;
      g->setMark(i, std::stoi(s));
    }

    ifs.close();

    return (Graph*) g;
  }
  catch (exception e) {
    return NULL;
  }
}


bool write_graph(Graph* g, string filename) {
  try {
    int      i, j;
    ofstream ofs;

    ofs.open(filename);

    // Write out the number of vertices
    ofs << g->n() << std::endl;

    // Write out a list of all the weights
    for (i = 0; i < g->n(); i++) {
      for (j = 0; j < g->n(); j++) {
        ofs << g->weight(i, j) << ' ';
      }
    }
    ofs << std::endl;

    // Write out a list of all the marks
    for (i = 0; i < g->n(); i++) {
      ofs << g->getMark(i) << ' ';
    }
    ofs << std::endl;

    ofs.close();

    return true;
  }
  catch (exception e) {
    return false;
  }
}