#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "List.h"
#include "Graph.h"


#define NIL 0
#define WHITE 0
#define GREY 1
#define BLACK 2

typedef struct Graph{
  int Vert;
  ListRef *adj;
  int *color;
  int *par;
  int *disc;
  int *fin;
  int time;
}Graph;

void DFSVisit(GraphRef G, int u, ListRef S);

/* Constructors-Destructors */
GraphRef newGraph(int n){
  GraphRef G = malloc(sizeof(Graph));
  G->Vert = n;
  G->adj = malloc(sizeof(ListRef) * (n+1));
  G->color = malloc(sizeof(int)* (n+1));
  int i;
  for(i =1; i < n+1; i++){
    G->color[i] = WHITE;
  }
  G->par = malloc(sizeof(int)  * (n+1));
  G->disc = malloc(sizeof(int) * (n+1));
  G->fin = malloc(sizeof(int)  * (n+1));
  G->time = 0;
  return G;
};
void freeGraph(GraphRef *G){
  assert(G != NULL);
  free((*G)->adj);
  free((*G)->color);
  free((*G)->par);
  free((*G)->disc);
  free((*G)->fin);
  (*G)->Vert = NULL;
  free(G);

};
/* Access functions */
int getOrder(GraphRef G){
  return G->Vert;
}

int getParent(GraphRef G, int u){ /* Pre: 1<=u<=n=getOrder(G) */
  assert(G != NULL);
  if(1 <=u && u<= getOrder(G)){
    return G->par[u];
  }else{
    return NIL;
  }
}

int getDiscover(GraphRef G, int u){ /* Pre: 1<=u<=n=getOrder(G) */
  assert(G != NULL);
  if(u <= getOrder(G)){
    return G->disc[u];
  }else{
    return 0;
  }
}
int getFinish(GraphRef G, int u){ /* Pre: 1<=u<=n=getOrder(G) */
  assert(G != NULL);
  if(u<=getOrder(G)){
    return G->fin[u];
  }else{
    return 0;
  }
}
/* Manipulation procedures */
void addDirectedEdge(GraphRef G, int u, int v){ /* Pre: 1<=u<=n, 1<=v<=n */
  assert(G != NULL);
  if(1 <= u && u <= getOrder(G) && 1<= v && v <= getOrder(G)){
    printf("before insert\n");
    insertAfterLast(G->adj[u], v);
    printf("after insert\n");
  }
}
void DFS(GraphRef G, ListRef S){ /* Pre: getLength(S)==getOrder(G) */
  if(getLength(S)==getOrder(G)){
    ListRef copy = copyList(S);
    int i;
    for(i =1; i <= getOrder(G); i++){
      G->color[i] = WHITE;
      G->par[i] = NIL;
    }
    for(moveFirst(copy); !offEnd(copy); moveNext(copy)){
      int u = getCurrent(copy);
      if(G->color[i]==WHITE){
        DFSVisit(G,u,S);
      }
    }
  }
}
void DFSVisit(GraphRef G, int u, ListRef S){
  G->color[u] = GREY;
  G->time++;
  G->disc[u] =G->time++;
  ListRef listu = G->adj[u];
  for(moveFirst(listu); !offEnd(listu); moveNext(listu)){
    int v = getCurrent(listu);
    if(G->color[v]== WHITE){
      G->par[v] = u;
      DFSVisit(G,v,S);
    }
    G->color[u]=BLACK;
    G->time++;
    G->fin[u]=G->time++;
    insertBeforeFirst(S,u);
  }
}
/* Other Functions */
GraphRef transpose(GraphRef G){
  assert(G != NULL);
  GraphRef G2 = newGraph(getOrder(G));
  ListRef listu = newList();
  int par;
  int i;
  for(i = 1; i <= getOrder(G); i++){
    par = i;
    listu = G->adj[i];
    for(moveFirst(G->adj[i]); !offEnd(G->adj[i]); moveNext(G->adj[i])){
      int u = getCurrent(G->adj[i]);
      addDirectedEdge(G2, u, par);
    }
  }
  return G2;
}
GraphRef copyGraph(GraphRef G){
  assert(G != NULL);
  GraphRef copy = newGraph(getOrder(G));
  int n = getOrder(G);
  int i;
  for(i =1; i <= getOrder(G); i++){
   copy->adj[i] = copyList(G->adj[i]);
  }
  copy->par = malloc(sizeof(int)* (n+1));
  copy->disc = malloc(sizeof(int)* (n+1));
  copy->fin = malloc(sizeof(int)* (n+1));
  copy->time = G->time;
  return copy;
}
void printGraph(FILE* out , GraphRef G){
  assert(G != NULL);
  ListRef P;
  int i;
  for(i=1; i <= getOrder(G); i ++){
    fprintf(out, "%d:", i);
    P = G->adj[i];
    printList(out, P);
    fprintf(out, "\n");
  }

}