/******************************************************************************/
/**
@file "MPI/C/Primer 4 - pbs/pbs.c"
@brief Parallel bucket sort primer.

Primer sortiranja liste jednako distribuiranih brojeva. Brojevi se
nasumicno generisu izmedju 0 i 2*n. Koriste se Bucket sort i Sequential
sort algoritmi.
*/
/******************************************************************************/

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

/******************************************************************************/

void make_numbers(long int big_array[], int n, int n_bar, int p);

void sequential_sort(long int array[], int size);

int  get_min_pos(long int array[] , int eff_size);

/******************************************************************************/

/**
@brief Glavni program
@param argc Broj argumenata komandne linije
@param argv Argumenti komandne linije
@return Vraca @b 0 ako je sve uspesno izvrseno
*/
int main(int argc, char* argv[]) {
	long int* big_array;
	long int* local_array;
	/* Podrazumevano se sortira 80 elemenata */
	int n = 80;
	int n_bar /* = n / p; */;
	int p;
	int my_rank;
	int i;
	double start, stop;   /* Za merenje proteklog vremena */

	/* Inicijalizujemo MPI */
	MPI_Init(&argc, &argv);
	/* Odredimo velicinu MPI sveta */
	MPI_Comm_size(MPI_COMM_WORLD, &p);
	/* Pronadjemo nas rank u MPI svetu */	
	MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);

    if (argc == 2) {
	    /*
	    Prvi argument komandne linije predstavlja broj elemenata niza
	    koji treba sortirati
	    */
	    n = atoi(argv[1]);
    }

    /* Napravimo veliki niz */
	big_array = malloc(n * sizeof(long int));

	/* Ako smo master */
	if (my_rank == 0)
	{
		start = MPI_Wtime();  /* Merimo vreme */		
		/* Proverimo da li su parametri n i p validni */
		if (n % p != 0)
		{
			fprintf(stderr,"The number of processes must evenly divide total elements.\n");
			/* Napustimo MPI svet */
			MPI_Abort(MPI_COMM_WORLD, 2);
			exit(1);
		}

		if (big_array == NULL)
		{
			fprintf(stderr, "Big_array malloc failed!!\n");
			/* Napustimo MPI svet */
			MPI_Abort(MPI_COMM_WORLD, 3);
			exit(0);
		}

		printf("\nTotal elements = %d; Each process sorts %d elements.\n", 
			n, n / p);

		/* Generisemo elemente niza */
		make_numbers(big_array, n, n / p, p);
	}

	n_bar = n / p;
	
	local_array = malloc(n_bar * sizeof(long int));
	
	if (local_array==NULL)
	{
		fprintf(stderr, "local_array malloc failed!!\n");
		/* Napustimo MPI svet */
		MPI_Abort( MPI_COMM_WORLD, 4 );
		exit(0);
	}
	
	/*
	Ako su brojevi grupisani u velikom nizu mozemo koristiti
	MPI rutinu MPI_Scatter() koja ce podatke podeliti svim
	procesima u MPI svetu
	*/
	MPI_Scatter(big_array, n_bar, MPI_LONG, 
		local_array, n_bar, MPI_LONG, 0, MPI_COMM_WORLD);

	/* Sortiramo deo podataka koji je ostao nasem procesu */
	sequential_sort(local_array, n_bar);

	/* Pokupimo rezultate od ostalih procesa u MPI svetu */
	MPI_Gather(local_array, n_bar, MPI_LONG, 
		big_array, n_bar, MPI_LONG, 0, MPI_COMM_WORLD);

	/* Zaustavljamo stopericu */	
	stop = MPI_Wtime();

	/* Ako smo master */
	if (my_rank == 0)
	{
		printf("\nAfter sorting:\n");
		for(i = 0; i < n; i++)
			printf("%7ld %c", big_array[i], i % 8 == 7 ? '\n'  : ' '); 
		printf("\n\nTime to sort using %d processes = %lf msecs\n", 
			p, (stop - start)/0.001);
	}

	/* Oslobodimo memorijski prostor koji smo zauzeli */
	free(local_array);
	if (my_rank == 0)
		free(big_array);

	/* Zavrsimo MPI */
	MPI_Finalize();
	
	return 0;
}

/******************************************************************************/

/**
@brief Metoda koja generise elemente bafera.
@param big_array Bafer u koji se smestaju generisani elementi.
@param n Velicina bafera.
@param n_bar Koeficijent koji koristimo za generisanje elemenata (= n / p).
@param p Koeficijent koji koristimo za generisanje elemenata.
*/
void make_numbers(long int	big_array[],
		  int		n,
		  int		n_bar,
		  int		p)
{
	/* Stavljamo brojeve u "kofe", mada ih mozemo tretirati i drugacije */ 
	int i, q;
	
	printf("Before sorting:\n");
	for (q = 0; q < p; q++)
	{
		printf("\nP%d: ", q); 
		for (i = 0; i < n_bar; i++)
		{
			big_array[q * n_bar + i] =
				rand() % (2 * n / p) + (q * 2 * n / p);
			printf("%7ld %s",
			 big_array[q * n_bar + i], i % 8 == 7 ? "\n\t" : " "); 
		}
		printf("\n"); 
	}
	printf("\n");
}

/******************************************************************************/

/**
@brief Sequential sort algoritam.
@param array Bafer.
@param size Velicina bafera.
*/
void sequential_sort(long int array[], int size)
{
	/*
	Koristimo Sequential sort algoritam da sortiramo niz po rastucem
	poretku
	*/
	int eff_size, min_pos;
	long int temp;
	
	for (eff_size = size; eff_size > 1; eff_size--)
	{
		min_pos = get_min_pos(array, eff_size);
		temp = array[min_pos];
		array[min_pos] = array[eff_size-1];
		array[eff_size-1] = temp;
	}
}

/******************************************************************************/

/**
@brief Vraca indeks najmanjeg od preostalih nesortiranih elemenata.
@param array Bafer cije elemente treba sortirati.
@param eff_size Broj preostalih elemenata.
@return Vraca indeks najmanjeg od preostalih nesortiranih elemenata.
*/
int get_min_pos(long int array[], int eff_size)
{
	int i, min_pos = 0;
	
	for (i=0; i < eff_size; i++)
		min_pos = array[i] > array[min_pos] ? i: min_pos;
	return min_pos;
}

/******************************************************************************/