import java.net.*;
import java.awt.*;
import java.awt.image.ImageObserver;
import java.awt.event.*;
import java.util.*;
import java.applet.Applet;
import java.io.*;

/** Applet that draws L System curves. It loads a list of Formulas from the file specifed by SRC. 
<p>Programmed by Robert Jessop (rj200@ecs.soton.ac.uk) */
public class DrawCurves extends Applet implements ActionListener, ImageObserver
{
	/** Reads all the data from the file and sets the layout. */
	public void init()
	{
		String input; // String for reading lines of input.
		String name =""; // Name of forumulae being read.
		int angle = 4; // angle of current formulae.
		StringBuffer axiom = new StringBuffer(); // axiom of current forumlae.
		String comments = ""; // Comments in formula file
		int commentIndex = 0; // Variable to simplify processing of comments.
		Vector rules = new Vector(); // Rules of the current forumulae.
		BufferedReader br; // Reader for the formula file.
		InputStreamReader isr; // Stream for reading the file.
	
		showStatus("Loading formulae");
		String url = getParameter("SRC"); // The file containing formulae;
		
		setLayout(new BorderLayout()); //  Set the layout so we can have controls at the right.
		Panel controls = new Panel(); // Container for the controls
		add(controls, BorderLayout.EAST); // Tells the applet to draw the panel everytime it paints.
		controls.setLayout(new BorderLayout()); //  Set the layout so we can have order controls above the list

		Panel controls2 = new Panel(); // Container for Order control
		controls.add(controls2, BorderLayout.NORTH);

		controls2.add(new Label("Order:")); // Add a label for the text field
  	   orderField = new TextField("4"); // Create a text box to input the order of the curve
		controls2.add(orderField); // Add the text box the the controls panel
		orderField.addActionListener(this); // Make the applet listen for changes.

		// Find the number of rows we can fit
		maxY = getSize().height;
		int rows = (maxY - 16)/16;
		
		curveList = new java.awt.List(rows); // Full name to aviod confusion with java.util.List
		controls.add(curveList, BorderLayout.SOUTH); // Add the list box to the panel
		curveList.addActionListener(this); // Make the applet listen for changes.

		try
		{
			// Open the URL and create an input stream.
			isr = new InputStreamReader((new URL(url)).openStream());
		}
		catch (Exception e) // If there is a problem opening the url display error message.
		{
			showStatus("Unable to open Formula File "+url);		
			System.err.println("Unable to open Formula File "+url);
			return;
		}

		br = new BufferedReader(isr); // Reader to read from is.
		curves = new Vector(); // initialize vector for the LSystems.

		/* Now we move through the formulae file reading entries. Entries will look something like this:
		Koch4 { ; Adrian Mariano
		; from The Fractal Geometry of Nature by Mandelbrot
		  angle 12
		  axiom f++++f++++f
		  f=+f--f++f-
		  }
		*/
		try
		{
			while(br.ready())
			{
				input = br.readLine(); // Read next line from the InputStream
				if(input == null) continue; // If there is no input then assume its the end.

				System.err.println(input);
				commentIndex = input.indexOf(';'); // Find the position where comments start
												
				if(input.indexOf('{') >= 0) // New formulae
				{
					rules = new Vector();
					comments = "";
					name = (input.substring(0,input.indexOf('{'))).trim();
				}

				if(commentIndex >= 0) // If there are comments
				{
					comments = comments.concat(input.substring(commentIndex+1)); // Build up comments string
					input = input.substring(0,commentIndex); // then forget them. 
				}

				input = input.trim(); // get rid of whitespace

				if(input.length() > 4)
				{
					if(input.substring(0,5).equalsIgnoreCase("angle")) // Set the angle
					{
						angle = Integer.parseInt(input.substring(6));
					}
	
					if(input.substring(0,5).equalsIgnoreCase(new String("axiom"))) // Set the axiom
					{
						axiom = new StringBuffer(input.substring(6).toLowerCase());
					}
				}
				if(input.indexOf('=') >= 0) // Add a rule string
				{
					rules.addElement(new Rule(input));	
				}

				if(input.indexOf('}') >= 0) // End of formulae
				{
					if(!name.equalsIgnoreCase("comment"))
					{
						curves.addElement(new LSystem(name, angle, axiom, rules, comments));
						curveList.add(name);
					}
				}

			}
		}
		catch (IOException e) // If theres an error assume its the end of the loop.
		{
			System.err.println(e.getMessage());
		}
		
		// Find the size of the view
		maxX = getSize().width - controls.getPreferredSize().width;

		// select the 1st item
		curveList.select(0);

		// Create drawing buffer
		buffer = createImage(maxX,maxY);
	}

