/*
 * Weasel illustrates the ability of evolutionary techniques to solve
 * enormous problems rapidly.
 * Copyright (C) 1998  Scott Maxwell
 * 
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 *
 * You can reach me at s-max@pacbell.net.
 */


// Weasel.java illustrates the ability of evolutionary techniques to
// solve enormous problems rapidly.  Since most of it is more general
// than the particular problem it's trying to solve, someday I may get
// around to breaking out some of the code for reuse.

// This applet is mostly finished.  Things to do:

// (*) Validate the user's input (to make sure all characters of the
// given phrase are in Weasel's alphabet).

// (*) Ghost controls that aren't usable (Stop vs. the others).

// (*) A better ScoreFn might mitigate the plateau problem.

import java.applet.*;
import java.awt.*;




// The simulation breeds (a derived type of) Critter.
interface Critter
{
    // Return a randomly created Critter.
    abstract public Critter spawn();


    // Breed this critter with the supplied one, returning the
    // offspring as a new Critter.
    abstract public Critter breedWith(Critter c);


    // Randomly mutate this critter.
    abstract public void mutate();


    // Return a short human-readable description of the Critter.
    abstract public String describe();
}




// ScoreFn objects are used to score Critters.  Typically, a ScoreFn
// is a closure that saves some state (such as a perfect Critter),
// which is used to compute the score.
interface ScoreFn
{
    // Return the supplied Critter's score.  Scores are never
    // negative, and the best score is 0 (so the computed score is a
    // measure of "wrongness").
    abstract int score(Critter c);


    // Return the worst possible score a Critter may receive.
    abstract int worst();
}




// Implement a simple progress bar.  This fills left to right and
// prints the filled percentage in the middle of the bar.
class SimpleProgressBar extends Canvas
{
    int numer = 0;		// Numerator of the filled-fraction.
    int denom = 1;		// Denominator of the filled-fraction.


    // Create the progress bar.
public SimpleProgressBar()
    {
	setForeground(Color.blue);
	setBackground(Color.white);
    }


    // Fill n/d of the progress bar.
public void progress(int n, int d)
    {
	numer = n;
	denom = d;

	Graphics g = getGraphics();
	if (g != null)
	    paint(g);
    }


    // Paint callback.
public void paint(Graphics g)
    {
	if (denom == 0)
	    return;

	int w = size().width;
	int h = size().height;

	double fraction = (((double) numer) / denom);
	int intFraction = (int) (fraction * 100.0);
	int mid = (int) (w * fraction);

	// Draw the filled and un-filled parts.
	g.setPaintMode();
	g.fillRect(0, 0, mid, h);
	if (mid != w)
	    g.clearRect(mid + 1, 0, w - mid + 1, h);
	g.drawRect(0, 0, w - 1, h - 1);

	// Draw the text in the middle of the bar (draw it in XOR mode
	// so that we can read it no matter how full the bar is).
	g.setXORMode(getBackground());
	String txt = "" + intFraction + "%";
	FontMetrics fm = g.getFontMetrics();
	g.drawString(txt,
	    w / 2 - fm.stringWidth(txt) / 2,
	    h / 2 + fm.getHeight() / 2);
    }
}




// Handle displaying tracing information.
class Tracer
{
private TextArea tracer;	// The TextArea in which we print the info.
private SimpleProgressBar bar;	// Progress bar we can fill.


    // Ctor.
public Tracer(TextArea t, SimpleProgressBar b)
    {
	tracer = t;
	bar = b;
    }


    // Print this tracing text.
public void trace(String txt)	{  tracer.appendText(txt);  }


    // Clear everything.
public void reset()		{  tracer.setText("");  progress(0, 1);  }


    // Set the progress bar to numer/denom full.
public void progress(int numer, int denom)
    {
	bar.progress(numer, denom);
    }
}




// Display Darwin's periodic Reports.
class Reporter
{
private Tracer tracer;		// Where to display the report text.


