package fplot;

import java.util.*;
/**
 * Basistyp der Knoten des Syntaxbaumes.
 * @author Christian Semrau
 * <a href="mailto:Christian.Semrau@student.uni-magdeburg.de">
 * Christian.Semrau@student.uni-magdeburg.de</a>
 * <br><a href="http://chsemrau.de">Homepage</a>
 */
class NodeBase {
	/* Operatoren */
	protected final static int
		// binaere
		ADD = 1, SUB = 2, MUL = 3, DIV = 4,
		MOD = 5, IDIV = 6, OPOW = 7,
		// unaere
		NEG = 20, // -left
		// Konstanten und Variablen
		ZAHL  = 50, // value

	// um eine neue Konstante hinzuzufuegen, muss man ihr hier einen
	// Wert zuweisen, und constnames und diese Funktion aktualisieren:
	// evaluate(double,double,double)
		CPI = 60,  CE  = 61,
		CVARX = 70, // Variable X
		CVARP = 71, // Parameter P
		CVARQ = 72, // Parameter Q
		CVARI = 73, // Schleifenzaehler I

		// Funktionstypen
		FUNC0 = 100,  FUNC1 = 101,
		FUNC2 = 102,  FUNC3 = 103;

	/* Prioritaeten der Operatoren */
	protected static final int[][] prioritaet = {
		{ADD,1}, {SUB,1},
		{MUL,2}, {DIV,2}, {IDIV,2}, {MOD,2},
		{NEG,3},
		{OPOW,4},
		{FUNC0,10}, {FUNC1,10}, {FUNC2,10}, {FUNC3,10},
		{ZAHL,11}, {CPI,11}, {CE,11},
		{CVARX,11}, {CVARP,11}, {CVARQ,11}, {CVARI,11}
	};

	/* Assoziative Operatoren, und Konstanten */
	protected static final int[] assoziativ ={
		ADD, MUL, ZAHL, CPI, CE, CVARX, CVARP, CVARQ, CVARI,
		FUNC0, FUNC1, FUNC2, FUNC3
	};

	// um eine neue Funktion hinzuzufuegen, muss man ihr hier einen Wert
	// entsprechend ihrer Parameterzahl zuweisen, und
	// funcnames und diese Methode aktualisieren:
	// evalFunc(double,double)

	/* Funktionen */
	protected final static int
		NOFUNC = 0, // Nullfunktion

		// ohne Parameter, liegen zwischen 1 und 999
		RND = 1, RNDN = 2,

		// ein Parameter, liegen zwischen 1000 und 1999
		SIN  = 1001,  COS  = 1002,  TAN  = 1003,  COT  = 1004,
		ASIN = 1005,  ACOS = 1006,  ATAN = 1007,  ACOT = 1008,
		SINH = 1009,  COSH = 1010,  TANH = 1011,  COTH = 1012,
		ARSINH = 1013,  ARCOSH = 1014,  ARTANH = 1015,  ARCOTH = 1016,
		
		EXP = 1020,  LN  = 1021,  LG  = 1022, LD = 1023,
		SQR = 1030,  SQRT = 1031,
		FAC = 1035,  GAMMA = 1036,
		
		ABS  = 1040, SGN  = 1041, INT  = 1042, FRAC = 1043, INV  = 1044,

		// zwei Parameter, liegen zwischen 2000 und 2999
		POW  = 2001, LOG  = 2002, ROOT = 2003,
		MPOW = 2004,
		MIN  = 2010, MAX  = 2011,
		SUM  = 2500,

		// drei Parameter, liegen zwischen 3000 und 3999
                SUM3 = 3001, IF = 3002;

	/* Zuordnung der Werte zu den Namen. */
	static class Name{
		int func; String name;
		Name(int f, String n){ func=f; name=n;}
	}