	/** If a new order is selected or an item is double clicked on then draw the new curve. */
	public void actionPerformed(ActionEvent event) // Change of curve detected
	{
		// Draw the curve.
		repaint();
	}

	/** Called when the screen is drawn. */
	public void paint(Graphics g) // Called when the applet is drawn
	{
		// Calculate new image only if necessary
		if(lastCurve != curveList.getSelectedIndex() || lastOrder != Integer.parseInt(orderField.getText()))		
		{
			// Set values of that curve
			lastCurve = curveList.getSelectedIndex();
			lastOrder = Integer.parseInt(orderField.getText());

			// Get a drawing surface for the buffer
			Graphics g2 = buffer.getGraphics();
			// Set the colour of the curve
			g2.setColor(Color.black);
			// Say what we are doing in the status bar
			showStatus("(Calculating) " + ((LSystem)curves.elementAt(curveList.getSelectedIndex())).getComments());
			// Draw the curve
			((LSystem)curves.elementAt(lastCurve)).draw(g2, maxX, maxY, lastOrder);	
			// Say that we have finished
			showStatus("(Done) " + ((LSystem)curves.elementAt(curveList.getSelectedIndex())).getComments());
		}

		// Draw the buffer to the screen
		g.drawImage(buffer, 0,0, maxX, maxY, this); // Draw the buffer to the screen
	}

	/** Return information about supported parameters. */
	public String[][] getParameterInfo()
	{
		String pinfo[][] = {
		{"SRC",   "url",     "The file containing the LSystems to draw"}
		};
		return pinfo;
	}

	/** Drawing area size. */
	private int maxX;
	/** Drawing area size. */
	private int maxY; 
	/** Text field for the order of the curve. */
	private TextField orderField; 
	/** Graphical List of possible L Systems to draw. */
	private java.awt.List curveList; 
	/** The L Systems. */
	private Vector curves; 
	/** Order of last curve drawn. */
	private int lastOrder; 
	/** Last curve drawn. */
	private int lastCurve;
   /** Buffer for fast displaying of graphics. */
	private Image buffer; 
}

/** Simple container for a rule in a formula. 
<p>Programmed by Robert Jessop (rj200@ecs.soton.ac.uk) */
class Rule
{
	/** Creates a rule from a string by splitting at the = sign. */
	public Rule(String rulestring)
	{
		name = Character.toLowerCase(rulestring.charAt(0));
		commands = new StringBuffer(rulestring.substring(rulestring.indexOf('=')+1).toLowerCase());
	}

	/** The name of the rule. */	
	public char name; // names are single characters.
	/** The list of commands in the rule. */
	public StringBuffer commands;
}

/** A Fractal Curve. Contains all the information necessary to draw it. 
<p>Programmed by Robert Jessop (rj200@ecs.soton.ac.uk) */
class LSystem
{
	/** Initializes all the basic values. */
	public LSystem(String name, int angle, StringBuffer axiom, Vector rules, String comments)
	{
		this.name = name;
		this.angle = angle;
		this.axiom = axiom;
		this.comments = comments;
		lastOrder = Integer.MAX_VALUE; // Not true but when we first draw it will make it start from scratch.

		Rule thisRule; 
		Rule lastRule;
		// Check for multi-line rules.
		if(rules.size() > 1) // If there is more than one rule.
		{
			for(int i = 0; i < rules.size() - 1; ) // Loop through rules
			{
				lastRule = (Rule)rules.elementAt(i++);
				thisRule = (Rule)rules.elementAt(i);
				if(thisRule.name == lastRule.name) // If they have the same name then merge them into 1 rule.
				{
					lastRule.commands.append(thisRule.commands);
					rules.removeElementAt(i);
				}
			}
		}
		this.rules = rules;
		
	}

