package com.caplet.manna;

import java.util.*;
import java.awt.*;

/**
 * The genetic algorithm itself.  For speed purposes, the parameters that can 
 * be changed while the GA is running are public instance variables, rather 
 * than get/set bean properties.
 *
 * @author Mark S. Miller, markm@caplet.com
 * @author Terry Stanley, tstanley@cocoon.com
 */
public class GA extends Canvas {
    static /*package*/ final int TOP_FITNESS = 10;

	static private final Color NONE_COLOR = Color.white;
	static private final Color DOT_COLOR = Color.black;
	static private final Color[] MANNA_COLORS = new Color[TOP_FITNESS+1];
	static {
	    for (int i=0; i <= TOP_FITNESS; i++) {
	        int c = (255*i)/TOP_FITNESS;
	        MANNA_COLORS[i] = new Color(255-c, c, 0);
	    }
	}

	/*package*/ GAPainter ourEvolver = null;

	private final static int DEFAULT_POP_SIZE = 1024;
	private int myPopSize = 0;
	
	/**
	 * How often is a bit flipped in one of the genomes? <p>
	 *
	 * Defaults to 2%.
	 */
	public float myMutationRate = (float)0.02;
	
	/**
	 * Do we encode position in binary or gray code? <p>
	 *
	 * Defaults to binary.
	 */
	public boolean amGray = false;
	
	/**
	 * Uniform crossover means that for each bit position, a random 
     * determination is made as to which child gets dad's allele and which 
     * gets mom's allele. <p>
     *
     * The alternative is two point crossover, which treats the genome as a 
     * ring, cuts it at two random places, and swaps corresponding segments 
     * from mom & dad in order to make the two kids. <p>
     *
     * Defaults to uniform crossover.
	 */
	public boolean amUniform = true;  // uniform crossover
	
	/**
	 * Are closer creatures more likely to mate than more distant creatures?  
     * The alternative is that distance doesn't matter. <p>
     *
     * Defaults to no locality effect.
	 */
	public boolean amLocal = false;
	
	/**
	 * Is Manna consumed by the creatures that land on it?  <p>
	 *
	 * Defaults to true.
	 */
	public boolean amConsumed = true;

	private final int X_SHIFT = 8;
	private final int AREA_X = 1 << X_SHIFT;
	private final int X_MASK = AREA_X -1;

	private final int Y_SHIFT = 8;
	private final int AREA_Y = 1 << Y_SHIFT;
	private final int Y_MASK = AREA_Y -1;

    private final int GENE_SIZE = X_SHIFT + Y_SHIFT;

	private int  myPopX[] = new int[0];
	private int  myPopY[] = new int[0];
	private int  myFitness[][];
	private boolean amOccupied[][];

	private Random myRand = new Random();

	private final int rand(int bound) {
	    return (myRand.nextInt() & 0x7FFFFFFF) % bound;
	}

    /**
     * What's the carrying capacity of the ecology?
     */
	public int popSize() {
	    return myPopSize;
	}

    /**
     * Changes the carrying capacity of the ecology
     */
	public void setPopSize(int new_size) {
  	    int[] oldX = myPopX;
        int[] oldY = myPopY;
    	    myPopX = new int[new_size];
   		myPopY = new int[new_size];
   		int common = Math.min(myPopSize, new_size);
   		System.arraycopy(oldX,0,myPopX,0,common);
   		System.arraycopy(oldY,0,myPopY,0,common);

        for(int i = common; i < myPopSize; i++) {
            amOccupied[oldX[i]][oldY[i]] = false;
        }
       	for(int i = common; i < new_size; i++) {
		myPopX[i] = X_MASK & myRand.nextInt();
		myPopY[i] = Y_MASK & myRand.nextInt();
  			amOccupied[myPopX[i]][myPopY[i]] = true;
   		}
        myPopSize = new_size;
    }

    /**
     * Creates and initializes a GA to default values.
     */
	public GA() {
	    super();
	    setForeground(Color.black);
	    setBackground(Color.white);
		myFitness = new int[AREA_X][AREA_Y];
		amOccupied = new boolean[AREA_X][AREA_Y];
        setPopSize(DEFAULT_POP_SIZE);
        resize(AREA_X, AREA_Y);
    }

    private final int Gray(int binary) {
        return binary; //hack;
    }

    private final int antiGray(int gray) {
        return gray; //hack
    }

	private final int genotype(int xp, int yp) {
	    if (amGray) {
	        xp = Gray(xp);
	        yp = Gray(yp);
	    }
	    return (xp << X_SHIFT) | yp;
	}

	private final int xpos(int geno) {
	    int result = geno >> X_SHIFT;
	    if (amGray) {
	        return antiGray(result);
	    }
	    return result;
	}

	private final int ypos(int geno) {
	    int result = geno & Y_MASK;
	    if (amGray) {
	        return antiGray(result);
	    }
	    return result;
	}

