/*					   
	Module: 	Ant4.java
	Author: 	F. Michael O'Brien (michael@obrienm.com)
	Version:	4.02
	Date:		02 Dec 2000
	Documents:	_projv[nnn].doc
	Notes:		
				written for the Sun JDK 1.2.2
	History:
	26 Oct 2000 - Class started, implemented by RouterAnimApplet
				to provide a Turing machine like independent entity that will
				route the circuit board in parallel with other Ant objects
	27 Oct 2000 - using behavior genome model, instead of direct state mapping
				of 64bit genotype into 18,446,744,073,709,551,616 states!
	30 Oct 2000 - V5: completed swarm enumeration and display, next ga calculation
	04 Nov 2000 - added selection, crossover code, behavior model additions
				- preparing for demo for 07.201 Presentation
	08 Nov 2000 - working on behavioral Model
				Output: total = 4 bits
					move 0:1 ;0
					dir 0-3 ;1-2
					switch 0:1 ;3
				Input: total = 16 bits, 2^16 = 65536  
				possible state reduction using only the following inputs
				(4 * 3 = 12) proxCurrent = proxBelow or proxAbove - depends on layer(0/1)
				(3) proxLayer
				Genotype Length: 65536 * 4 = 262144 bits
				Note:
					assume write always on
					hold is handled by a move with length of 0
					end will be handled outside the Ant class
					turn is handled above
					switch will be hangled by the output	
	09 Nov 2000	- schema model is too big for memory, I cannot create more than
				33*7 Ants using the current memory model
				- will use byte(8bits signed) for each allelle instead of
				a continuous stream of booleans, will reduce from 262144-65536
	10 Nov 2000	- added 2 layer handling code
	11 Nov 2000 - Modified Ant expression schema, a fixed length deterministic array of bytes
				each allele is read sequentially, the phenotype is expressed as follows
				bit0 = hold/move
				bit1-2 = direction [0:E, 1:N, 2:W, 3:S]
				bit3 = switch layer 0->1 or 1->0
				bit4 = move toward target node (override bits1-2)
				bit5-7 = reserved for future use
	12 Nov 2000 -
	15 Nov 2000	- fixed error where crossover was only one way
				- added bitwise mutation for crossed/copied bits in genotype during crossover
	17 Nov 2000 - error fixed: cannot switch layers and move at the same time
				- also, must be on bottom layer in order to connect with device
				- enforce: must be outside of initial device before switching layers from 0
	30 Nov 2000 - next version Ant4 combined with RouterAnimApplet4

*/

