#include <mpi.h>
#include <stdio.h>
#include <stdlib.h>
#define  TRUE 1
#include "math.h"
#include <time.h>
#include <string.h>
#include "mpe.h"

	int event1a, event1b, event2a, event2b, event3a, event3b, event4a, event4b,event5a, event5b, event6a, event6b,
    	event7a, event7b, event8a, event8b,event9a,  event9b, event10a, event10b,event11a, event11b, event12a, event12b;

//#define  DEBUG

#define  INIT  1        // Message giving size and height
#define  DATA  2        // Message giving vector to sort
#define  ANSW  3        // Message returning sorted vector
#define  FINI  4        // Send permission to terminate

// Required by qsort()
int IncOrder ( const void* left, const void* right );  // for qsort()
void parallelMerge ( int *vector, int size, int myHeight );

int main ( int argc, char* argv[] )
{
   int 		myRank;
   int 		nProc;
   int 		rc;
   int   	size;          // Size of the vector being sorted
   int 	        *vector,       // Vector for parallel sort
        	*solo;         // Copy for sequential sort
   double 	start,         // Begin parallel sort
          	middle,        // Finish parallel sort
          	finish;        // Finish sequential sort
    FILE *f1;

   rc = MPI_Init(&argc, &argv);


   if ( rc < 0 )
   	{
      		puts ("Failed to enroll in MPI.  Abort!");
      		exit(-1);
   	}
	
	MPI_Pcontrol( 0 );
		#if defined( NO_MPI_LOGGING )
	   	 	MPE_Init_log();
		#endif	

   if ( argc > 1 )
      	size = atoi(argv[1]);
	
	rc = MPI_Comm_rank (MPI_COMM_WORLD, &myRank);
   	rc = MPI_Comm_size (MPI_COMM_WORLD, &nProc);

	MPE_Log_get_state_eventIDs( &event1a, &event1b );
	MPE_Log_get_state_eventIDs( &event2a, &event2b );
	MPE_Log_get_state_eventIDs( &event3a, &event3b );
	MPE_Log_get_state_eventIDs( &event4a, &event4b );
	MPE_Log_get_state_eventIDs( &event5a, &event5b );
	MPE_Log_get_state_eventIDs( &event6a, &event6b );

#ifdef DEBUG
   printf ("Started rank %d\n", myRank);  fflush(stdout);
#endif

   if ( myRank == 0 )        // Host process
	{
		MPE_Describe_state( event1a, event1b, "Read data from the file", "red" );
		MPE_Describe_state( event2a, event2b, "parallel Merge sort routine calledby Master", "orange" );
		MPE_Describe_state( event3a, event3b, "Receiving height and size of data", "red" );
		MPE_Describe_state( event4a, event4b, "Receiving Array elements ....", "red" );
		MPE_Describe_state( event5a, event5b, "Parallel Merge sort routine called other than Master", "red" );
		MPE_Describe_state( event6a, event6b, "quick sort in case of single process only", "red" );

		int rootHt = 0;
		int nodeCount = 1;

      	while (nodeCount < nProc)
		{  
			nodeCount += nodeCount;
			rootHt++;
		}

	printf ("%d processes mandates root height of %d\n", nProc, rootHt);
	printf ("Enter the size of array \t");

	//scanf("%d",&size);
	
	MPI_Pcontrol( 1 );
	MPE_Log_event( event1a, 0, NULL );	       			
		//--------COUNT LINES---------
			int lines=0;
			char c;
			f1=fopen("d1000000","r");
			while((c = fgetc(f1)) != EOF)
			if(c == '\n')
			lines++;
			fclose(f1);
		//----------------------------
	printf("Data read and Lines are: %d \n",lines);
		size=lines;
		printf("%d\n",size);
		vector=(int *)malloc(size*sizeof(int));

		if(vector==0) 
			printf("Malloc memory error!");
		//---------------Data Reading-------------------

		f1=fopen("d1000000","r");

		int n;
		int i=0;

		for(i=0;i<size;i++) 
		{
			fscanf(f1, "%d", &vector[i]);

		//	printf("%d \t",n);
		}

			fclose(f1);
	MPE_Log_event( event1b, 0, NULL );
		//------------------------------------------------
		printf("\n");
	// Capture time to sequentially sort the idential array
     	 
	  solo = (int*) calloc ( size, sizeof *solo );
      	  memcpy (solo, vector, size * sizeof *solo);
	
      		start = MPI_Wtime();
	MPE_Log_event( event2a, 0, NULL );
      			parallelMerge ( vector, size, rootHt);
	MPE_Log_event( event2b, 0, NULL );
      		middle = MPI_Wtime();
	}  // End of Rank=0;

else                      // Node process
	{



     	int   iVect[2],        // Message sent as an array
              height,          // Pulled from iVect
              parent;          // Computed from myRank and height
        MPI_Status status;     // required by MPI_Recv


	MPE_Log_event( event3a, 0, NULL );
        	rc = MPI_Recv( iVect, 2, MPI_INT, MPI_ANY_SOURCE, INIT,MPI_COMM_WORLD, &status );
	MPE_Log_event( event3b, 0, NULL );

        size   = iVect[0];     // Isolate size
        height = iVect[1];     // and height
        vector = (int*) calloc (size, sizeof *vector);

	MPE_Log_event( event4a, 0, NULL );
        	rc = MPI_Recv(vector,size,MPI_INT, MPI_ANY_SOURCE, DATA,MPI_COMM_WORLD,&status );
	MPE_Log_event( event4b, 0, NULL );

	MPE_Log_event( event5a, 0, NULL );
        	parallelMerge ( vector, size, height );
	MPE_Log_event( event5b, 0, NULL );

	#ifdef DEBUG
      		printf ("%d resigning from MPI\n", myRank); 
		fflush(stdout);
	#endif

	//MPE_Log_sync_clocks();
	//#if defined( NO_MPI_LOGGING )
    	//	if ( argv != NULL )
        //		MPE_Finish_log( argv[0] );
    	//	else
        //		MPE_Finish_log( "cpilog" );
	//#endif

       MPI_Finalize();
       return 0;
       }

// Only the rank-0 process executes here.

MPE_Log_event( event6a, 0, NULL );
   qsort( solo, size, sizeof *solo, IncOrder );
MPE_Log_event( event6b, 0, NULL );

   finish = MPI_Wtime();

#ifdef DEBUG
      printf ("%d resigning from MPI\n", myRank); fflush(stdout);
#endif
   
if(myRank==0)
	{
	//int i;
	//printf("Finalize array : \n");
	//for(i=0;i<size;i++)
	//	{
	//	  printf("%10d",vector[i]);
	//	  printf("\t");
	//	}
	//	printf("\n");
	
   
	//printf ("Sequential:  %3.3f\n", (finish-middle) );
    	printf (" \n Parallel:  %3.3f\n", (middle-start) );
   	//printf ("  Speed-up:  %3.3f\n", (finish-middle)/(middle-start) );
	}
MPE_Log_sync_clocks();
#if defined( NO_MPI_LOGGING )
    if ( argv != NULL )
        MPE_Finish_log( argv[0] );
    else
        MPE_Finish_log( "cpilog" );
#endif

   MPI_Finalize();
}