    // Ctor.
public Reporter(Tracer t)  {  tracer = t;  }



    // Print a Report in human-readable format.
public void report(Report r)
    {
	progress(r.getNumer(), r.getDenom());
	tracer.trace(
	    "\n" +
	    "Generation        " + r.getGeneration() + "\n" +
	    "Tries <=          " + r.getTries() + "\n" +
	    "Best Critter      " + r.getCritter().describe() + "\n" +
	    "Score (0 is best) " + r.getHighScore() + "\n");
    }


    // Just update the progress bar (make it numer/denom full).
public void progress(int numer, int denom)
    {
	tracer.progress(numer, denom);
    }


    // Print some straight text.
public void printText(String txt)
    {
	tracer.trace(txt);
    }
}




// A progress report periodically issued by Darwin.
class Report
{
private int generation;		// # generations done so far.
private int tries;		// Upper bound on # Critters examined.
private int highScore;		// High score (non-negative, 0 is best).
private Critter critter;	// High-scoring critter.
private int numer;		// Numerator of filled fraction.
private int denom;		// Denominator of filled fraction.


    // Ctor.
public Report(int g, int t, int s, Critter c, int n, int d)
    {
	generation = g;
	tries = t;
	highScore = s;
	critter = c;
	numer = n;
	denom = d;
    }


    // Retrieve various aspects of the report.
public int getGeneration()	{  return generation;  }
public int getTries()		{  return tries;  }
public int getHighScore()	{  return highScore;  }
public Critter getCritter()	{  return critter;  }
public int getNumer()		{  return numer;  }
public int getDenom()		{  return denom;  }
}




// Evolve Critters toward a solution.
class Darwin implements Runnable
{
    Reporter reporter;		// Where to send my periodic progress reports.
    ScoreFn  scoreFn;		// How to score Critters.
    Critter  population[];	// Breeding population of Critters.
    int      nCritters;		// # Critters in population.
    int      updateFreq;	// How frequently to make a progress report.
    Thread   myThread;		// The thread I'm running in.


    // Return the index of a Critter randomly selected from the
    // population.
private int randomCritter()
    {
	return (int) (Math.random() * nCritters);
    }


    // Return the index of a Critter randomly selected from the
    // population, but don't return the supplied index.  This assumes
    // our population size is larger than 1.
private int randomCritterExcept(int not)
    {
	int n = randomCritter();
	while (n == not)
	    n = randomCritter();
	return n;
    }


    // Ctor.
public Darwin(Critter prototype, int n, int uf, ScoreFn f, Reporter r)
    {
	nCritters  = n;
	updateFreq = uf;
	reporter   = r;
	scoreFn    = f;

	// Use our prototype Critter to randomly create a population
	// of Critters.  Since this is often slow, show our progress
	// as we go.
	population = new Critter[nCritters];
	for (int i = 0; i < population.length; ++i)
	{
	    population[i] = prototype.spawn();
	    if ((i % 10) == 0)
		reporter.progress(i, population.length);
	}
	reporter.progress(1, 1);

	myThread = new Thread(this);

	// Since this thread is such a CPU hog, lower its priority.
	// Among other effects, this makes the GUI (specifically, the
	// Stop button) more responsive.  Under Netscape, this
	// generates an exception, but it still lets us get on with
	// life.
//	myThread.setPriority(myThread.getPriority() - 1);
    }


