package gleichung;

import java.util.*;
//import algds.IOUtils;
/**
 * 
 * 
 * @author Christian Semrau
 * <a href="mailto:Christian.Semrau@student.uni-magdeburg.de">
 * Christian.Semrau@student.uni-magdeburg.de</a>
 */
class GleichungValues {
	Thread me;
	boolean stopped;
	boolean mitDIV;

	int[] Xs;
	int Y;
	int[] opkomb;
	Vector loesungen;

	Hashtable ergebnisse;
	Hashtable tableTable;
/**
 * 
 * @param s java.lang.String
 */
public GleichungValues(String s, boolean div) {
	mitDIV = div;
	int[] I = filter(s);
	if (I==null||I.length<2){
		Xs = null; Y = 0;
	}else{
		Xs = new int[I.length-1];
		System.arraycopy(I,0,Xs,0,I.length-1);
		Y = I[I.length-1];
	}
	loesungen = new Vector();
}
/**
 * 
 */
public void calculate() {
	if (Xs.length<=0) return;
	int gesamtkomb = (int)Math.pow(mitDIV?4:3, Xs.length-1), aktkomb = 0;
	int allsum = 0;
	opkomb = new int[Xs.length-1];
	ergebnisse = new Hashtable();
	tableTable = new Hashtable();
	System.out.println("gesamtkomb:"+gesamtkomb);
	while (opkomb!=null){
		aktkomb++;

		Hashtable all = getTrees(0, Xs.length-1, true);
		allsum += all.size();
		boolean verbose = false;
//		System.out.println(all.size());
		for (Enumeration e = all.elements(); e.hasMoreElements(); ){
			GleichungBaum b = (GleichungBaum)e.nextElement();
			if (verbose)
				System.out.print(b);
			try{
				int result = b.calc();
				if (result==Y){
					loesungen.addElement(b);
					if (verbose){
						System.out.println(" = "+result+" Loesung");
					}
				}else
					if (verbose)
						System.out.println(" = "+result);
			}catch(ArithmeticException exc){
				if (verbose)
					System.out.println(" -> Exception "+exc);
			}
		}
		if (aktkomb%10==0)
			System.out.println(aktkomb+"/"+gesamtkomb);
		opkomb = Perm.nextComb_mWmR(mitDIV?4:3, opkomb);
	}

	System.out.println("allsum:"+allsum);
}
/**
 * 
 */
public void calculate(Thread me) {
	this.me = me;
	stopped = false;

	ergebnisse = new Hashtable();
	tableTable = new Hashtable();
	if (Xs.length<=0) return;

	if (me==null)
		System.out.println("working...");

	boolean verbose = false;

	ergebnisse = getResults(0, Xs.length-1, Xs.length-1);
	if (ergebnisse==null) return;

	sucheLoesung(Y, verbose);
	this.me = null;
}
/**
 * 
 * @return java.lang.String
 * @param start int
 * @param stop int
 */
public String createKey(int start, int stop) {
	String s = start+"-"+stop+" ";
	for(int i=start; i<stop; i++)
		s += GleichungBaum.opString(opkomb[i]);
	return s;
}
/**
 * 
 * @return boolean
 */
public int[] filter(String s) {
	StringTokenizer st = new StringTokenizer(s);
	int[] I = new int[st.countTokens()];
	int i = 0;
	while (st.hasMoreTokens())
		try{
			I[i++] = new Integer(st.nextToken()).intValue();
		}catch(NumberFormatException e){
			return null;
		}
	return I;
}
/**
 * 
 * @return java.util.Hashtable
 * @param start int
 * @param stop int
 */
public Hashtable getResults(int start, int stop, int depth) {
	if (stopped || start>stop)
		return null;

	Hashtable tbl = new Hashtable();
	if (start==stop){
		// nur ein Wert
		GleichungBaum b = new GleichungBaum(Xs[start], GleichungBaum.OP_NUL, null, null);
		tbl.put(""+b.calc(), b);
		return tbl;
	}

	// mehrere Werte
	for (int i = start; i<stop; i++){
		if (depth>=5){
			if (me!=null)
				me.yield(); // Rechenzeit abgeben
		}

		// beide Seiten berechnen
		Hashtable t1 = getResults(start, i, depth-1);
		if (t1==null) return null;
		Hashtable t2 = getResults(i+1, stop, depth-1);
		if (t2==null) return null;
		GleichungBaum b1, b2, b;

		int opTop = (mitDIV ? GleichungBaum.OP_DIV : GleichungBaum.OP_MUL);
		// beide Seiten mit allen Operatoren verknuepfen
		for (Enumeration e1 = t1.elements(); e1.hasMoreElements(); ){
			b1 = (GleichungBaum)e1.nextElement();
			for (Enumeration e2 = t2.elements(); e2.hasMoreElements(); ){
				b2 = (GleichungBaum)e2.nextElement();
				for (int op = GleichungBaum.OP_ADD; op <= opTop; op++){
					b = new GleichungBaum(0, op, b1, b2);
					try{
						String s = ""+b.calc();
						GleichungBaum bt = (GleichungBaum)tbl.get(s);
						if (bt==null || Math.random()>0.5) // b.evaluate()<=bt.evaluate())
							tbl.put(s, b);
					}catch(ArithmeticException exc){
					}
				}
			}
		}
	}
	return tbl;
}
/**
 * 
 * @return java.util.Vector
 * @param start int
 * @param stop int
 */
public Hashtable getTrees(int start, int stop, boolean neg) {
	Hashtable tbl;

	tbl = (Hashtable)tableTable.get(createKey(start, stop));
	if (tbl!=null)
		return tbl;

	tbl = new Hashtable();
	if (start==stop){
		GleichungBaum b;
		b = new GleichungBaum(Xs[start], GleichungBaum.OP_NUL, null, null);
		tbl.put(""+b.calc(), b);
		if (neg){
//			b = new GleichungBaum(-Xs[start], GleichungBaum.OP_NUL, null, null);
//			tbl.put(""+b.calc(), b);
		}
		tableTable.put(createKey(start, stop), tbl);
		return tbl;
	}

	for (int i = start; i<stop; i++){
		boolean n = (start==0) || (opkomb[i]!=GleichungBaum.OP_MUL && opkomb[i]!=GleichungBaum.OP_DIV);
		Hashtable t1 = getTrees(start, i, n);
		Hashtable t2 = getTrees(i+1, stop, false);
/*
		BitSet bs1n = new BitSet(); // negative
		BitSet bs1p = new BitSet(); // positive
		for (Enumeration e1 = t1.elements(); e1.hasMoreElements(); ){
			GleichungBaum b = (GleichungBaum)e1.nextElement();
			try{
				int r = b.calc();
				if (r<0) bs1n.set(-r); else bs1p.set(r);
			}catch(ArithmeticException exc){}
		}
		BitSet bs2n = new BitSet(); // negative
		BitSet bs2p = new BitSet(); // positive
		for (Enumeration e2 = t2.elements(); e2.hasMoreElements(); ){
			GleichungBaum b = (GleichungBaum)e2.nextElement();
			try{
				int r = b.calc();
				if (r<0) bs2n.set(-r); else bs2p.set(r);
			}catch(ArithmeticException exc){}
		}
*/
		for (Enumeration e1 = t1.elements(); e1.hasMoreElements(); ){
			GleichungBaum b1 = (GleichungBaum)e1.nextElement();
/*
			if (opkomb[i]==GleichungBaum.OP_MUL || opkomb[i]==GleichungBaum.OP_DIV){
				try{
					int r = b1.calc();
					if (r<0 && bs1p.get(-r))
						continue;
				}catch(ArithmeticException exc){
					continue;
				}
			}
*/
			for (Enumeration e2 = t2.elements(); e2.hasMoreElements(); ){
				GleichungBaum b2 = (GleichungBaum)e2.nextElement();
/*
				if (true){ //opkomb[i]==GleichungBaum.OP_MUL || opkomb[i]==GleichungBaum.OP_DIV){
					try{
						int r = b2.calc();
						if (r<0 && bs2p.get(-r))
							continue;
					}catch(ArithmeticException exc){
						continue;
					}
				}
*/
				GleichungBaum b = new GleichungBaum(0, opkomb[i], b1, b2);
				try{
					b.calc();
					tbl.put(""+b.toString(), b);
				}catch(ArithmeticException exc){
				}
			}
		}
	}
	tableTable.put(createKey(start, stop), tbl);
	return tbl;
}
/**
 * 
 * @param args java.lang.String[]
 */
public static void main(String args[]) {
	GleichungValues values;
//  1+2*3-4*(5+6-7*8*9) = 1979
//  (1-2-(3-4-5)*6*7)*8-9 = 1999
//  (1+2*(3*4*(5+6)-7))*8-9 = 1999
//  (1-2*(3-(4*5*6+7)))*8+9 = 2001
//  (1*2+3*4*(5+6))*(7+8)-9 = 2001
//  1+2*3*(4-5+6*7*8)-9 = 2002

//	values = new GleichungValues("2 3 4 5 6 100", false);
//	values.calculate(null);

//  (1+2*3+4+5)*(6+7*(8+9)) = 2000 (16*125, s.u.)
//  (1+2*3*4)*5*(6-7+8+9) = 2000 (25*5*16, s.u.)
//  (1-2-3)*(4+(5-6)*7*8*9) = 2000 (-4*-500, s.u.)
//  1*(2+3)*4*(5+(6+7)*8-9) = 2000 (5*4*100)
//  1*(2-( 3-(4+5+6)*(7+8) )*9) = 2000 (2-(-1998))
/*
erster Faktor (16):
1+2*3+4+5, 1-2+3*4+5, 1-2-3+4*5, (1+2)*(3+4)-5
1+(2+3)*4-5, 1+(2-3+4)*5, 1+(2-(3-4))*5, 1-(2+3)+4*5
1-(2+3-4*5), 1-2-(3-4*5), 1-(2-3*4)+5, 1-(2-3*4-5)
zweiter Faktor (125):
(6+7*(8+9))

erster Faktor (25*5): (1+2*3*4)*5
zweiter Faktor (16): 6-7+8+9, 6-(7-8)+9, 6-(7-8-9)

erster Faktor (-4): 1-(2+3), 1-2-3
zweiter Faktor (-500): 4+(5-6)*7*8*9, 4+5/6-7*8*9, 4-(5/6+7)*8*9, 4-5/6-7*8*9
*/
	String params = "";
	for (int i=0; i<args.length; i++)
		params += args[i]+" ";

	if (params.length()>0)
		values = new GleichungValues(params, true);
	else{
		System.out.println("Syntax (xi sind die Zahlen, y ist das Ergebnis):");
		System.out.println("java gleichung.GleichungValues x1 x2 x3 ... xn y");
		return;
	}

	values.calculate();

	System.out.println();
	for (int i = 0; i<values.loesungen.size(); i++)
		System.out.println(values.loesungen.elementAt(i).toString());
	System.out.println("loesungen:"+values.loesungen.size());

	System.out.println("calc:"+GleichungBaum.calcs+" creates:"+GleichungBaum.creates
		+" ergebnisse:"+values.ergebnisse.size()
		+" tableTable:"+values.tableTable.size());
}
/**
 * 
 * @param Y int
 */
public void sucheLoesung(int Y, boolean verbose) {
	this.Y = Y;
	loesungen = new Vector();
	for (Enumeration e = ergebnisse.elements(); e.hasMoreElements(); ){
		GleichungBaum b = (GleichungBaum)e.nextElement();
		if (verbose)
			System.out.print(b);
		try{
			int result = b.calc();
			if (result==Y){
				loesungen.addElement(b);
				if (verbose){
					System.out.println(" = "+result+" Loesung");
				}
			}else
				if (verbose)
					System.out.println(" = "+result);
		}catch(ArithmeticException exc){
			if (verbose)
				System.out.println(" -> Exception "+exc);
		}
	}
}
/**
 * 
 * @return java.lang.String
 */
public String toString() {
	if (loesungen==null || loesungen.size()<=0) return "-";
	return loesungen.elementAt(0).toString()+" = "+Y;
}
}