import java.util.Random;

public class GAIndividual {

	public static float[][] adj_matrix; // the adjacency matrix representation of graph

	private static Random randg = new Random(); // Random Generator
	// What if we choose a static random generator?
	// A unique random generator for all individuals!?

	public int nvert;
	public int[] left; // a subset of graph vertices
	public int[] right; // another subset of graph vertices
	// left and right are disjoint sets
	// left.length + right.length == nvert
	// left.length >= 1
	// right.length >= 1
	public int[] picklist;
	// picklist.length == left.length + right.length
	// picklist = left UNION right
	// picklist is a pick list! such that picklist[i] < picklist.length - i
	// for example {0, 0, 2, 2, 0, 0, 0} is a picklist and represents:
	// {0, 1, 4, 5, 2, 3, 6}

	public float fitness;

	public GAIndividual(int nvert){
	// Create a random individual of size numv,
	// numv: number of vertices of the grapg

		this.nvert = nvert;
		int leftsize = randg.nextInt(nvert-1)+1;
		left = new int[leftsize];
		right = new int[nvert - leftsize];

		int[] tmp = GAUtils.randperm(nvert);
		for(int i=0; i < left.length; i++)
			left[i] = tmp[i];
		for(int i=left.length; i < nvert; i++)
			right[i-left.length] = tmp[i];

		picklist = GAUtils.perm2picklist(tmp);

		evalFitness(); // evaluate fitness of this new individual
	}
	public GAIndividual(int[] l,int[] r){

		nvert = l.length+r.length;
		int[] tmp = new int[nvert];

		left = new int[l.length];
		for(int i=0; i < l.length; i++){
			left[i] = l[i];
			tmp[i] = l[i];
		}
		right = new int[r.length];
		for(int i=0; i < r.length; i++){
			right[i] = r[i];
			tmp[l.length+i] = r[i];
		}

		picklist = GAUtils.perm2picklist(tmp);

		evalFitness(); // evaluate fitness of this new individual
	}

	public GAIndividual mutate(){

		int[] child_picklist = new int[nvert];
		for(int i=0; i < nvert; i++)
			child_picklist[i] = picklist[i];

		// mutate one point:
		int m_point = randg.nextInt(nvert-1); // mutation point
		child_picklist[m_point] = randg.nextInt(nvert - m_point);

		int[] tmp = GAUtils.picklist2perm(child_picklist);
		int[] l,r;

		if( randg.nextBoolean() == true ){
		// this mutation preserves structure:
			if( randg.nextBoolean() == true ){
				l = new int[left.length];
				r = new int[right.length];
			}else{
				l = new int[right.length];
				r = new int[left.length];
			}
		}else{
		// mutate structure:
			int dpoint = 1 + randg.nextInt(nvert-1);// tmp division point
			l = new int[dpoint];
			r = new int[nvert - dpoint];
		}

		for(int i=0; i < l.length; i++)
			l[i] = tmp[i];
		for(int i=0; i < r.length; i++)
			r[i] = tmp[l.length + i];

	 	return new GAIndividual(l,r);
	}

	public static GAIndividual xover1p(GAIndividual f,GAIndividual m){
	// 1-point cross over
		int xpoint = 1 + randg.nextInt(f.nvert-1);
		int[] child_picklist = new int[f.nvert];
		for(int i=0; i < xpoint; i++)
			child_picklist[i] = f.picklist[i];

		for(int i=xpoint; i < f.nvert; i++)
			child_picklist[i] = m.picklist[i];

		int[] tmp = GAUtils.picklist2perm(child_picklist);
		int[] l,r;
/*->*/// HOW DEVIDE tmp INTO TWO PARTS? (i.e LEFT and RIGHT)

		if( randg.nextBoolean() == true ){

			l = new int[f.left.length]; // WHY?
			r = new int[tmp.length - f.left.length];
		}else{

			l = new int[m.left.length]; // WHY?
			r = new int[tmp.length - m.left.length];
		}

		for(int i=0; i < l.length; i++)
			l[i] = tmp[i];
		for(int i=0; i < r.length; i++)
			r[i] = tmp[l.length + i];

		return new GAIndividual(l,r);
	}

	public String toString(){

		String s = "{";
		for(int i=0; i < left.length - 1; i++){
			s+= left[i]+", ";
		}
		s+=left[left.length - 1] + "}";
		s+=" {";
		for(int i=0; i < right.length - 1; i++){
			s+= right[i]+", ";
		}
		s+=right[right.length - 1] + "}";

		s+="\nnumber of edges in between = "+(1.0f/fitness - 1);

		return s;
	}

	private void evalFitness(){
	// greater fitness means better individual
		int sum = 0; // number of edges between left and right
		for(int i=0; i < left.length; i++)
			for(int j=0; j < right.length; j++)
/*->*/	if( adj_matrix[left[i]][right[j]] == 1.0f ) // it is assumed adj_matrix is symmetric
					sum++;

		fitness = 1.0f/(1.0f + sum);
	}

  public static void main(String[] args) {

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

		GAIndividual i1 = new GAIndividual(nvert);
		GAIndividual i2 = new GAIndividual(nvert);

		for(int i=0; i < 1000; i++)
			System.out.println(new GAIndividual(nvert));
  }
}