    // Do the breeding.
public void run()
    {
	long start = System.currentTimeMillis();
	int tries = nCritters;	// Upper bound on different # Critters examined.
	int worst = scoreFn.worst();

	int highScorer = 0;	// Index of the high-scoring Critter.
	int highScore = -1;	// Its score (set in the init loop).

	// Get the initial fitnesses of all Critters in the
	// population.  This determines the initial best critter
	// (which could even be a perfect solution).
	for (int i = 0; i < nCritters; ++i)
	{
	    int score = scoreFn.score(population[i]);

	    if ((i == 0) || (score < highScore))
	    {
		highScore = score;
		highScorer = i;
	    }
	}

	// Loop until we find a solution.
	for (int generation = 0; true; ++generation)
	{
	    myThread.yield();	// Allow any other threads to run.

	    // If we've found a solution or it's time to issue a
	    // report, issue a report.
	    if ((highScore == 0) || ((generation % updateFreq) == 0))
		reporter.report(new Report(generation, tries, highScore,
		    population[highScorer], (worst - highScore), worst));

	    if (highScore == 0)
	    {
		long tm = (System.currentTimeMillis() - start) / 1000;
		if (tm != 0)
		    reporter.printText("\n\nChecked " + tries +
			" critters in " + tm +
			" seconds == " + (tries / tm) +
			" tries/sec.\n");
		return;
	    }

	    // Breed the high scorer with some of the other Critters,
	    // then mutate some.
	    int some = nCritters / 8;
	    for (int j = 0; j < some; ++j)
	    {
		int n = randomCritterExcept(highScorer);
		population[n] = population[highScorer].breedWith(population[n]);
		int score = scoreFn.score(population[n]);
		if (score < highScore)
		{
		    highScore = score;
		    highScorer = n;
		}
	    }

	    for (int j = 0; j < some; ++j)
	    {
		// I was using randomCritter() here, but for
		// efficiency I no longer check the fitness of all
		// critters at each iteration -- hence, if the high
		// scorer is mutated, the code won't choose his
		// successor.  Fix ASAP.
		int n = randomCritterExcept(highScorer);
		population[n].mutate();
		int score = scoreFn.score(population[n]);
		if (score < highScore)
		{
		    highScore = score;
		    highScorer = n;
		}
	    }

	    tries += some * 2;
	}
    }


public void stop()
	{
	    // I'd like to suspend()/resume() or wait()/notify() here,
	    // but Netscape just whines about that.  Playing around
	    // with ThreadGroups doesn't seem to make it happy,
	    // either.
	    if (myThread != null)
		myThread.stop();
	}


public void start()
	{
	    if (myThread != null)
		myThread.start();
	}
}




// A particular Critter for the purposes of the Weasel applet.
class WeaselCritter implements Critter
{
private static final String chars =
    "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ 0123456789,.?!'";
private static int nChars = chars.length();
private static char character [] = null;

private String rep;		// This Critter's guess at the solution.


    // Return a randomly generated string of the given length.
private static String randomStringOfLength(int len)
    {
	String s = "";
	for (int i = 0; i < len; ++i)
	    s = s + randomChar();
	return s;
    }


    // Return a character chosen randomly from our alphabet.
private static char randomChar()
    {
	return character[(int) (Math.random() * nChars)];
    }


    // Return the index of a random character position within my
    // guess.
private int randomPos()    {  return (int) (Math.random() * rep.length());  }


    // Return a String that is the result of replacing the indicated
    // substring of s1 with the corresponding substring of s2.  The
    // substring's range is from index start to end, inclusive.
private static String repl(String s1, String s2, int start, int end)
    {
	if (start > end)
	    return repl(s2, s1, end, start);

	String s = "";

	if (start > 0)
	    s = s1.substring(0, start);
	while (start <= end)
	    s = s + s2.charAt(start++);
	if (end < s1.length())
	    s = s + s1.substring(end + 1);

	return s;
    }


    // Initialize the class.
public static void init()
    {
	if (character == null)
	{
	    character = new char[chars.length()];
	    for (int i = 0; i < chars.length(); ++i)
		character[i] = chars.charAt(i);
	}
    }


    // Ctors.
public WeaselCritter(int len)
    {
	init();
	rep = randomStringOfLength(len);
    }

public WeaselCritter(String s)
    {
	init();
	rep = s;
    }


