/**********************************************************
  File:          find_min.cc                              
  Description:   Functions to find the minimum in an     
                 array that is split among the processes 
                                                         
  Author:        Dana Vrajitoru                          
  Class:         B424
  Date:          September 21, 2004
***********************************************************/
#include <mpi.h>
#include <cmath>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
#include "find_min.h"

// A function that generates a random array.
int *Generate_array(int size, int limit)
{
  int *the_array = new int[size];
  for (int i=0; i<size; i++)
    the_array[i] = rand() % limit;
  return the_array;
}

// A function that finds the minimum in an array.
int Find_min(int *the_array, int size)
{
  int min=the_array[0];
  for (int i=1; i<size; i++)
    if (the_array[i] < min)
      min = the_array[i];
  return min;
}

// The function that inputs the size and the upper limit for the
// elements of the array for the first process, shares this
// information with the others, then calls the function that generates
// the array for each proc.
void Initialize_array(int *&array, int &size, int proc_id, int nb_proc)
{
  int limit;
  if (proc_id == 0) {
    cout << "Enter the size of the array" << endl;
    cin >> size;
    cout << "Enter an upper limit for the elements of the array" << endl;
    cin >> limit;
  }
  size = size / nb_proc;
  MPI_Bcast(&size, 1, MPI_INT, 0, MPI_COMM_WORLD);
  MPI_Bcast(&limit, 1, MPI_INT, 0, MPI_COMM_WORLD);
  array = Generate_array(size, limit);
}

// The function that finds the global minimum.  Each process finds the
// minimum in its part of the array.  Each process but the last waits
// for the previous process to send it the minimum so far, then
// updates its own minimum according to it.  Then each process but the
// first sends the current minimum to the next one.  The last process
// writes the global minimum.
void Find_global_min(int my_min, int proc_id, int nb_proc)
{
  int recv_min = my_min;
  MPI_Status status;

  cout << "The process number " << proc_id << " has the minimum "
       << my_min << endl;
  MPI_Barrier(MPI_COMM_WORLD);

  if (proc_id != nb_proc-1) {
    MPI_Recv(&recv_min, 1, MPI_INT, proc_id+1, 0, MPI_COMM_WORLD, &status);
    if (recv_min < my_min)
      my_min = recv_min;
  }
  if (proc_id != 0)
    MPI_Send(&my_min, 1, MPI_INT, proc_id-1, 0, MPI_COMM_WORLD);
  else
    cout << "The global minimum is " << my_min << endl;
}

// The function that finds the global minimum.  Each process finds the
// minimum in its part of the array.  Each process but the first waits
// for the previous process to send it the minimum so far, then
// updates its own minimum according to it.  Then each process but the
// last sends the current minimum to the next one.  The last process
// writes the global minimum.
void Find_global_min_last(int my_min, int proc_id, int nb_proc)
{
  int prev_min = my_min;
  MPI_Status status;

  cout << "The process number " << proc_id << " has the minimum "
       << my_min << endl;
  MPI_Barrier(MPI_COMM_WORLD);

  if (proc_id != 0) {
    MPI_Recv(&prev_min, 1, MPI_INT, proc_id-1, 0, MPI_COMM_WORLD, &status);
    if (prev_min < my_min)
      my_min = prev_min;
  }
  if (proc_id != nb_proc-1)
    MPI_Send(&my_min, 1, MPI_INT, proc_id+1, 0, MPI_COMM_WORLD);
  else
    cout << "The global minimum is " << my_min << endl;
}

/**********************************************************************/
// Functions to be implemented by the student.

// The function that finds the global minimum using a binary tree
// communication scheme. The complexity is the binary logarithm of the
// number of processes.
void Find_global_min_lnp(int my_min, int proc_id, int nb_proc)
{
  // Code to be implemented by the student.
}

// This function should allocate an array with the given size for each
// process. Each process inputs their own part of the array in
// order. Then process 0 can start to input the numbers from the
// user. Each process except for 0 should wait for a message from the
// previous process telling them when their time to start the
// input. After they are done, each process except for the last one
// should send a message to the next process telling them to start the
// input. Each process should output their id just before they start
// asking the user for numbers.
int *Input_array(int proc_id, int nb_proc, int size)
{
  // Code to be implemented by the student.  
}