#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include <time.h>
#include <string.h>

/* gcc -std=gnu99 gnk.c -o gnk */

/* Utils */
void init_random_generator(){
  struct timespec time;
  clock_gettime(CLOCK_REALTIME, &time);
  srandom(time.tv_nsec ^ time.tv_sec);
}

/* Uniform integer [0..n-1], 
 * Based on a nonlinear additive feedback random number generator, 
 * period ~ 16 * ((2^31) - 1), and lower bits are safe. 
 * For better randomness, use /dev/random (slower).
 */
int uniform(int n){
  return random() % n;
}

// Linear search
bool in(int* tab, int len, int value){
  for(int i=0; i<len; i++)
    if(tab[i] == value)
      return true;
  return false;
}

void swp(int* tab, int len, int value){         // Swap (=erase) with last
  if(tab[len-1] != value){
    for(int i=0; i<len; i++)
      if(tab[i] == value)
        tab[i] = tab[len-1];
  }
}

/* K-out graphs */
typedef struct {
  int n, k; int** succ;                       // Graph
  int* indeg; int** pred; int* predlen;       // Extra-info : predecessor's list
  int* dist;                                  // Local buffer, used for comp.
}* gnk;

gnk allocate_graph(int n, int k){
  gnk g;
  g = malloc(sizeof(*g));
  g->n = n; g->k = k;
  g->predlen = (int*)malloc(n*sizeof(int));
  g->indeg = (int*)malloc(n*sizeof(int));
  g->dist = (int*)malloc(n*sizeof(int));
  g->succ = (int**)malloc(n*sizeof(int*));
  g->pred = (int**)malloc(n*sizeof(int*));
  for(int v=0; v<g->n; v++){
    g->succ[v] = (int*)malloc(sizeof(int)*k);
    g->pred[v] = (int*)malloc(sizeof(int));
    g->predlen[v] = 1;
  }
  return g;
}

void deallocate_graph(gnk g){
  for(int v=0; v<g->n; v++){
    free(g->succ[v]);
    free(g->pred[v]);
  }
  free(g->indeg); free(g->predlen); free(g->dist);
  free(g->succ); free(g->pred);
  free(g);
}

void duplicate_graph(gnk g, gnk g2){
  g2->n = g->n;
  memcpy(g2->predlen, g->predlen, sizeof(int)*g->n);
  memcpy(g2->indeg, g->indeg, sizeof(int)*g->n);
  for(int v=0; v<g->n; v++){
    memcpy(g2->succ[v], g->succ[v], sizeof(int)*g->k);
    g2->pred[v] = realloc(g2->pred[v], g->predlen[v]*sizeof(int));
    memcpy(g2->pred[v], g->pred[v], sizeof(int)*g->indeg[v]);
  }
}

void add_pred_graph(gnk g, int x, int v){
  if(g->indeg[x] == g->predlen[x]){
    g->predlen[x] *= 2;
    g->pred[x] = realloc(g->pred[x],g->predlen[x]*sizeof(int));
  }
  g->pred[x][g->indeg[x]++] = v;
}

void print_graph(gnk g){
  printf("Graph, n=%d, k=%d:\n", g->n, g->k);
  for(int v=0; v<g->n; v++){
    printf("%d -> ", v);
    for(int i=0; i<g->k; i++)
      printf("%d ", g->succ[v][i]);
    printf("\n");
    printf("%d <- ", v);
    for(int j=0; j<g->indeg[v]; j++)
      printf("%d ", g->pred[v][j]);
    printf("\n");
  }
}

/* Random Generation */
bool bernoulli(int a, int b){   // bernoulli(a/b)
  return uniform(b) < a;
}

int binomial(int n, int k){     // bin(n,k/n) slow but sufficient implementation
  int successes = 0;
  for(int i=0; i<n; i++)
    successes += bernoulli(k, n);
  return successes;
}

int random_vertex_avoiding(gnk g, int* tab, int v, int k){
  int x;
  do{x = uniform(g->n);} while(x == v || in(tab, k, x));
  return x;
}


void random_k_subset(gnk g, int v){
  for(int i=0; i<g->k; i++){
    g->succ[v][i] = random_vertex_avoiding(g, g->succ[v], v, i);
    add_pred_graph(g,g->succ[v][i],v);
  }
}

void generate_gnk(gnk g, int n){
  g->n = n;
  memset(g->indeg, 0, sizeof(int)*g->n);
  for(int v=0; v<g->n; v++)             // Generate Succcessors & Predecessors
    random_k_subset(g, v);
}

/* Update Algorithms 
 * Delete u the last vertex (swap neighborhoods and rename otherwise)
 * Insert u as the last vertex
 */

void delete(gnk g, int u){
  for(int i=0; i<g->k; i++){
    int v = g->succ[u][i];
    swp(g->pred[v], g->indeg[v], u);
    g->indeg[v]--;
  }
  g->n--;
}

