/*
 * Node version for parsing mathematical expressions
 *
 * Revision includes both "y" and "x" as evaluable
 */ 

//package lib;

import java.util.*;

public class Tree {

	 XVector children = new XVector();
	 boolean isLeaf = false;
	 Object leafValue;
	 boolean isX = false;
	 boolean isdx = false;
	 boolean isY = false;
	 boolean isT = false;

	 boolean hasOpValue = false;
	 int opValue = -1;
	 final static int ADD=0, MUL=1, DIV=2, EXP=3, SUB=4,
		  SIN=5, COS=6, LOG=7, TAN=8, ARCSIN=9, ARCTAN=10, UNARYMINUS=11,
		  POW=12, LN=13, SQRT=14, SEC=15;

  	 public Tree() {
  	 }

	 public Tree(Object ob) {
		  isLeaf = true;
		  leafValue = ob;
	 }

	 public void setdx() {
		  isdx = true;
	 }

	 public void setX() {
		  isX = true;
	 }

	 public void setY() {
		  isY = true;
	 }

	 public void setT() {
		  isT = true;
	 }

	 public final void addChildren(Object[] obs) {
		  for (int i=0; i<obs.length; i++) {
				Tree kid = new Tree( obs[i].toString() );
				addChild( kid );
		  }
	 }

	 public final void addChildren(Vector v) {
		  children.append( v );
	 }

	 public final Vector getChildren() {
		  return children;
	 }

	 public final void addChild(Tree Tree) {
		  getChildren().addElement( Tree );
	 }

	 public final Tree getChild(int i) {
		  return (Tree) getChildren().elementAt(i);
	 }

	 public final void setChild(Object obj, int i) {
		  children.setElementAt(obj, i);
	 }

	 public final void insertChild(Object obj, int i) {
		  children.insertElementAt(obj, i);
	 }

	 public final boolean isLeaf() {
		  return isLeaf;
	 }

	 public final Object getLeafValue() {
		  return leafValue;
	 }

	 public final void setLeafValue(Object obj) {
		  leafValue = obj;
		  isLeaf = true;
	 }

	 public final XVector getSlice(int i, int j) {
		  return this.children.getSlice(i,j);
	 }

	 public final XVector getSlice(int i) {
		  return this.children.getSlice(i, this.size());
	 }

	 public final void removeSlice(int i, int j) {
		  this.children.removeSlice(i,j);
	 }

	 public final void removeSlice(int i) {
		  this.children.removeSlice(i,this.size());
	 }

	 public final void removeChildren() {
		  children = new XVector();
	 }

	 public final int size() {
		  return getChildren().size();
	 }

	 public final String toString() {
		  if (isLeaf() == true) {
				return leafValue.toString();
		  }
		  else {
				StringBuffer sb = new StringBuffer("[");
				Enumeration en = getChildren().elements();
				while (en.hasMoreElements()) {
					 sb.append( en.nextElement().toString() ); // no (,)'s?!
				}
				sb.append("]");
				return sb.toString();
		  }
	 }

	 public final int indexOf(String str) {
		  for (int i=0; i<this.size(); i++) {
				if ( this.getChild(i).isLeaf() && 
					  ((String) this.getChild(i).getLeafValue()).equals( str ) ) {
					 return i;
				}
		  }
		  return -1; // not found
	 }

	 public final int lastIndexOf(String str) {
		  for (int i=this.size()-1; i>=0; i--) {
				if ( this.getChild(i).isLeaf() && 
					  ((String) this.getChild(i).getLeafValue()).equals( str ) ) {
					 return i;
				}
		  }
		  return -1; // not found
	 }

	 public final void setOpValue(int opval) {
		  opValue = opval;
		  hasOpValue = true;
	 }

	 public final int getOpValue() {
		  return opValue;
	 }

	 public final String enpar() throws SyntaxError { // wrap in parens if NOT leaf
		  if ( isLeaf() ) {
				return this.toTex();
		  }
		  else {
				return "(" + this.toTex() + ")";
		  }
	 }

	 //__EDIT__

	 public final String toTex() throws SyntaxError {
		  return toTex( false );
	 }