	private final int mask() {
	    if (amUniform) {  // uniform crossover
	        return myRand.nextInt();
	    } else {
	        //two point crossover
	        int a = rand(GENE_SIZE+1);
	        int b = rand(GENE_SIZE+1);
	        return ((1 << a)-1) ^ ((1 << b)-1);
	    }
	}

    private boolean compete(int a, int b) {
        int parent, child;
        //a and b compete to be the parent
        boolean result = myFitness[myPopX[a]][myPopY[a]]
                        >= myFitness[myPopX[b]][myPopY[b]];
        if (amConsumed) {
            if (result) {
                parent = a;
                child = b;
            } else {
                parent = b;
                child = a;
            }
            myFitness[myPopX[parent]][myPopY[parent]]--;
        }
        return result;
    }

    private boolean store(Graphics gfx, int i, int x, int y) {
        if (amOccupied[x][y]) {
            return false;
        }
        amOccupied[myPopX[i]][myPopY[i]] = false;
        paintDot(gfx, myPopX[i],myPopY[i]);
        myPopX[i] = x;
        myPopY[i] = y;
        amOccupied[x][y] = true;
        paintDot(gfx, x,y);
        return true;
    }

    /**
     * Do one crossover operation.  Occasionally also mutate according to the 
     * mutation rate.
     *
     * note: not synchronized for efficiency.  Call only with lock held
     */
	public void step(Graphics gfx) {
	    int a = rand(myPopSize);
	    int b = rand(myPopSize);
	    int c = rand(myPopSize);
	    int d = rand(myPopSize);

        int dad, son;
        //a and b compete to be the dad
        if (compete(a, b)) {
            dad = a;
            son = b;
        } else {
            dad = b;
            son = a;
        }

        int mom, daught;
        //c and d compete to be the mom
        if (compete(c, d)) {
            mom = c;
            daught = d;
        } else {
            mom = d;
            daught = c;
        }

        int sperm = genotype(myPopX[dad], myPopY[dad]);
        int egg   = genotype(myPopX[mom], myPopY[mom]);
        int m = mask();
        int zygote1 = (sperm & m) | (egg & ~m);
        int zygote2 = (sperm & ~m) | (egg & m);
        store(gfx, son, xpos(zygote1), ypos(zygote1));
        store(gfx, daught, xpos(zygote2), ypos(zygote2));

        if (myRand.nextFloat() <= myMutationRate * 2) {
            int cosmic = rand(myPopSize);
            int target = genotype(myPopX[cosmic], myPopY[cosmic]);
            int bitpos = rand(GENE_SIZE);
            target ^= 1 << bitpos;
            store(gfx, cosmic, xpos(target), ypos(target));
        }
    }



    private void paintDot(Graphics gfx, int x, int y) {
        int fit;
        if (amOccupied[x][y]) {
            gfx.setColor(DOT_COLOR);
        } else if ((fit = myFitness[x][y]) > 0) {
            gfx.setColor(MANNA_COLORS[fit]);
        } else {
            gfx.setColor(NONE_COLOR);
        }
		gfx.drawLine(x, y, x, y);
	}

   	private void paintManna(Graphics gfx) {
		int x, y;
		for(x=0; x < AREA_X; x++) {
			for(y=0; y < AREA_Y; y++) {
			    int fit;
				if((fit = myFitness[x][y]) > 0) {
            		gfx.setColor(MANNA_COLORS[fit]);
					gfx.drawLine(x, y, x, y);
				}
			}
		}
	}

	private void paintCreatures(Graphics gfx) {
		gfx.setColor(DOT_COLOR);
		for(int i=0; i < myPopSize; i++) {
			gfx.drawLine(myPopX[i], myPopY[i],
			               myPopX[i], myPopY[i]);
		}
	}

    /**
     * Show the manna and the creatures
     */
	public void paint(Graphics gfx) {
	    synchronized(ourEvolver) {
            if (gfx != getGraphics()) {
                System.err.println("which graphics context?\n");
            }
		    gfx.setColor(NONE_COLOR);
            gfx.fillRect(0, 0, AREA_X, AREA_Y);
		    paintManna(gfx);
		    paintCreatures(gfx);
		}
	}

    /**
     * Add a block of new manna at this position.
     */
	public void addManna(int cx, int cy, int amount) {
	    synchronized(ourEvolver) {
    	    Graphics gfx = getGraphics();
	        int xBound = Math.min(cx + 10, AREA_X);
	        int yBound = Math.min(cy + 10, AREA_Y);
    		gfx.setColor(MANNA_COLORS[amount]);
	    	gfx.fillRect(cx, cy, xBound - cx, yBound - cy);
		    gfx.setColor(DOT_COLOR);
		    for (int x = cx; x < xBound; x++) {
		        for (int y = cy; y < yBound; y++) {
		            myFitness[x][y] = amount;
		            if (amOccupied[x][y]) {
					    gfx.drawLine(x, y, x, y);
					}
			    }
			}
	    }
	}
}