// File: Lindenmayer.cs
// Created by: Beau Skinner
// Creation date: Nov 19, 2003

using System;
using System.IO;
using System.Collections;

namespace Lindenmayer
{
	/// <summary>
	/// Encapsulates the set of transformation rules for a Lindenmayer grammar.
	/// </summary>
	public class Rules {
		#region Inner Classes
		/// <summary>
		/// An enumerator class for the Rules class.
		/// </summary>
		public class RuleEnumerator {
			#region Constructors
			/// <summary>
			/// Constructor.  Sets index one left of first rule.
			/// </summary>
			/// <param name="rules">Rules object to enumerate.</param>
			public RuleEnumerator(Rules rules) {
				m_rules = rules;
				m_idx = -1;
			}
			#endregion

			#region Properties
			/// <summary>
			/// Accesses the rule in the set corresponding to the current index.
			/// </summary>
			public DictionaryEntry Current {
				get {
					return (DictionaryEntry)m_rules.m_rules[m_idx];
				}
			}
			#endregion

			#region Public Members
			/// <summary>
			/// Moves index to next rule.
			/// </summary>
			/// <returns>False if and only if there are no more rules.</returns>
			public bool MoveNext() {
				m_idx++;
				return(m_idx < m_rules.m_rules.Count);
			}
			#endregion

			#region Fields
			int m_idx;
			Rules m_rules;
			#endregion
		}
		#endregion

		#region Constructors
		/// <summary>
		/// Constructor.  Creates a blank set of rules.
		/// </summary>
		public Rules() {
			m_rules = new ArrayList();
		}
		#endregion

		#region Public Members
		/// <summary>
		/// Adds a rule to the stored set.
		/// </summary>
		/// <param name="key">Left side of rule.</param>
		/// <param name="val">Right side of rule.</param>
		public void Add(string key, string val) {
			m_rules.Add(new DictionaryEntry(key, val));
		}

		/// <summary>
		/// Returns an enumerator for this Rules object.
		/// </summary>
		/// <returns>Enumerator for this Rules object.</returns>
		public RuleEnumerator GetEnumerator() {
			return new RuleEnumerator(this);
		}
		#endregion

		#region Fields
		private ArrayList m_rules;
		#endregion
	}

	/// <summary>
	/// Generates PostScript files that are images of consecutive iterations of
	/// a Lindenmayer fractal described by a given Lindenmayer grammar.
	/// </summary>
	public class Lindenmayer {
		#region Inner Classes
		/// <summary>
		/// Encapsulates a Point as an x and y coordinate.
		/// </summary>
		private class Point {
			#region Constructors
			/// <summary>
			/// Constructor.  Sets Point to (0,0).
			/// </summary>
			public Point() {
				m_x = m_y = 0;
			}

			/// <summary>
			/// Constructor.  Sets Point to given coordinates.
			/// </summary>
			/// <param name="x">x coordinate.</param>
			/// <param name="y">y coordinate.</param>
			public Point(double x, double y) {
				m_x = x;
				m_y = y;
			}
			#endregion

			#region Properties
			/// <summary>
			/// Accesses the x coordinate of the Point.
			/// </summary>
			public double x {
				get {
					return m_x;
				}
				set {
					m_x = value;
				}
			}

			/// <summary>
			/// Accesses the y coordinate of the Point.
			/// </summary>
			public double y {
				get {
					return m_y;
				}
				set {
					m_y = value;
				}
			}
			#endregion

			#region Fields
			double m_x, m_y;
			#endregion
		}
		#endregion

		#region Constructors
		/// <summary>
		/// Constructor.  Sets fractal name and grammar according to given values.
		/// </summary>
		/// <param name="name">Name of fractal (used in naming the PostScript files).</param>
		/// <param name="seed">Initial axiom.</param>
		/// <param name="bearing">Initial heading.</param>
		/// <param name="angle">Rotation unit.</param>
		/// <param name="rules">Set of transformation rules.</param>
		public Lindenmayer(string name, string seed, double bearing, double angle, Rules rules) {
			m_name = name;
			m_movement = seed;
			m_initBearing = bearing % 360;
			m_angle = angle % 360;
			m_rules = rules;
			// Tracks the number of iterations that have been formed.  Used in naming the PostScript files.
			m_iteration = 1;
			// Filename for temporary output.
			m_tempFile = "linden.tmp";
			// Width and height of standard PostScript page in pixels.
			m_pageWidth = 72*8.5;
			m_pageHeight = 72*11;
			Init();
		}
		#endregion

		#region Properties
		/// <summary>
		/// Accesses the name of the fractal.
		/// </summary>
		public string Name {
			get {
				return m_name;
			}
		}
		#endregion