// Required by qsort()
int IncOrder ( const void* left, const void* right )
{
   int *lt = (int*) left,
        *rt = (int*) right,
         diff = *lt - *rt;

   if ( diff < 0 ) return -1;
   if ( diff > 0 ) return +1;
   return 0;
}
//////////////////////////////////////////////////////////////////
//////////////////Parallel Merge sort ///////////////////////////
void parallelMerge( int *vector, int size, int myHeight)
{  int parent;
   int myRank, nProc;
   int rc, nxt, rtChild;
   double t1,t2;
	MPI_Pcontrol( 1 );
		MPE_Log_get_state_eventIDs( &event7a, &event7b );
		MPE_Log_get_state_eventIDs( &event8a, &event8b );
		MPE_Log_get_state_eventIDs( &event9a, &event9b );
		MPE_Log_get_state_eventIDs( &event10a, &event10b );
		MPE_Log_get_state_eventIDs( &event11a, &event11b );
		MPE_Log_get_state_eventIDs( &event12a, &event12b );
	
	rc = MPI_Comm_rank (MPI_COMM_WORLD, &myRank);
   	rc = MPI_Comm_size (MPI_COMM_WORLD, &nProc);
	
	if ( myRank == 0 ) 
    {
      MPE_Describe_state( event7a, event7b, "Parallel Merge Recursive call", "Orange" );
      MPE_Describe_state( event8a, event8b, "Sending size and height to child", "green" );
      MPE_Describe_state( event9a, event9b, "Sending Array data to child process", "blue" );
      MPE_Describe_state( event10a, event10b, "Receiving data back from child.. ", "green" );
      MPE_Describe_state( event10a, event10b, "Squential quick sort in multi processes case.. ", "green" );
      MPE_Describe_state( event10a, event10b, "Sending data back to master process.. ", "green" );
	
		
    }
	
   parent = myRank & ~(1<<myHeight);
   nxt = myHeight - 1;
   if ( nxt >= 0 )
      rtChild = myRank | ( 1 << nxt );

#ifdef DEBUG
   if ( myHeight > 0 )
      printf ("%#x -> %#x -> %#x among %d\n", parent, myRank, rtChild, nProc);
#endif
   if ( myHeight > 0 )
   {
	//Possibly a half-full node in the processing tree
      if ( rtChild >= nProc )     // No right child.  Move down one level
	{
	MPE_Log_event( event7a, 0, NULL );
         parallelMerge ( vector, size, nxt );
	MPE_Log_event( event7a, 0, NULL );
	}
      else
      {
         int   left_size  = size / 2;
	 int   right_size = size - left_size;
         int *leftArray  = (int*) calloc (left_size, sizeof *leftArray),
              *rightArray = (int*) calloc (right_size, sizeof *rightArray);
         int   iVect[2];
         int   i, j, k;                // Used in the merge logic
         MPI_Status status;            // Return status from MPI

         memcpy (leftArray, vector, left_size*sizeof *leftArray);
         memcpy (rightArray, vector+left_size, right_size*sizeof *rightArray);
#ifdef DEBUG
         printf ("%d sending data to %d\n", myRank, rtChild); 
	 fflush(stdout);
#endif
         iVect[0] = right_size;
         iVect[1] = nxt;
MPE_Log_event( event8a, 0, NULL );
    rc = MPI_Send( iVect, 2, MPI_INT, rtChild, INIT,MPI_COMM_WORLD);
MPE_Log_event( event8b, 0, NULL );

MPE_Log_event( event9a, 0, NULL );
    rc = MPI_Send( rightArray, right_size, MPI_INT, rtChild, DATA,  MPI_COMM_WORLD);
MPE_Log_event( event9b, 0, NULL );

MPE_Log_event( event10a, 0, NULL );
         parallelMerge ( leftArray, left_size, nxt );
MPE_Log_event( event10b, 0, NULL );
#ifdef DEBUG
         printf ("%d waiting for data from %d\n", myRank, rtChild); fflush(stdout);
#endif

MPE_Log_event( event10a, 0, NULL );
         rc = MPI_Recv( rightArray, right_size, MPI_INT, rtChild, ANSW,MPI_COMM_WORLD, &status );
MPE_Log_event( event10b, 0, NULL );

         // Merge the two results back into vector
         i = j = k = 0;
         while ( i < left_size && j < right_size )
            if ( leftArray[i] > rightArray[j])
               vector[k++] = rightArray[j++];
            else
               vector[k++] = leftArray[i++];
         while ( i < left_size )
            vector[k++] = leftArray[i++];
         while ( j < right_size )
            vector[k++] = rightArray[j++];
      }
   }
   else
   {
	t1=MPI_Wtime();
	MPE_Log_event( event11a, 0, NULL );
      		qsort( vector, size, sizeof *vector, IncOrder );
	MPE_Log_event( event11b, 0, NULL );
	t2=MPI_Wtime();
printf("Process with ID %d and time %6.3f  \n",myRank,t2-t1);

#ifdef DEBUG
      printf ("%d leaf sorting %d items.\n", myRank, size); fflush(stdout);
#endif
   }


   if ( parent != myRank )
MPE_Log_event( event12a, 0, NULL );
      rc = MPI_Send( vector, size, MPI_INT, parent, ANSW,MPI_COMM_WORLD );
MPE_Log_event( event12a, 0, NULL );
}