    // Return a randomly generated (Weasel)Critter.
public Critter spawn()
    {
	return new WeaselCritter(randomStringOfLength(rep.length()));
    }


    // Return the result of breeding myself with the supplied
    // (Weasel)Critter.  This is a simple crossover technique.
public Critter breedWith(Critter c_)
    {
	WeaselCritter c = (WeaselCritter) c_;
	return new WeaselCritter(repl(rep, c.rep, randomPos(), randomPos()));
    }


    // Mutate myself.  This simply replaces one randomly chosen
    // character.
public void mutate()
    {
	int pos = randomPos();
	rep = ((pos <= 0)  ?  ""  :  rep.substring(0, pos)) +
	    randomChar() +
	    ((pos >= (rep.length() - 1))  ?  ""  :  rep.substring(pos + 1));
    }


    // Return a short readable self-description.  For this critter,
    // the job is trivial.
public String describe()  {  return rep;  }


    // Return the character at index i in my representation.
public char charAt(int i)  {  return rep.charAt(i);  }
}




// Score WeaselCritters.
class WeaselScoreFn implements ScoreFn
{
    String goal;		// A WeaselCritter matching this string wins.


    // Ctor.
public WeaselScoreFn(String g)
    {
	goal = g;
    }


    // Score the supplied (Weasel)Critter.
public int score(Critter c_)
    {
	WeaselCritter c = (WeaselCritter) c_;

	int wrong = 0;
	int len = goal.length();
	for (int i = 0; i < len; ++i)
	    if (c.charAt(i) != goal.charAt(i))
		++wrong;

	return wrong;
    }


    // Return the worst possible score (all wrong).
public int worst()
    {
	return goal.length();
    }
}




// And now, the Applet itself.
public class Weasel extends Applet
{
private boolean initialized = false;

private TextField		goalTxt;	// Where user types goal text.
private Button			breedBtn;	// Breed button.
private Button			stopBtn;	// Stop button.
private TextArea		tracingTxt;	// Where to print tracing info.
private TextField		nCrittersTxt;	// Where user types # critters.
private Choice			genChc;		// Where user chooses upd8 freq.
private SimpleProgressBar	progBar;	// Applet-wide progress bar.
private Tracer			tracer;		// Manages tracingTxt object.

private Darwin darwin = null;

public static final int wantW = 500;
public static final int wantH = 400;


    // Ctor.
public Weasel()  {}


