//package kcdc.applets.genart;

import java.awt.*;  // needed for color/image defs
import java.util.*; // needed for collections

public class QuaternionOperatorTree implements Cloneable
{
	// PUBLIC CONSTANTS //////////////////////////////////////////////////////////
	
	public final static QuaternionOperator[] quaternion_operators =
	{
		new QuaternionOperator.qplus(),
		new QuaternionOperator.qsub(),
		new QuaternionOperator.qmult(),
		new QuaternionOperator.qinv(),
		new QuaternionOperator.qdiv(),
		new QuaternionOperator.qconj(),
		new QuaternionOperator.qaut1(),
		new QuaternionOperator.qaut2(),
		new QuaternionOperator.qexp(),
		new QuaternionOperator.qfloor(),
		new QuaternionOperator.qmod(),
		new QuaternionOperator.qnorm(),
		new QuaternionOperator.qnormp(),
		new QuaternionOperator.qorth1(),
		new QuaternionOperator.qorth2(),
		new QuaternionOperator.qc1(),
		new QuaternionOperator.qc2(),
		new QuaternionOperator.qc3(),
		new QuaternionOperator.qc4(),
		new QuaternionOperator.qc5(),
		new QuaternionOperator.qcx(),
		new QuaternionOperator.qcy(),
		new QuaternionOperator.qcx1(),
		new QuaternionOperator.qcy1(),
		new QuaternionOperator.qcxy(),
		new QuaternionOperator.qcxy2(),
		new QuaternionOperator.qisin(),
		new QuaternionOperator.qilog(),
		new QuaternionOperator.qiexp(),
		new QuaternionOperator.qimin(),
		new QuaternionOperator.qimax(),
		new QuaternionOperator.qrl(),
		new QuaternionOperator.qrr()
	};

	public final static QuaternionOperator DEFAULT_OPERATOR = new QuaternionOperator.qcxy();

	// PUBLIC INSTANCE FIELDS ////////////////////////////////////////////////////
	
	// tree-node variables

	public QuaternionOperator op = null;
	public QuaternionOperatorTree l = null;
	public QuaternionOperatorTree r = null;
	public QuaternionOperatorTree parent = null;
	public transient Quaternion vl = null;
	public transient Quaternion vr = null;
	public transient Quaternion v = null;

	public Vector compiled_tree = null;

	public boolean constant = false;

	// PUBLIC INSTANCE ACCESS METHODS ////////////////////////////////////////////

	public boolean isConstant()
	{ return constant; }

	private void setConstant(boolean new_constant)
	{ this.constant = new_constant; }

	// PUBLIC INSTANCE CONSTRUCTORS //////////////////////////////////////////////

	/** Default constructor. */
	QuaternionOperatorTree()
	{
		v = new Quaternion();
	}

	/** Construct new tree from formatted string. */
	QuaternionOperatorTree(String s)
	{
		v = new Quaternion();
		parse(s, 0);
		// printtree();
	}
	
	// JM: random tree- nast probability model (not much care)
	// JM: or go to arcive
	/** Construct random tree. */
	QuaternionOperatorTree(int l)
	{
		v = new Quaternion();
		if (Math.random() < 0.5)
			this.r_rantree(l, null);
		else
			parse(FormulaArchive.getRandomFormula(), 0);
	}

	/** Clone this tree. Recursively clone this tree and all subtrees. */
	public Object clone()
	{
		QuaternionOperatorTree clone = new QuaternionOperatorTree();
		clone.parent = this.parent;
		clone.op = this.op;
		if (this.l != null) clone.l = (QuaternionOperatorTree) this.l.clone();
		if (this.r != null) clone.r = (QuaternionOperatorTree) this.r.clone();
		return clone;
	}

	// JM: compile the tree to go (sets constants etc)
	public void compile()
	{
		if (compiled_tree == null)
			compiled_tree = new Vector();
		else
			compiled_tree.removeAllElements();

		this.compileTree(compiled_tree);
		this.preevaluteTree();
	}