void deletion_nat(gnk g){
  int u = g->n-1;
  delete(g,u);

  for(int i=0; i<g->indeg[u]; i++){
    int v = g->pred[u][i];
    swp(g->succ[v], g->k, u);
    g->succ[v][g->k-1] = random_vertex_avoiding(g, g->succ[v], v, g->k-1);
    add_pred_graph(g,g->succ[v][g->k-1],v);
  }
}

void propose_vertex_or_rva(gnk g, int v, int i, int proposition){
  if(proposition != v && !in(g->succ[v], g->k-1, proposition))
    g->succ[v][g->k-1] = proposition;
  else
    g->succ[v][g->k-1] = random_vertex_avoiding(g, g->succ[v], v, g->k-1);
}

void deletion_succ(gnk g){
  int u = g->n-1;
  delete(g,u);

  for(int i=0; i<g->indeg[u]; i++){
    int v = g->pred[u][i];
    swp(g->succ[v], g->k, u);

    int proposition = v;
    if(i < g->k){
      if(bernoulli(i, g->n))
        proposition = g->succ[u][uniform(i)];
      else
        proposition = g->succ[u][i];
    }
    
    propose_vertex_or_rva(g,v,g->k-1,proposition);
    add_pred_graph(g,g->succ[v][g->k-1],v);
  }
}

void deletion_pred(gnk g){
  int u = g->n-1;
  delete(g,u);
  
  int candidates[g->indeg[u]-1], nb_candidates;

  for(int i=0; i<g->indeg[u]; i++){
    int v = g->pred[u][i];
    swp(g->succ[v], g->k, u);

    if(i == g->indeg[u]-1)
      propose_vertex_or_rva(g,v,g->k-1,g->succ[u][uniform(g->k)]);
    else{
      nb_candidates = 0;
      for(int j=0;j<i;j++)
        if(g->pred[u][j] != v && !in(g->succ[v], g->k-1, g->pred[u][j]))
          candidates[nb_candidates++] = g->pred[u][j];
      if(bernoulli(nb_candidates, g->n-g->k))
        g->succ[v][g->k-1] = candidates[uniform(nb_candidates)];
      else
        propose_vertex_or_rva(g,v,g->k-1,g->pred[u][i+1]);
    }
    
    add_pred_graph(g,g->succ[v][g->k-1],v);
  }
}

void insertion_nat(gnk g, int l){
  int u = g->n;
  g->n++;
  random_k_subset(g, u);
  g->indeg[u] = 0;

  while(g->indeg[u] != l){
    int v = random_vertex_avoiding(g, g->pred[u], u, g->indeg[u]);
    g->succ[v][uniform(g->k)] = u;
    add_pred_graph(g,u,v);
  }
}

void insertion_succ(gnk g, int l){
  int u = g->n;
  g->indeg[u] = 0;
  int j = 0;
  int candidates[g->k], nb_candidates;

  while(g->indeg[u] != l){
    int v = random_vertex_avoiding(g, g->pred[u], u, g->indeg[u]);
    add_pred_graph(g,u,v);
    
    int x = uniform(g->k), w = g->succ[v][x];
    g->succ[v][x] = g->succ[v][g->k-1];
    g->succ[v][g->k-1] = u;
    
    if(j < g->k){
      nb_candidates = 0;
      if(!in(g->succ[u], j, v))
        candidates[nb_candidates++] = v;
      for(int i=0; i<g->k-1; i++)
        if(!in(g->succ[u], j, g->succ[v][i]))
          candidates[nb_candidates++] = g->succ[v][i];
      if(bernoulli(nb_candidates,g->n-j))
        g->succ[u][j] = candidates[uniform(nb_candidates)];
      else 
        propose_vertex_or_rva(g,u,j,w);
      add_pred_graph(g,g->succ[u][j],u);
      j++;
    }
  }
  
  for(int i=j; i<g->k; i++){
    g->succ[u][i] = random_vertex_avoiding(g, g->succ[u], u, i);
    add_pred_graph(g,g->succ[u][i],u);
  }
  
  g->n++;
}

