// MPICH.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"
//#include <iostream>
//#include "mpi.h"
//
//using namespace std;
//
////int _tmain(int argc, _TCHAR* argv[])
//int main(int argc, char* argv[])
//{
// //cout << "Hello World\n";
//
// int  nTasks, rank; 
//
// MPI_Init(&argc,&argv);
// MPI_Comm_size(MPI_COMM_WORLD,&nTasks);
// MPI_Comm_rank(MPI_COMM_WORLD,&rank);
//
// printf ("Number of threads = %d, My rank = %d\n", nTasks, rank);
//
// MPI_Finalize();
// return 0;
//}




// ---------------------------

/*
BUBLE SORT
*/

////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
//////////////////////Required Headers//////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
//#include "stdafx.h"
#include <iostream>

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

////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
//////////////////////Time Calculation Function/////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
double startT, stopT; //Doubles to hold starting and finishing times.

double startTime;

int showElapsed (int id, char* m) {
 printf ("%d: %s %f secs\n", id, m, (clock () - startTime) / CLOCKS_PER_SEC);
 return id;
}

////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
///////////////Function to merge two arrays/////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
int* mergeArrays (int* v1, int n1, int* v2, int n2)
{
 int i, j, k;
 int* result;

 result = (int *)malloc ((n1 + n2) * sizeof (int)); //Allocating space 
 //for result array

 //Merge arrays,and put them in a right order !
 i = 0;
 j = 0;
 k = 0;

 while (i < n1 && j < n2)
  if (v1[i] < v2[j]) {
   result[k] = v1[i];
   i++;
   k++;
  } else {
   result[k] = v2[j];
   j++;
   k++;
  }

 if (i == n1)
  while (j < n2) {
   result[k] = v2[j];
   j++;
   k++;
  }
 else
  while (i < n1) {
   result[k] = v1[i];
   i++;
   k++;
  }

 return result;
}

////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
///////////////Function to swap two elements in array///////////////////////////
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
int swap (int v [], int i, int j)
{
 //Swapping two elements.
 int t;
 t = v[i];
 v[i] = v[j];
 v[j] = t;
 return v[j];
}

////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
///////////////Bubble Sort function/////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
int sort (int* v, int n)
{
 int i, j;

 for (i = n - 2; i >= 0; i--)
  for (j = 0; j <= i; j++)
   if (v[j] > v[j + 1])
    swap (v, j, j + 1);
 return  swap (v, j, j + 1);
}

////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
///////////////Main Function That Contains MPI PART/////////////////////////////
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
int main (int argc, char ** argv)
{
 FILE* fin;            //Our Input File, (It contains the unsorted Array)

 int* data;            //Our unsorted array
 int* resultant_array; //Sorted Array
 int* sub;
 //Essential Variables
 int m, n;
 int id, p;
 int s;
 int i;
 int z;
 int move;
 MPI_Status status;

 MPI_Init (&argc, &argv);
 MPI_Comm_rank (MPI_COMM_WORLD, &id);
 MPI_Comm_size (MPI_COMM_WORLD, &p);

 //Task Of The Master Processor
 if (id == 0) {
  //Read Unsorted Array From File and Other Initilization Procedures.
  int r;

  // fin = fopen (argv[1], "r"); //Open the text file to read.

  fin = fopen ("unsorted_array.txt", "w");

  fscanf (fin, "%d", &n);
  s = n / p;
  r = n % p;
  data = (int *)malloc ((n + s - r) * sizeof (int));

  for (i = 0; i < n; i++)
   fscanf (fin, "%d", & (data[i])); //Read from file.

  fclose (fin);                     //Close the file.

  if (r != 0) {
   for (i = n; i < n + s - r; i++)
    data[i] = 0;

   s = s + 1;
  }

  startT = clock ();                                  //Start The Time.
  MPI_Bcast (&s, 1, MPI_INT, 0, MPI_COMM_WORLD);
  resultant_array = (int *)malloc (s * sizeof (int)); //Allocating result array
  //Sending data array from master to all other slaves
  MPI_Scatter (data, s, MPI_INT, resultant_array, s, MPI_INT, 0, MPI_COMM_WORLD);
  sort (resultant_array, s);
 } else {
  MPI_Bcast (&s, 1, MPI_INT, 0, MPI_COMM_WORLD);
  //Allocating resultant array
  resultant_array = (int *)malloc (s * sizeof (int));
  MPI_Scatter (data, s, MPI_INT, resultant_array, s, MPI_INT, 0, MPI_COMM_WORLD);
  //Each slave processor will sort according to the array partitioning n/p
  sort (resultant_array, s); //Sort the array up to index s.
 }

 move = 1;

 //Merging the sub sorted arrays to obtain resultant sorted array
 while (move < p) {
  if (id%(2*move)==0) {
   if (id + move < p) {                     //Receive
    MPI_Recv (&m, 1, MPI_INT, id + move, 0, MPI_COMM_WORLD, &status);
    sub = (int *)malloc (m * sizeof (int)); //Allocate space for sub array
    MPI_Recv (sub, m, MPI_INT, id + move, 0, MPI_COMM_WORLD, &status);
    //Obtaing resultant array by merging sub sorted array
    resultant_array = mergeArrays (resultant_array, s, sub, m);
    s = s + m;
   }
  } else { //Send datas to neighbour processors
   int near = id - move;
   MPI_Send (&s, 1, MPI_INT, near, 0, MPI_COMM_WORLD);
   MPI_Send (resultant_array, s, MPI_INT, near, 0, MPI_COMM_WORLD);
   break;
  }

  move = move * 2;
 }

 //Final Part, In this part Master CPU outputs the results.!!!
 if (id == 0) {
  //Stop The Time.
  stopT = clock ();

  //Outputting Array Size, Available Processors, Total Working Time
  printf ("\nArray Size: %d \nTotal available processor(s): %d \nCompleted Sorting In %f secs\n",
      s, p, (stopT - startT) / CLOCKS_PER_SEC);
 }

 MPI_Finalize (); //Finalize MPI environment.

 //Outputting Unsorted array and The Sorted One.
 printf ("\nThe UnSorted Array :\n\n");

 for (z = 0; z < s; ++z)
  printf ("%d ", data[z]);

 printf ("\n\nThe Sorted Array :\n\n");

 for (z = 0; z < s; ++z)
  printf ("%d ", resultant_array[z]);
}
////////////////////////////////////////////////////////////////////////////////
//////////////////////End of Main function//////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////