	// JM: flatten recursive traversal of tree- pre-order traversal
	// JM: as a side-effect set constants in tree
	// JM: these constants are not re-evaluated, could eliminate
	// JM: common sub-expressions also, but I don't know if we
	// JM: have a lot of these.
	private void compileTree(Vector compiled_tree)
	{
		// Halt if there is no root operator, or this tree has a constant value
		if ((this.op == null) || (this.isConstant())) return;
		// If there is at least one subtree and it is not constant pre-dispatch left subtree
		if (this.op.getDegree() > 0)
		{
			if (!this.l.isConstant())
				this.l.compileTree(compiled_tree);
			// If there are two subtrees and it is not constant pre-dispatch right subtree
			if (this.op.getDegree() > 1)
			{
				if (!this.r.isConstant())
					this.r.compileTree(compiled_tree);
			}
		}
		// Add this to the flattened tree
		compiled_tree.addElement(this);
	}

	// JM: run through tree, evaluate at 0,0 to set constants
	// JM: and mark constant sub-trees, also set left/right 
	// JM: quaterinon links
	void preevaluteTree()
	{
		// Get the root operator at this tree node
		vl = null;
		vr = null;
		this.setConstant(true);

		// If there is no root operator then return
		// NOTE: Should this actually throw an exception?
		if (this.op == null) return;

		// If this tree has at least one subtree
		if (this.op.getDegree() > 0)
		{
			// pre-evaluate left tree
			this.l.preevaluteTree();
			// save a pointer to left tree value
			vl = this.l.v;
			// if the left tree is not a constant then neither is this
			if (!this.l.isConstant())
				this.setConstant(false);

			// If this tree has two subtrees			
			if (this.op.getDegree() > 1)
			{
				// pre-evaluate right tree
				this.r.preevaluteTree();
				// save a pointer to right tree value
				vr = this.r.v;
				// if the right tree is not a constant then neither is this
				if (!this.r.isConstant())
					this.setConstant(false);
			}
		}
		else
		{
			// if the operator is a constant then whole tree is constant
			if (!this.op.isConstant())
				this.setConstant(false);
		}

		// JM: evaluate the whole tree at 0,0 as a side-effect
		// RS: Why?
		this.op.operate(this.v, this.vl, this.vr, 0.0, 0.0);
	}

	public Quaternion evaluate(double x, double y)
	{
		if (compiled_tree.isEmpty()) compile();

		if (!compiled_tree.isEmpty())
		{
			for (Enumeration e = compiled_tree.elements(); e.hasMoreElements(); )
			{
				QuaternionOperatorTree tree = (QuaternionOperatorTree) e.nextElement();
				tree.op.operate(tree.v, tree.vl, tree.vr, x, y);
			}

			return this.v;
		}

		return null;
	}

	// JM: insert a null tok if not found, return degree
	// JM: convert + to _ in tokens of length > 1
	void findtok(String si)
	{
		int f;
		String s;

		if (si.length()>1)
			s = si.replace('+', '_');
		else
			s = si;

		f = -1;
		for (int i = 0; (f < 0) && (i < quaternion_operators.length); ++i)
		if (s.equals(quaternion_operators[i].getName()))
			f = i;

		if (f >= 0)
			// System.out.println("find \"" + s + "\" found \"" + quaternion_operators[f].getName() + "\"");
			this.op = quaternion_operators[f];
		else
			// System.out.println("find \"" + s + "\" missed");
			this.op = DEFAULT_OPERATOR;
	}

