#include<mpi.h>
#include<stdio.h>
#include<stdlib.h>
#define MAX 50000
#define COEFFICIENT 1
#define WORKTAG 1
#define DIETAG 2


int main(int argc, char *argv[])
{
MPI_Init(&argc, &argv);
int rank, numProcs;
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
MPI_Comm_size(MPI_COMM_WORLD, &numProcs);

 if (rank == 0) {
master();
} else {
worker();
}
 
typedef struct tasks
{
int pos;
double x;
int degree;
int coeffArr[];
} task_t;

task_t *task;

// queue of tasks
task_t *taskarray;
int taskid, numtasks;

void init_task(int n)
{
int i;
taskarray = malloc(n*sizeof(task_t));
taskid = 0;
numtasks= n;

for (i = 0; i < n; i++) {
taskarray[i].pos = i;
 }
 
task_t *getNextTask()
{
if (taskid >= numtasks) return NULL;
task_t *t = &taskarray[taskid];
taskid++;
return t;
}
 
}


// code to be executed by worker threads
 void worker(){
 
	MPI_Status status;
	task_t task;
	int rank;


	MPI_Recv(&task, 10, MPI_DOUBLE, 10, MPI_ANY_TAG, MPI_COMM_WORLD, &status);

	if (status.MPI_TAG == DIETAG) {
		return;
		}



	double power(double x, int degree)
	{     
      if(degree == 0)  return 1;
      
      if(degree == 1)  return x;

      return x * power(x, degree - 1);
	}

	double sequential(int coeffArr[], double x)
	{
   int maxDegree = MAX - 1;
   int i;
   double  answer = 0;
   
   for( i = 0; i < maxDegree;  i++)
   {
      
      double powerX = power(x, i);

      //printf("%f ", powerX);
      answer = answer + coeffArr[i] * powerX;
   }
   return answer;
	}

	double fixedChunks(int coeffArr[], double x)
	{
   int rank, numProcs;
   MPI_Comm_rank(MPI_COMM_WORLD, &rank);
   MPI_Comm_size(MPI_COMM_WORLD, &numProcs);
   
   int i;
   double answer = 0;
   int maxDegree = MAX - 1;
   
   int startIndex = (rank * MAX)/numProcs;
   int endIndex = (rank + 1) * MAX/numProcs;

   if(rank == numProcs - 1)
     endIndex = MAX;
   
   for( i = startIndex; i < endIndex; i++)
   {
      double powerX = power(x, i);

      answer = answer + coeffArr[i] * powerX;
   }
   return answer;
	}

	double roundRobin(int coeffArr[], double x)
	{
   int rank, numProcs;
   MPI_Comm_rank(MPI_COMM_WORLD, &rank);
   MPI_Comm_size(MPI_COMM_WORLD, &numProcs);
   
   int i;
   double answer = 0;
   int maxDegree = MAX - 1;
   
   for( i = rank; i < maxDegree; i = i+numProcs)
   {
      double powerX = power(x, i);

      answer = answer + coeffArr[i] * powerX;
   }
   return answer;  
	}

	void initialize(int coeffArr[])
	{
   int maxDegree = MAX - 1;
   int i;
   for( i = 0; i < maxDegree; i++)
   {
      coeffArr[i] = COEFFICIENT;
   }
	}
  double startTimer, endTimer;
  
  double answerSequential;
  
  double x = 0.99;
  
  
  int coeffArr[MAX]; 

  startTimer = MPI_Wtime();
  
   answerSequential = sequential(coeffArr, x);
 
   endTimer = MPI_Wtime();
 	
   printf("Answer Sequential %f and Time taken is %f\n", answerSequential, (endTimer - startTimer));
 
 

 	MPI_Barrier(MPI_COMM_WORLD);
 
 	/////////////////////////////////////////////////////////////////////////////////

 	startTimer = MPI_Wtime();

 	double answerRoundRobin = roundRobin(coeffArr, x);

 	endTimer = MPI_Wtime();

 	double finalAnswerRR;
 
 	printf("Rank = %d Answer Round Robin %f, Time = %f\n", rank, answerRoundRobin, (endTimer - startTimer));
 	fflush(stdout);
 
 
	// send round robin answer
	MPI_Send(&answerRoundRobin, 1, MPI_DOUBLE, 0, 0, MPI_COMM_WORLD);

	// answer by fixed chunks method
	 MPI_Barrier(MPI_COMM_WORLD); 
 
 	startTimer = MPI_Wtime();
 
	 double answerFixedChunks = fixedChunks(coeffArr, x);

 	endTimer = MPI_Wtime();

	 printf("\n");
 	fflush(stdout);
	 
 
 
	 double finalAnswerFC;

	 printf("Rank = %d Answer Fixed Chunks %f, Time = %f\n", rank, answerFixedChunks, (endTimer - startTimer));
 	fflush(stdout);
	//send fixed chunks answer
	MPI_Send(&answerFixedChunks, 1, MPI_DOUBLE, 0, 0, MPI_COMM_WORLD);

	}
  
  
 	 // This code will be run by the master process that is rank 0
  
  
	void master(){
	
 	

	MPI_Comm_size(MPI_COMM_WORLD, &numtasks); 
	
	MPI_Status status;
 	// assign ten tasks to each of the processes
 	 MPI_Bcast(&task, 10, MPI_DOUBLE, 0, MPI_COMM_WORLD );
 
	task_t task;
		for (rank = 1; rank < numtasks; rank++) 
		{
		task =getNextTask();

	 	MPI_Send(task, 10, MPI_DOUBLE, rank, MPI_ANY_TAG, MPI_COMM_WORLD); 
		}

	//Receive computed polynomial from any worker and send ten new tasks
 	double answerFixedChunks, answerRoundRobin;
 
	task= getNextTasK();
	//while there are tasks in the queue
	while (task != NULL) {
	//recieve computed answer by round robin
	MPI_Recv(&answerRoundRobin, 1, MPI_DOUBLE, MPI_ANY_SOURCE,  MPI_ANY_TAG , MPI_COMM_WORLD, &status); 
 
   //send another set of 10 tasks
	MPI_Recv(&answerFixedChunks, 1, MPI_DOUBLE, MPI_ANY_SOURCE,  MPI_ANY_TAG, MPI_COMM_WORLD, &status);
  
 
	//get next task in the array
	task = getNextTask();
	// send the next ten to the worker that has sent the tasks that is the destination rank is the source of recieved tasks.
	MPI_Send(task, 10, MPI_DOUBLE, status.MPI_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD);
	}
	
	
	for (rank = 1; rank < numtasks; rank++) {
	MPI_Send(0, 0, MPI_DOUBLE, rank, DIETAG, MPI_COMM_WORLD);
	}
	
 	double finalAnswerFC, finalAnswerRR;
	
	 MPI_Reduce(&answerRoundRobin, &finalAnswerRR, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD);
 
	 MPI_Reduce(&answerFixedChunks, &finalAnswerFC, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD);
 
 
 
 	if(rank == 0)
    printf("Answer verification roundRobin = %f fixedChunks = %f \n", finalAnswerRR, finalAnswerFC);
 
 	MPI_Finalize();
 	
 return ; 
}