	/** Draws the curve to the specified order. */
	public void draw(Graphics g, int width, int height, int order)
	{
		// Clear graphics
		g.clearRect(0,0,width,height);
	
		int i; // Loop counter.

		// Make sin and cos tables to save calculation time.
		sin = new double[angle];
		cos = new double[angle];
		for(i = 0; i < angle; i++)
		{
			sin[i] = Math.sin((double)(i*2)*Math.PI/(double)angle);
			cos[i] = Math.cos((double)(i*2)*Math.PI/(double)angle);
		}
		
		System.err.println();
		long st = System.currentTimeMillis(); // Time info to help test optimization.
	
		// Now we will generate a string of drawing instructions by combining the axiom and rules.
		
		if(order != lastOrder) // If the order has changed then calculate the string again.
		{	
			result = new StringBuffer();
			if(rules.size() == 1) // If there is only one rule then use the fast version
				simpleExpand(axiom, order); // The quicker recurive function for simple curves.
			else
				expand(axiom, order); // Start recursive function to generate the result.
		}
		// if order = lastOrder then do nothing - we already have the right instructions to draw it.
		
		System.err.println(st-System.currentTimeMillis()); // Time info to help optimization
		// Now find the area taken by this curve.
		Position pen = new Position(0,0,0,10);
		int left = angle - 1; // increment of a when turning left
		int right = 1; // increment of a when turning right
		int tempInt; // needed for swapping two int values
		double hx = 1;
		double hy = 1;  // Highest and lowest x and y values
		double lx = -1;
		double ly = -1; 
		Stack stack = new Stack(); // Stored pen positions.
		int numstart, inv, q; // Variables used when changing size (@ command)
		double negflag, sizeMult; // Calculated and use in the @ routine.

		for(i=0; i < result.length(); i++)
		{
			switch(result.charAt(i))
 		   {
				case 'g':
				case 'm':
				case 'f':
				case 'd':
					// Move forward
					pen.x += pen.step*cos[pen.a];
					pen.y += pen.step*sin[pen.a];
					// update the bounds of the area
					if(pen.x > hx) hx = pen.x;
					if(pen.y > hy) hy = pen.y;
					if(pen.x < lx) lx = pen.x;
					if(pen.y < ly) ly = pen.y;
					break;				
				case '+':
					// Increase angle (left turn)
					pen.a = (pen.a + left) % angle;
					break;
				case '-':
					// decrease angle (right turn)
					pen.a = (pen.a + right) % angle;
					break;
				case '|':
					// U-turn
					pen.a = (pen.a + (angle/2)) % angle;
					break;
				case '!':
					// Swap the meanings of left and right
					tempInt = left;
					left = right;
					right = tempInt;
					break;
				case '[':
					// Save the pen position. This is used to make trees where one branch is drawn
					// and then the pen jumps back to draw another branch.
					stack.push(pen.clone());
					break;
				case ']':
					// Return to the last saved position and forget it.
					pen = (Position)stack.pop();
					break;
				case '@':
					//Change length of lines
					inv = q = numstart = 0; // reset variables
					negflag = 1;
					while(++i < result.length()) // Move along string noting special characters
					{
						if(result.charAt(i) == 'i') inv = i; // Set inverse flag.
						if(result.charAt(i) == 'q') q = i; // Set square root flag.
						if(result.charAt(i) == '-')
						{
							negflag = -1; // note minus sign. 
							numstart = i; // This means the start of the number.
							break;
						}
						if(result.charAt(i) == '.' || Character.isDigit(result.charAt(i)))
						{
							numstart = i; // Note the number has started
							break;
						}						
					}
					while(++i < result.length())
					{
						if(!(result.charAt(i) == '.') && !(Character.isDigit(result.charAt(i)))) break;
					}
					sizeMult = (new Double(result.toString().substring(numstart,i))).doubleValue();
					if(inv < q) // Adjust if there were i,q, or - characters. Order of i and q matters.
					{
						if(q > 0) sizeMult = Math.sqrt(sizeMult);
						if(inv > 0) sizeMult = 1/sizeMult;
					}
					else
					{
						if(inv > 0) sizeMult = 1/sizeMult;
						if(q > 0) sizeMult = Math.sqrt(sizeMult);
					}
					pen.step *= sizeMult * negflag;
					i--;
					break;
				default:
					// ignore everything else
					break;
			}
		}

		System.err.println(st-System.currentTimeMillis()); // Time info to help optimization
		// now draw it
		// Work out where to start on the screen
		pen.x = (-lx*(double)width)/((hx-lx));
		pen.y = (-ly*(double)height)/((hy-ly));
		double x; // Temp position store for line drawing
		double y;
		// and the scale
		pen.step = (double)width/(hx-lx);
		if((double)height/(hy-ly) < pen.step)
			pen.step = (double)height/(hy-ly);
		pen.step *= 9.9;
		pen.a = 0; // current angle
		left = angle - 1; // increment of a when turning left
		right = 1; // increment of a when turning right

		for(i=0; i < result.length(); i++)
		{
			switch(result.charAt(i))
 		   {
				case 'f':
				case 'd':
					// Move forward
					x = pen.x + pen.step*cos[pen.a];
					y = pen.y + pen.step*sin[pen.a];
					// Draw line
					g.drawLine((int)pen.x, (int)pen.y, (int)x, (int)y);
					// update position
					pen.x = x;
					pen.y = y;
					break;
				case 'g':
				case 'm':
					// Move forward
					pen.x += pen.step*cos[pen.a];
					pen.y += pen.step*sin[pen.a];
					break;				
				case '+':
					// Increase angle (left turn)
					pen.a = (pen.a + left) % angle;
					break;
				case '-':
					// decrease angle (right turn)
					pen.a = (pen.a + right) % angle;
					break;
				case '|':
					// U-turn
					pen.a = (pen.a + (angle/2)) % angle;
					break;
				case '!':
					// Swap the meanings of left and right
					tempInt = left;
					left = right;
					right = tempInt;
					break;
				case '[':
					// Save the pen position. This is used to make trees where one branch is drawn
					// and then the pen jumps back to draw another branch.
					stack.push(pen.clone());
					break;
				case ']':
					// Return to the last saved position and forget it.
					pen = (Position)stack.pop();
					break;
				case '@':
					//Change length of lines
					inv = q = numstart = 0; // reset variables
					negflag = 1;
					while(++i < result.length()) // Move along string noting special characters
					{
						if(result.charAt(i) == 'i') inv = i; // Set inverse flag.
						if(result.charAt(i) == 'q') q = i; // Set square root flag.
						if(result.charAt(i) == '-')
						{
							negflag = -1; // note minus sign. 
							numstart = i; // This means the start of the number.
							break;
						}
						if(result.charAt(i) == '.' || Character.isDigit(result.charAt(i)))
						{
							numstart = i; // Note the number has started
							break;
						}						
					}
					while(++i < result.length())
					{
						if(!(result.charAt(i) == '.') && !(Character.isDigit(result.charAt(i)))) break;
					}
					sizeMult = (new Double(result.toString().substring(numstart,i))).doubleValue();
					if(inv < q) // Adjust if there were i,q, or - characters. Order of i and q matters.
					{
						if(q > 0) sizeMult = Math.sqrt(sizeMult);
						if(inv > 0) sizeMult = 1/sizeMult;
					}
					else
					{
						if(inv > 0) sizeMult = 1/sizeMult;
						if(q > 0) sizeMult = Math.sqrt(sizeMult);
					}
					pen.step *= sizeMult * negflag;
					i--;
					break;
				default:
					// ignore everything else
					break;
			}
		}
		System.err.println(st-System.currentTimeMillis() ); // Time info to help optimization
	}

