#include <iostream>
#include <stdio.h>
#include <string.h>
#include "mpi.h" // message passing interface
using namespace std;

// Do this ONCE when you start up thomas
// module load openmpi-x86_64

// New compile and run commands for MPI!
// mpicxx -o blah file.cpp
// mpirun -np 32 blah

int main (int argc, char * argv[]) {

	int my_rank;			// my CPU number for this process
	int p;					// number of CPUs that we have
	int source;				// rank of the sender
	int dest;				// rank of destination
	int tag = 0;			// message number
	char message[100];		// message itself
	MPI_Status status;		// return status for receive

	// Start MPI
	MPI_Init(&argc, &argv);

	// Find out my rank!
	MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);

	// Find out the number of processes!
	MPI_Comm_size(MPI_COMM_WORLD, &p);

	// THE REAL PROGRAM IS HERE
/*
int a[5] = {7, 4, 3, 6, -2};
int psum[5]={0};

psum [0]= a[0];
for (int x=1; x<5; x++)
	psum[x] = psum [x-1] + a[x];
*/

	int srand (time (0));
	int n = 300000;
	int a [300000], psum [300000];

	if (my_rank==0)
		for (int x =0; x<300000; x++)
			a[x]= rand () %8;

		int locala[10000];
		double localpsum[10000];
		int local_n= n/p;
		MPI_Scatter(&a[0], local_n, MPI_INT, locala, local_n, MPI_INT, 0, MPI_COMM_WORLD) ;

	localpsum[0] =locala [0] ;
	for (int x =0; x < 300000; x++)
		localpsum[x] = localpsum[x-1] + locala[x];

	//send my last partial prefix sum to all later processors

	for (x= my_rank +1; x < p; x++)
		MPI_Send(&localpsum[local_n-1], 1, MPI_DOUBLE, x, tag, MPI_COMM_WORLD);

	// get all of the partial prefix sum answers from all earlier processors

	double temp=0;
	int num_messRec=0; // keeps track of how many messages i processed so far
	double localadd=0; // final number we need to add to our prefix sums

	while (num_messRec < my_rank){
		MPI_Recv(&temp, 1, MPI_DOUBLE, MPI_ANY_SOURCE, tag, MPI_ COMM_WORLD, &status);
		localadd+= temp;
		num_mesg_recvd++;
	}

	//time to add the localadditive to each entry of my local sum arrray

	for (int x= 0; x <localn; x++)
		localpsum[x]+= localadd;

	// finally collect all the answers by reversing our scatter

		MPI_Gather(&localpsum[0], local_n, MPI_DOUBLE, psum, local_n, MPI_DOUBLE, 0, MPI_COMM_WORLD);

		if (my_rank ==0)
			for (int x=0; x<n; x++){
				cout << psum[x] << " ";
			if (x %10= 0)
				cout << endl;

			}

	// Shut down MPI
	MPI_Finalize();

	return 0;
}