public class Polynome extends MiniJava {

	public static int[] quadraticFormula(double[] coefficients) {
		double discriminant = Math.pow(coefficients[1], 2) - 4 * coefficients[0] * coefficients[2];

		if (discriminant < 0) // keine Lösung
			return new int[0];

		if (discriminant == 0) // genau eine Lösung
			return new int[] { (int) (-0.5 * coefficients[1] / coefficients[0]) };

		double sqrt = Math.sqrt(discriminant);
		int[] sol = new int[2]; // zwei Lösungen
		sol[0] = (int) (0.5 * (-coefficients[1] + sqrt) / coefficients[0]);
		sol[1] = (int) (0.5 * (-coefficients[1] - sqrt) / coefficients[0]);
		return sol;
	}

	public static double[] hornerSchema(double[] coefficients, int x0) {
		double[] result = new double[3];  // 3. Zeile der Tabelle
		
		// 1.
		result[0] = coefficients[0];
		
		// 2.
		result[1] = coefficients[1] + x0*result[0];
		result[2] = coefficients[2] + x0*result[1];
		
		return result;
	}

	public static double calculateY(double[] coefficients, int x) {
		double result = 0;
		int exponent = coefficients.length-1;  // bei Grad 3: Länge 4 -> 4-1=3
		
		for (double coef : coefficients)
			result += coef * Math.pow(x, exponent--);
		
		return result;
	}

	public static int[] findIntervalRecursive(double[] coeffizients, int a, int b, int factor) {
		double f_a = calculateY(coeffizients, a);
		double f_b = calculateY(coeffizients, b);
		
		if (f_a > 0 == f_b > 0 && f_a != 0 && f_b != 0) { // same sign
			return findIntervalRecursive(coeffizients, a*factor, b*factor, factor);
		} // else: Unterschiedliches Vorzeichen oder mind. einer ist schon 0
		
		if (a < b)  // kleinere Zahl immer zuerst
			return new int[] {a, b};
		else
			return new int[] {b, a};
	}

	public static int findRootRecursive(double[] coefficients, int a, int b) {
		// 1. Mittelpunkt berechnen
		int m = (a+b) / 2;
		
		// 2. Nullstelle gefunden?
		double f_a = calculateY(coefficients, a);
		if (f_a == 0)
			return a;
		double f_b = calculateY(coefficients, b);
		if (f_b == 0)
			return b;
		double f_m = calculateY(coefficients, m);
		if (f_m == 0)
			return m;
		
		// 3. & 4.
		if (f_a > 0 != f_m > 0) {  // unterschiedliche Vorzeichen
			return findRootRecursive(coefficients, a, m);
		} else {  // f(b) und f(m) müssen unterschiedlich sein (bei korrekten Param.)
			return findRootRecursive(coefficients, m, b);
		}
	}

	public static void main(String[] args) {
		// Koeffizienten einlesen:
		double[] input = new double[4];
		for (int i = 0; i < input.length; i++)
			input[i] = readDouble("Bitte a_" + (input.length-1-i) + " eingeben:");
		// Ausgabestring:
		String output = "Die Nullstellen des Polynoms\n\n";
		output += polynomToString(input);
		output += "\n\nsind:\n\n";

		int[] x = new int[3];  // Array für alle Nullstellen (maximal 3)
		int amountRoots = 0;  // Zähler für die Anzahl Nullstellen (-1 =~ unendlich viele)
		
		if (input[0] != 0) {  // Grad = 3
			// Bestimmung des passenden Intervalls:
			int[] interval = findIntervalRecursive(input, -1, 1, 10);
		
			// Bestimmung der ersten Nullstelle:
			x[amountRoots++] = findRootRecursive(input, interval[0], interval[1]);
			
			// Reduktion des Polynoms:
			double[] quadratic = hornerSchema(input, x[0]);
			System.out.println(java.util.Arrays.toString(quadratic));
			
			// Bestimmung der übrigen Nullstellen mittels Lösungsformel
			int[] xn = quadraticFormula(quadratic);
			
			// In Array einfügen:
			if (xn.length >= 1) {
				if (xn[0] != x[0]) // noch nicht enthalten
					x[amountRoots++] = xn[0];
				if (xn.length == 2)
					if (xn[0] != x[0] && (amountRoots < 2 || xn[0] != x[1]))
						x[amountRoots++] = xn[1];
			}
		} else if (input[1] != 0) {  // Grad = 2
			// Bestimmung der Nullstellen einer quadratischen Gleichung
			int[] xn = quadraticFormula(java.util.Arrays.copyOfRange(input, 1, input.length));

			// In Array einfügen:
			if (xn.length >= 1) {
				x[amountRoots++] = xn[0];
				if (xn.length == 2 && xn[1] != x[0])
					x[amountRoots++] = xn[1];
			}
		} else if (input[2] != 0) {  // Grad = 1
			x[amountRoots++] = (int) -(input[3] / input[2]);
		} else if (input[3] != 0) {  // Grad = 0 / Konstante
			// amountRoots = 0 (bereits gesetzt)
		} else {  // keine Nullstelle
			amountRoots = -1;
		}
		
		// Ausgabe:
		if (amountRoots == 0)
			output += "Keine";
		else if (amountRoots == -1)
			output += "Unendlich viele (jedes x)";
		else 
			for (int i = 0; i < amountRoots; i++)
				output += "x_" + i + " = " + x[i] + "\n";
		write(output);
	}
	
	// Gibt ein Polynom beliebigen Grades als String zurück.
	public static String polynomToString(double[] coefficients) {
		String result = "";
		
		for (int i = 0; i < coefficients.length; i++) {
			if (coefficients[i] == 0)  // keine Ausgabe
				continue;
			
			result += (coefficients[i] > 0) ? '+' : '-';
			
			double c = Math.abs(coefficients[i]);
			int exponent = coefficients.length-1-i;
			
			if (c != 1 || exponent == 0)
				if (c == (int) c)
					result += (int) c;
				else 
					result += c;

			if (exponent != 0) {
				result += "x";
				
				if (exponent == 1);
				else if (exponent == 2)
					result += '²';
				else if (exponent == 3)
					result += '³';
				else if (exponent <= 9)
					result += (char)('\u2070'+exponent);
				else 
					result += "^" + exponent;
			}
		}
		
		return result;
	}

}