	/** Recursive method for expanding a rulestring to an order */
	private void expand(StringBuffer commands, int order)
	{
		if(order == 0) // If order is zero add the commands (no expansion).
		{
			result.append(commands);
			return;
		}

		// Most recurive algorithms have a return value. But if this one returned strings
		// there would be many very large objects created temporarily. To avoid this, this
 	   // algorithm produces commands in the correct order and so can just append them to
		// a class StringBuffer, so theres no need for on in each activation record.
		// 
		// Not returning a string speeds things up by several orders of magnitude.

		int j; // Loop counter for checking all the rules.
		Rule thisRule; // Currently worked on Rule;
		
		for(int k = 0; k < commands.length(); k++) // evaluate every character in commands
		{
			if(Character.isLetter(commands.charAt(k))) // If character is found then...
			{
				j = 0;
				while(j < rules.size()) // Loop through the rules...
				{
					thisRule = (Rule)rules.elementAt(j++);
					if(commands.charAt(k) == thisRule.name) // until we've found the one refered to by charAt(k)
					{						
						// Instead of adding the letter we add that rule's expansion, order - 1
						expand(thisRule.commands, order - 1); // Recursive call
						j = 0;
						break;
					}
				}
				if(j == rules.size()) // If no rule for this letter wasn't found then leave the character in.
				{
					result.append(commands.charAt(k));
				}
			}
			else // If character is anything else then add it to the string.
			{
				result.append(commands.charAt(k));
			}
		}
		return;
	}

