import java.util.Random;

/*
  int N; // number of items in the permutation
  float fitness;// this must be evaluated when gene is created 
  Evaluator E;
  int hash = 0;
  
  abstract int[] getPermutation();
  abstract Gene mutate(); 
  abstract Gene crossover(Gene another); 
  
*/

class TSPGene extends Gene {

    String S;
    Random gen;

    /*
    TSPGene(int n, Evaluator e){
	N   = n;
	E   = e;
	S   = "";
	gen = new Random();
	for (int i=0;i<n*(n-1)/2;i++) 
	    if (gen.nextDouble() < 0.5) 
		S = S + "0";
	    else
		S = S + "1";
	fitness = e.evaluate(getPermutation());
    }
    */

    TSPGene(int n, Evaluator e){
	N   = n;
	E   = e;
	S   = "";
	gen = new Random();
	for (int i=0;i<n*(n-1)/2;i++) S = S + gen.nextInt(2);
	fitness = e.evaluate(getPermutation());
    }

    TSPGene(int n,Evaluator e,String s, double p){
	N   = n;
	E   = e;
	S   = "";
	gen = new Random();
	for (int i=0;i<n*(n-1)/2;i++) 
	    if (gen.nextDouble() < p) 
		if (s.charAt(i) == '1')
		    S = S + "0";
		else
		    S = S + "1";
	    else
		S = S + s.charAt(i);
	fitness = e.evaluate(getPermutation());
    }
    //
    // produce a mutation of s with allele probability p
    //

    TSPGene(int n,Evaluator e,String s){
	N         = n;
	E         = e;
	S         = s;
	gen       = new Random();
	fitness = e.evaluate(getPermutation());
    }

    String getS(){return S;}

    public String toString(){
	String s = S +" -> ";;
	int[] P = getPermutation();
	for (int i=0;i<N;i++) s = s + P[i] + " ";
	s = s +" : "+ 1.0/E.evaluate(P);
	return s;
    }
	
	
    private void swap(int[] P,int i,int j){int temp = P[i]; P[i] = P[j]; P[j] = temp;}

    int[] getPermutation(){
	int[] P = new int[N];
	for (int i=0;i<N;i++) P[i] = i;
	int k = 0;
	for (int i=N-1;i>0;i--)
	    for (int j=0;j<i;j++){
		if (S.charAt(i) == '1') swap(P,j,j+1);
		k++;
	    }
	return P;
    }

    Gene mutate(){return new TSPGene(N,E,S,0.5);}

    Gene crossover(Gene another){
	String S  = "";
	String Sx = this.getS();
	String Sy = ((TSPGene)another).getS();
	int k     = gen.nextInt(N*(N-1)/2);
	if (gen.nextDouble() < 0.5){Sx = ((TSPGene)another).getS(); Sy = this.getS();}
	for (int i=0;i<k;i++) S = S + Sx.charAt(i);
	for (int i=k;i<N*(N-1)/2;i++) S = S + Sy.charAt(i);
	return new TSPGene(N,E,S);
    }
}