		#region Public Members
		/// <summary>
		/// Applies the transformation rules to the current axiom to produce the axiom for the next
		/// iteration.
		/// </summary>
		public void Iterate() {
			// Loop through each rule and replace occurrences of the left side in the current axiom
			// with the right side.  Parts of the axiom that are between a slash and backslash are
			// not modified, as those are the parts that have already been replaced by another
			// rule.
			foreach (DictionaryEntry rule in m_rules) {
				string key = rule.Key.ToString();
				string val = rule.Value.ToString();
				int fSlash = m_movement.IndexOf('/');
				int bSlash = -1;
				while (fSlash >= 0) {
					Replace(key, val, bSlash+1, fSlash-1);
					bSlash = m_movement.IndexOf('\\', fSlash+1);
					fSlash = m_movement.IndexOf('/', bSlash+1);
				}
				Replace(key, val, bSlash+1, m_movement.Length-1);
			}

			// Remove any slashes and backslashes from the axiom.
			m_movement = m_movement.Replace("/", "").Replace("\\", "");

			m_iteration++;
		}

		/// <summary>
		/// Outputs the current axiom to a PostScript file as a fractal image.
		/// </summary>
		public void Output() {
			Init();
			OpenTempOutput();
			Start();
			
			// moveto the current turtle position to start the image.
			PSGoTo(false);
			
			// Keep track of the total number of linetos and movetos.
			int length = 1;
			
			// Loop through each character in the current axiom string.
			foreach (char c in m_movement) {
				switch (c) {
					// F or G means move forward with pen down.
					case 'F':
					case 'G':
						Move(true);
						length++;
						break;
					// f or g means move forward with pen up.
					case 'f':
					case 'g':
						Move(false);
						length++;
						break;
					// + means rotate one unit counter-clockwise.
					case '+':
						Turn(1);
						break;
					// - means rotate one unit clockwise,
					// or rotate -1 units counter-clockwise.
					case '-':
						Turn(-1);
						break;
					// [ means store the current position.
					case '[':
						SavePosition();
						break;
					// ] means return to the most recently remembered position.
					case ']':
						RestorePosition();
						length++;
						break;
					default:
						break;
				}

				// If the path has exceeded the threshold length, end it and
				// start a new one.
				if (length % m_threshold == 0) {
					Refresh();
					length++;
				}
			}

			End();
			CloseOutput();
			
			// If any movements were made, output them in a PostScript file.
			if (length > 1) {
				OpenOutput();
				WriteBoundaries();
				CopyOutput();
				CloseOutput();
			}
		}
		#endregion

		#region Private Members
		/// <summary>
		/// Inititalizes values to prepare for outputting current axiom as a PostSript image.
		/// </summary>
		private void Init() {
			m_bearing = m_initBearing;
			m_storedPositions = new Stack();
			m_storedBearings = new Stack();
			m_position = new Point();
			m_min = new Point();
			m_max = new Point();

			// Maximum path length (movetos and linetos).
			m_threshold = 1000;
		}

		/// <summary>
		/// Replaces occurrences of a given key in a given substring of the current axiom
		/// with a given value.
		/// </summary>
		/// <remarks>
		/// The value is surrounded by a slash on the left and a backslash on the right, to
		/// indicate that part of the axiom has already been replaced.
		/// </remarks>
		/// <param name="key">Key to replace.</param>
		/// <param name="val">Value to replace key with.</param>
		/// <param name="start">Start index of substring in which to replace occurrences of the key.</param>
		/// <param name="end">End index of substring in which to replace occurrences of the key.</param>
		private void Replace(string key, string val, int start, int end) {
			m_movement = m_movement.Substring(0, start) +
				m_movement.Substring(start, end-start+1).Replace(key, "/" + val + "\\") +
				m_movement.Substring(end+1);
		}
		


		/// <summary>
		/// Opens the temporary file for output.  If a file of the same name exists, it is erased.
		/// </summary>
		private void OpenTempOutput() {
			m_output = new StreamWriter(m_tempFile);
		}

		/// <summary>
		/// Opens and initializes PostScript file for output.  If a file of the same name exists, it is erased.
		/// </summary>
		private void OpenOutput() {
			m_output = new StreamWriter(m_name + m_iteration + ".ps");
			m_output.WriteLine("%!");
			m_output.WriteLine();
		}

		/// <summary>
		/// Copies the contents of the temporary file to the end of the PostScript file and erases
		/// the temporary file.
		/// </summary>
		private void CopyOutput() {
			m_input = new StreamReader(m_tempFile);
			string line;
			while ((line = m_input.ReadLine()) != null) {
				m_output.WriteLine(line);
			}
			m_input.Close();
			File.Delete(m_tempFile);
		}

		/// <summary>
		/// Closes the PostScript file.
		/// </summary>
		private void CloseOutput() {
			m_output.Close();
		}

		/// <summary>
		/// Starts a new PostScript path.
		/// </summary>
		private void Start() {
			m_output.WriteLine("newpath");
		}

		/// <summary>
		/// Ends a PostScript path.
		/// </summary>
		private void End() {
			m_output.WriteLine("stroke");
			m_output.WriteLine("closepath");
		}

		/// <summary>
		/// Ends the current PostScript path and begins a new one at the same
		/// point that the previous path left off.
		/// </summary>
		private void Refresh() {
			End();
			m_output.Flush();
			Start();

			// To start the new path, moveto the current turtle position.
			PSGoTo(false);
		}

