#include <stdio.h>
#include <string.h>
#include <time.h>
#include "mpi.h"

#define TAM 120
#define DELTA 20

int *juntar(int *v1,int n1,int *v2,int n2);
void quicksort(int * v,int esq,int dir);
void trocaelemento(int *v,int i,int j);

main(int argc, char** argv)
  {   
   int my_rank; 				//identificador do processo	 
   int proc_n;  				//numero de processos
   int metade, resto, resto2;
   int i,j;
   int *vetor,*vet1, *vet2, *vet3, *vet4;
   double tempoInicial,tempoFinal;
   MPI_Status status;
	
   MPI_Init(&argc, &argv);
   MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);
   MPI_Comm_size(MPI_COMM_WORLD, &proc_n);	       

// INICIO DO NIVEL INICIAL (PROCESSO 0)    
   if (my_rank == 0)
     {        
      vetor = (int *) malloc(TAM*(sizeof(int)));
      vet1  = (int *) malloc((TAM/2)*(sizeof(int)));
      vet2  = (int *) malloc((TAM/2)*(sizeof(int)));       
               
      tempoInicial = MPI_Wtime();
      srand(time(NULL));
      
      for (i=0;i<TAM;i++)                       //inicializa vetor com numeros aleatorios
      vetor[i]= rand() % 99;

      metade = TAM/2;
        
      if (TAM >= DELTA)
        {                          
         for (i=0;i<metade;i++)                 //divide metade do vetor p vet1 e outra metade p vet2
           { 
              vet1[i]=vetor[i];
              vet2[i]=vetor[i+metade];
           }   
           
         printf("\n Rank %d: vai enviar %d elementos do vetor para os ranks %d e %d \n",my_rank,metade,my_rank+1,my_rank+2);
        
	 MPI_Send(vet1,metade,MPI_INT,my_rank+1,0, MPI_COMM_WORLD);         //envia p proc 1
	 MPI_Send(vet2,metade,MPI_INT,my_rank+2,0, MPI_COMM_WORLD);         //envia p proc 2
	       
         printf("\n Rank %d: envio para baixo com sucesso\n", my_rank);
		   
         MPI_Recv(vet1,metade,MPI_INT,my_rank+1,0,MPI_COMM_WORLD,&status);  //recebe proc 1
	 MPI_Recv(vet2,metade,MPI_INT,my_rank+2,0,MPI_COMM_WORLD,&status);  //recebe proc 2
		   
	 printf("\n Rank %d: recebimento de baixo concluído!!\n", my_rank);
		   
         vetor = juntar(vet1,metade,vet2,metade);           
        }
    
      quicksort(vetor,0,TAM);
         
      tempoFinal = MPI_Wtime();
         
      for(j=0;j<TAM;j++) 
         printf("vetor[%d]=%d\n",j,vetor[j]);
                 
      printf("\nTempo de Execução do Algoritmo = %f segundos. \n", tempoFinal - tempoInicial);
     }

// FIM DO NIVEL INICIAL (PROCESSO 0)   