    // One-time applet initialization.
public void init()
    {
	// I've heard that some browsers may (incorrectly) invoke this
	// method more than once.  So guard against that.
	if (initialized)
	    return;
	initialized = true;

	Label lbl = null;

	// Set up the user interface.  This uses the default
	// FlowLayout, creating a full-width Panel for each row of
	// items.

	// First row.
	int rowHeight = 0;
	Panel p = new Panel();
	p.add(lbl = new Label("Goal Phrase:"));
	rowHeight = Math.max(rowHeight, lbl.size().height);

	goalTxt = new TextField("Methinks it is like a weasel", 32);
	goalTxt.resize(new Dimension(wantW - lbl.size().width,
	    lbl.size().height));
	p.add(goalTxt);
	rowHeight = Math.max(rowHeight, goalTxt.size().height);

	p.resize(new Dimension(wantW, rowHeight));
	add(p);

	// Second row.
	rowHeight = 0;
	p = new Panel();
	p.add(lbl = new Label("Population Size:"));
	rowHeight = Math.max(rowHeight, lbl.size().height);
	p.add(nCrittersTxt = new TextField("1024", 5));
	rowHeight = Math.max(rowHeight, nCrittersTxt.size().height);

	p.add(lbl = new Label("Update Every"));
	rowHeight = Math.max(rowHeight, lbl.size().height);
	genChc = new Choice();
	String choices[] = {
	    "1 Generation",
	    "10 Generations",
	    "25 Generations",
	    "50 Generations",
	    "100 Generations",
	    "250 Generations",
	    "1000 Generations"
	};
	for (int i = 0; i < choices.length; ++i)
	    genChc.addItem(choices[i]);
	genChc.select(1);
	p.add(genChc);
	rowHeight = Math.max(rowHeight, genChc.size().height);

	p.resize(new Dimension(wantW, rowHeight));
	add(p);

	// Third row.
	rowHeight = 0;
	p = new Panel();
	p.add(breedBtn = new Button("Evolve A Solution"));
	rowHeight = Math.max(rowHeight, breedBtn.size().height);

	p.add(stopBtn = new Button("Stop Breeding!"));
	rowHeight = Math.max(rowHeight, stopBtn.size().height);

	p.resize(new Dimension(wantW, rowHeight));
	add(p);

	// Fourth row.
	rowHeight = 0;
	p = new Panel();
	p.add(progBar = new SimpleProgressBar());
	progBar.resize(wantW, 32);
	rowHeight = Math.max(rowHeight, progBar.size().height);

	p.resize(new Dimension(wantW, rowHeight));
	add(p);

	// Fifth row.
	rowHeight = 0;
	p = new Panel();
	p.add(tracingTxt = new TextArea("", 8, 64));
	tracingTxt.setFont(new Font("Courier", Font.PLAIN, 12));
	tracingTxt.setEditable(false);
	rowHeight = Math.max(rowHeight, tracingTxt.size().height);

	p.resize(new Dimension(wantW, rowHeight));
	add(p);

	tracer = new Tracer(tracingTxt, progBar);
    }


    // Wait for the "Breed Solution" button to be clicked.
public boolean action(Event e, Object o)
    {
	if (e.target.equals(breedBtn))
	{
	    tracer.reset();
	    String goal = goalTxt.getText();
	    tracer.trace("Attempting to match `" + goal + "'\n" +
		"(Generating initial population now ....)\n");

	    int n = 0;
	    while (true)
	    {
		n = new Integer(nCrittersTxt.getText()).intValue();
		if (n <= 1)
		    nCrittersTxt.setText("1024");
		else
		    break;
	    }

	    String gTxt = genChc.getSelectedItem();

	    darwin = new Darwin(new WeaselCritter(goal.length()),
		n,
		new Integer(gTxt.substring(0, gTxt.indexOf(' '))).intValue(),
		new WeaselScoreFn(goal),
		new Reporter(tracer));
	    darwin.start();

	    return true;	// Handled it myself.
	}
	else if (e.target.equals(stopBtn))
	{
	    if (darwin == null)
		tracer.trace("Not evolving.\n");
	    else
	    {
		darwin.stop();
		darwin = null;
		tracer.trace("Stopped evolving.\n");
	    }
	}

	return super.action(e, o);
    }


    //
public void stop()
	{
	    if (darwin == null)
		return;		// We weren't doing anything anyway.

	    darwin.stop();
	    darwin = null;
	    tracer.trace("\nThe browser stopped Weasel.\n");
	}

public void start()
	{
	    if (darwin != null)
		darwin.start();
	}

    // In case we're not running in in a Web browser.
public static void main(String args[])
	{
	    WeaselFrame frame = new WeaselFrame(wantW, wantH);
	}
}




// Only used when the Weasel applet is not running in a Web browser.
class WeaselFrame extends Frame
{
public WeaselFrame(int w, int h)
	{
	    super("Weasel");

	    resize(w, h);	// Approximately; will change later.
	    Weasel weasel = new Weasel();
	    //add(weasel, BorderLayout.CENTER);
	    add(weasel);
	    weasel.init();
	    weasel.start();
	    show();
	}


    // Old (Java 1.0-style) event handling.
public boolean handleEvent(Event e, Object arg)
	{
	    if (e.id == Event.WINDOW_DESTROY)
		System.exit(0);
	    return super.handleEvent(e);
	}
}