import java.util.*;			
import java.awt.*;
import java.io.*;
//import java.applet.Applet;
/*
   Class:      Ant4
   Structure:  ()
   SubClasses: -
   Inherits:   Object 
   Friends:    -
*/
//----------------------------------------------------------------
// Implements:		-
// Inherits:		-
// Implementors:	RouterAnimApplet
//----------------------------------------------------------------
class Ant4
{						  
	// simple behaviors within genotype
//protected int		genotypeArray[];
//protected boolean	genotypeBits[];
protected byte		genotypeBits[];

// static constant vectors
// directional vectors for the 4 possible directions 0=E, 1=N, 2=W, 3=S
private static int	xdir[]={1,0,-1,0};
private static int	ydir[]={0,-1,0,1};
// directional vectors
private static int	toxdir[]={2,1};
private static int	toydir[]={1,3};

//dirGoal,dirTwin,distGoal,distTwin
// invariant constants
protected int			netId;
protected int			nodeId;	// array index within swarm
// previous state
protected int			pDirection;
protected boolean		pHold, pWrite, pRemove, pSwitchLayer, pEnd;
// current state
protected int			cDirection;
protected boolean		cHold, cWrite, cRemove, cSwitchLayer, cEnd;
			
// fitess and genetics
protected int			cMoveSuccessfull;
protected int			cAlleleValue;
protected int			cAllelePosition; 

protected int			completedTurns;
protected int			completedSwitches;
protected int			timeToSolution;
protected int			attemptedMoves;
protected int			actualMoves;
protected int			age;
protected int			generation;

// next state
//protected int 			nDirection;
//protected boolean		nHold, nWrite, nRemove, nSwitchLayer, nEnd;
// sensory inputs (set by the implementing class)
// horizontal 8 way proximity grid (exluding center cell), for both layers
// direction:				values:
// 0-11 10du swne swne		0 = empty			4 = device
//      0123 4567 8901		1 = trace other		5 = Ant other
//    p 1098 7654 3210		2 = trace twin		6 = Ant twin
//                6745		3 = trace self		7 = target in sight
protected int			proxBelow[];
protected int			proxAbove[];
protected int			proxTraceBelow[];
protected int			proxTraceAbove[];

protected int			proxLayer;
protected int			proxTraceLayer;
// nearest goal direction gradient
protected int			dirGoal;
// nearest twin direction gradient
protected int			dirTwin;
// nearest goal distance 16=(16->infinity)
protected int			distGoal;
// nearest twin distance 16=(16->infinity)
protected int			distTwin;
// layer (self, nearest twin, nearest goal)
protected int			layer,pLayer;
protected int			posx, posy;	
// src and dest grid
protected int			srcx,srcy,destx,desty;
	
// constants
protected final int		behaviorBitLength=8;
//protected final int		genotypeLength=behaviorBitLength*8;
// length = 4*[0:layer][1-3:proxLayer][4-6:prox0][7-9:prox1][10-12:prox2][13-15:prox3]
//protected final int		genotypeLength=262144;	// 2^16 * 4
// +1 for 0-2^16, +1 for initial dir
protected final int		genotypeInitialOffset=0;
protected final int		genotypeLength;
protected final int		outputBitLength=4;

// behavior priorities
protected int			priorityVectorValue[];
protected int			priorityVectorIndex[];
protected int			currentPriorityIndex;
	
// proximity requests

// behavior
   
// for file output
//private	byte fileBuffer[] = new byte[80];
private DataOutputStream outFile;  

// new ants are initialized in the following state
public Ant4(int aNetId, int gLength) {
	netId 			= aNetId;
	pDirection 		= 0;
	pHold 			= false;
	pWrite 			= true;
	pRemove 		= false;
	pSwitchLayer 	= false;
	pEnd 			= false;

	cHold 			= false;
	cWrite 			= true;
	cRemove 		= false;
	cSwitchLayer 	= false;
	cEnd 			= false;

	proxBelow 		= new int[4];
	proxAbove 		= new int[4];
	proxTraceBelow 	= new int[4];
	proxTraceAbove 	= new int[4];
	proxLayer 		= 0;
	proxTraceLayer 	= 0;

	completedSwitches=0;
	completedTurns	= 0;
	timeToSolution 	= 0;
	attemptedMoves	= 0;
	actualMoves		= 0;
	age				= 0;
	generation		= 0;

	layer=0;


	// initial environment is empty
	for(int i=0;i<4;i++) {
		proxBelow[i]=0;
		proxAbove[i]=0;
	}

	genotypeLength=gLength+1+genotypeInitialOffset;	// 2^16 * 4
	genotypeBits = new byte[genotypeLength];

	cAllelePosition	= 0;

	// generate random genotype
/*	for(int i=0;i<genotypeLength;i++) {
		if((int)Math.floor(Math.random()*1000)<500)
			genotypeBits[i]=true;
		else
			genotypeBits[i]=false;
*/
		for(int j=0;j<genotypeLength;j++) {
			genotypeBits[j]=(byte) Math.floor(Math.random()*128);
			//System.out.print(" " + (new Byte(genotypeBits[j])).toString());
		}
	//}
	// initial direction
	//cDirection =	(int)(Math.floor(Math.random()*4));
	// start out by reading the first allele of the genotype
	cDirection = 	intFromTo(genotypeBits[0],1,2) >> 1;

//	System.out.println("Genotype completed for " + (new Integer(aNetId)).toString());

	// compute priorities
	priorityVectorValue = new int[behaviorBitLength];
	priorityVectorIndex = new int[behaviorBitLength];

	// enumerate priorities
	//sortPriorities();	// 2000nov08 commented
}

// copy constructor
public Ant4(Ant4 anAnt, double pMutation, boolean bvMutateAllBits) {
	netId 			= anAnt.getNetId();
	pDirection 		= 0;
	pHold 			= false;
	pWrite 			= true;
	pRemove 		= false;
	pSwitchLayer 	= false;
	pEnd 			= false;

	cHold 			= false;
	cWrite 			= true;
	cRemove 		= false;
	cSwitchLayer 	= false;
	cEnd 			= false;

	proxBelow 		= new int[4];
	proxAbove 		= new int[4];
	proxTraceBelow 	= new int[4];
	proxTraceAbove 	= new int[4];
	proxLayer 		= 0;
	proxTraceLayer 	= 0;

	completedSwitches=0;
	completedTurns	= 0;
	timeToSolution 	= 0;
	attemptedMoves	= 0;
	actualMoves		= 0;
	age				= 0;
	layer			= 0;
	// increment generation for this individual
	generation++;

	// initial environment is empty
	for(int i=0;i<4;i++) {
		proxBelow[i]=0;
		proxAbove[i]=0;
	}

	//genotypeArray[] = new int[genotypeLength];
	genotypeLength=anAnt.getGenotypeLength();
	genotypeBits = new byte[genotypeLength];
	
	for(int i=0;i<genotypeLength;i++) {
		// next line to test for random search behavior
		// when copying the genotype; substitute for random strings			
		//genotypeBits[i]=(byte) Math.floor(Math.random()*128);
		if(bvMutateAllBits)
			genotypeBits[i]=mutateBits(anAnt.getGenotypeAllele(i),pMutation,bvMutateAllBits);
		else
			genotypeBits[i]=anAnt.getGenotypeAllele(i);
	}
	cAllelePosition	= 0;

	// initial direction
	//cDirection =	(int)(Math.floor(Math.random()*4));
	// start out by reading the first allele of the genotype
	cDirection = 	intFromTo(genotypeBits[0],1,2) >> 1;
	srcx=anAnt.getSrcx();
	srcy=anAnt.getSrcy();
	destx=anAnt.getDestx();
	desty=anAnt.getDesty();

	posx=srcx;
	posy=srcy;


//	System.out.println("Genotype completed for " + (new Integer(aNetId)).toString());

	// compute priorities
	priorityVectorValue = new int[behaviorBitLength];
	priorityVectorIndex = new int[behaviorBitLength];
}


// new ants are reset to the following state
public void reset() {
//	netId 			= aNetId;
	pDirection 		= 0;
	pHold 			= false;
	pWrite 			= true;
	pRemove 		= false;
	pSwitchLayer 	= false;
	pEnd 			= false;

	cHold 			= false;
	cWrite 			= true;
	cRemove 		= false;
	cSwitchLayer 	= false;
	cEnd 			= false;

//	proxBelow 		= new int[4];
//	proxAbove 		= new int[4];
//	proxTraceBelow 	= new int[4];
//	proxTraceAbove 	= new int[4];
	proxLayer 		= 0;
	proxTraceLayer 	= 0;

	completedSwitches=0;
	completedTurns	= 0;
	timeToSolution 	= 0;
	attemptedMoves	= 0;
	actualMoves		= 0;
	age				= 0;
	generation++;

	// initial environment is empty
	for(int i=0;i<4;i++) {
		proxBelow[i]=0;
		proxAbove[i]=0;
	}

	//genotypeArray[] = new int[genotypeLength];
//	genotypeLength=gLength+1+genotypeInitialOffset;	// 2^16 * 4
//	genotypeBits = new byte[genotypeLength];

	cAllelePosition	= 0;

	// generate random genotype
//		for(int j=0;j<genotypeLength;j++) {
//			genotypeBits[j]=(byte) Math.floor(Math.random()*128);
//			//System.out.print(" " + (new Byte(genotypeBits[j])).toString());
//		}
	//}
	// initial direction
	//cDirection =	(int)(Math.floor(Math.random()*4));
	// start out by reading the first allele of the genotype
	cDirection = 	intFromTo(genotypeBits[0],1,2) >> 1;

//					anAnt.setNetId(n);
//					anAnt.setLayer(0);
//					anAnt.setNodeId(lNodeCount);
//					anAnt.setSrcx(anAnt.getPosx());
//					anAnt.setSrcy(anAnt.getPosy());
	// reset position
	posx=srcx;
	posy=srcy;

//	System.out.println("Genotype completed for " + (new Integer(aNetId)).toString());

	// compute priorities
//	priorityVectorValue = new int[behaviorBitLength];
//	priorityVectorIndex = new int[behaviorBitLength];

	// enumerate priorities
	//sortPriorities();	// 2000nov08 commented


}

private byte mutateBits(byte aByte, double pMutation,boolean bvMutateAllBits) {
	int 	fbit;
	byte 	val=aByte;

	//return (byte)(Math.floor(Math.random()*128));

	if(Math.random()<pMutation) {
		// bytes are signed 7bit #'s, dont change bit7
		fbit=(int)(Math.floor(Math.random()*7));
		if((val & (1 << fbit))>0) {
			val=(byte)(val - (1 << fbit));
		} else {
			val=(byte)(val + (1 << fbit));
		}

		System.out.println("_mutating_" + (new Integer(nodeId)).toString() +
//			"\tAllele: " + (new Integer(j)).toString() + 
			"\tBit: " + (new Integer(fbit)).toString() + 
			"\tFrom: " + (new Integer(aByte)).toString() + 
			"\tTo: " + (new Integer(val)).toString());
	}
	return val;
}

public void performCrossoverWithMutation(Ant4 anAnt,int cpos,double pMutation, 
		boolean bvMutateAllBits) {
	byte hold;
	// set the age of this individual back to 0;
	generation=0;
	// set the age of anAnt back to 0;
	anAnt.setGeneration(0);

	// test mutation
	//for(int j=0;j<9;j++) {
	//	genotypeBits[j]=(byte)(Math.floor(Math.random()*256));
	//}
	// perform mutation first
	// mutate in the copy constructor, so asexual repro is also mutated
	if(!bvMutateAllBits) { // otherwise mutate in the copy constructor
		for(int j=0;j<genotypeLength;j++) {
			// first ant
			genotypeBits[j]=mutateBits(genotypeBits[j],pMutation,bvMutateAllBits);
			// second ant
			anAnt.setGenotypeAllele(j,mutateBits(anAnt.getGenotypeAllele(j),pMutation,bvMutateAllBits));
		}
	}

	// perform crossover on first part
	for(int j=0;j<cpos;j++) {
		// temp hold gene from 1
		hold=genotypeBits[j];
		// copy gene from 2 to 1
		genotypeBits[j]=anAnt.getGenotypeAllele(j);
		// copy gene from 1 to 2
		anAnt.setGenotypeAllele(j,hold);
	}		
}

public void performCrossover(Ant4 anAnt,int cpos) {
	byte hold;
	// set the age of this individual back to 0;
	generation=0;
	// set the age of anAnt back to 0;
	anAnt.setGeneration(0);

	// perform crossover on first part
	for(int j=0;j<cpos;j++) {
		// temp hold gene from 1
		hold=genotypeBits[j];
		// copy gene from 2 to 1
		genotypeBits[j]=anAnt.getGenotypeAllele(j);
		// copy gene from 1 to 2
		anAnt.setGenotypeAllele(j,hold);
	}		
}

// extract a portion of bits from an integer
private int intFromTo(int n, int a, int b) { 
	return (n & ((1 << (b+1))-1)) & (((1 << (b+1))-1)-((1 << a)-1));
}

// extract a portion of bits from an integer
private String binStringFromTo(int n, int a, int b) { 
	return Integer.toBinaryString(intFromTo(n,a,b) >> a);
}

