import java.util.Random;

public class GAPopulation {

	private static Random randg = new Random(); // Random Generator

	public int pop_size;
	public GAIndividual[] ind;

	public int best_index; // index of the best individual in ind array
	public int worst_index; // index of the worst individual in ind array

	public float avr_fitness; // average fitness of this population
	// best_fitness = ind[best_index].fitness
	// worst_fitness = ind[worst_index].fitness

	public GAPopulation(int psize,int nvert){
	// Create a random population of size pop_size
	// psize: population size
	// nvert: number of vertices
		pop_size = psize;
		ind = new GAIndividual[pop_size];
		for(int i=0; i < pop_size; i++)
			ind[i] = new GAIndividual(nvert);

		evaluate();
	}

	public GAPopulation(GAIndividual[] p){
	// Create a population with the same individuals in p
		pop_size = p.length;
		ind = new GAIndividual[pop_size];
		for(int i=0; i < pop_size; i++)
			ind[i] = p[i];

		evaluate();
	}

	public static GAPopulation generate(GAPopulation p,int xrate,int mrate){
	// Generate a new population from p, xrate percent of the induviduals
	// of new population are generated by cross-over, mrate percent of them are
	// generated by mutation, and others by reproduction.

		if( xrate < 0 || xrate > 100 || mrate < 0 || mrate > 100 || xrate + mrate > 100 )
			System.err.println("error: xrate and/or mrate are not properly set");

		GAIndividual[] newg = new GAIndividual[p.pop_size];
		int newg_index = 0;

		int xn = xrate * p.pop_size/100; // xn: number of offsprings to be produced by xover
		int mn = mrate * p.pop_size/100; // mn: number of offsprings to be produced by mutation

		// xover:
		for(int i=0; i < xn; i++){
			// select two parents for cross-over:
			// we want two distinct parents (i.e. p1 != p2)
			int p1,p2;
			do{
				p1 = p.tr_select();
				p2 = p.tr_select();
			}while( p1 == p2 );

			newg[newg_index++] = GAIndividual.xover1p(p.ind[p1],p.ind[p2]);
		}

		// mutation:
		for(int i=0; i < mn; i++)
			newg[newg_index++] = p.ind[p.tr_select()].mutate();

		// reproduction:
		for(int i = newg_index; i < p.pop_size; i++)
			newg[i] = p.ind[p.tr_select()];

		return new GAPopulation(newg);
	}

	public int tr_select(){
	// tournament selection of size pop_size/10
	// it returns the index of selected individual in ind[]

		int s_index = randg.nextInt(pop_size); // index of the selected individual
		float s_fitness = ind[s_index].fitness;

		int tr_size = Math.min(10,pop_size);
		for(int i=1; i < tr_size; i++){
			int tmp = randg.nextInt(pop_size);
			if( ind[tmp].fitness > s_fitness ){
				s_index = tmp;
				s_fitness = ind[tmp].fitness;
			}
		}
		return s_index;
	}

	private void evaluate(){
	// evaluate average fitness, best and worst individual of this population
	// greater fitness means better individual
		int best = 0; // index of the best individual
		float best_fitness = ind[0].fitness;
		int worst = 0; // index of the worst individual
		float worst_fitness = ind[0].fitness;
		float sum = ind[0].fitness; // sum of the fitness of individuals of this population

		for(int i=1; i < pop_size; i++){
			sum += ind[i].fitness;
			if( ind[i].fitness > best_fitness ){
				best = i;
				best_fitness = ind[i].fitness;
			}else if( ind[i].fitness < worst_fitness ){
				worst = i;
				worst_fitness = ind[i].fitness;
			}
		}

		best_index = best;
		worst_index = worst;
		avr_fitness = sum / (float) pop_size;
	}

	public String toString(){

		String s = "best individual = "+ind[best_index];
		// s += "\nworst individual = "+ind[worst_index];
		s += "\naverage fitness = "+avr_fitness;

		return s;
	}

  public static void main(String[] args) {

		GAIndividual.adj_matrix = GAUtils.readMatrix("graph.txt");
		int nvert = GAIndividual.adj_matrix.length; // number of vertices

		GAPopulation gap = new GAPopulation(100,nvert);

		for(int i=0; i < 100; i++){
			System.out.println(gap.ind[gap.best_index]);
			gap = gap.generate(gap,60,30);
		}
		System.out.println(gap.ind[gap.best_index]);
  }
}