	// JM: attach first token to this node and recurse
	int parse(String s, int offset)
	{
		int a,b;

		// JM: some safe defaults
		this.l = null;
		this.r = null;
		this.setConstant(false);
		this.op = DEFAULT_OPERATOR;

		if ((s == null) || (s.length() < 1)) return offset;

		a = offset;

		// JM: skip whitespace
		while(a < s.length())
		{
			char ch = s.charAt(a);
			if ((Character.isWhitespace(ch))||(ch=='(')||(ch==')'))
				++a;
			else
				break;
		}

		b = a;

		if (a < s.length())
		{
			b = a+1;
			while (b < s.length())
			{
				char ch = s.charAt(b);
				if ((Character.isWhitespace(ch))||(ch=='(')||(ch==')'))
					break;
				else
					++b;
			}
		}

		String t = s.substring(a,b);
		this.findtok(t);

		if ((this.op != null)&&(this.op.getDegree() > 0))
		{
			this.l = new QuaternionOperatorTree();
			this.l.parent = this;
			b = this.l.parse(s, b);

			if (this.op.getDegree() > 1)
			{
				this.r = new QuaternionOperatorTree();
				this.r.parent = this;
				b = this.r.parse(s, b);
			}
		}

		return b;
	}

	// JM: print tree, prints to stdout
	public void printtree()
	{
		String s = toString();
		System.out.println(s);
	}

	// JM: tree to string, needs final println() after done
	public String toString()
	{
		QuaternionOperator q = null;

		if (this != null)
			q = this.op;

		if (q == null)
		{
			if (this == null)
				return "NULL";
			else
				return "null";
		}
		else
		{
			if (q.getDegree() == 0)
				return q.getName();
			else if (q.getDegree() == 1)
			{
				String nl;
				if (this.l==null)
					nl = "NULL";
				else
					nl = this.l.toString();

				return "( " + q.getName() + " " + nl + " )";
			}
			else
			{
				String nl;
				if (this.l==null)
					nl = "NULL";
				else
					nl = this.l.toString();

				String nr;
				if (this.r==null)
					nr = "NULL";
				else
					nr = this.r.toString();

				return "( " + q.getName() + " " + nl + " " + nr + " )";
			}
		}
	}

	// JM: side effect variable nodes() is allowed to set
	static QuaternionOperatorTree lastmatch = null;

	// JM: count non-null nodes in tree, inorder traversal made obvious
	// JM: also can pick up a matching node (count starts at 0)
	// JM: allowed to alter lastmatch variable
	// JM: call with nodes(0, target)
	public int nodes(int start, int target)
	{
		QuaternionOperator q = this.op;
		if (q == null)
			return start;

		int d = q.getDegree();
		if (d > 0)
			start = this.l.nodes(start,target);

		if (start == target)
			// JM: found matching node
			lastmatch = this;

		start += 1; // JM: self
		if (d > 1)
			start = this.r.nodes(start,target);

		return start;
	}

	// JM: get a random op of given degree, -1 means any degree
	// JM: fix: make a lookup
	static QuaternionOperator randop(int d) 
	{
		int i, n, k;
		
		if (d < 0)
		{
			n = quaternion_operators.length;
			k = (int)(Math.random() * n);
			return quaternion_operators[k];
		}
		else
		{
			// JM: Count number of operators of requested degree
			n = 0;
			for (i = 0; i < quaternion_operators.length; ++i)
				if (quaternion_operators[i].getDegree() == d) ++n;

			k = (int)(Math.random() * n);
			for (i = 0; (k >= 0) && (i < quaternion_operators.length); ++i)
			{
				if (quaternion_operators[i].getDegree()==d)
				{
					if (k==0)
						return quaternion_operators[i];
					--k;
				}
			}
		}

		return null; 
	}

	public void mutate(double mutation_rate)
	{
		if (op == null) return;
		
		if (Math.random() < mutation_rate)
			op = randop(op.getDegree());

		if (op.getDegree() > 0)
			l.mutate(mutation_rate);
		if (op.getDegree() > 1)
			r.mutate(mutation_rate);
	}

	public void mutate()
	{
		// double mutation_rate = 2.0 / nodes(0, -1);
		// mutate(mutation_rate);

		// JM: mutation
		int size = nodes(0,-1);
		int rnd = (int)(Math.random() * size);
		nodes(0, rnd);
		QuaternionOperatorTree qtree = lastmatch;
		qtree.op = randop(qtree.op.getDegree());
	}

