import java.util.Random;
import java.math.BigInteger;

public abstract class Gene implements java.lang.Comparable {

    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); 

    String permutationString(){
	int[] p = getPermutation();
	String s = "";
	for(int i= 0;i<N;i++)s += p[i]+" ";
	return s;
    }
	
    public int compareTo(Object o){
	if(o instanceof Gene){
	    Gene g = (Gene)o;
	    if (fitness < g.fitness) return -1;
	    if (fitness > g.fitness) return 1;
	    if(equals(g))return 0;
	    return -1;
	}
	return 1;
    }
}

class Permutor1 extends Gene{
    static boolean showwork=false;
    byte[][] genome ;
    static Random randomGenerator = new Random();
    int J,L;  
    int[] permutation=null;

    Permutor1(int n, Evaluator e){
	N=n;E=e;
	int i=1;int j=1;
	while (i<n){i=i*2;j++;}J=j-1;L=i;
	genome = new byte[J][L];
	hash=hashgene();
	fitness=e.evaluate(getPermutation());
    }

    public String toString(){
	String heading = "";
	for(int j=0;j<J;j++) for(int i=0;i<L;i++) heading += genome[j][i];
	heading = heading + " -> "+ permutationString()+ " : "+ 1.0/fitness;
	return heading;
    }
	
    Permutor1(Permutor1 p){
	N=p.N;E=p.E;genome= p.genome.clone();fitness=p.fitness;
	L=p.L;J=p.J;
	for (int  i=0;i<J;i++) genome[i]=genome[i].clone();
    }
	
    int[] getPermutation(){
	if(permutation==null){
	    int[] mine = new int[L];
	    for(int i=0;i<L;i++) mine[i]=i;
	    for(int j=0;j<J;j++)
		{ 
		    recursiveswap(mine,genome[j],(int)Math.pow(2,j));
		    
		}
	    permutation=mine;
	}
	return permutation;
    }
	 
    void recursiveswap(int [] perm, byte[] gene, int offset){
	int genescan=0;
	int permscan=0;
	int permstep= L/2;
	while(permstep>=1){
	    permscan=0; 
	    while((permscan+permstep+permstep-1)<L){
		int doit = gene[genescan];
		if(showwork){
		    System.out.println("permstep="+permstep+"permscan="+permscan+"genescan="+genescan);
		    for(int i=0;i<L;i++)System.out.print(perm[i]);
		    System.out.println();
		    for(int i=0;i<L;i++)System.out.print(gene[i]);
		    System.out.println();
		    for(int i=0;i<genescan;i++)System.out.print(" ");
		    System.out.println("^");
		}
		genescan++;
		if(doit>0){// swap the entries
		    for(int j=0;j<permstep;j++){
			int temp = perm[(offset+permscan+j)%L];
			
			perm[(offset +permscan+j)%L] = perm [(offset+permscan+permstep+j)%L];
			perm[(offset+permscan+ permstep+j)%L]=temp;
		    }
		    
		}
		if(showwork){
		    for(int i=0;i<L;i++)System.out.print(perm[i]);
		    System.out.println();
		}
		permscan+= (2*permstep);
	    }
	    permstep = permstep / 2;
	}
    }
	
    Gene mutate(){
	Permutor1 p = new Permutor1(this);
	for(int i =0;i<J;i++)
	    p.genome[i][ randomGenerator.nextInt(L)] ^= 1;
	//int[] P = p.getPermutation();
	//for (int i=0;i<N;i++) System.out.print(P[i] +" ");
	//System.out.println();
	p.fitness=E.evaluate(p.getPermutation());
	p.hash=p.hashgene();
	return p;
	
    }
	
    int hashgene(){
	int h=312;
	for(byte[] g : genome)for(byte b : g)h = (h+b)*7;
	return h;
    }

    Gene crossover(Gene another){
	Permutor1 p2=this;
	Permutor1 p = new Permutor1(this);
	if (another instanceof Permutor1) p2=(Permutor1)another;
	int pos = randomGenerator.nextInt(J);
	for(int i=pos;i<J;i++)p.genome[i]=p2.genome[i].clone();
	p.fitness = E.evaluate(p.getPermutation());
	p.hash=p.hashgene();
	return p;
    }	
}

