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

/* Funkciju prototipai */
void SukurtiSkaicius(long int [], int, int, int);
void NuoseklusRikiavimas(long int [], int);
int MinPozicija(long int [], int);

int main(int argc, char* argv[]) {
	long int * big_array; // Bendras masyvas
	long int * local_array; // Masyvas kiekvienam procesui
	int n=0; // Bendro masyvo kiekis
	int nProc; // Masyvo kiekis procesui
	int p; // Procesu skaicius
	int my_rank; // Proceso numeris
	int i; // ciklams
	double start, stop; // Skaiciavimo pradzia, pabaiga

	MPI_Init(&argc, &argv);
	MPI_Comm_size(MPI_COMM_WORLD, &p); // Nustatome procesu skaiciu
	MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);  // Nustatome proceso numeri

	n = atoi(argv[1]); // Pirmas argumentas - masyvo dydis

	if (my_rank == 0) {

		start = MPI_Wtime(); // Pradedame laiko skaiciavima

		/* Tikrinam parametru tikslinguma */
		if (n%p != 0) {
			fprintf(stderr,"Procesu skaicius turi lygiai isdalinti masyvo elementu skaiciu.\n");
			MPI_Abort( MPI_COMM_WORLD, 2 );
			exit(1);
		}

		/* Tikrinam ar priskirta atmintis bendram masyvui */
		big_array = new long int[n];
		if (big_array==NULL) {
			fprintf(stderr, "Nepavyko sukurti bendro masyvo\n");
			MPI_Abort( MPI_COMM_WORLD, 3 );
			exit(0);
		}
		printf("\nViso elementu = %d; Kiekvienas procesas rikiuos po %d elementu.\n",
			n, n/p);
		SukurtiSkaicius(big_array, n, n/p, p);
	}

	nProc = n/p;

	/* Tikrinam ar priskirta atmintis vietiniam masyvui */
	local_array = new long int[nProc];
	if (local_array==NULL) {
		fprintf(stderr, "Nepavyko sukurti vietinio masyvo\n");
		MPI_Abort( MPI_COMM_WORLD, 4 );
		exit(0);
	}

	/* Naudojam MPI_Scatter, kuris kiekvienam procesui i local_array nusiuncia po nProc elementu */
	MPI_Scatter(big_array, nProc, MPI_LONG, local_array, nProc, MPI_LONG, 0, MPI_COMM_WORLD);

	NuoseklusRikiavimas(local_array, nProc);

	/* Naudojam MPI_Gather, kuris is kiekvieno proceso i big_array nusiuncia po nProc elementu is local_array */
	MPI_Gather(local_array, nProc, MPI_LONG, big_array, nProc, MPI_LONG, 0, MPI_COMM_WORLD);

	stop = MPI_Wtime(); // Stabdome laiko skaiciavima

	if (my_rank==0) {
		printf("\nPo rikiavimo:\n");
		for(i=0; i<n; i++) printf("%7ld %c", big_array[i], i%8==7 ? '\n' : ' '); // Surikiuoto masyvo spausdinimas
			printf("\n\nLaikas sugaistas rikiuojant masyva su %d procesu = %lf ms\n",
			p, (stop - start)/0.001);
	}

	delete []local_array;
	if (my_rank==0) delete []big_array;
	MPI_Finalize();
}


void SukurtiSkaicius(long int big_array[], int n, int nProc, int p)
{
	/* Is anksto sugrupuojam elementus i kibirelius(buckets) */
	int i, q;

	/* big_array elementai bus sugrupuoti taip jog kiekvienam procesui teks kibirelis, kuriame */
	/* bus reiksmes nekonfliktuojancios su kituose kibireliuose esanciomis reiksmemis, tuomet  */
	/* panaudojus MPI_Scatter funkcija mes siuos elementus isdalinsime procesams               */
	//printf("Pries rikiavima:\n");
	for (q = 0; q < p; q++) {
		//printf("\nP%d: ", q);
		for (i = 0; i < nProc; i++) {
			big_array[q*nProc+i] = rand() % (2*n/p) + (q*2*n/p);
			//printf("%7ld %s", big_array[q*nProc+i], i%8==7 ? "\n " :
			//	" ");
		}
		//printf("\n");
	}
	//printf("\n");
}


void NuoseklusRikiavimas(long int masyvas[], int size)
{
	/* Naudojame selection sort ir surikiuojame elementus nuo maziausio iki didziausio */
	int efektDydis, minpos;
	long int temp;

	for(efektDydis = size; efektDydis > 1; efektDydis--) {
		minpos = MinPozicija(masyvas, efektDydis);
		temp = masyvas[minpos];
		masyvas[minpos] = masyvas[efektDydis-1];
		masyvas[efektDydis-1] = temp;
	}
}

/* Grazina maziausio elemento pozicija */
int MinPozicija(long int masyvas[], int efektDydis)
{
	int i, minpos = 0;

	for (i=0; i<efektDydis; i++)
		minpos = masyvas[i] > masyvas[minpos] ? i: minpos;
	return minpos;
}