import java.awt.*;
import java.applet.Applet;
import java.util.Vector;
import java.util.Hashtable;
import java.util.Enumeration;
import java.math.BigInteger;

public class NeuroApplet extends Applet
{
	final Randomizer 	r = new Randomizer();
	Image 				offscreen;
	public final int	numNodes = 10;
	final Node			nodes[] = new Node[numNodes];

	public void init()
	{		
		offscreen = createImage(500, 570);
		
		// Create nodes
		for(int k = 0; k < numNodes; k++)
			nodes[k] = new Node(k*50, 0, this);
			
		// Link nodes
		for(int k = 1; k < numNodes-1; k++)
		{
			nodes[k].link(nodes[k-1], nodes[k+1]);			
		}
		nodes[0].link(nodes[numNodes-1], nodes[1]);
		nodes[numNodes-1].link(nodes[numNodes-2], nodes[0]);
		
		// Start them all up
		for(int k = 0; k < numNodes; k++)
			nodes[k].start();
	
		repaint();
	}
	
	public void update(Graphics g) // Override clearing behavior
	{
		paint(g);
	}
	
	public void paint(Graphics G)
	{
		Graphics g = offscreen.getGraphics();
		g.setClip(0, 0, 500, 570);
		
		g.setColor(Color.white);
		g.fillRect(0, 0, 500, 160);
		
		for(int k = 0; k < numNodes; k++)
			nodes[k].paint(g);
			
		G.drawImage(offscreen, 0, 0, null);
	}

}

public class Node extends Thread
{
	final NeuroApplet	neuro;
	final int			x, y;
	Node				prev, next;
	PriorityQueue		population;
	final int			popSize = 20;
	final int 			trials = 50;
	private Image		monitor, monitorScratch;
	final Semaphore		lock = new Semaphore(1);
	final Randomizer 	r = new Randomizer();
	
	private class Network
	{
		private Gene		dna[][];
		private final int	numGenes = 8; // Not including BiasGene
		private final double mutationRate = 0.05;
		private final int   B = 0; // BiasGene Constant
		public int			fitness;
		
		private class Gene
		{
			public double	xWeight, yWeight, bias, outputWeight;
			
			public Gene()
			{
				xWeight = r.nextDouble(-1, 1);
				yWeight = r.nextDouble(-1, 1);
				bias = r.nextDouble(-1, 1);
				outputWeight = r.nextDouble(-1, 1);
			}
			
			public Gene(Gene g)
			{
				xWeight = g.xWeight;
				yWeight = g.yWeight;
				bias = g.bias;
				outputWeight = g.outputWeight;
			}
			
			public void mutate()
			{
				xWeight += r.nextDouble(-0.1, 0.1);
				yWeight += r.nextDouble(-0.1, 0.1);
				bias += r.nextDouble(-0.1, 0.1);
				outputWeight += r.nextDouble(-0.1, 0.1);
			}
		}
		
		private class BiasGene extends Gene
		{
			public BiasGene()
			{
				xWeight = 0;
				yWeight = 0;
				bias = 1;
				outputWeight = r.nextDouble(-1, 1);
			}
			
			public BiasGene(Gene g)
			{
				xWeight = 0;
				yWeight = 0;
				bias = 1;
				outputWeight = g.outputWeight;
			}
			
			public void mutate()
			{
				outputWeight += r.nextDouble(-0.1, 0.1);
			}
		}
		
		public Network()
		{
			dna = new Gene[numGenes+1][2];
			
			dna[B][0] = new BiasGene();
			dna[B][1] = new BiasGene();
			
			for (int k = 1; k < numGenes+1; k++)
			{
				dna[k][0] = new Gene();
				dna[k][1] = new Gene();
			}
			computeFitness();
		}
		
		public Network(Network mom, Network dad)
		{
			dna = new Gene[numGenes+1][2];
			
			if (r.nextBoolean(0.5))
				dna[B][0] = new BiasGene(mom.dna[B][0]);
			else
				dna[B][0] = new BiasGene(mom.dna[B][1]);
				
			if (r.nextBoolean(0.5))
				dna[B][1] = new BiasGene(dad.dna[B][0]);
			else
				dna[B][1] = new BiasGene(dad.dna[B][1]);
				
			if (r.nextBoolean(mutationRate))
				if (r.nextBoolean(0.5))
					dna[B][0].mutate(); 
				else
					dna[B][1].mutate();
			
			for (int k = 1; k < numGenes+1; k++)
			{
				if (r.nextBoolean(0.5))
					dna[k][0] = new Gene(mom.dna[k][0]);
				else
					dna[k][0] = new Gene(mom.dna[k][1]);
					
				if (r.nextBoolean(0.5))
					dna[k][1] = new Gene(dad.dna[k][0]);
				else
					dna[k][1] = new Gene(dad.dna[k][1]);
					
				if (r.nextBoolean(mutationRate))
					if (r.nextBoolean(0.5))
						dna[k][0].mutate(); 
					else
						dna[k][1].mutate();
					
			}
			computeFitness();
		}
		
		private int computeFitness()
		{
			fitness = 0;
			
			// Circle
			final int t2 = trials/2;
			final double delta = (2*Math.PI)/t2;
			for (int k = 0; k < t2; k++)
			{
				double radius = r.nextDouble(0, 1);
				double angle = delta*k;
				
				double x = radius*Math.cos(angle);
				double y = radius*Math.sin(angle);
				
				boolean answer = true;
				
				boolean prediction = runNetwork(x, y);
				
				if (answer == prediction)
					fitness++;
			}
			for (int k = 0; k < t2; k++)
			{
				double radius = r.nextDouble(1, 2);
				double angle = delta*k;
				
				double x = radius*Math.cos(angle);
				double y = radius*Math.sin(angle);
				
				boolean answer = false;
				
				boolean prediction = runNetwork(x, y);
				
				if (answer == prediction)
					fitness++;
			}
			
			return fitness;
		}
		
