#include <time.h>
#include <unistd.h>
#include <stdlib.h>
#include <stdio.h>
#include <omp.h>
#include "main.h"
#include "mpi.h"

/** the number of chromosomes contained into a population */
#define POP_SIZE	128

/** the number of generation after which the populations exchange their bests chromosomes */
#define EXCHANGE 	10

/** the number of generation all populations evolve - in the genetic algorithm */
#define NR_GEN		50

/** the number of generation all populations evolve - in the immune algorithm */
#define IMMUNE_GEN	10

/** the maximum number of clones for each chromosome - for the immune algorithm */
#define MAX_CLONES 	3

/** the maximum number of mutations a chromosome can suffer - for the immune algorithm */
#define MAX_MUTATIONS	7

/** the simple mutation probability */
#define SIMPLE_MUT_PROB	50

/** the swap gene mutation probability */
#define SWAP_MUT_PROB	25

/** the hyper-mutation probability */
#define HYPER_MUT_PROB	25

/** the tour's size - in the tournament selection */ 
#define TOUR_SIZE 	4

#define debug 0

using namespace std;

/**
* structure used in the MPI communication to send the configuration of the best individual
*/
struct chromompi
{
	double dbs[6];
	int ints[2500];
};

/**
* function that executes the serial quicksort
*
* @param chs the list of chromosomes
* @param index the list containing the chromosomes' id - the list specifies the order according to the fitness
* @param left the left limit of the interval
* @param right the right limit of the interval
*/
void quickSort(Chromosome chs[], int index[], int left, int right) {

      int i = left, j = right;
      int tmp;
      double pivot = chs[index[(left + right) / 2]].fitness;

      /**
      * partition 
      */
      
      while (i <= j) {

            while (chs[index[i]].fitness > pivot)
                  i++;

            while (chs[index[j]].fitness < pivot)
                  j--;
           // printf("i=%d j=%d ::\n",i,j);

	     if (i <= j) {
                  tmp = index[i];
                  index[i] = index[j];
                  index[j] = tmp;
                  i++;
                  j--;
            }
      };

      /**
      * recursion 
      */
      
      if (left < j)
            quickSort(chs,index, left, j);

      if (i < right)
            quickSort(chs,index , i, right);

}

/**
* function that merges the results
*
* @param chs the list of chromosomes
* @param index the index list - specifies the order according to the fitness
* @param start the start index
* @param middle - the first range=from "start" to "middle"
* @param end the end start - the second range=from "middle+1" to "end"
*/
void merge(Chromosome chs[], int index[], int start, int middle, int end, int *aux_index, int aux_start){
	int p = start;
	int q = middle + 1;
	int r = aux_start; 

	//printf(" interclass (%d %d)-(%d %d) \n",start,middle,middle+1,end);
	int total = end - start  + 1; 				
	while(r <= aux_start + total){
		//printf("R=%d\n   P(%d)= %lf Q(%d)=%lf\n",r, p, chs[index[p]].fitness , q, chs[index[q]].fitness);
		if (chs[index[p]].fitness >= chs[index[q]].fitness ){
			aux_index[r] = index[p];
			p++;
			r++;
		//	printf(" P++ => p=%d q=%d r=%d aux  = %d val=%lf\n", p,q,r,aux_index[r-1],chs[aux_index[r-1]].fitness ); 			
		}else if (q <= end ){
			aux_index[r] = index[q];
			q++;
			r++;
		//	printf(" Q++ => p=%d q=%d r=%d aux  = %d val=%lf\n", p,q,r,aux_index[r-1],chs[aux_index[r-1]].fitness); 				
		}
					
		if (q > end){ 
			while ( p <= middle ) {
				aux_index[r] = index[p];
				p++;
				r++;
		//		printf(" P++ NO Q => p=%d q=%d r=%d aux  = %d val=%lf\n", p,q,r,aux_index[r-1],chs[aux_index[r-1]].fitness); 				
			}
			break;
		}else if (p > middle){ 
			while ( q <= end ) {
				aux_index[r] = index[q];
				q++;
				r++;
		//		printf(" Q++ NO P => p=%d q=%d r=%d aux  = %d val=%lf\n", p,q,r,aux_index[r-1],chs[aux_index[r-1]].fitness); 			
			}
			break;
		}					
	}
}

