/*
 * Static methods to do stuff to Tree objects
 * related to forming parse trees for mathematical objects
 */

//package lib;

public final class MathParser {

	 public final static String[] binaryOperators = 
		  new String[] {"+", "-", "*", "/", "^"};

	 public final static String[] unaryOperators = 
		  new String[] {"log", "sin", "cos", "tan", "sec", "arcsin", 
							 "arctan", "exp", "ln", "sqrt"};

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

	 public final static Tree stringToTree(String str) throws SyntaxError {
		  XVector xv = MathParser.mathTokenize(str);
		  Tree tree = MathParser.branchByParens( xv );
		  branchByPrecedence( tree );
		  finalizeLeaves( tree ); // pi, e, "x", "y", "t", "dx" etc
		  return tree;
	 }

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

	 public final static void finalizeLeaves(Tree tree) throws SyntaxError {
		  /* numerical leaf values turned into doubles ... */
		  if (tree.isLeaf() == false) {
				for (int i=0; i<tree.size(); i++) {
					 finalizeLeaves( tree.getChild(i) );
				}
				return;
		  }
		  else { // leaf case
				String str = (String) tree.getLeafValue();
				if ( str.equals("dx") ) {
					 tree.setdx();
					 return;
				}
				else if ( str.equals("x") ) {
					 tree.setX();
					 return;
				}
				else if ( str.equals("y") ) {
					 tree.setY();
					 return;
				}
				else if ( str.equals("t") ) {
					 tree.setT();
					 return;
				}
				else if ( str.equals("pi") ) {
					 tree.setLeafValue(new Double( Math.PI ) );
				}
				else if ( str.equals("e") ) {
					 tree.setLeafValue(new Double( Math.E ) );
				}
				else {
					 try {
						  tree.setLeafValue(new Integer( str ) );
					 }
					 catch (NumberFormatException excep) {
						  try {
								tree.setLeafValue(new Double( str ) );
						  }
						  catch (NumberFormatException exc) {
								System.out.println(str + " is used incorrectly");
								tree.setLeafValue( "?" );
								throw new SyntaxError(str + " is used incorrectly");
						  }
					 }
				}
		  }
	 }

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

	 public final static void branchByPrecedence(Tree tree) throws SyntaxError {

		  if ( tree.size() == 1 ) {
				if ( tree.isLeaf() ) {
					 return;
				}
				else {
					 branchByPrecedence( tree.getChild(0) );
					 return;
				}
		  }

		  /* unary operators: higher precedence than all binary!?!...  */
		  /* Ooops, should work from right... */
		  for (int i=tree.size()-1; i>=0; i--) {
				for (int j=0; j<unaryOperators.length; j++) {
					 if ( tree.getChild(i).toString().equals( unaryOperators[j] ) ) {
						  // throw SyntaxError(String msg) if improperly formed...
						  if ( tree.size() < i+1 ) {
								throw new SyntaxError("missing operand for " + 
															 unaryOperators[j]);
						  }
						  Tree kid = new Tree();
						  kid.addChild( tree.getChild(i+1) );
						  kid.setOpValue( opToCode( unaryOperators[j] ) );
						  tree.removeSlice(i,i+2);
						  branchByPrecedence( kid.getChild(0) );
						  tree.insertChild(kid, i);
					 }
				}
		  }

		  /* unary PLUS sign */
		  int ix = tree.indexOf( "+" );
		  if (ix == 0) {
				tree.removeSlice(0,1);
		  }

		  /* binary operators */
		  for (int i=0; i<binaryOperators.length; i++) {
//  				if (tree.size() < 3) { // helps efficiency
//  					 throw new SyntaxError("operator "+binaryOperators[i]+
//  												  " lacks left operand");
//  					 // break;
//  				}
				ix = tree.lastIndexOf( binaryOperators[i] );
				if ( ix >= 0 ) { // operator occurs
					 // worry about lack of operands
					 if (ix == 0) {
						  // case of unary minus!?!? 
						  //__EDIT__ from here...
						  if (binaryOperators[i].equals("-")) {
								Tree rightKid;
								rightKid = new Tree();
								rightKid.addChildren( tree.getSlice(1) );
								branchByPrecedence( rightKid );
								tree.removeChildren();
								tree.addChild( rightKid );
								tree.setOpValue(opToCode("unaryMinus"));
								return;
					 //__EDIT__ to here
						  }
						  else {
								throw new SyntaxError("operator "+binaryOperators[i]+
															 " lacks left operand");
						  }
					 }
					 else if (ix == tree.size()-1) {
						  throw new SyntaxError("operator "+binaryOperators[i]+
														" lacks right operand");
					 }
					 Tree leftKid;
					 Tree rightKid;
					 if (ix == 1) {
						  leftKid = tree.getChild(0);
					 }
					 else {
						  leftKid = new Tree();
						  leftKid.addChildren( tree.getSlice(0,ix) );
					 }
					 if (ix == tree.size()-2) {
						  rightKid = tree.getChild(ix+1);
					 }
					 else {
						  rightKid = new Tree();
						  rightKid.addChildren( tree.getSlice(ix+1) );
					 }
					 branchByPrecedence( leftKid ); /* recurse! */
					 branchByPrecedence( rightKid );
					 tree.removeChildren();
					 tree.addChild( leftKid );
					 tree.addChild( rightKid );

					 tree.setOpValue(opToCode( binaryOperators[i] )) ; //__NB__!!!
				}
		  }
		  		  
//  		  /* unary MINUS sign */  /* __EDIT__ should change precedence... */
//  		  ix = tree.indexOf( "-" );
//  		  if (ix == 0) {
//  				Tree kid = new Tree();
//  				kid.addChild( tree.getChild(1) );
//  				kid.setOpValue( opToCode( "unaryMinus" ) );
//  				tree.removeSlice(0,2);
//  				branchByPrecedence( kid.getChild(0) );
//  				tree.insertChild(kid, 0);
//  		  }

	 }