// INICIO DO NIVEL INTERMEDIARIO (PROCESSOS 1 E 2)
	
   if ((my_rank > 0) && (my_rank <=2))
     {      
      vet1  = (int *) malloc((TAM/2)*(sizeof(int)));  

      metade = TAM/2;        
                   
      MPI_Recv(vet1,metade,MPI_INT,0,0,MPI_COMM_WORLD,&status);                
      printf("\n Rank %d: recebimento de cima (processo 0) de %d elementos do vetor concluido!\n",my_rank,metade);  

      metade = metade/2;

      if (metade >= DELTA)
        {
         vet3 = (int *)malloc ((metade)*sizeof(int));
         vet4 = (int *)malloc ((metade)*sizeof(int)); 
         printf("\n Rank %d: vai enviar %d elementos do vetor para os ranks: %d e %d\n",my_rank,metade,(my_rank*2)+1,(my_rank*2)+2);
         
         for(i=0;i<metade;i++)          //divide metade de vet1 p vet3 e outra metade p vet4
           {
              vet3[i]=vet1[i];
              vet4[i]=vet1[i+metade];
           }
         MPI_Send(vet3,metade,MPI_INT,(my_rank*2)+1,0, MPI_COMM_WORLD);
         MPI_Send(vet4,metade,MPI_INT,(my_rank*2)+2,0, MPI_COMM_WORLD);
         printf("\n Rank %d: envio para baixo com sucesso\n", my_rank);

         MPI_Recv(vet3,metade,MPI_INT,(my_rank*2)+1,0,MPI_COMM_WORLD,&status);
         MPI_Recv(vet4,metade,MPI_INT,(my_rank*2)+2,0,MPI_COMM_WORLD,&status); 
         printf("\n Rank %d: recebimento de baixo concluído!!\n", my_rank);

         vet1 = juntar(vet3,metade,vet4,metade); 
        }
      metade=metade*2;
      quicksort(vet1,0,metade);
      MPI_Send(vet1,metade,MPI_INT,0,0, MPI_COMM_WORLD); 
      printf("\n Rank %d: envio de volta para o processo 0 de %d elementos do vetor concluído!!\n",my_rank,metade);
     }

// FIM DO NIVEL INTERMEDIARIO (PROCESSOS 1 E 2)

// INICIO DO NIVEL FOLHA (PROCESSOS 3, 4, 5 E 6)

   if (my_rank > 2)
     {
      metade = TAM/4; 
      vet3 = (int *)malloc ((metade)*sizeof(int));
      resto = (my_rank % 2);  
      if (resto == 0)           //se my_rank é par 
        {
         MPI_Recv(vet3,metade,MPI_INT,(my_rank-2)/2,0,MPI_COMM_WORLD,&status);
         printf("\n Rank %d: recebeu do rank %d %d elementos do vetor\n", my_rank,(my_rank-2)/2,metade); 
        }     
      else
        {
         MPI_Recv(vet3,metade,MPI_INT,(my_rank-1)/2,0,MPI_COMM_WORLD,&status);
         printf("\n Rank %d: recebeu do rank %d %d elementos do vetor\n", my_rank,(my_rank-1)/2,metade);  
        }   
      quicksort(vet3,0,metade);
      resto2 = (my_rank % 2); 
      if (resto2 == 0) //se my_rank é par 
        {
         MPI_Send(vet3,metade,MPI_INT,(my_rank-2)/2,0, MPI_COMM_WORLD);
         printf("\n Rank %d: enviou de volta para rank %d %d elementos do vetor\n",my_rank,(my_rank-2)/2, metade);
        }
      else
        {
         MPI_Send(vet3,metade,MPI_INT,(my_rank-1)/2,0, MPI_COMM_WORLD);
         printf("\n Rank %d: enviou de volta para rank %d %d elementos do vetor\n",my_rank,(my_rank-1)/2,metade);
        }
     }

// FIM DO NIVEL FOLHA (PROCESSOS 3, 4, 5 E 6)

 MPI_Finalize();
 return(0);
}

void trocaelemento(int *v,int i,int j){
   int t;
   t = v[i];
   v[i] = v[j];
   v[j] = t;
}

void quicksort(int * v,int esq,int dir){  
   int i,ult;
   if(esq>=dir)
      return;
   trocaelemento(v,esq,(esq + dir)/2);
   ult = esq;
   for(i=esq+1;i<= dir;i++)
      if(v[i]<v[esq])
         trocaelemento(v,++ult,i);
   trocaelemento(v,esq,ult);
   quicksort(v,esq,ult-1);
   quicksort(v,ult+1, dir);
}

int *juntar(int *v1,int n1,int *v2,int n2){  
   int i,j,k;
   int * saida;

   saida = (int *)malloc((n1+n2)*sizeof(int));

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