/**
* function that realizes the parallel sort
*
* @param chs the list of chromosomes
* @param num_chs the number of chromosomes
* @param index simulates a shared memory 
* @param aux_index simulates a shared memory 
*/
void inline parallel_sort(Chromosome chs[], int num_chs , int index[], int *aux_index){
	int j,k;
	int num_th = omp_get_num_threads();
	int th_id = omp_get_thread_num();			
	int chunk_size = num_chs / num_th ;  
	int start = th_id * chunk_size; 
	
	int chunk;

	//int *res = index ;	
	//int *aux_ptr;
	int end; 

	chunk = chunk_size;
	
	if (num_chs % num_th > 0){
		if (th_id < (num_chs % num_th)){
			start+=th_id;
			end = start + chunk; 
		}else{
			start += (num_chs % num_th);
			end = start + chunk - 1; 
		}

	}else{
		end = start + chunk -1 ; 

	}

	//printf("Th[%d] (%d->%d)\n",th_id,start,end);

	#pragma omp barrier

	#pragma omp for private(j) nowait 
	for (j = 0 ; j < num_chs ; j++){
		index[j]=j;
	}
		
	#pragma omp barrier 

	//printf("Th[%d] QSort %d %d \n",th_id,start , end);
	
	quickSort(chs,index, start, end) ;

	//printf("Th[%d] QSort Done!!!\n",th_id);	
	#pragma omp barrier 


		
	int n = num_th ;
	int merge_st, merge_mid, merge_end;
	int extra_chunks = num_chs % num_th;  
	for (j = 2 ; j <= n ; j = j * 2 ){
		//printf("Active th %d [%d]  j= %d chunk = %d\n",n,th_id, j, chunk);
		if (th_id % j == 0) {
			merge_st = start;

			merge_mid = start +  j/2 * chunk - 1 ;

			merge_end = end + (j-1) * chunk;
			if (th_id < extra_chunks && th_id + j - 1 <= extra_chunks){
				merge_end += j - 1;
			} else if (th_id < extra_chunks && th_id + j - 1 > extra_chunks){
				merge_end += extra_chunks - th_id - 1;
			} 

			if (th_id < extra_chunks && th_id + j/2 <= extra_chunks){
				merge_mid += j/2;
			} else if (th_id < extra_chunks && th_id + j/2  > extra_chunks){
				merge_mid += extra_chunks - th_id ;
			} 
	

//			printf("Th[%id] :: Merge (%d,%d)->(%d,%d)\n", th_id, merge_st, merge_mid,merge_mid+1,merge_end);
			merge(chs, index , merge_st, merge_mid, merge_end, aux_index, merge_st);	
		}
		
		#pragma omp barrier			

		#pragma omp for private(k) schedule(static)
		for (k=0;k<num_chs;k++){
		//	printf("Th[%d] copying %d => %d  -- val=%lf\n",th_id,k, aux_index[k] , chs[aux_index[k]].fitness);		
			index[k] = aux_index[k];

		}
		#pragma omp barrier		
		//printf("COPY DONE\n");	
	}
}

/**
* function that performes the evaluation of one population
*
* @param chs the list of chromosomes
* @param num_chs the number of chromosomes
* @param ev the chromosomes evaluator 
* @param best simulates a shared memory
*/
void inline evaluatePopulation(Chromosome *chs, int num_chs , Evaluator &ev, double best[]){
	int th_id = omp_get_thread_num();
	int j;
	int num_th = omp_get_num_threads();

	#pragma omp for schedule(static) nowait 
		for (j=0; j < num_chs ; j++){
			ev.evaluateIndividual(chs[j]);
		}

	#pragma omp barrier
			
	best[th_id] = 30000;
	
			

	#pragma omp for schedule(static) nowait
		for (j=0; j < num_chs ; j++){
			if (best[th_id] > chs[j].makespan){
				best[th_id] = chs[j].makespan;					
			}				
		}
	#pragma omp barrier
			
	#pragma omp master 
	{
		
		for (j=0;j<num_th;j++)
			if (best[0] > best[j])
				best[0] = best[j];
		for (j=1;j<num_th;j++)	
			best[j] = best[0];
			
	}
	
	#pragma omp barrier 

	
	#pragma omp for schedule(static) nowait
		for (j = 0 ; j < num_chs ; j++){
			chs[j].evalT3 = best[th_id]/chs[j].makespan;
			chs[j].fitness = chs[j].evalT1 * chs[j].evalT2 * chs[j].evalT3 * chs[j].evalT3 * chs[j].evalT3 ;
		}
	

}

