#include <stdio.h>
#include <stdlib.h>
#include <mpi.h>
#include <math.h>
#define PRECISION 0.000001
#define RANGESIZE 1
#define DATA 0
#define RESULT 1
#define FINISH 2
#define QUEUESIZE 5
//#define DEBUG

struct Node {
	double range[2];
	struct Node* next;
};

struct Node* front = NULL;
struct Node* rear = NULL;

void Enqueue(double rangeStart, double rangeEnd) {
	struct Node* temp =
		(struct Node*)malloc(sizeof(struct Node));
	temp->range[0] = rangeStart;
    temp->range[1] = rangeEnd;
	temp->next = NULL;
	if(front == NULL && rear == NULL){
		front = rear = temp;
		return;
	}
	rear->next = temp;
	rear = temp;
}

// To Dequeue an integer.
void Dequeue() {
	struct Node* temp = front;
	if(front == NULL) {
		printf("Queue is Empty\n");
		return;
	}
	if(front == rear) {
		front = rear = NULL;
	}
	else {
		front = front->next;
	}
	free(temp);
}

double* Front() {
	if(front == NULL) {
		printf("Queue is empty\n");
		return;
	}
	return front->range;
}

void Print() {
	struct Node* temp = front;
	while(temp != NULL) {
		printf("%f %f; ",temp->range[0], temp->range[1]);
		temp = temp->next;
	}
	printf("\n");
}

double f(double x) {
  return sin(x);
}
double SimpleIntegration(double a,double b) {
  double i;
  double sum=0;
  for (i=a;i<b;i+=PRECISION)
    sum+=f(i)*PRECISION;
  return sum;
}
int main(int argc, char **argv) {
  int myrank,proccount;
  double a=0,b=100*M_PI;
  double range[2];
  double result=0,resulttemp;
  int sentcount=0;
  int i, j;

  MPI_Status status;
  // Initialize MPI
  MPI_Init(&argc, &argv);
  // find out my rank
  MPI_Comm_rank(MPI_COMM_WORLD, &myrank);
  // find out the number of processes in MPI_COMM_WORLD
  MPI_Comm_size(MPI_COMM_WORLD, &proccount);
  if (proccount<2) {
    printf("Run with at least 2 processes");
    MPI_Finalize();
    return -1;
  }
  if (((b-a)/RANGESIZE)<2*(proccount-1)) {
    printf("More subranges needed");
    MPI_Finalize();
    return -1;
  }
  // now the master will distribute the data and slave processes will perform computations
  if (myrank==0) {
    range[0]=a;
    // first distribute some ranges to all slaves
    //for(j=0;j<QUEUESIZE;j++)
    //{
        for(i=1;i<proccount;i++) {
          range[1]=range[0]+RANGESIZE;
    #ifdef DEBUG
          printf("\nMaster sending range %f,%f to process %d",range[0],range[1],i);
          fflush(stdout);
    #endif
            MPI_Request sendRequest;
          // send it to process i
            MPI_Isend(range,2,MPI_DOUBLE,i,DATA,MPI_COMM_WORLD, &sendRequest);
            MPI_Status myStatus;
            MPI_Wait(&sendRequest, &myStatus);
          sentcount++;
          range[0]=range[1];
        }
    //}
    do {
      // distribute remaining subranges to the processes which have completed their parts
      MPI_Recv(&resulttemp,1,MPI_DOUBLE,MPI_ANY_SOURCE,RESULT,MPI_COMM_WORLD,&status);
        sentcount--;
      result+=resulttemp;
#ifdef DEBUG
      printf("\nMaster received result %f from process %d",resulttemp,status.MPI_SOURCE);
      fflush(stdout);
#endif
      // check the sender and send some more data
      range[1]=range[0]+RANGESIZE;
      if (range[1]>b) range[1]=b;
#ifdef DEBUG
      printf("\nMaster sending range %f,%f to process %d",range[0],range[1],status.MPI_SOURCE);
      fflush(stdout);
#endif
      MPI_Send(range,2,MPI_DOUBLE,status.MPI_SOURCE,DATA,MPI_COMM_WORLD);
        sentcount++;
      range[0]=range[1];
    } while (range[1]<b);
    // now receive results from the processes
    //for(i=0;i<(proccount-1);i++)
    while(sentcount>0){
      MPI_Recv(&resulttemp,1,MPI_DOUBLE,MPI_ANY_SOURCE,RESULT,MPI_COMM_WORLD,&status);
        sentcount--;
#ifdef DEBUG
      printf("\nMaster received result %f from process %d",resulttemp,status.MPI_SOURCE);
      fflush(stdout);
#endif
      result+=resulttemp;
    }
    // shut down the slaves
    for(i=1;i<proccount;i++) {
      MPI_Send(NULL,0,MPI_DOUBLE,i,FINISH,MPI_COMM_WORLD);
    }
    // now display the result
    printf("\nHirange, I am process 0, the result is %.20f\n",result);
  } else { // slave
    // this is easy - just receive data and do the work

    do {
        int flag;
        MPI_Request receive_request;
      MPI_Iprobe(0,MPI_ANY_TAG,MPI_COMM_WORLD,&flag,&status);

      if (flag && status.MPI_TAG==DATA) {
        MPI_Irecv(range,2,MPI_DOUBLE,0,DATA,MPI_COMM_WORLD,&receive_request);
        // compute my part
        //resulttemp=SimpleIntegration(range[0],range[1]);
        // send the result back
        //MPI_Send(&resulttemp,1,MPI_DOUBLE,0,RESULT,MPI_COMM_WORLD);
        //printf("Test %d\n", myrank);
        MPI_Status myStatus;
        MPI_Wait(&receive_request, &myStatus);
        //printf("Test2 %f %f; %d\n",range[0], range[1], myrank);
        Enqueue(range[0], range[1]);
        double* test = Front();
        //printf("Test3 %f %f; %d\n",test[0], test[1], myrank);
        //Print();
      }
        if(front != NULL)
        {
            double* curRange = Front();

            //printf("slave calculating range: %f, %f/n", curRange[0],curRange[1]);
            resulttemp=SimpleIntegration(curRange[0],curRange[1]);
            Dequeue();
            // send the result back
            MPI_Send(&resulttemp,1,MPI_DOUBLE,0,RESULT,MPI_COMM_WORLD);
            //Print();
        }



    } while (status.MPI_TAG!=FINISH);
  }
  // Shut down MPI
  MPI_Finalize();
  return 0;
}