	/* Die Namen der Funktionen.
	* wenn mehrere Namen fuer eine Funktion vorhanden sind,
	* wird der erste bei der Ausgabe verwendet
	*/
	static Name[] funcnames = {
		new Name(RND, "rnd"),
		new Name(RNDN, "rndn"),

		new Name(SIN, "sin"),
		new Name(COS, "cos"),
		new Name(TAN, "tan"),
		new Name(COT, "cot"),
		new Name(ASIN, "asin"),
		new Name(ACOS, "acos"),
		new Name(ATAN, "atan"),
		new Name(ACOT, "acot"),
		new Name(ASIN, "arcsin"),
		new Name(ACOS, "arccos"),
		new Name(ATAN, "arctan"),
		new Name(ACOT, "arccot"),

		new Name(SINH, "sinh"),
		new Name(COSH, "cosh"),
		new Name(TANH, "tanh"),
		new Name(COTH, "coth"),
		new Name(ARSINH, "arsinh"),
		new Name(ARCOSH, "arcosh"),
		new Name(ARTANH, "artanh"),
		new Name(ARCOTH, "arcoth"),
		new Name(ARSINH, "asinh"),
		new Name(ARCOSH, "acosh"),
		new Name(ARTANH, "atanh"),
		new Name(ARCOTH, "acoth"),

		new Name(EXP, "exp"),
		new Name(LN, "ln"),
		new Name(LG, "lg"),
		new Name(LG, "log10"),
		new Name(LD, "ld"),
		new Name(LD, "log2"),
		new Name(SQR, "sqr"),
		new Name(SQRT, "sqrt"),
		new Name(FAC, "fak"),
		new Name(FAC, "fac"),
		new Name(GAMMA, "gamma"),
		new Name(ABS, "abs"),
		new Name(SGN, "sgn"),
		new Name(INT, "int"),
		new Name(FRAC, "frac"),
		new Name(INV, "inv"),

		new Name(POW, "pow"),
		new Name(LOG, "log"),
		new Name(ROOT, "root"),
		new Name(MPOW, "mpow"),
		new Name(MIN, "min"),
		new Name(MAX, "max"),
		new Name(SUM, "sum"),
		
		new Name(SUM3, "sum3"),
		new Name(IF, "if")
	};

	static Name[] constnames = {
		new Name(CE,  "e"),
		new Name(CPI, "pi"),
		new Name(CVARX, "x"),
		new Name(CVARP, "p"),
		new Name(CVARQ, "q"),
		new Name(CVARI, "i")
	};

