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

#define CONS 8719
#define MAX_SIZE 9999
#define N 100

int init;
int local_primes[MAX_SIZE];
int local_size;

void vote(int rank, int size)
{
	srand(time(NULL) + CONS * rank);
	int myvote = rand() % size;
	if (rank == 0) {
 		MPI_Status status;
		int votes[size], i, count[size];
		votes[0] = myvote;
		for (i = 1; i < size; i++)
			MPI_Recv(&votes[i], 1, MPI_INT, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &status);
		for (i = 0; i < size; i++)
			count[i] = 0;
		for (i = 0; i < size; i++)
			count[votes[i]]++;
		int max = count[0];
		init = 0;
		for (i = 1; i < size; i++)
			if (count[i] > max) {
				init = i;
				max = count[i];
			}
		MPI_Bcast(&init, 1, MPI_INT, 0, MPI_COMM_WORLD);
	}
	else {
		MPI_Send(&myvote, 1, MPI_INT, 0, 1, MPI_COMM_WORLD);
		MPI_Bcast(&init, 1, MPI_INT, 0, MPI_COMM_WORLD);
	}
	MPI_Barrier(MPI_COMM_WORLD);
}

int is_prime(int nr)
{

	if (local_size == 0)
		return 1;
	int i;

	for (i = 0; i < local_size; i++)
		if (nr % local_primes[i]== 0)
			return 0;
	return 1;
}

int main(int argc, char **argv) {
	int rank, size;
	int prev, next;

	MPI_Init(&argc, &argv);
	MPI_Comm_rank(MPI_COMM_WORLD, &rank);
	MPI_Comm_size(MPI_COMM_WORLD, &size);

	prev = (rank - 1) % size;
	next = (rank + 1) % size;
	if (rank == 0)
		prev = size - 1;

	vote(rank, size);
	int i, count = 0;
	MPI_Status status;
	int sizep;
	sizep = size - ((rank-init)%size);
	if(rank!=init)
		printf("%d %d\n",rank,sizep);
	MPI_Barrier(MPI_COMM_WORLD);


/******************************************************************************/
/* procesul initiator */
/******************************************************************************/

	if (rank == init){
		int rec, s = 1;
		MPI_Request req;
		for (i = 2; i <= N; i++) {

			MPI_Send(&i, 1, MPI_INT, next, 1, MPI_COMM_WORLD);
			int ok = 1, prime;
			while(ok) {
				if(s)
					MPI_Irecv(&rec, 1, MPI_INT, prev, MPI_ANY_TAG, MPI_COMM_WORLD, &req);
				MPI_Test(&req, &s, &status);

				//procesul initiator primeste un mesaj
				if (s) {

						switch(status.MPI_TAG) {
						//am primit un nr prim
						case 1:
							ok = 0;
							prime = is_prime(rec);

							if(prime) {

								if (count % size == 0){
									local_primes[local_size++] = rec;
								}
								else
									MPI_Send(&rec, 1, MPI_INT, next, 2, MPI_COMM_WORLD);
								count ++;
							}
							break;
						//am primit un nr neprim
						case 4:
							ok = 0;
							break;
						case 3:
						//am primit mesaj de finalizare
							ok = 0;
							MPI_Send(&rec, 1, MPI_INT, next, 3, MPI_COMM_WORLD);
							break;
						default:
							ok = 0;
							break;
						}
				}
			}
		}
		MPI_Send(&rec, 1, MPI_INT, next, 3, MPI_COMM_WORLD);
#if 0
		while(1) {
			if(s)
				MPI_Irecv(&rec, 1, MPI_INT, prev, MPI_ANY_TAG, MPI_COMM_WORLD, &req);
			MPI_Test(&req, &s, &status);
			if (s) {
					if (status.MPI_TAG == 3) {
						MPI_Send(&rec, 1, MPI_INT, next, 3, MPI_COMM_WORLD);
						break;
					}
					printf("am primit %d\n",rec);
					if (count % size == 0)
						local_primes[local_size++] = rec;
					else
						MPI_Send(&rec, 1, MPI_INT, next, 2, MPI_COMM_WORLD);
					count ++;
			}
		}
#endif
	}
	else {
		int nr;
		int ok = 1;
		int prime;
		while(ok) {
			MPI_Recv(&nr, 1, MPI_INT, prev, MPI_ANY_TAG, MPI_COMM_WORLD, &status);
			//printf("r=%d nr=%d tag=%d\n",rank, nr, status.MPI_TAG);
			//daca e mesaj de verificare
			switch(status.MPI_TAG){
			//mesaj de test
			case 1:
				prime = is_prime(nr);

				if (prime) {
					MPI_Send(&nr, 1, MPI_INT, next, 1, MPI_COMM_WORLD);
				}
				else
					MPI_Send(&nr, 1, MPI_INT, next, 4, MPI_COMM_WORLD);
				if (nr == N && prime == 0)
					MPI_Send(&nr, 1, MPI_INT, next, 3, MPI_COMM_WORLD);
				break;
			case 2:
				if(nr == 89) printf("te-am prins\n");
				if (count % sizep == 0) {
					local_primes[local_size++] = nr;
					MPI_Send(&nr, 1, MPI_INT, next, 4, MPI_COMM_WORLD);
				}
				else {
					MPI_Send(&nr, 1, MPI_INT, next, 2, MPI_COMM_WORLD);
				}
				count++;
				break;
			case 4:

				MPI_Send(&nr, 1, MPI_INT, next, 4, MPI_COMM_WORLD);
				break;
			case 3:
				ok = 0;
				MPI_Send(&nr, 1, MPI_INT, next, 3, MPI_COMM_WORLD);
				break;
			}
		}
	}

	if (rank == init) {
		printf("%d : ",rank);
		for (i = 0; i < local_size; i++)
			printf("%d ", local_primes[i]);
		printf("\n");
		fflush(stdout);
		MPI_Send(&i, 1, MPI_INT, next, 1, MPI_COMM_WORLD);
	}
	else {
		MPI_Recv(&i, 1, MPI_INT, prev, 1, MPI_COMM_WORLD, &status);
		printf("%d : ",rank);
		for (i = 0; i < local_size; i++)
			printf("%d ", local_primes[i]);
		printf("\n");
		fflush(stdout);
		MPI_Send(&i, 1, MPI_INT, next, 1, MPI_COMM_WORLD);
	}

	MPI_Finalize();
	return 0;
}