	 public final static int opToCode(String str) throws SyntaxError {
		  if (str.equals("+")) {
				return Tree.ADD;
		  }
		  else if (str.equals("-")) {
				return Tree.SUB;
		  }
		  else if (str.equals("unaryMinus")) {
				return Tree.UNARYMINUS;
		  }
		  else if (str.equals("/")) {
				return Tree.DIV;
		  }
		  else if (str.equals("*")) {
				return Tree.MUL;
		  }
		  else if (str.equals("^")) {
				return Tree.POW;
		  }
		  else if (str.equals("log")) {
				return Tree.LOG;
		  }
		  else if (str.equals("sin")) {
				return Tree.SIN;
		  }
		  else if (str.equals("cos")) {
				return Tree.COS;
		  }
		  else if (str.equals("tan")) {
				return Tree.TAN;
		  }
		  else if (str.equals("sec")) {
				return Tree.SEC;
		  }
		  else if (str.equals("arcsin")) {
				return Tree.ARCSIN;
		  }
		  else if (str.equals("arctan")) {
				return Tree.ARCTAN;
		  }
		  else if (str.equals("exp")) {
				return Tree.EXP;
		  }
		  else if (str.equals("sqrt")) {
				return Tree.SQRT;
		  }
		  else if (str.equals("ln")) {
				return Tree.LN;
		  }
		  else {
				System.out.println("Getting an operator lacking a code: |" + str + "|");
				throw new SyntaxError("" + str + " used incorrectly");
		  }
	 }

	 public final static String codeToOp(int code) throws SyntaxError {
		  switch (code) {
		  case Tree.LOG:
				return "log";
		  case Tree.COS:
				return "cos";
		  case Tree.SIN:
				return "sin";
		  case Tree.ADD:
				return "+";
		  case Tree.MUL:
				return "*";
		  case Tree.DIV:
				return "/";
		  case Tree.SUB:
				return "-";
		  case Tree.UNARYMINUS:
				return "-";
		  case Tree.POW:
				return "^";
		  case Tree.TAN:
				return "tan";
		  case Tree.SEC:
				return "sec";
		  case Tree.ARCSIN:
				return "arcsin";
		  case Tree.ARCTAN:
				return "arctan";
		  case Tree.EXP:
				return "exp";
		  case Tree.SQRT:
				return "sqrt";
		  case Tree.LN:
				return "ln";
		  default:
				System.out.println("Unknown binary opcode |"+ code + "|");
				throw new SyntaxError("" + code + " does not parse as operator");
		  }
	 }

