/* voting.mpi.c SJ */

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

/* uncomment to see the values */
// #define VERBOSE

int votes(int *input, int n, int maxval);
int votes_mpi(int *input, int K, MPI_Comm comm);

int main(int argc, char **argv)
{
	int PID,  /* process-ID */
		P;    /* number of processes */
	/* MPI_Status tmpstat; */

	int K = 3;	/* number of elements/process */
	int *input = NULL;
	int res;

	int i, r;
	int *votes = NULL, max = -1, maxidx = -1;

	int result, a;

	double start_ustime, used_ustime;

	MPI_Init(&argc, &argv);
	MPI_Comm_rank(MPI_COMM_WORLD, &PID);
	MPI_Comm_size(MPI_COMM_WORLD, &P);

	/* read command line parameters */

	for (a = 1; a < argc; a++) {
		if (! strcmp(argv[a], "-K") && argv[a+1] != NULL &&
			atoi(argv[a+1]) > 0)
			K = atoi(argv[a+1]);
		if (! strcmp(argv[a], "-P") && argv[a+1] != NULL &&
			atoi(argv[a+1]) > 0)
			P = atoi(argv[a+1]);
	}

	#ifdef VERBOSE
	if (PID == 0) printf("P = %d, K = %d.\n", P, K);
	#endif

	/* all processes have (generate) a piece of input */
	input = (int*)malloc(K * sizeof(int));

	for (i = 0; i < K; i++) {
		r = rand() % P;

		input[i] = r;
		#ifdef VERBOSE
		printf(" %d", r);
		#endif
	}

	#ifdef VERBOSE
	printf("\n");
	#endif

	MPI_Barrier(MPI_COMM_WORLD);

	/* in parallel ------------ */

	res = votes_mpi(input, K, MPI_COMM_WORLD);

	/* all processes get also the same result */
	#ifdef VERBOSE
	printf("PID%d, result is %d\n", res);
	#endif


	free(input);

	MPI_Finalize();

	return 0;

}   /* main() */


/* sequential vote counting, values are 0..maxval-1 */
/* not used, just for example */
int votes(int *input, int n, int maxval) {

	int max = -1, i, maxi = 0;
	int *votes = (int*)malloc((maxval) * sizeof(int));

	/* zero votes */
	for (i = 0; i < maxval; i++)
		votes[i] = 0;

	/* count votes */
	for (i = 0; i < n; i++) {
		int x = input[i];
		if (x >= 0 && x < maxval)
			votes[x]++;
	}

	/* find max */
	for (i = 0; i < maxval; i++)
		if (votes[i] > max) {
			max = votes[i];
			maxi = i;
		}

	free(votes);

	return maxi;

} /* votes() */

/* parallel vote counting, values are 0..P-1 */
/* input is split among all processes */
/* all processes return the result */
int votes_mpi(int *input, int K, MPI_Comm comm) {

	int PID, P, i, max = 0, myvotes = 0, result = -1;

	int *lvotes = NULL, *allvotes = NULL;


	MPI_Comm_size(comm, &P);
	MPI_Comm_rank(comm, &PID);

	/* count local votes */
	lvotes = (int*) malloc(sizeof(int)*P);

	/* zero votes */
    for (i = 0; i < P; i++)
        lvotes[i] = 0;

    /* count votes locally */
    for (i = 0; i < K; i++) {
        int x = input[i];
        if (x >= 0 && x < P)
            lvotes[x]++;
    }

	// TODO: task 28-29
	// hint: use collective communication
	//
	// below hints show some idea, but it can be done even easier
	//
	// in task 29, a new communication group is not necessarily needed, depends
	// on your algorithm for 28


	/* redistribute votes */

	/* sum my part of votes locally */

	/* find maximum */

	/* the one with maximum number of votes finds the correct index */

	/* deliver the winning index to all */

	free(lvotes);

	return result;

} /* votes_mpi() */