/* par20_ex6_t26.c SJ */

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <mpi.h>
#include <time.h>

/* these variables are used by prefix sum also, hence here */
static int P, PID;

// for ease of debug
int M = 10;

int *prefix_sum_26(int *values, int m);
int prefix_sum_26_1(int value);
double ltime();

int main(int argc, char **argv)
{
  int i, num, psum, ksum, *result, *input;
  int *subinput, *subresult;
  double starttime, starttime1, endtime, parttime, fulltime;

  MPI_Init(&argc, &argv);
  MPI_Comm_rank(MPI_COMM_WORLD, &PID);
  MPI_Comm_size(MPI_COMM_WORLD, &P);


  subinput = (int*)malloc(M*sizeof(int));
  /* 0 creates input */
  if (PID == 0) {
	  srand(getpid());
	  input = (int*)malloc(P*M*sizeof(int));
	  result = (int*)malloc(P*M*sizeof(int));
	  printf("Input is:");
	  for (i = 0; i < P*M; i++) {
		  input[i] = rand()%10;
		  // input[i] = 1; // easier to debug
		  if (P*M < 100) {
			  printf(" %d", input[i]);
		  }
	  }
	  printf("\n %dx%d\n", P, M);

  }




  starttime = ltime();
  /* 0 sends pieces of data to everyone */
  MPI_Scatter(input, M, MPI_INT, subinput, M, MPI_INT, 0, MPI_COMM_WORLD);

  /* everyone prints input (if you want) */
  // printf("PID%d: input = %d\n", PID, num);


  starttime1 = ltime();
  /* all processes call the prefix sum */
  subresult = prefix_sum_26(subinput, M);
  MPI_Barrier(MPI_COMM_WORLD);	// to ensure fair timing ar PID 0
  endtime = ltime();
  parttime = endtime-starttime1;

  /* everyone prints result (if you want) */
  // printf("PID%d: result = %d\n", PID, psum);

  /* collect the prefix sum to the first process */
  MPI_Gather(subresult, M, MPI_INT, result, M, MPI_INT, 0, MPI_COMM_WORLD);

  endtime = ltime();
  fulltime = endtime-starttime;

  /* process 0 prints the result */
  if (PID == 0) {
	  printf("Prefix sum:");

	  printf("Full time: %.6lf us, core time %.6lf us\n", fulltime*1000000, parttime*1000000);
	  if (P*M < 100) {
		  for (i = 0; i < P*M; i++) {
			  printf(" %d", result[i]);
		  }
	  } else printf(" last: %d", result[P*M-1]);
	  printf("\n");
	  free(result);
	  free(input);
  }

  free(subresult);
  free(subinput);

  MPI_Finalize();

  exit(0);

}








/* prefix sum */
/* each process has a single (the parameter value)
 * and returns the corresponding element of the prefix sum of values.
 */
int prefix_sum_26_1(int value)
{
  int sum = value, i, mess;
  MPI_Status stat;

  /* repeat logP times */
  /* i is like 2^(1-i) at original algorithm */

  // TODO

  return sum;
}


/* prefix sum */
/* each process has m values (the parameter values)
 * and returns new array of prefix sum results
 */
int * prefix_sum_26(int *values, int m)
{
  int sum = 0, i, presum = 0;
  MPI_Status stat;

  int *subresult = (int*)malloc(m*sizeof(int));

  /* do local prefx sum */

  // TODO

  /* prefix sum among subresults */
  presum = prefix_sum_26_1(sum);

  /* substrac own value (0-prefix-sum) */
  presum -= sum;

  /* update local values (if needed) */
  // TODO

  return subresult;
}

double ltime()
{
    struct timeval tv;
    gettimeofday(&tv, NULL);
    return tv.tv_sec + (double)tv.tv_usec/1000000;
}