#undef SEEK_SET
#undef SEEK_END
#undef SEEK_CUR
#include "mpi.h"
#include <iostream>
#include <cstdlib>
using namespace std;
/*************************************************
* copyright ? 2013 Soheil Hooshdaran			 *
* The purpose of this program is to sort a  	 *
* nember of randomly generated numbers			 *
*************************************************/

void generate( int *A, int m, int s, int n, int rank);

int main( int argc, char*argv[])
{
/***************Executed on all processors**************/
	 int 	*cat;			 //used to categorize  the numbers according to their rank-the
							 //small buckets
	 int 	*A;   			 //Array to hold numbers
	 int 	i, j, k;   		 //Loop indices
	 int	base, r;   		 //Used as the range for numbers
	 int	m;				 //m numbers will be generated
	 int    iLBucketSize;    //size of the large bucket at the rank 0 process
	 int    *lBucket;        //The large bucket at the rank 0 process
	 int	iWorldSize;
	 int 	iRank;
	 int 	disp;			//displaces the index in the case there is a duplicated 
	                        //number for a processor  
	                        
	 int temp;		 //holds a copy of a given number temporarily
	 int count = 0;	 //holds the number of times a given numer is divisible by
	                 // the size  of eachsmall bucket and used as index into the cat array
	     
	 
	
	 MPI_Init(&argc, &argv);
	
	 MPI_Comm_size( MPI_COMM_WORLD, &iWorldSize);
	
	 MPI_Comm_rank( MPI_COMM_WORLD, &iRank);	 	
	 
	 m = atoi( argv[1]);
	 base = atoi( argv[2]);
	 r = atoi( argv[3]);
	 if(iRank == 0)
	 {
		 cout << "Program written by Soheil Hooshdaran ID 9260642\n"
		        "this program is to sort some randomly generated numbers parallely using"
		        " bucketsort" << endl;
	 }	 
	
	 cout << "My rank is " << iRank << endl;
 
	 int iRangeSize = r - base + 1;   //Size of the interval
	 int catSize = iRangeSize/iWorldSize;   //The size for each category(the range  of 
	                                        //numbers belonging to each process) 
	 
	 cat = new int[catSize];
	 A = new int[m];
	 int *aux = new int[iRangeSize];
	 
	 for(int j=0;j<iRangeSize;++j)
	    aux[j] = -1;
	    
	 for(int j=0;j<m;++j)
	    A[j] = -1;
	  
 	 generate(A, m, iRangeSize, base, iRank);
 	 
 	 cout << "\nRank=" << iRank <<"\nArray A: " << endl;
 	 
 	 
 	 for(int j=0;j<m;++j)
	 {
		 cout << A[j] << ", ";
		 
		 temp = A[j];
		 
		 while(temp >= catSize)
		 {
			 temp -= catSize;
			 ++count;			 
		 }
	    cat[count] = A[j];
	 }  
	    
	 //Sorting using bucket sort
	 for(int j=0;j<m;++j)
	 {
		  if(aux[A[j]] != -1)
		    ++disp;  
	      aux[ A[j] + disp ] = cat[j];       
	 }
	 int index_cat = 0;//the index for the array cat
 	 
 	  	 	 
	 for(int j=0;j<catSize;++j)
       cat[j] = -1;
/*	    
       	 for(int j=0;j<iRangeSize;++j)
	       if(aux[j] != -1)
	       {			   
			   if( index_cat == m )
				 cat[index_cat] = aux[j];
			   else if( index_cat < m )
	             cat[index_cat++] = aux[j];
	           else
		         index_cat = 0;
			}
			
	 cout << "\nAfter bucket sort:" << endl;
	  	  
     for(int j=0;j<catSize;++j)
        cout << cat[j] << ", ";

       if(iRank==0)   //The processor is the master processor	
       { 	   
 	    iLBucketSize = iWorldSize*m;//the size of the large Bucket 	    
		lBucket = new int[iLBucketSize]; //the large bucket
       }//END IF processor is the root	      
*/         
//  MPI_Gather( &(cat[0]), catSize, MPI_INT, lBucket, catSize, MPI_INT, 0, MPI_COMM_WORLD);
	      
  if(iRank == 0 )
  {
//	cout << "\nAfter gathering:" << endl;  	
//	for(int index_lBucket=0;index_lBucket<iLBucketSize;++index_lBucket)
	//   cout << lBucket[index_lBucket] << ", ";
	MPI_Finalize();   
  }
       
   return 0;
}
/*****************************************************/
/*****************************************************/
/*****************************************************/
void generate( int *A, int m, int s, int n, int rank)
{
/*********initialize random seed*********/
	srand( time(0) );
			
	for(int i = 0;i<m;++i)
//	   A[i] = (rand() % s) + (n*rank);
 
 A[i]=1;	  
}