	 public final String toTex(boolean high_parenth) throws SyntaxError {
		  if (isLeaf()) {
				return getLeafValue().toString();
		  }
		  else if ( size() == 1 && hasOpValue == false) {
				return this.getChild(0).toTex();
		  }
		  else if ( size() == 1) { // unary operator
				return MathParser.codeToOp( getOpValue() ) 
					 + getChild(0).enpar();
		  }
		  else if ( getOpValue() == ADD ) {
				if (high_parenth) {
					 return getChild(0).enpar() + " + " + getChild(1).enpar();
				}
				else {
					 return getChild(0).toTex() + " + " + getChild(1).toTex();
				}
		  }
		  else if ( getOpValue() == SUB ) {
				if (high_parenth) {
					 return getChild(0).enpar() + " - " + getChild(1).enpar();
				}
				else {
					 return getChild(0).toTex() + " - " + getChild(1).toTex();
				}
		  }
		  else if ( getOpValue() == MUL ) {
				return getChild(0).enpar() + "*" + getChild(1).enpar();
		  }
		  else if ( getOpValue() == DIV ) {
				return "{"+getChild(0).toTex() + "\\over " + getChild(1).toTex()+"}";
		  }
		  else if ( getOpValue() == POW ) {
				return getChild(0).enpar() + "^{" + getChild(1).enpar() + "}";
		  }
		  else if ( getOpValue() == SQRT ) {
				return "\\sqrt{" + getChild(0).toTex() + "}";
		  }
		  else { // for the moment: other binary operators (?)
				System.out.println(">>> unknown case ????" + 
										 "(" + getChild(0).toTex() + 
										 MathParser.codeToOp( getOpValue() ) +
										 getChild(1).toTex() + ")");
  				return "(" + getChild(0).toTex() + 
  					 MathParser.codeToOp( getOpValue() ) +
  					 getChild(1).toTex() + ")" ;
				//				return ">>?????<<";
		  }
	 }

	 /************************************************************/

	 public final double eval(double xval) 
		  throws ArithmeticException, SyntaxError {
		  return eval( xval, 0, 0, 0 ); // dummy value for "y", "t", "dx"
	 }

	 public final double eval(double xval, double yval) 
		  throws ArithmeticException, SyntaxError {
		  return eval( xval, yval, 0, 0 ); // dummy value for "t", "dx"
	 }

	 public final double eval(double xval, double yval, double tval, double dxval) 
		  throws ArithmeticException, SyntaxError 
	 {
		  if  (isLeaf() && isdx == true ) { // the leaf is "dx"
				return dxval;
		  }
		  else if (isLeaf() && isX == true ) { // the leaf is "x"
				return xval;
		  }
		  else if (isLeaf() && isY == true ) { // the leaf is "y"
				return yval;
		  }
		  else if (isLeaf() && isT == true ) { // the leaf is "t"
				return tval;
		  }
		  else if (isLeaf()) {
				try {
					 return ((Integer) getLeafValue()).intValue();
				}
				catch (ClassCastException excep) { //__NOTE__ lets SyntaxErrors "out"
					 return ((Double) getLeafValue()).doubleValue();
				}
		  }
		  else if ( size() == 1 && hasOpValue == false ) {
				return getChild(0).eval(xval,yval,tval,dxval);
		  }
		  else if ( size() == 1 ) {
				double val = getChild(0).eval( xval,yval,tval,dxval );
				switch (getOpValue()) {
				case EXP:
					 return Math.exp( val );
				case SQRT:
					 if ( val < 0 ) {
						  throw new ArithmeticException();
					 }
					 return Math.sqrt( val );
				case UNARYMINUS:
					 return -val;
				case SIN:
					 return Math.sin( val );
				case COS:
					 return Math.cos( val );
				case LN:
					 if ( val <= 0 ) {
						  throw new ArithmeticException();
					 }
					 return Math.log( val );
				case LOG:
					 if ( val <= 0 ) {
						  throw new ArithmeticException();
					 }
					 return Math.log( val );
				case TAN:
					 return Math.tan( val );
				case SEC:
					 return 1/Math.cos( val );
				case ARCSIN:
					 if ( val > 1 || val < -1 ) {
						  throw new ArithmeticException();
					 }
					 return Math.asin( val );
				case ARCTAN:
					 return Math.atan( val );
				default:
					 System.out.println("Problem in evaluating unary op: |" +
											  getOpValue() + "|");
					 return 0;
				}
		  }
		  else if ( size() == 2 && hasOpValue == true ) {
				switch (getOpValue()) {
				case ADD:
					 return getChild(0).eval(xval,yval,tval,dxval) + 
						  getChild(1).eval(xval,yval,tval,dxval);
				case MUL:
					 return getChild(0).eval(xval,yval,tval,dxval) * 
						  getChild(1).eval(xval,yval,tval,dxval);
				case DIV:
					 double val = getChild(1).eval(xval,yval,tval,dxval);
					 if ( Math.abs( val ) < .0001 ) { //__EDIT__
						  throw new ArithmeticException();
					 }
					 return getChild(0).eval(xval,yval,tval,dxval) / val;
				case SUB:
					 return getChild(0).eval(xval,yval,tval,dxval) 
						  - getChild(1).eval(xval,yval, tval,dxval);
				case POW:
					 double base = getChild(0).eval(xval,yval,tval,dxval);
					 double exp = getChild(1).eval(xval,yval,tval,dxval);
					 /* following condition on "exp" is about integrality */
					 if ( base <= .0001 && Math.abs(Math.sin( Math.PI * exp))>.000001 ) {
						  throw new ArithmeticException();
					 }
					 return Math.pow(base,exp);
				default:
					 System.out.println("Problem in evaluating binary op :|" +
											  getOpValue() + "|");
					 return 0;
				}				
		  }
		  else {
				System.out.println("Eh? String repn is " + toString() +
										 " math repn is " + toTex() );
				return 0;
		  }
	 }