		private double compute(double x, double y, Gene g1, Gene g2)
		{
			if ((x*(g1.xWeight+g2.xWeight) + y*(g1.yWeight+g2.yWeight) + (g1.bias+g2.bias)) > 0)
				return (g1.outputWeight+g2.outputWeight);
			else
				return 0;
		}
		
		private boolean runNetwork(double x, double y)
		{
			double sum = 0;
			for (int k = 0; k < numGenes+1; k++)
				sum += compute(x, y, dna[k][0], dna[k][1]);
			return (sum > 0);
		}
		
		public void paint(Graphics g)
		{
			g.setColor(Color.white);
			g.fillRect(0, 0, 50, 410);
			
			g.setColor(Color.red);
			for(int y = 0; y < 50; y++)
				for(int x = 0; x < 50; x++)
					if (runNetwork(x/12.5 - 2.0, y/12.5 - 2.0))
						g.fillRect(x, y, 1, 1);
			
			g.setColor(Color.black);
			g.drawOval(0, 0, 50, 50);
			g.drawOval(12, 12, 25, 25);
			
			try // Not sure why NoSuchMethodError happens on occasion...
			{
				for (int k = 0; k < numGenes+1; k++)
				{
					if (k % 2 == 0)
						g.setColor(Color.black);
					else
						g.setColor(Color.darkGray);
				
					StringBuffer s;
					
					s = new StringBuffer("x:");
					s.append(dna[k][0].xWeight+dna[k][1].xWeight);
					s.setLength(7);
					g.drawString(s.toString(), 0, k*40+60);
					
					s = new StringBuffer("y:");
					s.append(dna[k][0].yWeight+dna[k][1].yWeight);
					s.setLength(7);
					g.drawString(s.toString(), 0, k*40+70);
					
					s = new StringBuffer("B:");
					s.append(dna[k][0].bias+dna[k][1].bias);
					s.setLength(7);
					g.drawString(s.toString(), 0, k*40+80);
					
					s = new StringBuffer("o:");
					s.append(dna[k][0].outputWeight+dna[k][1].outputWeight);
					s.setLength(7);
					g.drawString(s.toString(), 0, k*40+90);
				}
			}
			catch (NoSuchMethodError e)
			{
			}
		}
	}
	
	private class LessFitNetwork implements LTEQ
	{
		// Return true if the first network is less fit than the second network.
		// NOT returning true on equals means newer networks get higher placing than older networks in the 
		// priority queue, which is what we want
		public boolean lteq( Object first, Object second )
		{
			return ((Network)first).fitness < ((Network)second).fitness;
		}
	}
		
	public Node(int X, int Y, NeuroApplet na)
	{
		x = X;
		y = Y;
		neuro = na;
		LessFitNetwork lfn = new LessFitNetwork();
		population = new PriorityQueue(lfn);
		for (int k = 0; k < popSize; k++)
			population.enqueue(new Network());
		monitor = neuro.createImage(50, 410);
		monitorScratch = neuro.createImage(50, 410);
	}
	
	public void link(Node Prev, Node Next)
	{
		prev = Prev;
		next = Next;
	}
		
	// main loop
	public void run()
	{
		try
		{
			int pass = 1;
			while (((Network) population.elementAt(4)).fitness < trials) // Stop when top 5 test perfect
			{
				Network dad;
				
				if (pass % 6 == 3)
				{
					// Lock to read neighbor's data
					prev.lock.acquire();
					dad = (Network) prev.population.elementAt(r.nextInt(0,4));
					prev.lock.release();
				}			
				else if (pass % 6 == 0)
				{
					// Lock to read neighbor's data
					next.lock.acquire();
					dad = (Network) next.population.elementAt(r.nextInt(0,4));
					next.lock.release();
				}			
				else
					// No need to lock to read our own data, as only we would write to it
					dad = (Network) population.elementAt(r.nextInt(0,4));
					
				Network mom = (Network) population.elementAt(r.nextInt(0,9));
				
				// Lock to write to our own data
				lock.acquire();
				population.enqueue(new Network(mom, dad));
				population.removeElementAt(popSize);
				lock.release();
				
				if (pass % 100 == 1) // Update monitor every 100 passes
				{
					((Network) population.elementAt(0)).paint(monitorScratch.getGraphics());
					{
						Image temp;
						temp = monitor;
						monitor = monitorScratch;
						monitorScratch = temp;
					}
				}
				if (pass % 10 == 1) // Update numbers every ten passes
					neuro.repaint();
				pass++;
			}
			// Make sure monitor image reflects winning network
			((Network) population.elementAt(0)).paint(monitorScratch.getGraphics());
			{
				Image temp;
				temp = monitor;
				monitor = monitorScratch;
				monitorScratch = temp;
			}
			neuro.repaint();
		}
		catch (InterruptedException e)
		{
			return;
		}
	}

	public void paint(Graphics g)
	{
		try
		{
			lock.acquire();
			g.setColor(Color.red);
			int k = 0;
			while (k < 10 && ((Network) population.elementAt(k)).fitness == trials)
			{
				g.drawString("" + ((Network) population.elementAt(k)).fitness, x+15, y+k*15+10);
				k++;
			}
			g.setColor(Color.black);
			while (k < 10)
			{
				g.drawString("" + ((Network) population.elementAt(k)).fitness, x+15, y+k*15+10);
				k++;
			}
			lock.release();
		}
		catch (InterruptedException e)
		{
			return;
		}
		g.drawImage(monitor, x, 160, null);
	}
}