/**********************************************************
  File:          master.cc                              
  Description:   A program that inputs an integer number 
                 and determines if it is a prime number or 
		 not in parallel.
		 The functions for the master process.
                                                         
  Author:        Dana Vrajitoru                          
  Organization:  IUSB                                    
  Date:          September 28. 2004
***********************************************************/

#include <mpi.h>
#include <iostream>
using namespace std;
#include <cmath>
#include "master.h"
#include "slave.h"

// A function that sends the divisor to all of the processes except
// for the master. If the divisor is > 1, this causes all of them to
// stop loop that searches for a divisor. The function also makes sure
// that it only sends the divisor once to each process by the use of
// the static variable count.
void Finalize_all(int nr_proc, int divisor)
{
  static int count = 0;
  if (count == 0) {
    for (int i=1; i<nr_proc; i++)
      MPI_Send(&divisor, 1, MPI_INT, i, 0, MPI_COMM_WORLD);
    count++;
  }
}

// A function that checks if there is any incoming message from any
// slave process. In case there is a message with a non-trivial
// divisor, it stops all of them.
void Check_incoming(int nr_proc, MPI_Request &request, 
		    int &div, int &nr_done, int &divisor)
{
  MPI_Status status;
  int flag;
  MPI_Test(&request, &flag, &status);
  if (flag) {
    nr_done++;
    if (div > 1) {
      divisor = div;
      Finalize_all(nr_proc, div);
    }
    if (nr_done < nr_proc-1)
      MPI_Irecv(&div, 1, MPI_INT, MPI_ANY_SOURCE, 0, 
		MPI_COMM_WORLD, &request);
  }
}

// The function that checks if n is a prime. While it is testing for
// the divisors between start and end, it also checks if any other
// process has already found a non-trivial divisor, and in this case,
// it stops all of them. It also makes sure there are no pending
// processes waiting to send or receive something.
int Check_prime_master(int nr_proc, int start, int end, int n)
{
  MPI_Request request;
  int flag, div=1, divisor = 1;
  int nr_done = 0;

  MPI_Irecv(&div, 1, MPI_INT, MPI_ANY_SOURCE, 0, MPI_COMM_WORLD, &request);
  for (int i=start; i<=end && divisor == 1; i += 2) { 
    if (n % i == 0) {
      divisor = i;
      Finalize_all(nr_proc, divisor);
    }
    Check_incoming(nr_proc, request, div, nr_done, divisor);
  }
  while (nr_done < nr_proc-1)
    Check_incoming(nr_proc, request, div, nr_done, divisor);
  if (divisor == 1) 
    Finalize_all(nr_proc, divisor);
  return divisor; 
}

// The master function that inputs the number, finds out if it is a
// prime by coordinating all of the others, then outputs the result.
void Master(int nr_proc)
{
  int n, divisor;
  cout << "Enter a number to check if it is a prime or not" << endl;
  cin >> n;
  MPI_Bcast(&n, 1, MPI_INT, MASTER_ID, MPI_COMM_WORLD);

  if (n % 2 == 0)
    divisor = 2;
  else {
    int sqroot = sqrt(float(n)); 
    int steps = (sqroot - 2)/nr_proc;
    int start = 3, end = 2 + steps;
  
    divisor = Check_prime_master(nr_proc, start, end, n);
  }
  if (divisor == 1)
    cout << "The number is prime" << endl;
  else
    cout << "The number is not prime and has at least this divisor: "
	 << divisor << endl;
}