	/** Simple recursive method for expanding a rulestring to an order when there is only 1 rule. 
	Includes a method to speed it up by remembering expansion and copying, instead of repeating. */
	private void simpleExpand(StringBuffer commands, int order) // Quick version for curves with 1 rule
	{
		if(order == 0) // If order is zero add the commands (no expansion).
		{
			result.append(commands);
			return;
		}
		int start = 0; // Vars used for quick expansion of terms. Once the 
		int end = 0; // rule is expanded its location in the string is remembered so it can be copied.

		for(int k = 0; k < commands.length(); k++) // evaluate every character in commands
		{
			if(commands.charAt(k) == ((Rule)rules.elementAt(0)).name) // If character is found then...
			{
				// Instead of adding the letter we add that rule's expansion, order - 1
				if(end == 0)
				{
					start = result.length();
					simpleExpand(((Rule)rules.elementAt(0)).commands, order - 1); // Recursive call
					end = result.length();
				}
				else // we have expanded this before so just copy it.
				{
					result.append(result.toString().substring(start,end));
				}
			}
			else // If character is anything else then add it to the string.
			{
				result.append(commands.charAt(k));
			}
		}
		return;
	}

	/** Access function for the curve's name. */
	public String getName()
	{
		return name;
	}

	/** Returns the comments about this curve. */
	public String getComments()
	{
		return comments;
	}

	/** Name of forumulae. */
	private String name; 
	/** Angle as a fraction of 360 degrees. The curve will only use multiples of this angle and we can
	use this to speed up drawing by pre-calculating all the necessary sin and cos values. */
	private int angle; 
	/** String that starts everything. */
	private StringBuffer axiom; 
	/** Rules of the current forumulae. */
	private Vector rules; 
	/** Comments describing this curve. */
	private String comments; 
	/** Look up table for the sin values we are likely to use many times. */
	private static double[] sin; // Make look up tables for trig functions to speed calculation.
	/** Look up table for the cos values we are likely to use many times. */
	private static double[] cos; // static because only one instance uses them at a time (save memory).
	/** Result of operations - instructions to draw. */
	private StringBuffer result; 
	/** Store of previous order drawn, used to speed up drawing of subsequent higher order images. */
	private int lastOrder;
}

/** Contains co-ordinates, line length and direction. 
<p>Programmed by Robert Jessop (rj200@ecs.soton.ac.uk) */
class Position implements Cloneable
{
	/** Creates a new Position. */
	public Position(double x, double y, int a, double step)
	{
		this.x = x;
		this.y = y;
		this.a = a;
		this.step = step;
	}
	
	/** Creates a copy of the current Position */
	public Object clone()
	{
		return (new Position(x,y,a,step));
	}

	/** X co-ordinate. */
	public double x; 
	/** Y co-ordinate. */
	public double y; 
	/** Angle as a fraction of 360 degrees. */
	public int a; 
	/** Line length. */
	public double step; 
}

		/* Original Drawing Algorithm is slow so I wrote a better one. It also needed rule commands to be
		upper case and rule names to be lower case. The new recursive version is several times faster,
		mostly because symbols are found in the correct order and appended, where as here many strings 
		are generated and inserted into the main string and the replace method is slower than append.

		Here is the original:

		StringBuffer result = new StringBuffer(axiom); // Result of operations - instructions to draw.

		// iterate order times.
		for(i=0;i < order; i++)
		{
			// Now replace characters with appropriate command strings.
			// Search for every instance of each rule string
			for (j = 0; j < rules.size() ; j++) 
			{
				thisRule = (Rule)rules.elementAt(j);

				// Now move through result looking for instances of thisRule
				for(k = 0; k < result.length(); k++)
				{
					if(result.charAt(k) == thisRule.name.charAt(0)) // If first character found and...
					{
						// if its length 1 or the second character is found then...
						if(thisRule.name.length() == 1 || result.charAt(k+1) == thisRule.name.charAt(1))
						{
							// insert the commands. 
							result.replace(k,k+thisRule.name.length(),thisRule.commands);
							k += thisRule.commands.length();
							k -= thisRule.name.length();
						}
					}
				}
			}			
			result = new StringBuffer(result.toString().toLowerCase());
		}
		*/