/**
* function that computes the prefix sums
* 
* @param input the input series
* @param n the number of input elements
* @param sum the prefix sums
*/
void inline computePrefixSum(int input[], int n, int sum[]){
	int *aux_sum;
	//int *aux_ptr;
	int k,j;
	int num_th = omp_get_num_threads();
	int th_id = omp_get_thread_num();		
	
	aux_sum = (int *)calloc(n,sizeof(int));

	#pragma omp for private(j) 
	for (j = 0 ; j < n ; j++){
		aux_sum[j] = sum[j] = input [j];
	}

	#pragma omp barrier 

	int start,end; 
	int step, num_tasks; 

		
	for (step = 1 ; step < n ; step*=2) {
			
		num_tasks = (n - step) / num_th ; 
		if (th_id < ((n - step) % num_th)){
			num_tasks ++;
			start = step + num_tasks * th_id ; 
			end = start + num_tasks;  
		}else{
			start = step + num_tasks * th_id + ((POP_SIZE - step) % num_th) ;
			end =  start + num_tasks;  
		}
		for (k = start ; k < end ; k++){
			aux_sum[k] = sum[k] + sum[k - step];
		}

		#pragma omp barrier
			
		for (k = start ; k < end ; k++){
			sum[k] = aux_sum[k];
		}
		
		#pragma omp barrier
		//printf("Th[%d] #tasks = %d st = %d stop = %d \n",th_id, num_tasks, start, end);
				
		
	}
	free(aux_sum);
}

/**
* function that converts a chromompi structure to a Chromosome
* 
* @param c the chromompi structure
* @return the Chromosome
*/
Chromosome to_chromosome(chromompi c)
{
	Chromosome chr = Chromosome();
	chr.makespan = c.dbs[0];
	chr.fitness = c.dbs[1];
	chr.evalT1 = c.dbs[2];
	chr.evalT2 = c.dbs[3];
	chr.evalT3 = c.dbs[4];
	chr.loadBalance = c.dbs[5];

	for(int i = 0 ; i < c.ints[0]*3 ; i += 3)
	{
		Gene g = Gene(c.ints[i+1], c.ints[i+2], c.ints[i+3]);
		chr.genes.push_back(g);
	}	
	int start = c.ints[0]*3+1;
	for(int i = 0 ; i < c.ints[start] ; i ++)
		chr.f_nodes.push_back(c.ints[start+i+1]);
	return chr;
}

/**
* function that converts a Chromosome structure to a chromompi
*
* @param chrom the Chromosome
* @return the chromompi
*/
chromompi to_chromompi(Chromosome chrom)
{
	chromompi c;
	c.dbs[0] = chrom.makespan;
	c.dbs[1] = chrom.fitness;
	c.dbs[2] = chrom.evalT1;
	c.dbs[3] = chrom.evalT2;
	c.dbs[4] = chrom.evalT3;
	c.dbs[5] = chrom.loadBalance;

	c.ints[0] = chrom.genes.size();
	int i;
	for(i = 1 ; i < c.ints[0]*3 ; i += 3)
	{
		c.ints[i] = chrom.genes[(i-1)/3].task_index;
		c.ints[i+1] = chrom.genes[(i-1)/3].proc_index;
		c.ints[i+2] = chrom.genes[(i-1)/3].level;
	}
	c.ints[i++] = chrom.f_nodes.size();
	for(int k = 0 ; k < (int)chrom.f_nodes.size(); k++)
		c.ints[i++] = chrom.f_nodes[k];
	//for(int i = 0 ; i < chrom.genes.size()*3 + chrom.f_nodes.size() +2 ; i ++)
	//	printf("%i ", c.ints[i]);
	//printf("\n");
	return c;
}

/**
* function that prints the chromosome's information
*
* @param chrom the chromosome
*/
void print(chromompi chrom)
{
	printf("%lf %lf %lf %lf %lf %lf\n", chrom.dbs[0], chrom.dbs[1], chrom.dbs[2], chrom.dbs[3],chrom.dbs[4], chrom.dbs[5]);
	printf("[%i]:", chrom.ints[0]);
	for(int i = 0 ; i < chrom.ints[0]*3 ; i+=3)
		printf("(%i %i %i) ", chrom.ints[1 + i], chrom.ints[1 + i+ 1], chrom.ints[1 + i+ 2]);
	int count = chrom.ints[0]*3+1;
	printf("\n[%i]:", chrom.ints[count]);
	for(int i = 0 ; i < chrom.ints[count] ; i ++)
		printf("%i ", chrom.ints[count+1+i]);
	printf("\n");
}