class BigIntGene extends Gene{
	BigInteger I= new BigInteger("0");
	int MaxBits;
	static Random randomGenerator = new Random();
	double logOfBase(int base, int num) {  
        return Math.log(num) / Math.log(base);  
    }  
    int[] getPermutation()
    {
			int [] indices = new int[N];
			boolean [] used = new boolean[N];
			int[] finalpermutation = new int[N];
			BigInteger work=I;
			BigInteger divisor = BigInteger.ONE;
			for(int i=0;i<N;i ++)
			{
				indices[i] = (work.mod(divisor)).intValue();
				
				work = work.divide(divisor);
				divisor= divisor.add(BigInteger.ONE);
			}
			/*for(int i=N-1;i>=0;i--)System.out.print(indices[i]+" ");
			System.out.println();*/
			for(int i=0;i<N;i++)
			{
				int reverse = N-i-1;
				int selection = indices[reverse];
				int found =0;
				for(int j=0;j<N;j++)
				{
					if(! used [j])
					{
						if(found==selection)
						{	
							used[j]=true;
							finalpermutation[i]=j;
							break;
						}
						found++;
					}
				}
			}
			return finalpermutation;
	}
	 BigIntGene (int n , Evaluator e)
	{N=n;E=e;
	 int bytelen=(int) (1+  (logOfBase(256,n)))*n;
	 byte[] nulls = new byte[bytelen];
	 I= new BigInteger(nulls);
	 MaxBits = 8*bytelen;
	  hash=hashgene();
	  fitness=e.evaluate(getPermutation());
	}
	int hashgene(){return I.hashCode();}
	Gene mutate()
	{   BigIntGene newGene = new BigIntGene(N,E);
	     
	    int point = randomGenerator.nextInt(MaxBits);
	    BigInteger mutated = I.xor(BigInteger.ONE.shiftLeft(point));
	    for(int i=0;i<10;i++){
			if (randomGenerator.nextInt(13)<2){
				point = randomGenerator.nextInt(MaxBits);
	            mutated = mutated.xor(BigInteger.ONE.shiftLeft(point));
			}
		}
	    newGene.I = mutated;
		newGene.hash=newGene.hashgene();
		newGene.fitness= E.evaluate(newGene.getPermutation());
		return newGene;
	}
	static byte[] masks={0,1,3,7,15,31,63,127};
	Gene crossover(Gene another){
		if(another instanceof BigIntGene){
			BigIntGene other= (BigIntGene ) another;
			 
			BigIntGene newGene = new BigIntGene(N,E);
			byte[] mybytes =I.toByteArray();
			byte[] otherbytes = other.I.toByteArray();
			int minlen = (mybytes.length<otherbytes.length?mybytes.length:otherbytes.length);
			int split= randomGenerator.nextInt(minlen);
			byte[] newbytes = new byte[minlen];
			for(int i=0;i<split;i++)newbytes[i]=mybytes[i];
			int mask = masks[randomGenerator.nextInt(8)];
			newbytes[split] =(byte)( ((int)mybytes[split] & mask) |(byte)((int)otherbytes[split] & ~mask));
			for(int i=split+1;i<minlen;i++)newbytes[i]=otherbytes[i];
			newGene.I = new BigInteger(newbytes);
			newGene.hash=newGene.hashgene();
			newGene.fitness= E.evaluate(newGene.getPermutation());
			return newGene;
		}
		return this;
	}
	public static void main(String args[])
	{
		
		BigIntGene g = new BigIntGene(10, new SillyEvaluator());
		System.out.println(g );
		Gene g2=g.mutate();
		System.out.println(g2 );
		int N=32;int pop=64;
		for(int j=0;j<10;j++)
	//	for(N=4;N<=32;N=N*2)
		{
	    g = new BigIntGene(N, new SillyEvaluator());
		Genalg alg = new Genalg(pop,g);
		for(int i=0;i<6000;i++){
			//alg.showPop();
			//System.out.println("-----------------");
			alg.optimise(1);
			System.out.println(""+ N+","+(pop+i)+","+alg.population[pop-1].fitness);
		}
		}
		/*for (int i=1;i<8;i++){
		Gene g3 = g2.mutate();
		System.out.println(g3+"\n");
		}*/
	}
	public String toString(){
		return I +" -> "+ permutationString()+" : "+ 1.0/fitness;
	}
}