	 /************************************************************/

	 /*
	  * The following "vectorized" version of the subsequent "scalar" comparisons
	  * does not have to scale amazingly well, but should be ok.
	  * Do not attempt to enumerate all permutations of n things... ;)
	  *
	  * (ttd: maybe boolean return value is too limiting?)
	  */

	 public static final boolean probEquals(String[] first, String[] second,
														 double left, double right,
														 double tolerance) 
		  throws SyntaxError 
	 {
		  boolean OK = true;
		  if (first.length == 1 && second.length == 1) {
				return probEquals( first[0], second[0] , 0.1, .9, .00001);
		  }
		  if (first.length != second.length) { // this treats multiple answers
				return false;
		  }
		  /*
			* Now treat the case that there are several entities
			*/ 
		  Tree[] forest = new Tree[ first.length ];
		  for (int i=0; i<forest.length; i++) {
				forest[i] = MathParser.stringToTree( first[i] );
		  }
		  Tree[] forest2 = new Tree[ second.length ];
		  for (int i=0; i<forest2.length; i++) {
				forest2[i] = MathParser.stringToTree( second[i] );
		  }

		  boolean thisOneOK;
		  for (int k=0; k<forest.length; k++) {
				thisOneOK = false;
				for (int ell=0; ell<forest2.length; ell++) {
					 if ( Tree.probEquals( forest[k], forest2[ell],
												  0, 1, .00001 ) ) {
						  thisOneOK = true;
//  						  System.out.println("one ok, moving on ... ");
						  continue;
					 }
					 else {
//  						  System.out.println("Failed with indices " + k + " and "
//  													+ ell);
					 }
				}
				if (thisOneOK == false) {
//  					 System.out.println("Failed at index " + k);
					 return false;
				}
		  }
		  return true;
	 }

	 /************************************************************/

	 /*
	  * Compares a String for equality-by-evaluation with the given
	  * Tree object, by evaluation at 10 "random" points in the
	  * interval [left, right]
	  * 
	  */

	 public static final boolean probEquals(String first, String second,
														 double left, double right,
														 double tolerance) 
		  throws SyntaxError {
		  return probEquals(MathParser.stringToTree( first ),
								  MathParser.stringToTree( second ),
								  left, right, tolerance);
	 }

	 public static final boolean probEquals(Tree first, Tree second,
														 double left, double right,
														 double tol) 
		  throws SyntaxError 
	 {
		  Random rand = new Random();
		  double input;
		  double x,y,t,dx;
		  for (int i=0; i<10; i++) {
				x = rand.nextDouble();
				y = rand.nextDouble();
				t = rand.nextDouble();
				dx = rand.nextDouble();
				x = left*x + right*(1-x);
				y = left*y + right*(1-y);
				t = left*t + right*(1-t);
				dx = left*dx/10.0 + right*(1-dx)/10.0;

//  				System.out.println("" + first.eval(input) + " vs " +
//  										 second.eval(input) );
				
				if ( Math.abs(first.eval(x,y,t,dx) - second.eval(x,y,t,dx)) > tol ) {
					 return false;
				}
		  }
		  return true;
	 }

} // end of Tree class

/*******************************************************************************/