#include <stdio.h>
#include <mpi.h>
#include <math.h>
#include <stdlib.h>
#define RESULT 1
#define FINISH 2
#define DEBUG
#define DATA 0

#define TABLESIZE 10
#define CHUNKS 3

void merge2(int arr[], int l, int m, int r)
{
    int i, j, k;
    int n1 = m - l + 1;
    int n2 =  r - m;

    int L[n1], R[n2];

    for(i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for(j = 0; j <= n2; j++)
        R[j] = arr[m + 1+ j];

    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2)
    {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort2(int arr[], int l, int r)
{
    if (l < r)
    {
        int m = l+(r-l)/2; //Same as (l+r)/2, but avoids overflow for large l and h
        mergeSort2(arr, l, m);
        mergeSort2(arr, m+1, r);
        merge2(arr, l, m, r);
    }
}

int compare4qsort(const void *a, const void *b){
	return (*(int*)a-*(int*)b);
}

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

	int myrank,proccount;
	int i,j,k,l,z;
	int size, chunks;
	int tobesorted[TABLESIZE];
	MPI_Status status;
	int *temp2send;
	int *receivedBuffer;
	int amountToSend=0;
	int chunksSent=0;
	int amountSortedAlready=0;

	MPI_Init(NULL,NULL);
	MPI_Comm_rank(MPI_COMM_WORLD, &myrank);
	MPI_Comm_size(MPI_COMM_WORLD, &proccount);

	if (proccount<2){
		printf("Run with at least 2 processes");
		MPI_Finalize();
		return -1;
	}

	if (myrank == 0){ // MASTER


		printf("\nTablica z %d elementami, liczba paczek, to %d\n\n", TABLESIZE, CHUNKS);
		printf("Przed posortowaniem: ");
		fflush(stdout);


		srand(time(NULL));
		for (i=0;i<TABLESIZE;i++){
			tobesorted[i]=rand()%40;
			printf("%d, ", tobesorted[i]);
		}
//		printf("\n");

	int amountPerChunk = TABLESIZE / CHUNKS;
	int beginIndex=0;
	int endIndex=0;
	int sentcount=0;
// FIRST SENDING
	for (j=1; j<proccount;j++) {
		endIndex = beginIndex+amountPerChunk-1;
/*		if (j==proccount-1) {
			endIndex = endIndex + (TABLESIZE%CHUNKS);
		}*/


		printf("proc %d: indeks elementu poczatkowego=%d indeks elementu koncowego=%d\n", j,beginIndex,endIndex);
		fflush(stdout);

		amountToSend = endIndex-beginIndex+1;
		// send it to process j
		MPI_Send((void*)(tobesorted+sentcount+1),amountToSend,MPI_INT,j,DATA,MPI_COMM_WORLD);
		beginIndex = beginIndex + amountToSend;
		sentcount=sentcount+amountToSend;
		chunksSent++;

		printf("\n Paczka [%d] wyslana do procesu (%d)! Z calkowitej liczby [%d]\n", chunksSent, j, sentcount);
		fflush(stdout);


	}
//
		int *sortedBuffer = &tobesorted;
		// process results from slaves
		while (chunksSent<CHUNKS-1) {
			int left=0;
			int right=0;
			int resultReceivedAmount=0;
			MPI_Probe(MPI_ANY_SOURCE,MPI_ANY_TAG,MPI_COMM_WORLD,&status);
			MPI_Get_count(&status,MPI_INT,&resultReceivedAmount);

			//int  *receivedResult = malloc(resultReceivedAmount * sizeof(int));
			MPI_Recv((void*)(sortedBuffer+amountSortedAlready),resultReceivedAmount,MPI_INT,MPI_ANY_SOURCE,RESULT,MPI_COMM_WORLD,&status);

			//mergeSort2(sortedBuffer,0,amountSortedAlready);

			MPI_Send((void*)(tobesorted+sentcount+1),amountPerChunk,MPI_INT,status.MPI_SOURCE,DATA,MPI_COMM_WORLD);
			amountSortedAlready=amountSortedAlready+resultReceivedAmount;
			chunksSent++;
			sentcount=sentcount+amountPerChunk;
		}
		// LAST CHUNK
		amountToSend = TABLESIZE-sentcount;
		MPI_Send((void*)(tobesorted+sentcount+1),amountToSend,MPI_INT,status.MPI_SOURCE,DATA,MPI_COMM_WORLD);
		int lastResultReceivedAmount=0;
		MPI_Probe(MPI_ANY_SOURCE,MPI_ANY_TAG,MPI_COMM_WORLD,&status);
		MPI_Get_count(&status,MPI_INT,&lastResultReceivedAmount);

		MPI_Recv((void*)(sortedBuffer+amountSortedAlready),lastResultReceivedAmount,MPI_INT,MPI_ANY_SOURCE,RESULT,MPI_COMM_WORLD,&status);

		mergeSort2(sortedBuffer,0,TABLESIZE);
		//shutdown the slaves
		for (j=1;j<proccount;j++){
			MPI_Send(NULL,0,MPI_INT,j,FINISH,MPI_COMM_WORLD);
		}

		printf("Tablica koncowa: \n");
		for(i=0;i<TABLESIZE;i++){
			printf("%d > ", sortedBuffer[i]);
			//printf("\n final sorted table size = %d", )
		}
		printf("\n");
		fflush(stdout);
		//
	} else { // SLAVE NOW

		do {
			int receivedAmount=0;
			MPI_Probe(0,MPI_ANY_TAG,MPI_COMM_WORLD,&status);
			MPI_Get_count(&status,MPI_INT,&receivedAmount);

			receivedBuffer = malloc(receivedAmount * sizeof(int));
			if (status.MPI_TAG==DATA){
				MPI_Recv(receivedBuffer,receivedAmount, MPI_INT,MPI_ANY_SOURCE,DATA,MPI_COMM_WORLD,&status);

				qsort(receivedBuffer,receivedAmount, sizeof(int), compare4qsort);
				//mergeSort2(receivedBuffer,0,receivedAmount);

				MPI_Send(receivedBuffer,receivedAmount,MPI_INT,0,RESULT,MPI_COMM_WORLD);
			}
		} while (status.MPI_TAG!=FINISH);
	}
	MPI_Finalize();
	return 0;
}