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

int blockSize = 1024;

template <class T, class F> 
T reduce(T* A, int n, F f) {
  int numBlocks = (n-1)/blockSize + 1;
  T sums = new int[numBlocks];
  cilk_for (int i=0; i < numBlocks; i++) {
    T sum = A[i*blockSize];
    for (int j=i*blockSize+1; j < min(n,(i+1)*blockSize), j++)
      sum = f(sum,A[j]);
    sums[i] = sum;
  }
  T result = sums[0];
  for (int i=1; i < numBlocks; i++)
    result = f(result,sums[i]);
  return result;
}

template <class T, class F> 
T scan(T* In, T* out, int n, T ident, F f) {
  int numBlocks = (n-1)/blockSize + 1;
  T sums = new int[numBlocks];
  cilk_for (int i=0; i < numBlocks; i++) {
    T sum = In[i*blockSize];
    for (int j=i*blockSize+1; j < min(n,(i+1)*blockSize), j++)
      sum = f(sum,In[j]);
    sums[i] = sum;
  }
  T result = ident;
  for (int i=0; i < numBlocks; i++) {
    T t = sums[i];
    sums[i] = result;
    result = f(result,t);
  }
  cilk_for (int i=0; i < numBlocks; i++) {
    T sum = sums[i];
    for (int j=i*blockSize+1; j < min(n,(i+1)*blockSize), j++) {
      T t = In[i];
      Out[i] = sum;
      sum = f(sum,t);
    }
  }
  return result;
}