	// JM: create a new tree
	// JM: fix: switch from Math.random()
	public QuaternionOperatorTree breed(QuaternionOperatorTree t)
	{
		QuaternionOperatorTree r = null;
		QuaternionOperatorTree t2 = null;

		// JM: maybe whole new tree
		//if (Math.random() < 0.3)
		//	return new QuaternionOperatorTree(8);

		///System.out.println("// formula source = crossover");

		if (Math.random() < 0.5)
		{
			r = (QuaternionOperatorTree) this.clone();
			t2 = t;
		}
		else
		{
			r = (QuaternionOperatorTree) t.clone();
			t2 = this;
		}

		int s1 = r.nodes(0,-1);
		int r1 = (int)(Math.random()*s1);
		r.nodes(0,r1);
		QuaternionOperatorTree q1 = r.lastmatch;

		int s2 = t2.nodes(0,-1);
		int r2 = (int)(Math.random()*s2);
		t2.nodes(0,r2);
		QuaternionOperatorTree q2 = t2.lastmatch;

		// JM: do the graft
		boolean isleft = true;
		QuaternionOperatorTree par = q1.parent;
		QuaternionOperatorTree st = (QuaternionOperatorTree)q2.clone();
		if (par!=null)
		{
			if (par.l==q1)
			{
				par.l = null;
				isleft = true;
			}
			else
			{
				par.r = null;
				isleft = false;
			}
		}
		// System.out.println();
		// System.out.println("host");
		// r.printtree();
		// System.out.println("donation");
		// st.printtree();

		if (par!=null)
		{
			if (isleft)
				par.l = st;
			else
				par.r = st;
		}
		st.parent = par;

		// System.out.println("result");
		// r.printtree();

		r.mutate();

		return r;
	}

	// JM: breed a tree
	public static QuaternionOperatorTree sbreed(String s1, String s2)
	{
		QuaternionOperatorTree t1 = new QuaternionOperatorTree(s1);
		QuaternionOperatorTree t2 = new QuaternionOperatorTree(s2);
		QuaternionOperatorTree t3 = t1.breed(t2);
		return t3;
	}

	void r_rantree(int l, QuaternionOperatorTree p)
	{
		this.parent = p;
		if (l <= 0)
			// JM: terminate tree
			this.op = randop(0);
		else
		{
			// JM: pick degree of node, prefer degree 2
			int d = (int)(Math.random() * 5);
			if (d > 2)
				d = 2;
			this.op = randop(d);
		}

		if (this.op.getDegree()>0)
		{
			this.l = new QuaternionOperatorTree();
			this.l.r_rantree(l-1,this);
			if (this.op.getDegree()>1)
			{
				this.r = new QuaternionOperatorTree();
				this.r.r_rantree(l-1,this);
			}
		}
	}

	static final public void main(String[] args)
	{
		// Construct a default tree
		QuaternionOperatorTree default_tree = new QuaternionOperatorTree();
		System.out.println("Default tree = " + default_tree);
		System.out.print("Compiling tree...");
		default_tree.compile();
		System.out.println("done");
		System.out.println("Evaluation at (0,0) = " + default_tree.evaluate(0, 0));
		System.out.println();

		// Construct a tree from a string
		QuaternionOperatorTree string_tree = new QuaternionOperatorTree(FormulaArchive.getFormula(0));
		System.out.println(" String tree = " + string_tree);
		System.out.print("Compiling tree...");
		string_tree.compile();
		System.out.println("done");
		System.out.println("Evaluation at (0,0) = " + string_tree.evaluate(0, 0));
		System.out.println();

		// Construct a random tree
		QuaternionOperatorTree random_tree = new QuaternionOperatorTree((int)(Math.random() * 10));
		System.out.println(" Random tree = " + random_tree);
		System.out.print("Compiling tree...");
		random_tree.compile();
		System.out.println("done");
		System.out.println("Evaluation at (0,0) = " + random_tree.evaluate(0, 0));
		System.out.println();
	}
}