	// sensory inputs (set by the implementing class)
	// horizontal 8 way proximity grid (exluding center cell), for both layers
	// direction:				values:
	// 0-11 10du swne swne		0 = empty			4 = device
	//      0123 4567 8901		1 = trace other		5 = Ant other
	//    p 1098 7654 3210		2 = trace twin		6 = Ant twin
	//                6745		3 = trace self		7 = target in sight

private int activateBehavior_haltWhenAdjacentTo(int proxType) {
	if(proxType==4) {
		// check if adj device cell is dest
		for(int d=0;d<4;d++) {
			if((posx+xdir[d]==destx)&&(posy+ydir[d]==desty)) {
				// must be on bottom layer in order to connect with device
				if(layer==0) {
					cEnd=true;
	
					//System.out.println("Halt1 " + (new Integer(nodeId)).toString());
					return 1;
				}
			}
		}		
	}

	//if(proxType==2) {
		// check if adj cell is twin trace [excluding self trace]
		for(int d=0;d<4;d++) {
			if(layer==0) {
				if(proxBelow[d]==2) {
					if((proxTraceBelow[d]<nodeId+1)||(proxTraceBelow[d]>nodeId+1)) {
						cEnd=true;
//						System.out.println("Halt2 " + (new Integer(proxTraceBelow[d])).toString() + 
//							" " + (new Integer(nodeId+1)).toString());
						return 1;
					}
				}
			} else {
				if(proxAbove[d]==2) {
					if((proxTraceAbove[d]<nodeId+1)||(proxTraceAbove[d]>nodeId+1)) {
						cEnd=true;
//						System.out.println("Halt3 " + (new Integer(proxTraceAbove[d])).toString() + " " 
//							+ (new Integer(nodeId+1)).toString());
						return 1;
					}
				}
			}
		}		
	//}
	return 0;
}
/*
private int activateBehavior_haltWhenNextWillBe(int proxType) {
	if(proxType==7) {
		// check if next cell is dest
		if((posx+xdir[cDirection]==destx)&&(posy+ydir[cDirection]==desty)) {
			cEnd=true;
			return 1;
		} else {
			return 0;
		}
	}

	if((proxBelow[cDirection]==7)) {
		cEnd=true;
		return 1;
	} else {
		return 0;
	}
}
*/

private int activateBehavior_moveUntilAdjacentIs(int proxType) {
	// check prox ahead
	//if(nodeId==0)
	//	System.out.println("verify proxBelow[cDirection]:" + 
	//		(new Integer(proxBelow[cDirection])).toString());			 
	attemptedMoves++;
	if(layer==0) {
		if((proxBelow[cDirection]==proxType)||
			(proxBelow[cDirection]==1)||
			(proxBelow[cDirection]==4)||
			(proxBelow[cDirection]==5)||
			(proxBelow[cDirection]==6)) {
			// dont go through devices, alien ants, or twin ants

			return 0;
		} else {
			// dont go through alien traces, only empty=0 and twin=2
			if((proxBelow[cDirection]==2)||(proxBelow[cDirection]==0)) { 
			//if((proxBelow[cDirection]==0)) {
				//if(nodeId==0)
				//	System.out.println("moving: proxBelow[cDirection]:" + 
				//		(new Integer(proxBelow[cDirection])).toString());			 
				// move ahead
				posx+=xdir[cDirection];
				posy+=ydir[cDirection];
				actualMoves++;
				// moved? so recompute for all ants
				return 1;
			} else {
				return 0;
			}
		}
	} else {
		if((proxAbove[cDirection]==proxType)||
			(proxAbove[cDirection]==1)||
			(proxAbove[cDirection]==4)||
			(proxAbove[cDirection]==5)||
			(proxAbove[cDirection]==6)) {
			// dont go through devices, alien ants, or twin ants
			return 0;
		} else {
			// dont go through alien traces, only empty=0 and twin=2
			if((proxBelow[cDirection]==2)||(proxBelow[cDirection]==0)) { 
			//if((proxAbove[cDirection]==0)) { 
				// move ahead, but not if at src at layer 1, should be handled by attemptToSwitchLayer()
				if((posx>srcx)||(posy>srcy)||(posx<srcx)||(posy<srcy)) {
					posx+=xdir[cDirection];
					posy+=ydir[cDirection];
					// moved? so recompute for all ants
					return 1;
				} else {
					return 0;
				}
			} else {
				return 0;
			}
		}
	}
}

private int attemptToSwitchLayer() {
	if((proxLayer==1)||
		(proxLayer==4)||
		(proxLayer==5)||
		(proxLayer==6)) {
		// dont go through devices, alien ants, or twin ants
		return 0;
	} else {
		// dont go through alien traces, only empty=0 and twin=2
		if((proxTraceLayer==2)||(proxTraceLayer==0)) { 
		//if((proxBelow[cDirection]==0)) {
			//if(nodeId==0)
			//	System.out.println("moving: proxBelow[cDirection]:" + 
			//		(new Integer(proxBelow[cDirection])).toString());			 
			// move ahead
			
			// enforce: must be outside of initial device before switching layers from 0
			if((posx>srcx)||(posy>srcy)||(posx<srcx)||(posy<srcy)) {
				layer=1-layer;
				// moved? so recompute for all ants
				return 1;
			} else {
				return 0;
			}
		} else {
			return 0;
		}
	}
}

// computeNextState
public int computeNextState() {
	int antsMoved=0;
	int allele;
	boolean behaveMove,seekGoal;

	// check for solution
	age++;
	if(!cEnd)
		timeToSolution++;

	if((pDirection<cDirection)||(pDirection>cDirection)) {
		completedTurns++;
	}


	// save current state to previous state
	pDirection = 	cDirection;
	pHold =			cHold;
	pWrite =		cWrite;
	pRemove = 		cRemove;
	pSwitchLayer = 	cSwitchLayer;
	pEnd = 		cEnd;

	// compute next state using the Ant genotype
	// get 64bit state vector as an integer
	long 			lvNextState=0;
	long 			lvMult=1;
	int				offset,dirToDest;

	// sensory inputs (set by the implementing class)
	// horizontal 8 way proximity grid (exluding center cell), for both layers
	// direction:				values:
	// 0-11 10du swne swne		0 = empty			4 = device
	//      0123 4567 8901		1 = trace other		5 = Ant other
	//    p 1098 7654 3210		2 = trace twin		6 = Ant twin
	//                6745		3 = trace self		7 = target in sight

/*			Output: total = 4 bits
					move 0:1 ;0
					dir 0-3 ;1-2
					switch 0:1 ;3
// length = 4*[0:layer][1-3:proxLayer][4-6:prox0][7-9:prox1][10-12:prox2][13-15:prox3]
*/
	// express current allele position in genotype
	cDirection=0;
	// get allele
	//System.out.println("gp:"+(new Integer(cAllelePosition)).toString());
	allele = (int)genotypeBits[cAllelePosition];
	cAlleleValue=allele;

	// increment allele position
	if(cAllelePosition<genotypeLength-1) {
		cAllelePosition++;
	} else {
		cAllelePosition=1;
		cHold=true;
	}

//	System.out.println("L:"+(new Integer(layer)).toString()+"-Ant("+(new Integer(nodeId)).toString()
//		+").genotypeBits["+(new Integer(cAllelePosition)).toString() 
//			+"] = "+(new Integer(allele)).toString());			 

	if((allele & 1) > 0)
		behaveMove=true;
	else
		behaveMove=false;

	if((allele & 2) > 0)
		cDirection+=1;
	if((allele & 4) > 0)
		cDirection+=2;
	if((allele & 8) > 0)
		cSwitchLayer=true;
	else
		cSwitchLayer=false;
	if((allele & 16) > 0)
		seekGoal=true;
	else
		seekGoal=false;

//	for(int j=0;j<genotypeLength;j++) {
//			cAlleleValue=(int)genotypeBits[j];
//			//System.out.print(" " + (new Byte(genotypeBits[j])).toString());
//			System.out.print(" " + (new Integer(cAlleleValue)).toString());
//		}

	// try to move
	// testing
	//cDirection = (int)(Math.floor(Math.random()*4));
	//behaveMove=true;
	// if seek goal is true
	if(!cEnd) {
		if(seekGoal) {
			//cDirection = addOffsetToDirection(cDirection, computeDirectionToDestination());
			cDirection = computeDirectionToDestination();
		}

		if(behaveMove) {
			// stop ant when next to dest device
			activateBehavior_haltWhenAdjacentTo(4);
			// stop ant when next to twin trace [excluding its own self trace]
			activateBehavior_haltWhenAdjacentTo(2);	
			antsMoved+=activateBehavior_moveUntilAdjacentIs(7);
			if(antsMoved>0) 
				cMoveSuccessfull=1;
			else
				cMoveSuccessfull=0;
			//activateBehavior_haltWhenAdjacentTo(7);
		}
		// cannot switch layers and move at the same time, vertical diagonal
		if((antsMoved==0)&&(!behaveMove)) {
			if(cSwitchLayer) {
				antsMoved+=attemptToSwitchLayer();
				if(antsMoved>0) {
					completedSwitches++;
				}
			}
		}
	}		
	//System.out.println("_ComputeNextState: posx=" + (new Integer(posx)).toString() + ",posy=" + (new Integer(posy)).toString());
	//}
	// must send a value back for switched layers as well
	return antsMoved;
}	        

private int computeDirectionToDestination() {
	int ddir,dx,dy;
	dx=destx-posx; dy=desty-posy;
	if(Math.abs(dx)<Math.abs(dy)) {
		// go in the y dir
		if(dy<0)
			return 1;
		else
			return 3;
	} else {
		// go in the x dir
		if(dx<0)
			return 2;
		else
			return 0;
	}
}

private int addOffsetToDirection(int dir, int offset) {
	int newDir=dir+offset;
	if(newDir<0)
		return newDir+4;
	else
		if(newDir>3)
			return newDir-4;
		else
			return newDir;
}

/*
// perform a bubble-sort on the priority list  
// must adjust code for genotypeBits 2000 nov 09
private void sortPriorities() {
	boolean unsorted=true;
	boolean paired=true;
	int i,j,p,t1;
	int behavior1, behavior2;
	int priority;

//	System.out.println("\n_Ant["+ (new Integer(netId)).toString() + "]:Behavior Priorities["+ (new Integer(behaviorBitLength)).toString() + "] before sorting");
	// display unsorted behaviors
	for(i=0;i<behaviorBitLength;i++) {
		priority=convertBitsToInt(genotypeBits[i*behaviorBitLength+1],
			genotypeBits[i*behaviorBitLength+2],
			genotypeBits[i*behaviorBitLength+3],
			genotypeBits[i*behaviorBitLength+4],
			genotypeBits[i*behaviorBitLength+5],
			genotypeBits[i*behaviorBitLength+6],
			genotypeBits[i*behaviorBitLength+7]);
		//System.out.println((new Integer(i)).toString() + ":" + (new Integer(convertBitsToInt(genotypeBits[i*8],false,false,false,false,false,false))).toString() + " " + (new Integer(priority)).toString());
//		System.out.print((new Integer(convertBitsToInt(genotypeBits[i*8],false,false,false,false,false,false))).toString() + ":" + (new Integer(priority)).toString() + "\t");
	}
//	System.out.println();

	// first find lowest priority and fill the array, to account for non-existent behaviors
	int highestBehavior=2 << (behaviorBitLength-1);
	int highestBehaviorIndex=0;
	int currentBehavior;//=256;
	for(i=0;i<behaviorBitLength;i++) {
		if(genotypeBits[i*behaviorBitLength]) {
			currentBehavior=convertBitsToInt(genotypeBits[i*behaviorBitLength+1],
			genotypeBits[i*behaviorBitLength+2],
			genotypeBits[i*behaviorBitLength+3],
			genotypeBits[i*behaviorBitLength+4],
			genotypeBits[i*behaviorBitLength+5],
			genotypeBits[i*behaviorBitLength+6],
			genotypeBits[i*behaviorBitLength+7]);
			if(currentBehavior < highestBehavior) {
				highestBehavior = currentBehavior;
				highestBehaviorIndex = i;
			}
		}
	}

	// prefill the array with the highest priority ie: 32103333
	for(i=0;i<behaviorBitLength;i++) {
		priorityVectorValue[i]=highestBehavior;
		priorityVectorIndex[i]=highestBehaviorIndex;
	}
	// then fill beginning with all active behaviors
	j=0;
	for(i=0;i<behaviorBitLength;i++) {
		if(genotypeBits[i*behaviorBitLength]) {
			priorityVectorIndex[j]=i;
			priorityVectorValue[j]=convertBitsToInt(genotypeBits[i*behaviorBitLength+1],
			genotypeBits[i*behaviorBitLength+2],
			genotypeBits[i*behaviorBitLength+3],
			genotypeBits[i*behaviorBitLength+4],
			genotypeBits[i*behaviorBitLength+5],
			genotypeBits[i*behaviorBitLength+6],
			genotypeBits[i*behaviorBitLength+7]);
			// increment dest vector index
			j++;
		}
	}
	//System.out.println("J:" + (new Integer(j)).toString());

//	System.out.println("_priorityVectorIndex["+ (new Integer(behaviorBitLength)).toString() + "] before sorting");
	// display unsorted behaviors
//	for(i=0;i<behaviorBitLength;i++)
//		System.out.print((new Integer(priorityVectorIndex[i])).toString()+ ":" + (new Integer(priorityVectorValue[i])).toString()+ "\t");
//	System.out.println();

	// perform sort
	unsorted=true;
	while(unsorted)	{
		unsorted=false;
		for(i=0;i<behaviorBitLength-1;i++) {
			//unsorted=false;
			behavior1=priorityVectorValue[i];
			behavior2=priorityVectorValue[i+1];
			//behavior2=convertBitsToInt(genotypeBits[p*8+1],genotypeBits[p*8+2],genotypeBits[p*8+3],genotypeBits[p*8+4],genotypeBits[p*8+5],genotypeBits[p*8+6],genotypeBits[p*8+7]); 
			if(behavior1<behavior2) {
				//System.out.println((new Integer(i)).toString() + "-" + (new Integer(i+1)).toString());
				unsorted=true;					
				priorityVectorValue[i]=behavior2;
				priorityVectorValue[i+1]=behavior1;
				t1=priorityVectorIndex[i];
				priorityVectorIndex[i]=priorityVectorIndex[i+1];
				priorityVectorIndex[i+1]=t1;
				i=0;
			}
		}
	}

//	System.out.println("_priorityVectorIndex["+ (new Integer(behaviorBitLength)).toString() + "] after sorting");
	// display unsorted behaviors
//	for(i=0;i<behaviorBitLength;i++)
//		System.out.print((new Integer(priorityVectorIndex[i])).toString()+ ":" + (new Integer(priorityVectorValue[i])).toString()+ "\t");
//	System.out.println();
}
*/

// get/set methods
// sensory inputs (set by the implementing class)
// horizontal 8 way proximity grid (exluding center cell), for both layers
// direction:				values:
// 0-11 10du swne swne		0 = empty			4 = device
//      0123 4567 8901		1 = trace other		5 = Ant other
//    p 1098 7654 3210		2 = trace twin		6 = Ant twin
//                6745		3 = board edge		7 = target in sight
public void			setGenotypeAllele(int aPos, byte anInput) { genotypeBits[aPos]=anInput; }
public void 		setGenotypeBits(byte[] anArray) { genotypeBits = anArray; }
//public void setGenotypeArray(int[] anArray) { genotypeArray = anArray; }
//public void setProxBelow(int[] anArray) { proxBelow = anArray; }
public void 		setProxBelow(int d0,int d1,int d2,int d3) { 
	proxBelow[0]=d0;	proxBelow[1]=d1;	proxBelow[2]=d2;	proxBelow[3]=d3; }
//public void setProxAbove(int[] anArray) { proxAbove = anArray; }
public void 		setProxAbove(int d0,int d1,int d2,int d3) { 
	proxAbove[0]=d0;	proxAbove[1]=d1;	proxAbove[2]=d2;	proxAbove[3]=d3; }
// the NodeId trails on the prox
public void 		setProxTraceAbove(int d0,int d1,int d2,int d3) { 
	proxTraceAbove[0]=d0;	proxTraceAbove[1]=d1;	proxTraceAbove[2]=d2;	proxTraceAbove[3]=d3; }
public void 		setProxTraceBelow(int d0,int d1,int d2,int d3) { 
	proxTraceBelow[0]=d0;	proxTraceBelow[1]=d1;	proxTraceBelow[2]=d2;	proxTraceBelow[3]=d3; }
// set the state of the cell either above or below the Ant
public void 		setProxLayer(int anInput) { proxLayer = anInput; }
public void 		setProxTraceLayer(int anInput) { proxTraceLayer = anInput; }
// nearest goal direction gradient
public void 		setDirGoal(int anInput) { dirGoal = anInput; }
// nearest twin direction gradient
public void 		setDirTwin(int anInput) { dirTwin = anInput; }
// nearest goal distance 16=(16->infinity)
public void 		setDistGoal(int anInput) { distGoal = anInput; }
// nearest twin distance 16=(16->infinity)
public void 		setDistTwin(int anInput) { distTwin = anInput; }
// layer (self, nearest twin, nearest goal)
public void 		setLayer(int anInput) {	layer = anInput; }
public void 	setPosx(int anInput) { posx = anInput; }
public void 	setPosy(int anInput) { posy = anInput; }
public void 	setNetId(int anInput) { netId = anInput; }
public void 	setNodeId(int anInput) { nodeId = anInput; }
public void 	setSrcx(int anInput) { srcx = anInput; }
public void 	setSrcy(int anInput) { srcy = anInput; }
public void 	setDestx(int anInput) { destx = anInput; }
public void 	setDesty(int anInput) { desty = anInput; }
public void		setGeneration(int anInput) { generation = anInput; }

// get state info
public byte		getGenotypeAllele(int anInput) { return genotypeBits[anInput]; }
public byte[] 	getGenotypeBits() { return genotypeBits; }
public int	 	getGenotypeLength() { return genotypeLength; }

//public int[] 	getGenotypeArray() { return genotypeArray; }
public int 		getProxBelow(int pos) { return proxBelow[pos]; }
public int 		getProxAbove(int pos) { return proxAbove[pos]; }
public int 		getProxTraceBelow(int pos) { return proxTraceBelow[pos]; }
public int 		getProxTraceAbove(int pos) { return proxTraceAbove[pos]; }
public int 		getProxLayer() { return proxLayer;}
public int 		getProxTraceLayer() { return proxTraceLayer;}
public int 		getpDirection() { return pDirection; }
public boolean 	getpHold() { return pHold; }
public boolean 	getpWrite() { return pWrite; }
public boolean 	getpRemove() { return pRemove; }
public boolean 	getpSwitchLayer() { return pSwitchLayer; }
public boolean 	getpEnd() { return pEnd; }
public int 		getcDirection() { return cDirection; }
public boolean 	getcHold() { return cHold; }
public boolean 	getcWrite() { return cWrite; }
public boolean 	getcRemove() { return cRemove; }
public boolean 	getcSwitchLayer() { return cSwitchLayer; }
public boolean 	getcEnd() { return cEnd; }
//public int 	getnDirection() { return nDirection; }
//public boolean 	getnHold() { return nHold; }
//public boolean 	getnWrite() { return nWrite; }
//public boolean 	getnRemove() { return nRemove; }
//public boolean 	getnSwitchLayer() { return nSwitchLayer; }
//public boolean 	getnEnd() { return nEnd; }
public int 		getNetId() { return netId; }
public int 		getLayer() { return layer; }
public int 		getPosx() { return posx; }
public int 		getPosy() { return posy; }
public int 		getNodeId() { return nodeId; }
public int 		getSrcx() { return srcx; }
public int 		getSrcy() { return srcy; }
public int 		getDestx() { return destx; }
public int 		getDesty() { return desty; }
public int		getCompletedSwitches() { return completedSwitches; }
public int 		getCompletedTurns() { return completedTurns; }
public int 		getcMoveSuccessfull() { return cMoveSuccessfull; }
public int 		getcAlleleValue() { return cAlleleValue; }
public int 		getcAllelePosition() { return cAllelePosition; } 
public int		getTimeToSolution() { return timeToSolution; }
public int		getGeneration() { return generation; }

public void writeGenomeToFile(String fname) {
  	// write output header to disk for non-applets
	try {
		// create output stream
		outFile = new DataOutputStream(new FileOutputStream(fname,false));	// append=false
		outFile.writeBytes("#\t"+fname + "\r\n"); 		
		outFile.writeBytes("L\t" + (new Integer(genotypeLength)).toString() + "\r\n");

		// output genotype
		for(int i=0;i<genotypeLength;i++) {
			outFile.writeBytes((new Integer(genotypeBits[i])).toString() + "\r\n");
		}
		outFile.close();
	} catch (Exception e) {
		String err = e.toString();
		System.out.println(err);
	}
}


public void decodeGenotypeBits(){
// 0: end
// 1: hold
// 2: move
// 3: remove trace
// 4: switch
// 5: turn
// 6: write	trace
}

public void encodeGenotypeBits(){
}

private int convertBitsToInt(boolean b0, boolean b1, boolean b2, boolean b3,boolean b4, boolean b5, boolean b6) {
	int total=0;
	if(b0)	total+=1;
	if(b1)	total+=2;
	if(b2)	total+=4;
	if(b3)	total+=8;
	if(b4)	total+=16;
	if(b5)	total+=32;
	if(b6)	total+=64;
	return total;
}

public static void main(String args[]) {
		Ant4 a = new Ant4(0,100);
		int x;
//		for(int i=1;i<=10;i++) {
//			x=(int)Math.floor(Math.random()*100)+1;
//			a.insert(x);
//		}
}

/*
askAdjacentAntToWaitOn(right, left, around, vertical)
askAdjacentAntToHaltOn(right, left, around, vertical)
askAdjacentAntToTurnOn(right, left, around, vertical)

moveWhileAdjacentIs(empty, Device, Trace, Ant) on (right, left, prev, next, up | down)
followCorridorUntil(empty, Device, Trace, Ant) on (right, left, prev, next, up | down)
//interrogateAntOn(
haltWhenAdjacentTo(empty, Device, Trace, Ant)
haltWhenNextWillBe(empty, Device, Trace, Ant)
overwriteTraceWhen(empty, Trace, Ant, self)
turnFromNextCellContainingAlienTraceOn(right, left, around, vertical)
turnTowardsNextCellContainingAlienTraceOn(right, left, around, vertical)
waitFor(steps)
waitUntilProximityWith(empty, Device, Trace, Ant) on (right, left, prev, next, up | down)
waitUntilNoProximityWith(empty, Device, Trace, Ant) on (right, left, prev, next, up | down)
willHonourRequests()
*/
/*		
		ivNextState=ivNextState+=pDirection*lvMult; lvMult*=8;
		if(pHold) ivNextState=ivNextState+=pHold*lvMult; lvMult*=2;
		if(pWrite) ivNextState=ivNextState+=pWrite*lvMult; lvMult*=2;
		if(pRemove) ivNextState=ivNextState+=pRemove*lvMult; lvMult*=2;
		if(pSwitchLayer) ivNextState=ivNextState+=pSwitchLayer*lvMult; lvMult*=2;
		if(pEnd) ivNextState=ivNextState+=pEnd*lvMult; lvMult*=2;
		ivNextState=ivNextState+=cDirection*lvMult; lvMult*=8;
		if(cHold) ivNextState=ivNextState+=pHold*lvMult; lvMult*=2;
		if(cWrite) ivNextState=ivNextState+=pcWrite*lvMult; lvMult*=2;
		if(cRemove) ivNextState=ivNextState+=pRemove*lvMult; lvMult*=2;
		if(cSwitchLayer) ivNextState=ivNextState+=pSwitchLayer*lvMult; lvMult*=2;
		if(cEnd) ivNextState=ivNextState+=pEnd*lvMult; lvMult*=2;
		ivNextState=ivNextState+=proxBelow[0]*lvMult; lvMult*=8;
		ivNextState=ivNextState+=proxBelow[1]*lvMult; lvMult*=8;
		ivNextState=ivNextState+=proxBelow[2]*lvMult; lvMult*=8;
		ivNextState=ivNextState+=proxBelow[3]*lvMult; lvMult*=8;
		ivNextState=ivNextState+=proxBelow[4]*lvMult; lvMult*=8;
		ivNextState=ivNextState+=proxBelow[5]*lvMult; lvMult*=8;
		ivNextState=ivNextState+=proxBelow[6]*lvMult; lvMult*=8;
		ivNextState=ivNextState+=proxBelow[7]*lvMult; lvMult*=8;
		ivNextState=ivNextState+=proxAbove[0]*lvMult; lvMult*=8;
		ivNextState=ivNextState+=proxAbove[1]*lvMult; lvMult*=8;
		ivNextState=ivNextState+=proxAbove[2]*lvMult; lvMult*=8;
		ivNextState=ivNextState+=proxAbove[3]*lvMult; lvMult*=8;
		ivNextState=ivNextState+=proxAbove[4]*lvMult; lvMult*=8;
		ivNextState=ivNextState+=proxAbove[5]*lvMult; lvMult*=8;
		ivNextState=ivNextState+=proxAbove[6]*lvMult; lvMult*=8;
		ivNextState=ivNextState+=proxAbove[7]*lvMult; //lvMult*=8;
		// 2^64 = 18,446,744,073,709,551,616
		// pass 
		cDirection = 	genotype[ivNextState] & 7;
		cHold =			(genotype[ivNextState] & 8) >> 3;
		cWrite =		(genotype[ivNextState] & 16) >> 4;
		cRemove = 		(genotype[ivNextState] & 32) >> 5;
		cSwitchLayer = 	(genotype[ivNextState] & 64) >> 6;
		cEnd = 		(genotype[ivNextState] & 128) >> 7;
*/

/*
// new ants are initialized in the following state
public Ant4(int anetId, int apDirection, boolean apHold,
	boolean apWrite, boolean apRemove, boolean apSwitchLayer, boolean apEnd, 
	int acDirection, boolean acHold, boolean acWrite, boolean acRemove, boolean acSwitchLayer, boolean acEnd) {
	netId = 		anetId;
	pDirection = 	apDirection;
	pHold =			apHold;
	pWrite =		apWrite;
	pRemove = 		apRemove;
	pSwitchLayer = 	apSwitchLayer;
	pEnd = 			apEnd;
	
	cDirection = 	acDirection;
	cHold =			acHold;
	cWrite =		acWrite;
	cRemove = 		acRemove;
	cSwitchLayer = 	acSwitchLayer;
	cEnd = 			acEnd;
	
	//genotype = new short[18446744073709551616];
	proxBelow = new int[4];
	proxAbove = new int[4];
	proxLayer = 0;
	//genotypeArray[] = new int[genotypeLength];
	genotypeBits = new boolean[genotypeLength];

	for(int i=0;i<genotypeLength;i++) {
		//genotypeArray[i]=0;
		genotypeBits[i]=false;
	}
}
*/

}