/**
* entry point for the GAIIA project
*
* @param argc ignored
* @param args ignored
*/
int main(int argc, char ** args)
{
	int numprocs, rank;//number of populations
	srand(time(NULL) + getpid());	

	/**
	* MPI initialization
	*/
	
	MPI_Init(&argc, &args);
	MPI_Comm_size(MPI_COMM_WORLD, &numprocs);
	MPI_Comm_rank(MPI_COMM_WORLD, &rank);

	int i, master=rank; 
	MPI_Request request;
	MPI_Status status;
	
	/**
	* MPI datatype construction
	*/

	chromompi sent;
	MPI_Datatype Chromotype; 
	MPI_Datatype type[2] = {MPI_DOUBLE, MPI_INT}; 
	int blocklen[2] = {6, 2500}; 
	MPI_Aint disp[2]; 
	int base;
	MPI_Address( &sent, disp); 
	MPI_Address( &sent.ints, disp+1); 
	base = disp[0]; 
	for (i=0; i <2; i++) disp[i] -= base;
	MPI_Type_struct( 2, blocklen, disp, type, &Chromotype);
	MPI_Type_commit( &Chromotype); 

	printf("hello mpi from %i\n", rank);
	master =0;
	
	/**
	* the tasks graph we want to schedule
	*/
	
	TaskGraf tasks = TaskGraf();
	tasks.init((char*)"test500.in");//in.txt

	/**
	* the processors graph we can se
	*/
	
	ProcesorGraf procs = ProcesorGraf();
	procs.init((char *)"proc.txt");

	/**
	* the random population generator
	*/
	
	Generator gen = Generator(POP_SIZE, tasks, procs.nr_noduri);
	gen.setFloatingNodes(tasks.f_nodes);
	gen.generate();	

		
	/**
	* we need two populations and three pointers in order to use double buffering 
	*/
	
	Chromosome *chs;
	Chromosome *new_pop;
	Chromosome *aux;  

	chs = (Chromosome *)calloc(POP_SIZE,sizeof(Chromosome));
	new_pop = (Chromosome *)calloc(POP_SIZE,sizeof(Chromosome));




	for(i = 0 ; i < POP_SIZE ; i ++)
	{
		chs[i] = gen.getNext();
		new_pop[i] = Chromosome();
	}

	
	int j,k,th_id; 
	int num_th;
	
	#pragma omp parallel shared(num_th)
	{
		num_th = omp_get_num_threads();		
		
	}

	int selected[128];//[POP_SIZE];
	int used[128];//[POP_SIZE];
	
	int free_ch[128];//[num_th];

	Evaluator ev[128];//[num_th]; 
	Crossover cross[128];//[num_th];

	SimpleMutation simple_mut[128];//[num_th]; 
	SwapMutation swap_mut[128];//[num_th];
	HyperMutation hyper_mut[128];//[num_th];
	double best[128];//[num_th];	

	time_t ltime;
	time(&ltime);                                                                
   	printf("The start time is %s\n", ctime(&ltime)); 


	
	#pragma omp parallel private(j,k,th_id) shared(i,num_th,chs,ev,new_pop, aux, used, selected)
	{
				 
		th_id = omp_get_thread_num();
		cross[th_id] = Crossover();
		ev[th_id]   = Evaluator(tasks, procs);	
		simple_mut[th_id]  = SimpleMutation(procs.nr_noduri, tasks.max_level, 0.4);
		swap_mut[th_id]    = SwapMutation(procs.nr_noduri, tasks.max_level, 0.4);
		hyper_mut[th_id]   = HyperMutation(tasks, 0.3);		
		printf("Th[%d/%d]: Init\n",th_id,num_th);
	
		#pragma omp for private(i) schedule(static) 
		for (i = 0; i < POP_SIZE ; i++){
			selected[i] = 0; 
			used [i] = 0 ;
		}
		
		evaluatePopulation(chs, POP_SIZE ,ev[th_id], best);			
		#pragma omp barrier
	}
		



	/**
	* prefix sums computation
	*/
	
	int *clones;
	int *sum ; 
	sum = (int *)calloc(POP_SIZE,sizeof(int));
	clones = (int *)calloc(MAX_CLONES * POP_SIZE,sizeof(int));
	
	Chromosome clone_pop[POP_SIZE * MAX_CLONES];

	double fit_med[num_th]; 

	int num_clones;

	int *index;
	int *aux_index;
	int *clones_index;
	int * clones_aux;

	index = (int *)calloc(POP_SIZE,sizeof(int));
	aux_index = (int *)calloc(POP_SIZE,sizeof(int));
	clones_index = (int *)calloc(MAX_CLONES * POP_SIZE,sizeof(int));
	clones_aux = (int *)calloc(MAX_CLONES * POP_SIZE,sizeof(int));

	/**
   	* start of the immune algorithm
   	*/

    for(i=0;i<IMMUNE_GEN;i++){


	#pragma omp parallel private(j,k,th_id) shared(num_clones, clone_pop,i,num_th,chs,ev,new_pop, aux, used, selected, sum,clones)
	{	
		th_id = omp_get_thread_num();
		fit_med[th_id] = 0 ;
		best[th_id] = 0 ;
		#pragma omp for private(j) nowait 
		for (j = 0 ; j < POP_SIZE ; j++){
			fit_med[th_id]+= chs[j].fitness; 
			if (chs[j].fitness > best[th_id] ) 
				best[th_id] = chs[j].fitness; 			
		}
		#pragma omp barrier 

		#pragma omp master 
		{
			double mean = 0; 
			for (j = 0 ; j < num_th ; j++ ){
				mean += fit_med[j]; 
			}
			mean = mean / POP_SIZE ; 
			for (j = 0 ; j < num_th ; j++ ){
				fit_med[j] = mean; 
			}
			for (j=0 ; j < num_th ; j++){
				if (best[j] > best[th_id])
					best[th_id] = best[j];
			}
			for (j=0 ; j < num_th ; j++){
					best[j] = best[th_id];
			}

		}
		#pragma omp barrier 

		#pragma omp for private(j)
		for (j=0 ; j < POP_SIZE ; j++) { //TODO not all - first selection 
			clones[j] = 1 + (MAX_CLONES - 1) * (chs[j].fitness - fit_med[th_id]) / (best[th_id] - fit_med[th_id]);
			if ( clones[j] < 0) 
				clones[j] = 0 ;
			//printf("Th[%d] For Ch[%d] -- %d clones\n",th_id, j, clones[j]);
		}

		#pragma omp barrier 
	
		computePrefixSum(clones,POP_SIZE,sum);

		#pragma omp barrier

		#pragma omp master 
		{
			num_clones = sum[POP_SIZE - 1];

			//printf("Th[%d] :: Nr clone = %d\n",th_id, sum[POP_SIZE-1]);
			
		}	

		#pragma omp barrier 
	
		int base; 
		#pragma omp for private(j,k) schedule(static) nowait
		for (j = 0 ; j < POP_SIZE; j ++){
			if (clones[j] > 0) {
				base = 0; 
				if (j > 0) 
					base = sum[j-1];
				for (k = 0 ; k < clones[j] ; k++) { 
					clone_pop[base + k] = chs[j];
				}
 	
			}

		} 

		#pragma omp barrier 

		#pragma omp barrier 

		int num_mut ;
		double rnd ;  
		//aplicarea operatorilor de mutatie asupra clonelor 

		simple_mut[th_id].mutation_pb = 1;
		swap_mut[th_id].mutation_pb = 1;   
		hyper_mut[th_id].mutation_pb = 1;   	
		
		#pragma omp for private(j,k) schedule(static) nowait
		for (j = 0 ; j < num_clones; j ++){

			//printf("b=%lf f=%lf mk=%lf fmed=%lf\n",best[th_id], clone_pop[j].fitness, clone_pop[j].makespan, fit_med[th_id]);
			num_mut = 3 + (MAX_MUTATIONS - 1) * (best[th_id] - clone_pop[j].fitness) / (best[th_id] - fit_med[th_id]);

			//printf("Th[%d] Clone = %d Mut# = %d\n",th_id, j , num_mut);
			for (k = 0  ; k < num_mut ; k++) {
				rnd = (double)(rand() % 10000) / 100;
				if (rnd < SIMPLE_MUT_PROB){
					simple_mut[th_id].mutateIndividual(clone_pop[j]);
				//	printf("Simple\n");
				}else if (rnd < SIMPLE_MUT_PROB + SWAP_MUT_PROB){
				//	printf("Swap\n");					
					swap_mut[th_id].mutateIndividual(clone_pop[j]);
				}else {
				//	printf("Hyper\n");
					hyper_mut[th_id].mutateIndividual(clone_pop[j]);
				}

			}
		}	

		/**
		* clone population evaluation 
		*/

		#pragma omp barrier 
		
		evaluatePopulation(clone_pop, num_clones ,ev[th_id], best);	
			
		#pragma omp barrier 
				
	
		#pragma omp for private(j) nowait
		for (j=0; j < POP_SIZE; j++)
			index[j]=j;

		#pragma omp barrier 
		parallel_sort(chs, POP_SIZE, index,aux_index);
	
		#pragma omp barrier 

		#pragma omp for private(j) nowait
		for (j=0; j < num_clones; j++)
			clones_index[j]=j;

		#pragma omp barrier 
		parallel_sort(clone_pop, num_clones, clones_index, clones_aux);
	
		#pragma omp barrier 
		
		int clone_base = 2* POP_SIZE / 3 + 1;
		
		#pragma omp for private(j) 
		for (j=0 ; j < clone_base ; j++){
			new_pop[j] = chs[index[j]];
		}  		

		#pragma omp barrier 

		#pragma omp for private(j) 
		for (j=0 ; j < POP_SIZE - clone_base ; j++){
			new_pop[clone_base + j] = clone_pop[clones_index[j]];
		}  		

		#pragma omp barrier 

		#pragma omp master 
		{
			
			aux = new_pop;
			new_pop = chs;
			chs = aux;
 

		}
	}
    }

    /**
    * end of the immune algorithm
    */

	time(&ltime);                                                                
   	printf("IA The end time is %s\n", ctime(&ltime)); 

   	/**
   	* start of the genetic algorithm
   	*/	

   	printf("GA\n");
   	
	for (i = 0 ; i < NR_GEN ; i++) {
	
		#pragma omp parallel private(j,k,th_id) shared(i,num_th,chs,ev,new_pop, aux, used, selected)
		{
			
			th_id = omp_get_thread_num();
	
			/**
			* choosing of the mutations' probabilities
			*/
					
			simple_mut[th_id].mutation_pb = 0.4;
			swap_mut[th_id].mutation_pb = 0.3;   
			hyper_mut[th_id].mutation_pb = 0.3;   	
		
	
			/**
			* selection 
 			*/
			
			/**
			* first step -> reset used vector 
			*/
			
			#pragma omp for schedule(static) 
				for (j = 0 ; j < POP_SIZE ; j++){
					used[j]  =  0;
					selected[j] = 0;
				}

			#pragma omp barrier 
			double best_makespan;
			int best_poz ; 
			int base;
			int offset;
			int chunk_size = POP_SIZE / num_th ;  
			int crt_chunk;
			int new_poz; 

			/**
			* compute the number of unselected nodes for each chunck
			*/
			
			int tours = POP_SIZE / ( 2 * num_th ) ; 
			int l ;	
			for (l = 0 ; l < tours ; l++){ 

				best_makespan = 30000;
				best_poz = -1;
				free_ch[th_id] = chunk_size; 
				
				/**
				* update unselected chromosomes 
				*/
				
				for (j=0; j < chunk_size ; j++){
					if (selected[th_id * chunk_size + j] == 1) 
						free_ch[th_id]--;
					used[th_id * chunk_size + j] = 0; 
				}

				#pragma omp barrier 
	
				/**
				* start new tour 
				*/
				
				for (j=0; j < TOUR_SIZE ; j++){
					crt_chunk = (th_id + j) % num_th; 
					base = crt_chunk * chunk_size;
					if (free_ch[crt_chunk] - j > 0 )
						offset = rand() % (free_ch[crt_chunk] - j); 
					else {
						//printf("Th[%d] :: No selection possible\n",th_id);
					}					
					//printf("Th[%d] - step=%d base=%d offset=%d\n",th_id, j, base, offset);

					for (k = 0 ; k < chunk_size ; k++){
						if (used[base + k] == 0 && selected[base + k] == 0){
							if (offset == 0){ //this one is selected in this step
								//printf("Th[%d] - selected in tour -> %d\n", th_id , (base+k)); 
								used[base + k] = 1; 										
								if (best_makespan > chs[base + k].makespan){
									best_makespan = chs[base + k].makespan; 
									best_poz = base + k ;
								}
								break;
							}else 
								offset--; 
						}else {
							//printf("Th[%d] - %d DROP uz:%d sel:%d\n", th_id , (base+k), used[base+k], selected[base + k]);
						}
					}
					#pragma omp barrier
				}
				//printf("Th[%d] - Winner = %d Makespan = %lf \n",th_id, best_poz, best_makespan);
	

				selected[best_poz] = 1; 
				new_poz = l * num_th + th_id;
				new_pop[new_poz] = chs[best_poz];			
				
				#pragma omp barrier 

			}

			
			/**
			* crossover phase
			*/
			
			offset = POP_SIZE / 2;

			#pragma omp for private(j) schedule(static) nowait 
			for(j = 0 ; j < POP_SIZE / 2 ; j+=2 ){
				//printf("T[%d] :: Cross (%d %d) -> (%d %d)\n" , th_id , j, j+1 , offset + j , offset+j+1);
				cross[th_id].crossover(new_pop[j], new_pop[j+1], new_pop[offset + j], new_pop[offset + j + 1]);				
			}
 
			#pragma omp barrier 


			/**
			* simple mutation phase 
			*/
			
			#pragma omp for private(j) schedule(static) nowait 
			for(j = 0 ; j < POP_SIZE ; j++ ){
				simple_mut[th_id].mutateIndividual(new_pop[j]);
			}	
			#pragma omp barrier 

			/**
			* swap gene mutation phase 
			*/
			
			#pragma omp for private(j) schedule(static) nowait 
			for(j = 0 ; j < POP_SIZE ; j++ ){
				swap_mut[th_id].mutateIndividual(new_pop[j]);
			}	
			#pragma omp barrier 
				

			/**
			* topo hyper-mutation phase 
			*/
			
			#pragma omp for private(j) schedule(static) nowait 
			for(j = 0 ; j < POP_SIZE ; j++ ){
				hyper_mut[th_id].mutateIndividual(new_pop[j]);
			}	
			#pragma omp barrier 
			
			
			
			/**
			* evaluation
			*/
			 
			#pragma omp for schedule(static) nowait 
				for (j=0; j < POP_SIZE ; j++){
					ev[th_id].evaluateIndividual(new_pop[j]);
				}

			#pragma omp barrier
			
			best[th_id] = 30000;
	
			

			#pragma omp for schedule(static) nowait
				for (j=0; j < POP_SIZE ; j++){
					if (best[th_id] > new_pop[j].makespan){
						best[th_id] = new_pop[j].makespan;					
					}				
				}

			#pragma omp barrier
			
			#pragma omp master 
			{
				
				for (j=0;j<num_th;j++)
					if (best[0] > best[j])
						best[0] = best[j];
				for (j=1;j<num_th;j++)	
					best[j] = best[0];
				
				//printf("Th[%d] - Best = %lf\n",th_id, best[0]);
			}

			#pragma omp for schedule(static) nowait
				for (j = 0 ; j < POP_SIZE ; j++){
					new_pop[j].evalT3 = best[th_id]/new_pop[j].makespan;
					new_pop[j].fitness = new_pop[j].evalT1 * new_pop[j].evalT2 * new_pop[j].evalT3 * new_pop[j].evalT3 * new_pop[j].evalT3 ;

				}
		
		
		}
		aux = chs ; 
		chs = new_pop;
		new_pop = aux;

		//for(j = 0 ; j < POP_SIZE ; j++ ){
		//	chs[j].print();
		//}
		

		/**
		* each population will exchange its worsts individuals with the others bests
		*/
		
		if(i % EXCHANGE == 0 && i != NR_GEN - 1)
		{
			int best = 0;
			for(j = 1 ; j < POP_SIZE ; j++ )
				if (chs[best].makespan > chs[j].makespan)
					best = j;
				
			int worst[numprocs];
			int used[128];//[POP_SIZE];

			for(j = 0 ; j < POP_SIZE ; j++)
				used[j] = 1;

			for(j = 0; j < numprocs - 1; j ++)
				worst[j] = -1;

			for(int k = 0 ; k < numprocs - 1; k ++)
			{

				for(j = 1 ; j < POP_SIZE ; j++ )
					if ((worst[k] == -1 || chs[worst[k]].makespan < chs[j].makespan) && used[j] != 2)
						worst[k] = j;

				used[worst[k]] = 2;
			}
		/*	printf("[%i] best %i, worst ",rank, best);
			for(int k = 0 ; k < numprocs - 1; k ++)
				printf("%i ", worst[k]);
			printf("\n");
		*/	

			int ready = 1;
		  
		
			printf("[%i] exchange \n", rank);
			chromompi b = to_chromompi(chs[best]);

			/**
			* each population broadcasts its best chromosome
			*/
			
			for(int jj = 0 ; jj < numprocs ; jj ++)
			{
				if(jj != rank)
				{
					MPI_Isend(&b, 1, Chromotype, jj, i, MPI_COMM_WORLD, &request);
					//if (debug) printf("[%i] j(%i)->k(%i) %lf\n", rank, sursa, jj, to_chromosome(b).makespan);

				}
			}

			int recv = 0;
			
			/**
			* each population receives other bests
			*/
			
			for(int i = 0 ; i < numprocs - 1 ; i ++)
			{
				MPI_Irecv(&b, 1, Chromotype, MPI_ANY_SOURCE, i, MPI_COMM_WORLD, &request);
				int flag = 0, step = 100000;
				MPI_Test(&request, &flag, &status);

				while (!flag && step > 0)
				{
					MPI_Test(&request, &flag, &status);
					step --;
				}

				if(step > 0)
				{
					/**
					* exchange the worst with the best
					*/
					
					chs[worst[recv++]] = to_chromosome(b);
					//if (debug) printf("[%i] received best %lf %lf\n", rank, to_chromosome(b).makespan, to_chromosome(b).fitness);
				}

			}

			printf("[%i] exchange done\n", rank);
	      
		}

		/**
		* the end of the algorithm -> we have to compute the general best
		*/
		
		if(i == NR_GEN - 1)
		{

			/**
			* leader selection
			*/

			/**
			* broadcast of the rank
			*/
			
			for(int j = 0 ; j < numprocs ; j ++)
				if(j != rank)
					MPI_Isend(&rank, 1, MPI_INT, j, 0, MPI_COMM_WORLD, &request);

			/**
			* wait for other ranks
			*/
			
			int candidat = -1, max = rank;
			for(int j = 0 ; j < numprocs - 1 ; j ++)
			{

				MPI_Irecv(&candidat, 1, MPI_INT, MPI_ANY_SOURCE, 0, MPI_COMM_WORLD, &request);
				int flag = 0, step = 500000;
				MPI_Test(&request, &flag, &status);

				while (!flag && step > 0)
				{
					MPI_Test(&request, &flag, &status);
					step --;
				}

				/**
				* new message received
				*/
				if(step > 0)
				{
					//printf("IRECV[%i]: sursa = %i, candidat = %i\n", rank, sursa, candidat);
					if(max < candidat)
						max = candidat;
							
				}
			}


			/**
			* broadcast of the candidate master 
			*/
			
			for(int j = 0 ; j < numprocs ; j ++)
				if(j != rank)
					MPI_Isend(&master, 1, MPI_INT, j, 0, MPI_COMM_WORLD, &request);

			for(int ii = 0 ; ii < numprocs - 1 ; ii ++)
			{
				MPI_Irecv(&candidat, 1, MPI_INT, MPI_ANY_SOURCE, 0, MPI_COMM_WORLD, &request);
				int flag = 0, step = 500000;
				MPI_Test(&request, &flag, &status);

				while (!flag && step > 0)
				{
					MPI_Test(&request, &flag, &status);
					step --;
				}

				if(step > 0)
				{
					//	int sursa = status.MPI_SOURCE;
					//printf("IRECV[%i]: sursa = %i, candidat = %i\n", rank, sursa, candidat);
					if(master > candidat)
						master = candidat;
				}

			}

			printf("END\n");
			int best = 0;
			chromompi b;
			for(int j = 1 ; j < POP_SIZE ; j++ )
				  if (chs[best].makespan > chs[j].makespan)
					  best = j;

			if(rank != master) 
			{
				/**
				* sends the best chromosome to the master
				*/
				
				b = to_chromompi(chs[best]);
				MPI_Isend(&b, 1, Chromotype, master, 1, MPI_COMM_WORLD, &request);
				//printf("[%i] => trimit best %lf -> master\n", rank, chs[best].makespan);
			}
			else if(rank == master)
			{
				/**
				* receives the others' bests
				*/
				printf("[%i] leader\n", rank);
  
				Chromosome crtbest = chs[best];//the best is the master's best

				for(int ii = 0 ; ii < numprocs - 1 ; ii ++)
				{
					MPI_Irecv(&b, 1, Chromotype, MPI_ANY_SOURCE, 1, MPI_COMM_WORLD, &request);
					int flag = 0, step = 100000;
					MPI_Test(&request, &flag, &status);

					while (!flag && step > 0)
					{
						MPI_Test(&request, &flag, &status);
						step --;
					}

					if(step > 0)
					{
						Chromosome ch = to_chromosome(b);//the received chromosome 
						
						/**
						* computes the general best
						*/
						
						if(ch.makespan < crtbest.makespan )
							crtbest = ch;
					}
				}
				
				/**
				* the final result
				*/
				printf("[%i]BEST: %lf", rank, crtbest.makespan);//crtbest.print();
				time(&ltime);                                                                
				printf("GA The end time is %s\n", ctime(&ltime)); 
			}

		}

	}
	
	MPI_Finalize();
		
	return 0;
}