	/* Klammerungsstufen */
	static final int
		KLAMMERUNG_ALLES = 2,
		KLAMMERUNG_MITTEL = 1,
		KLAMMERUNG_WENIG = 0;
/**
 * 
 * @return int
 * @param op int
 */
protected static boolean assoziativ(int op) {
	for (int i=0; i<assoziativ.length; i++)
		if (assoziativ[i]==op)
			return true;
	return false;
}

/**
 * kleiner als 0, wenn c1 geringere Prioritaet als c2 hat.
 * gleich 0, wenn c1 die gleiche Prioritaet wie c2 hat.
 * groesser als 0,  wenn c1 hoehere Prioritaet als c2 hat.
 */
protected static int comparePriority(char c1, char c2) {
	switch (c1){
		case '+': case '-':
			switch (c2){
				case '+': case '-': return 0;
				case '*': case '/': case '%': case '\\': return -1;
				case '_': return -1;
				case '^': return -1;
			}break;
		case '*': case '/': case '%': case '\\':
			switch (c2){
				case '+': case '-': return +1;
				case '*': case '/': case '%': case '\\': return 0;
				case '_': return -1;
				case '^': return -1;
			}break;
		case '_':
			switch (c2){
				case '+': case '-': return +1;
				case '*': case '/': case '%': case '\\': return +1;
				case '_': return 0;
				case '^': return -1;
			}break;
		case '^':
			switch (c2){
				case '+': case '-': return +1;
				case '*': case '/': case '%': case '\\': return +1;
				case '_': return +1;
				case '^': return 0;
			}break;
	}
	throw new IllegalArgumentException("("+c1+","+c2+")");
}
/**
 * kleiner als 0, wenn op1 geringere Prioritaet als op2 hat.
 * gleich 0, wenn op1 die gleiche Prioritaet wie op2 hat.
 * groesser als 0,  wenn op1 hoehere Prioritaet als op2 hat.
 */
protected static int comparePriority(String op1, String op2) {
	if (!isOp(op1) || !isOp(op2))
		throw new IllegalArgumentException("("+op1+","+op2+")");
	char c1 = op1.charAt(0), c2 = op2.charAt(0);
	return comparePriority(c1,c2);
}

/** Liefert die Nummer der Konstanten */
protected static String constName(int c) {
	for(int i=0; i<constnames.length; i++)
		if (constnames[i].func==c)
			return constnames[i].name;

	throw new IllegalArgumentException("Keine Konstante: ["+c+"]");
}
/**
 * Liefert <code>n!</code> (n Fakultaet). 0! = 1, 1! = 1, n! = (n-1)!*n
 * @return double
 * @param n int
 */
public static double fakd(int n) {
	if (n<=1) return 1;
	double f = n--;
	while (n>1) f *= n--;
	return f;
}
/**
 * Filtert s fuer die Auswertung als Infix-Ausdruck.
 */
protected static String filterInfix(String s) {
  String chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"+"abcdefghijklmnopqrstuvwxyz"
  	+"0123546789.+-*/%\\^(),";
  // enthaelt alle Zeichen, die der Filter "durchlassen" soll
  StringBuffer f = new StringBuffer(); char c;
  for (int i = 0; i < s.length(); )
	if (chars.indexOf(c=s.charAt(i++))>=0){
	  f.append(c);
	}
  return f.toString().toLowerCase();
}
/**
 * Filtert s fuer die Auswertung als Postfix-Ausdruck.
 */
protected static String filterRPN(String s) {
  String chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"+"abcdefghijklmnopqrstuvwxyz"
  	+"0123546789.+-*/%\\^()_ ";
  // enthaelt alle Zeichen, die der Filter "durchlassen" soll
  StringBuffer f = new StringBuffer(); char c;
  boolean preSpace = true;
  for (int i = 0; i < s.length(); )
	if (chars.indexOf(c=s.charAt(i++))>=0){
	  if (c!=' ' || !preSpace)
		  f.append(c);
	  preSpace = (c==' ');
	}
  return f.toString().toLowerCase();
}

/** Liefert den Namen der Funktion */
protected static String funcName(int func) {
	for(int i=0; i<funcnames.length; i++)
		if (funcnames[i].func==func)
			return funcnames[i].name;

	return "F["+func+"]";
}
/**
 * Liefert den Wert der Gammafunktion.
 * Interpoliert linear zwischen den Hundertstel-Stellen.
 * @return double
 * @param x double
 */
public static double gamma(double x) {
	double frac = (x-Math.floor(x*100)/100)*100;
	return gamma2(x+0.01)*frac + gamma2(x)*(1-frac);
}
/**
 * Liefert die Werte der Gammafunktion fuer das
 * naechstkleinere Hundertstel.
 * @return double
 * @param x double
 */
private static double gamma2(double x) {
	if (x>172) return Double.POSITIVE_INFINITY;
	// gamma(172) > Double.MAX_VALUE (ca. 1.7e308)
	double g = gamma3(x);
	double f = (Math.floor((x)*100)/100);
	while(f>=3){
		f=f-1;
		g = g * f;
	}
	while(f<2){
		g = g / f;
		f=f+1;
	}
	return g;
}

/** Werte der Gamma-Funktion.
 * Enthaelt die Werte fuer x=2.00, 2.01, ... 1.99, 3.00
 */
private static final double GAMMA_LUT[] = new double[]{
//2
1.00000000, 1.00426928, 1.00862131, 1.01305665, 1.01757586, 1.02217953,
1.02686823, 1.03164257, 1.03650316, 1.04145062,
1.04648561, 1.05160877, 1.05682079, 1.06212236, 1.06751419, 1.07299700,
1.07857155, 1.08423859, 1.08999893, 1.09585335,
1.10180269, 1.10784779, 1.11398951, 1.12022874, 1.12656638, 1.13300335,
1.13954059, 1.14617908, 1.15291980, 1.15976375,
1.16671195, 1.17376547, 1.18092535, 1.18819270, 1.19556862, 1.20305424,
1.21065072, 1.21835924, 1.22618098, 1.23411717,
1.24216904, 1.25033788, 1.25862495, 1.26703157, 1.27555908, 1.28420884,
1.29298222, 1.30188063, 1.31090550, 1.32005830,
1.32934049, 1.33875360, 1.34829916, 1.35797872, 1.36779388, 1.37774625,
1.38783748, 1.39806924, 1.40844323, 1.41896118,
1.42962486, 1.44043604, 1.45139656, 1.46250827, 1.47377304, 1.48519280,
1.49676948, 1.50850507, 1.52040159, 1.53246106,
1.54468559, 1.55707727, 1.56963825, 1.58237073, 1.59527691, 1.60835905,
1.62161944, 1.63506042, 1.64868434, 1.66249360,
1.67649065, 1.69067797, 1.70505808, 1.71963354, 1.73440695, 1.74938095,
1.76455824, 1.77994153, 1.79553361, 1.81133729,
1.82735545, 1.84359099, 1.86004688, 1.87672613, 1.89363183, 1.91076708,
1.92813506, 1.94573901, 1.96358224, 1.98166809,
//3
2.00000000};

/**
 * Liefert die Werte der Gamma-Funktion fuer das naechstkleinere
 * Hundertstel von x, 2<=x<3. Exakte Werte fuer x=2.00, 2.01, 2.02,...
 * @return double
 * @param x double
 */
private static double gamma3(double x) {
	double frac = (Math.floor((x)*100)%100+100)%100;
	return GAMMA_LUT[(int)frac];
}
/**
 * Liefert das naechste Token [0] und den Rest von s [1].
 */
protected static String[] getToken(String s) {
	s = filterInfix(s);
	String t = "";
	char c = s.charAt(0);
	switch (c){
		case '+': return new String[]{"+", s.substring(1)};
		case '-': return new String[]{"-", s.substring(1)};
		case '*': return new String[]{"*", s.substring(1)};
		case '/': return new String[]{"/", s.substring(1)};
		case '%': return new String[]{"%", s.substring(1)};
		case '\\':return new String[]{"\\",s.substring(1)};
		case '^': return new String[]{"^", s.substring(1)};
		case '_': return new String[]{"_", s.substring(1)};
		case '(': return new String[]{"(", s.substring(1)};
		case ')': return new String[]{")", s.substring(1)};
		default:
		if (c>='0' && c<='9' || c=='.'){
			if (c=='.') t += '0';
			t += c;
			if (s.length()==1) return new String[]{t, ""};
			boolean lastWasE = false;
			do{
				s = s.substring(1);
				c = s.charAt(0);
				if (c>='0' && c<='9' || c=='.'){
					t += c; lastWasE = false;
				}else
				if (c=='e'){
					t += c; lastWasE = true;
				}else
				if (c=='-' && lastWasE){
					t += c; lastWasE = false;
				}else
					return new String[]{t, s};
			}while(s.length()>1);
			return new String[]{t, ""};
		}else
		if (c>='a' && c<='z'){
			t += c;
			if (s.length()==1) return new String[]{t, ""};
			do{
				s = s.substring(1);
				c = s.charAt(0);
				if ((c>='a' && c<='z') || (c>='0' && c<='9'))
					t += c;
				else
					return new String[]{t, s};
			}while(s.length()>1);
			return new String[]{t, ""};
		}else
		
		return new String[]{s.substring(0,1),s.substring(1)};
	}
}
/**
 * 
 * @return boolean
 * @param c int
 */
protected static boolean isConst(int c) {
	for(int i=0; i<constnames.length; i++)
		if (constnames[i].func==c)
			return true;
	return false;
}

/** Liefert true, wenn f eine bekannte Konstante ist */
protected static boolean isConst(String f) {
	return nameConst(f)>0;
}

/** Liefert true, wenn f eine bekannte parameterlose Funktion ist */
protected static boolean isFunc0(String f) {
	int nr = nameFunc(f);
	return nr>=1 && nr<1000;
}

/** Liefert true, wenn f eine bekannte Funktion mit einem Parameter ist */
protected static boolean isFunc1(String f) {
	int nr = nameFunc(f);
	return nr>=1000 && nr<2000;
}

/** Liefert true, wenn f eine bekannte Funktion mit zwei Parametern ist */
protected static boolean isFunc2(String f) {
	int nr = nameFunc(f);
	return nr>=2000 && nr<3000;
}

/** Liefert true, wenn f eine bekannte Funktion mit drei Parametern ist */
protected static boolean isFunc3(String f) {
	int nr = nameFunc(f);
	return nr>=3000 && nr<4000;
}

/** Liefert true, wenn f eine bekannte Funktion ist */
protected static boolean isFunction(String f) {
	int nr = nameFunc(f);
	return nr>=1 && nr<4000;
}
/**
 * Liefert true, wenn c ein binaerer Operator ist.
 * @return boolean
 * @param op int
 */
protected static boolean isOp(int c) {
	return c==ADD || c==SUB || c==MUL || c==DIV || c==IDIV || c==MOD
	|| c==OPOW;
}
/**
 * Liefert true, wenn s ein Operationszeichen ist.
 */
protected static boolean isOp(String s) {
	return
	  "+".equals(s) || "-".equals(s) ||
	  "*".equals(s) || "/".equals(s) ||
	  "%".equals(s) || "\\".equals(s) ||
	  "^".equals(s) || "_".equals(s);
}

/** Liefert true, wenn s eine double-Zahl ist */
protected static boolean isVal(String s) {
	try{
		Double.valueOf(s);
		return true;
	}catch(NumberFormatException exc){
		return false;
	}
}

/** Liefert die Nummer der Konstanten */
protected static int nameConst(String func) {
	for(int i=0; i<constnames.length; i++)
		if (constnames[i].name.equals(func))
			return constnames[i].func;

	return 0;
}

/** Liefert die Nummer der Funktion */
protected static int nameFunc(String func) {
	for(int i=0; i<funcnames.length; i++)
		if (funcnames[i].name.equals(func))
			return funcnames[i].func;

	return NOFUNC;
}
/**
 * Liefert das binaere Operationszeichen.
 * @return int
 * @param op char
 */
protected static int nameOp(char c) {
	return c=='+' ? ADD : c=='-' ? SUB : c=='*' ? MUL
		: c=='/' ? DIV : c=='%' ? MOD : c=='\\' ? IDIV
		: c=='^' ? OPOW : 0;
}
/**
 * Liefert das Operationszeichen eines binaeren Operators.
 * @return char
 * @param op int
 */
protected static char opName(int op) {
	switch(op){
		case ADD: return '+';
		case SUB: return '-';
		case MUL: return '*';
		case DIV: return '/';
		case MOD: return '%';
		case IDIV:return '\\';
		case OPOW:return '^';
	}
	throw new IllegalArgumentException("Kein Operator: "+op);
}
/**
 * 
 * @return java.lang.String
 */
String opString(int op) {
	String s;
	switch(op){
		case ADD: return "+";
		case SUB: return "-";
		case MUL: return "*";
		case DIV: return "/";
		case MOD: return "%";
		case IDIV:return "\\";
		case OPOW:return "^";
		case NEG: return "_";
		case ZAHL:return "ZAHL";
		case CPI: return "CPI";
		case CE:  return "CE";
		case CVARX: return "CVARX";
		case CVARP: return "CVARP";
		case CVARQ: return "CVARQ";
		case CVARI: return "CVARI";
		case FUNC0: return "FUNC0";
		case FUNC1: return "FUNC1";
		case FUNC2: return "FUNC2";
		case FUNC3: return "FUNC3";
	}
	return "["+op+"]";
}
/**
 * 
 * @return int
 * @param op int
 */
protected static int prioritaet(int op) {
	for (int i=0; i<prioritaet.length; i++)
		if (prioritaet[i][0]==op)
			return prioritaet[i][1];
	return 100;
}
}