		/// <summary>
		/// Writes scale, setlinewidth, and translate commands to the PostScript file
		/// according to the boundaries of the fractal.
		/// </summary>
		private void WriteBoundaries() {
			// According to the maximum x and y coordinates the turtle went to, calculate
			// the width and height of the fractal.  These values are increased slightly
			// to allow a small space between the fractal and the page boundaries.
			double fractalWidth = (m_max.x - m_min.x) * 1.01;
			double fractalHeight = (m_max.y - m_min.y) * 1.01;

			// We scale the maximum amount that will keep the fractal from being too wide
			// or too tall.
			double xscale = m_pageWidth/fractalWidth;
			double yscale = m_pageHeight/fractalHeight;
			double scale = Math.Min(xscale, yscale);

			// We must translate the centre of the fractal to the centre of the page.
			// To do this, we subtract the current location of the fractal's centre from
			// the coordinates of the centre of the page.
			double xcentre = m_pageWidth/2/scale - (m_min.x + m_max.x)/2;
			double ycentre = m_pageHeight/2/scale - (m_min.y + m_max.y)/2;
			
			// Output the appropriate commands to the PostScript file.
			m_output.WriteLine("{0} dup scale", scale);
			m_output.WriteLine("1 {0} div setlinewidth", scale);
			m_output.WriteLine("{0} {1} translate", xcentre, ycentre);
			m_output.WriteLine();
		}

		/// <summary>
		/// Moves the turtle forward one unit and outputs to the PostScript file.
		/// </summary>
		/// <param name="draw">True will cause a line to be drawn.  False will simply move the turtle.</param>
		private void Move(bool draw) {
			UnitForward();
			PSGoTo(draw);
		}

		/// <summary>
		/// Rotates the turtle counter-clockwise by some multiple of the rotation unit.
		/// </summary>
		/// <param name="mult">Multiple of rotation unit by which the turtle is to be rotated.</param>
		private void Turn(int mult) {
			m_bearing = (m_bearing + mult*m_angle) % 360;
		}

		/// <summary>
		/// Add the current turtle position to the top of the Stack of stored positions.
		/// Add the current turtle heading to the top of the Stack of stored headings.
		/// </summary>
		private void SavePosition() {
			Point tempPosition = new Point(m_position.x, m_position.y);
			m_storedPositions.Push(tempPosition);
			m_storedBearings.Push(m_bearing);
		}

		/// <summary>
		/// Remove the first item on the Stack of stored positions and move the turtle to that point.
		/// Remove the first item on the Stack of stored headings and rotate the turtle to that heading.
		/// </summary>
		private void RestorePosition() {
			m_position = (Point)m_storedPositions.Pop();
			m_bearing = (double)m_storedBearings.Pop();
			PSGoTo(false);
		}

		/// <summary>
		/// Outputs a lineto or moveto command to the PostScript file, moving to the current turtle position.
		/// </summary>
		/// <param name="draw">True will output a lineto command.  False will output a moveto command.</param>
		private void PSGoTo(bool draw) {
			string command;
			if (draw) {
				command = "lineto";
			} else {
				command = "moveto";
			}
			m_output.WriteLine("{0} {1} {2}", m_position.x, m_position.y, command);
			UpdateBoundaries();
		}

		/// <summary>
		/// Updates the fractal boundaries according to the boundaries found so far and the current turtle position.
		/// </summary>
		private void UpdateBoundaries() {
			// If the x coordinate is less than the smallest found so far, update the left boundary.
			m_min.x = Math.Min(m_min.x, m_position.x);
			// If the y coordinate is less than the smallest found so far, update the bottom boundary.
			m_min.y = Math.Min(m_min.y, m_position.y);
			// If the x coordinate is more than the largest found so far, update the right boundary.
			m_max.x = Math.Max(m_max.x, m_position.x);
			// If the y coordinate is more than the largest found so far, update the top boundary.
			m_max.y = Math.Max(m_max.y, m_position.y);
		}

		/// <summary>
		/// Moves the turtle to a point one unit forward in the direction of the current heading.
		/// </summary>
		private void UnitForward() {
			// Calculate the change in each coordinate required to move the turtle one unit forward
			// in the direction of its current heading.
			double dy = Math.Sin(ToRadians(m_bearing));
			double dx = Math.Cos(ToRadians(m_bearing));
			
			// Add these to the current position to move the turtle forward one unit.
			m_position.x += dx;
			m_position.y += dy;
		}

		/// <summary>
		/// Converts a given value in degrees into radians.
		/// </summary>
		/// <param name="degrees">Degrees to convert.</param>
		/// <returns>Given degrees converted to radians.</returns>
		private double ToRadians(double degrees) {
			return degrees * Math.PI / 180;
		}
		#endregion

		#region Fields
		private string m_movement, m_name, m_tempFile;
		private double m_bearing, m_initBearing;
		private double m_angle;
		private Rules m_rules;
		private int m_iteration;
		private Stack m_storedPositions, m_storedBearings;
		private Point m_position, m_min, m_max;
		private StreamWriter m_output;
		private StreamReader m_input;
		private int m_threshold;
		private double m_pageWidth, m_pageHeight;
		#endregion
	}
}