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

void compareVectors(int * a, int * b, int n) {
	// DO NOT MODIFY
	int i;
	for(i = 0; i < n; i++) {
		if(a[i]!=b[i]) {
			printf("Sorted incorrectly\n");
			return;
		}
	}
	printf("Sorted correctly\n");
}

void displayVector(int * v, int n) {
	// DO NOT MODIFY
	int i;
	for(i = 0; i < n; i++) {
		printf("%d ", v[i]);
	}
	printf("\n");
}

int cmp(const void *a, const void *b) {
	// DO NOT MODIFY
	int A = *(int*)a;
	int B = *(int*)b;
	return A-B;
}

int main(int argc, char * argv[]) {
	int rank;
	int nProcesses;
	MPI_Init(&argc, &argv);

	MPI_Comm_rank(MPI_COMM_WORLD, &rank);
	MPI_Comm_size(MPI_COMM_WORLD, &nProcesses);
	printf("Hello from %i/%i\n", rank, nProcesses);

	int *v, *vQSort, * v_aux;
	int v_size;
	MPI_Status status;
	int parts, myNumber, myPlace;


	if(rank==0) { // This code is run by a single process
		int i;

		// read the vector v
		// DO NOT MODIFY
		scanf("%d", &v_size);
		v_aux = (int*) calloc(v_size,sizeof(int));
		// Alocate memory
		vQSort = (int*)malloc(sizeof(int)*v_size);
		v = (int*)malloc(sizeof(int)*v_size);

		for(i = 0; i < v_size; i++)
			scanf("%d", &v[i]);

		// make copy to check it against qsort
		// DO NOT MODIFY
		for(i = 0; i < v_size; i++)
			vQSort[i] = v[i];

		qsort(vQSort, v_size, sizeof(int), cmp);
		// Sending the vector to the other processes
		for(i=0 ; i < nProcesses; i++)
		{
			MPI_Send(&v_size,1 ,MPI_INT,i,0, MPI_COMM_WORLD);
			MPI_Send(v,v_size,MPI_INT,i,1,MPI_COMM_WORLD);
		}

	}

	else
	{
		//	For all the other processes beside rank 0  we recieve the
		//	size and the vector
		MPI_Recv(&v_size,1,MPI_INT,0,0,MPI_COMM_WORLD,&status);
		v = (int*)calloc(v_size,sizeof(int));

		MPI_Recv(v,v_size,MPI_INT,0,1,MPI_COMM_WORLD,&status);
	}

	//	Spliting the vector in parts;
	parts = v_size / nProcesses;
	if(rank < nProcesses -1)
	{
		printf("Sunt rank %d si voi prelucra %d elemente, situate intre indicii: %d si %d\n",rank, parts,rank*parts,rank * parts + parts-1 );
		//For every element of the vector that is between the split of the rank we calculate and send the appropiate place in the sorted vector
		for(int j = rank * parts; j < rank * parts + parts ; j++)
		{
			myNumber = v[j];
			myPlace = 0;
			for(int k = 0; k  < v_size; k++)
			{
				if(myNumber > v[k])
				{
					myPlace++;
				}
			}
			if(rank != 0 )
			{
				MPI_Send(&myPlace,1,MPI_INT,0,2,MPI_COMM_WORLD);
				MPI_Send(&myNumber,1,MPI_INT,0,3, MPI_COMM_WORLD);
			}
			else
			{
				v_aux[myPlace] = myNumber;
				for(int k = 1; k < nProcesses-1 ; k++)
				{
					MPI_Recv(&myPlace,1,MPI_INT,k,2,MPI_COMM_WORLD,&status);
					MPI_Recv(&myNumber,1,MPI_INT,k,3,MPI_COMM_WORLD,&status);
					v_aux[myPlace] = myNumber;

				}
			}
		}
	}
	else
	{
		printf("Sunt rank %d si voi prelucra %d elemente, situate intre indicii: %d si %d\n",rank, v_size - (rank*parts),rank*parts,v_size );
		for(int j = rank *parts; j < v_size; j++) {
			myNumber = v[j];
			myPlace = 0;
			for(int k = 0 ; k < v_size; k++)
			{
				if(myNumber > v[k])
					myPlace++;
			}
			MPI_Send(&myPlace,1,MPI_INT,0,2,MPI_COMM_WORLD);
			MPI_Send(&myNumber,1,MPI_INT,0,3,MPI_COMM_WORLD);

		}
	}

	if(rank == 0)
	{
		for(int j = 0; j < parts + (v_size % nProcesses); j++)
		{
			MPI_Recv(&myPlace, 1, MPI_INT, nProcesses-1,2,MPI_COMM_WORLD,&status);
			MPI_Recv(&myNumber,1,MPI_INT,nProcesses-1,3,MPI_COMM_WORLD,&status);
			v_aux[myPlace] = myNumber;
		}
	}




	// DO NOT MODIFY
	if(rank == 0) {
		//displayVector(v_aux, v_size);
		compareVectors(v_aux, vQSort, v_size);
	}

	MPI_Finalize();
	return 0;
}