// 15-210, example code
// Extracted from real code...might be some typos in translation

#include "utils.h"
#include "sequence.h"
using namespace std;

struct nonNegF{bool operator() (int a) {return (a>=0);}};

struct vertex {
  int* Ngh;
  int d;
};

struct graph {
  vertex *V;
  int n;
  int m;
};

// Does a BFS starting at s, and returns the number of rounds
// and a parent array (every vertex points to its parent in the BFS tree)
pair<int,int*> BFS(int s, graph GA) {
  int n = GA.n;
  int m = GA.m;
  vertex *G = GA.V;

  int* X = new int[n];  // Visited
  int* F = new int[m];  // Frontier
  int* Ftmp = new int[m];  // Temporary Frontier
  int* C = new int[n];    // Counts

  cilk_for(int i = 0; i < n; i++) X[i] = -1;

  F[0] = s;
  int Fsize = 1;
  X[s] = s;
  int r = 0;

  while (Fsize > 0) {
    r++;

    // Get the degrees of the frontier vertices
    cilk_for (int i=0; i < Fsize; i++) 
	C[i] = G[F[i]].d;

    // Get offsets for each vertex by doing a plus scan on the degrees
    // Result of scan is written back to C, and total sum is returned as nr
    int nr = plusScan(C,Fsize);

    // For each vertex in the frontier try to "hook" unvisited neighbors.
    cilk_for(int i = 0; i < Fsize; i++) {
      int v = F[i];
      int o = C[i];
      for (int j=0; j < G[v].d; j++) {
        int ngh = G[v].Ngh[j];
	if (X[ngh] == -1 && CAS(&X[ngh],-1,v))
	  Ftmp[o+j] = ngh;
	else Ftmp[o+j] = -1;
      }
    }

    // Filter out the empty slots (marked with -1)
    // Ftmp is the source, and F is the result
    Fsize = filter(Ftmp,F,nr,nonNegF());
  }
  delete[] Ftmp; delete[] F; delete[] C; 
  return pair<int,int*>(r,X);
}