#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <mpi.h>

#define MASTER 0		/* taskid of first task */

void showVector(int *v, int n, int id);

double startT, stopT;

/*function to print a vector*/
void showVector(int *v, int n, int id)
{
	int i;
	printf("%d: ",id);
	for(i=0;i<n;i++)
		printf("%d ",v[i]);
	putchar('\n');
}

int* allocate_int_1D(int n)
{
  int *a;
  a = (int*)malloc(n*sizeof(int));
  return a;
}

int mergeTwo(int *p1, int *r1, int n1, int *p2, int *r2, int n2, int *p, int *r)
{
    int n = n1+n2;
    int i;
    int i1,i2;
      
    i = 0;
    i1 = 0; i2 = 0;
    
    while((i1 < n1) && (i2 < n2))
    {
	if(p1[i1] >= p2[i2])
	{
	    p[i] = p1[i1];
	    r[i] = r1[i1];
	    i++;
	    i1++;
	}
	else
	{
	    p[i] = p2[i2];
	    r[i] = r2[i2];
	    i++;
	    i2++;
	}
    }
    
    if(i1 < n1)
    {
      for(; i1 < n1; i1++, i++)
      {
	    p[i] = p1[i1];
	    r[i] = r1[i1];	
      }
    }
    if(i2 < n2)
    {
      for(; i2 < n2; i2++, i++)
      {
	    p[i] = p2[i2];
	    r[i] = r2[i2];		
      }
    }
    
    return n;
}

void sortTakmicari(int *a, int *b, int n)
{
  int i,j,t; 
  for(i = 0; i < n-1; i++)
    for(j = i+1; j < n; j++)
      if(a[i] < a[j])
      {
	t = a[i];
	a[i] = a[j];
	a[j] = t;
	t = b[i];
	b[i] = b[j];
	b[j] = t;
      }
}

int main(int argc, char **argv)
{
  int id,np;
  int i, j, krug;
  int step, t;
  
  int broj_takmicara;
  int local_broj_takmicara;
  int *redni_brojevi;
  int *broj_poena;
  int max_poena;
  int max_poeni_krug;
  int *r_recv, *p_recv, n_recv;;
  
  MPI_Status status;

  MPI_Init(&argc,&argv);
  MPI_Comm_rank(MPI_COMM_WORLD,&id);
  MPI_Comm_size(MPI_COMM_WORLD,&np);
  
  if(id == MASTER)
  {
    printf("Uneti broj takmicara:\n");
    scanf("%d", &broj_takmicara);
    printf("Uneti max broj poena po krugu:\n");
    scanf("%d", &max_poeni_krug);
    printf("\n\n");
    
    startT = MPI_Wtime();   
  }
  
  MPI_Bcast(&broj_takmicara, 1, MPI_INT, 0, MPI_COMM_WORLD);
  MPI_Bcast(&max_poeni_krug, 1, MPI_INT, 0, MPI_COMM_WORLD);
  local_broj_takmicara = id < broj_takmicara%np ? broj_takmicara/np + 1 : broj_takmicara/np;
  
  redni_brojevi = allocate_int_1D(broj_takmicara);
  broj_poena = allocate_int_1D(broj_takmicara);
  
  srand(time(NULL) * id + id + 10);
  
  for(i = 0; i < local_broj_takmicara; i++)
    redni_brojevi[i] = local_broj_takmicara*id + i;  
  
  for(i = 0; i < local_broj_takmicara; i++)
  {
    broj_poena[i] = 0;
  }

  max_poena = 0;
  krug = 1;
 
  while(broj_takmicara > 100)
  {
    krug++;
    max_poena += max_poeni_krug;
    
    for(i = 0; i < local_broj_takmicara; i++)
    {
      broj_poena[i] += rand() % (max_poeni_krug + 1);
    }
    
    sortTakmicari(broj_poena, redni_brojevi, local_broj_takmicara);

    int max_broj_proslih = local_broj_takmicara;
    local_broj_takmicara = 1;
    while((broj_poena[local_broj_takmicara-1] > (double)max_poena / 2.0) && (local_broj_takmicara <= max_broj_proslih))
      local_broj_takmicara++;
    
    MPI_Allreduce(&local_broj_takmicara, &broj_takmicara, 1, MPI_INT, MPI_SUM, MPI_COMM_WORLD);
  }
  
  if(id == MASTER)
    printf("Broj krugova potrebnih da se zavrsi takmicenje je bio %d\n", krug);
  
  step = 1;
  while(step < np)
  {
      if(id%(2*step) == 0)
      {
	if(id + step < np)
	{
	    int near = id + step; 
	    MPI_Probe(near, 10, MPI_COMM_WORLD, &status);
	    MPI_Get_count(&status, MPI_INT, &n_recv);
	    
	    p_recv = allocate_int_1D(n_recv);
	    r_recv = allocate_int_1D(n_recv);
	    	    
	    MPI_Recv(p_recv, n_recv, MPI_INT, id+step, 10, MPI_COMM_WORLD, &status);   
	    MPI_Recv(r_recv, n_recv, MPI_INT, id+step, 10, MPI_COMM_WORLD, &status);
	    
	    int *pp, *rr;
	    int n = local_broj_takmicara + n_recv;
	    pp = allocate_int_1D(n);
	    rr = allocate_int_1D(n);

	    local_broj_takmicara = mergeTwo(broj_poena, redni_brojevi, local_broj_takmicara, p_recv, r_recv, n_recv, pp, rr);
	    
	    broj_poena = pp;
	    redni_brojevi = rr;
	}
      }
      else if(id%(2*step) == step)
      {
	int near = id-step;
	MPI_Send(broj_poena, local_broj_takmicara, MPI_INT, near, 10, MPI_COMM_WORLD);
	MPI_Send(redni_brojevi, local_broj_takmicara, MPI_INT, near, 10, MPI_COMM_WORLD);
      }
    
    step *= 2;
  }

  if(id == MASTER)
  {
    stopT = MPI_Wtime();
    printf("Run-time is %lf\n", (stopT - startT));
    
    FILE *f = fopen("rezultati.dat", "wt");
    for(i = 0; i < local_broj_takmicara; i++)
      fprintf(f, "%d\t%d\n", redni_brojevi[i], broj_poena[i]);
   
    fclose(f);
  }

  MPI_Finalize();

  return 0;
}