void insertion_pred(gnk g, int l){
  int u = g->n;
  g->indeg[u] = 0;
  int candidates[g->k], nb_candidates;
  
  int x = uniform(g->n);

  while(g->indeg[u] != l){
    add_pred_graph(g,u,x);
    
    int d = uniform(g->k), w = g->succ[x][d];
    g->succ[x][d] = g->succ[x][g->k-1];
    g->succ[x][g->k-1] = u;
    
    if(g->indeg[u] < l){
      nb_candidates = 0;
      for(int i=0; i<g->k-1; i++)
        if(!in(g->pred[u], g->indeg[u], g->succ[x][i]))
          candidates[nb_candidates++] = g->succ[x][i];
      if(bernoulli(nb_candidates,g->n-g->indeg[u]))
        x = candidates[uniform(nb_candidates)];
      else{
        x = w;
        while(in(g->pred[u],g->indeg[u],x) || in(candidates,nb_candidates,x))
          x = uniform(g->n);
      }
    }
    else if(bernoulli(g->k, g->n)){
      int d = uniform(g->k);
      if(d != g->k-1)
        x = g->succ[x][d];
    }
    else
      x = w;
  }
  
  g->succ[u][0] = x;
  add_pred_graph(g,g->succ[u][0],u);
  
  for(int i=1; i<g->k; i++){
    g->succ[u][i] = random_vertex_avoiding(g, g->succ[u], u, i);
    add_pred_graph(g,g->succ[u][i],u);
  }
  
  g->n++;
}



/* Stats */

// Perform a bfs in the udnerlying undirected graph
void bfs(gnk g, int u){
  int queue[g->n], top = 0, bot = 0;
  memset(g->dist, -1, sizeof(int)*g->n);
  g->dist[u] = 0;
  queue[top++] = u;
    
  while(bot < top){
    int v = queue[bot++];
    
    for(int i=0; i<g->k; i++){                  /* Successors */
      int x = g->succ[v][i];
      if(g->dist[x] == -1){
        g->dist[x] = g->dist[v]+1;
        queue[top++] = x;
      }
    }
    
    for(int i=0; i<g->indeg[v]; i++){           /* Predecessors */
      int x = g->pred[v][i];
      if(g->dist[x] == -1){
        g->dist[x] = g->dist[v]+1;
        queue[top++] = x;
      }
    }
  }
}

int diameter(gnk g){
  int diameter = -1;
  for(int u=0; u<g->n; u++){
    bfs(g,u);                      
    for(int v=u+1; v<g->n; v++)                   
      if(g->dist[v] == -1)                      /* Disconnected */
        return -1;
      else if(g->dist[v] > diameter)
        diameter = g->dist[v];
  }
  return diameter; 
}

void print_distances_stats(gnk g[4]){
  int d1[3] = {0,0,0}, d2[3] = {0,0,0}, d3[3] = {0,0,0};
  for(int u=0; u<g[1]->n; u++){
    for(int i=0; i<4; i++)
      bfs(g[i],u);
    for(int v=u+1; v<g[1]->n; v++)
      for(int i=0; i<3; i++){
        d1[i] += (g[0]->dist[v] != g[i+1]->dist[v]);
        d2[i] += abs(g[0]->dist[v]-g[i+1]->dist[v]);
        d3[i] += (abs(g[0]->dist[v]-g[i+1]->dist[v]) > 1);
      }
  }
  printf("%d %d %d %d %d %d %d %d %d\n", \
  d1[0],d1[1],d1[2], d2[0],d2[1],d2[2], d3[0],d3[1],d3[2]);
}

/* Main test */

int main(int argc, char** argv){
  init_random_generator();
  
  if(argc < 4){
    printf("usage: %s n k 'd'/'s'/'i' [m]\n", argv[0]);
    printf("n number of nodes\n");
    printf("k out-degree\n");
    printf("d diameter computation \n");
    printf("s distances' modifications after deletion\n");
    printf("i distances' modifications after insertion\n");
    printf("m number of simulations (default 1)\n");
    printf("example : %s 10 2 d\n", argv[0]);
    return EXIT_FAILURE;
  }
  
  int n = atoi(argv[1]), k = atoi(argv[2]), m = 1;
  if(n < k+1){
    printf("error: n < k+1 \n");
    return EXIT_FAILURE;
  }
  if(argc >= 5) 
    m = atoi(argv[4]);

  gnk g[4]; 
  for(int i=0; i<4; i++)
    g[i] = allocate_graph(n, k);
  
  for(int i=0; i<m; i++){
    switch(argv[3][0]){
      case 'd':
        generate_gnk(g[0], n); 
        printf("%d\n", diameter(g[0]));
      break;
      case 's':
        generate_gnk(g[0], n); 
        for(int i=1; i<4; i++)
          duplicate_graph(g[0], g[i]);
        printf("%d ", g[0]->indeg[g[0]->n-1]);
        deletion_nat(g[1]); 
        deletion_succ(g[2]);
        deletion_pred(g[3]); 
        print_distances_stats(g);
      break;
      case 'i':
        generate_gnk(g[0], n-1); 
        for(int i=1; i<4; i++)
          duplicate_graph(g[0], g[i]);
        int l = binomial(n-1, k);
        printf("%d ", l);
        insertion_nat(g[1],l); 
        insertion_succ(g[2],l);
        insertion_pred(g[3],l);
        print_distances_stats(g);
      break;
    }
    fflush(stdout);
  }
  
  for(int i=0; i<4; i++)
    deallocate_graph(g[i]);

  return EXIT_SUCCESS;
}