	 public final static Tree branchByParens(XVector v) throws SyntaxError {
		  /* v is list of tokens (String's) from mathTokenize()'ing */
		  Tree tree = new Tree();
		  int ix = leftParen( v );
		  if (ix < 0) {                           /* no parentheses */
				if ( rightParen( v ) >= 0) {
					 throw new SyntaxError("unmatched right parenthesis");
				}
				for (int i=0; i<v.size(); i++) {
					 tree.addChild(new Tree( (String) v.elementAt(i) ) );
				}
		  }
		  else {                                  /* some parentheses */
				int end;
				while (ix >= 0) { // there are some parens left...

					 /* top-level children */
					 for (int i=0; i<ix; i++) {
						  tree.addChild(new Tree( (String) v.elementAt(i) ) );
					 }
					 v.removeSlice(0,ix+1); // remove the leftParen, too

					 end = matchingRightParen( v, 0); // in v, offset=0
					 if (end < 0) {
						  throw new SyntaxError("unmatched left parenthesis");
					 }
					 Tree newkid = branchByParens( v.getSlice(0,end) ); 
					 v.removeSlice(0,end+1); // includes end-th element
					 tree.addChild( newkid );
					 ix = leftParen(v);
				}
				/* now after all parens: leftovers */
				for (int i=0; i<v.size(); i++) {
					 tree.addChild(new Tree( (String) v.elementAt(i) ) );
				}
		  }
		  return tree;
	 }	

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

	 public static final boolean isLetter(char ch) {
		  int t = (int) ch;
		  if ( (t >= 97 && t <=122) || (t>=65 && t<=90) ) { return true; }
		  else {	return false; }
	 }

	 public static final boolean isDigit(char ch) {
		  int t = (int) ch;
		  if ( t >= 48 && t <=57 ) { return true; }
		  else {	return false; }
	 }

	 public static final boolean isLetterOrDigit( char ch ) {
		  return isDigit(ch) ^ isLetter(ch);
	 }

	 public static final boolean isLetterOrDigitOrDecimal( char ch ) {
		  return isDigit(ch) ^ isLetter(ch) ^ ( ch == '.' );
	 }

  	 public static final XVector mathTokenize(String str) {
  		  str = str.replace('[','(');
  		  str = str.replace(']',')');
  		  str = str.replace('{','(');
  		  str = str.replace('}',')');
		  XVector v = new XVector();
		  int begin = 0;
		  for (int i=0; i<str.length(); i++) {
				if ( isLetterOrDigitOrDecimal( str.charAt(i) ) == true ) {
					 // just keep accumulating characters...
				}
				else if ( str.charAt(i) == ' ' ) {
					 if (begin < i) {
						  v.addElement( str.substring(begin,i) );
					 }
					 begin = i+1;
				}
				else { // non-alphanumeric
					 if (begin < i) {
						  v.addElement( str.substring(begin,i) );
					 }
					 v.addElement( str.substring(i,i+1) );
					 begin = i+1;
				}
		  }
		  String leftover = str.substring(begin);
		  if ( leftover.length() > 0 ) {
				v.addElement( leftover );
		  }
		  return v;
  	 }

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

	 public final static int leftParen(XVector v) { // Vector of String objects...
		  int ix = 0;
		  while (ix < v.size() ) {
				if ( ((String) v.elementAt(ix)).equals("(") ) {
					 return ix;
				}
				ix++;
		  }
		  return -1;
	 }

	 public final static int rightParen(XVector v) { // Vector of String objects...
		  int ix = 0;
		  while (ix < v.size() ) {
				if ( ((String) v.elementAt(ix)).equals(")") ) {
					 return ix;
				}
				ix++;
		  }
		  return -1;
	 }

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

	 public final static int matchingRightParen(XVector v, int offset) {
		  int net = 1; // presumably already had a "("
		  int end = offset-1;
		  while (net > 0 && end < v.size()-1 ) {
				end++; // so end >= 0
				if (((String) v.elementAt(end)).equals("(") ) {
					 net++;
				}
				else if (((String) v.elementAt(end)).equals(")") ) {
					 net--;
				}
				else {
					 // do nothing
				}
		  }
		  if (end < v.size() ) {
				return end;
		  }
		  else {
				return -1;
		  }
	 }

} // end of Tree class

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