/**
 * Code by Daniel Rinehart <danielr@neophi.com>
 * Created for CSG260 Fall 2006 with Karl Lieberherr
 */
/**
 * Generic polynomial class. All polynomials returned by this class are
 * immutable.
 */
public class Polynomial implements PolynomialI {
	/**
	 * Maximum difference between two doubles for them to be considered equal.
	 */
	public static final double DELTA = Math.pow(10, -8);

	private double coefficients[] = new double[4];

	/**
	 * Create a new polynomial with the given coefficients.
	 * 
	 * @param x_3
	 *            Coefficient for x^3
	 * @param x_2
	 *            Coefficient for x^2
	 * @param x_1
	 *            Coefficient for x^1
	 * @param x_0
	 *            Coefficient for x^0
	 */
	public Polynomial(double x_3, double x_2, double x_1, double x_0) {
		coefficients[3] = x_3;
		coefficients[2] = x_2;
		coefficients[1] = x_1;
		coefficients[0] = x_0;
	}

	/**
	 * Used internally when creating results.
	 */
	private Polynomial() {
	}

	/**
	 * Multiple all coefficients in the polynomial by the given value.
	 * 
	 * @param value
	 *            Value to multiply by
	 * @return Polynomial with all values multiplied
	 */
	public Polynomial multiply(double value) {
		Polynomial result = new Polynomial();
		for (int i = 0; i < coefficients.length; i++) {
			result.coefficients[i] = coefficients[i] * value;
		}
		return result;
	}

	/**
	 * Add one polynomial to another.
	 * 
	 * @param polynomial
	 *            Polynomial to add
	 * @return Sum of the two polynomials
	 */
	public Polynomial add(Polynomial polynomial) {
		Polynomial result = new Polynomial();
		for (int i = 0; i < coefficients.length; i++) {
			result.coefficients[i] = coefficients[i] + polynomial.coefficients[i];
		}
		return result;
	}

	/**
	 * Subtract one polynomial from another.
	 * 
	 * @param polynomial
	 *            Polynomial to subtract
	 * @return Difference of the two polynomials
	 */
	public Polynomial subtract(Polynomial polynomial) {
		Polynomial result = new Polynomial();
		for (int i = 0; i < coefficients.length; i++) {
			result.coefficients[i] = coefficients[i] - polynomial.coefficients[i];
		}
		return result;
	}

	/**
	 * Compute and return the derivative of the polynomial.
	 * 
	 * @return Derivative
	 */
	public Polynomial differentiate() {
		Polynomial result = new Polynomial();
		result.coefficients[2] = coefficients[3] * 3;
		result.coefficients[1] = coefficients[2] * 2;
		result.coefficients[0] = coefficients[1];
		return result;
	}

	/**
	 * Return the coefficient for the given degree.
	 * 
	 * @param degree
	 *            Degree to return
	 * @return Coefficient
	 */
	public double getCoefficient(int degree) {
		return coefficients[degree];
	}

	/**
	 * Return the degree of the polynomial.
	 * 
	 * @return degree
	 */
	public int degree() {
		for (int i = 3; i > 0; i--) {
			if (!equal(0.0, coefficients[i])) {
				return i;
			}
		}
		return 0;
	}

	/**
	 * Solve the polynomial for when it equals 0.
	 * 
	 * @return Array of solutions
	 */
	public double[] solve0() {
		int degree = degree();
		if ((degree == 3) || (degree == 0)) {
			throw new UnsupportedOperationException("Can't solve degree " + degree + ".");
		}
		if (degree == 2) {
			double temp = coefficients[1] * coefficients[1] - 4 * coefficients[2] * coefficients[0];
			if (temp < 0.0) {
				return new double[] {};
			}
			double plus = (-coefficients[1] + Math.sqrt(temp)) / (2 * coefficients[2]);
			double minus = (-coefficients[1] - Math.sqrt(temp)) / (2 * coefficients[2]);
			return new double[] { plus, minus };
		}
		return new double[] { (-coefficients[0]) / coefficients[1] };
	}

	/**
	 * Compute the value of the polynomial for the given x.
	 * 
	 * @param x
	 *            X
	 * @return value
	 */
	public double eval(double x) {
		double result = 0;
		for (int i = coefficients.length - 1; i > 0; i--) {
			result += coefficients[i];
			result *= x;
		}
		result += coefficients[0];
		return result;
	}

	/**
	 * Find the value of x which maximizes the value of the polynomial given by
	 * the coefficients over the domain 0 to 1 inclusive.
	 * 
	 * @return best value of x
	 */
	public double maxX0To1() {
		// find best between maximum and minimum of domain
		double result = 0.0;
		double best = eval(0.0);
		double test = eval(1.0);
		if (test > best) {
			result = 1.0;
			best = test;
		}
		// if it is more than just a line we need to check
		// for interesting points between 0 and 1
		if (degree() > 1) {
			// when the derivative is 0 we have a stationary point
			// which could be a local maximum, minimum, or inflection
			// for each such value check to see if it gives a higher
			// value for y
			double results[] = differentiate().solve0();
			if (results.length > 0) {
				for (int i = 0; i < results.length; i++) {
					if ((results[i] > 0.0) && (results[i] < 1.0)) {
						test = eval(results[i]);
						if (test > best) {
							result = results[i];
							best = test;
						}
					}
				}
			}
		}
		return result;
	}

	/**
	 * @see java.lang.Object#toString()
	 */
	public String toString() {
		StringBuffer data = new StringBuffer();
		for (int i = coefficients.length - 1; i >= 0; i--) {
			if (!equal(0.0, coefficients[i])) {
				if ((data.length() > 0) && (coefficients[i] > 0.0)) {
					data.append("+");
				}
				if ((i > 0) && (equal(-1.0, coefficients[i]))) {
					data.append("-");
				} else if ((i == 0) || (!equal(1.0, coefficients[i]))) {
					data.append(coefficients[i]);
				}
				if (i > 0) {
					data.append("x");
					if (i > 1) {
						data.append("^");
						data.append(i);
					}
				}
			}
		}
		return data.toString();
	}

	/**
	 * Determine if the two values are equal 0 within the set tolerance.
	 * 
	 * @param a
	 *            Value a
	 * @param b
	 *            Value b
	 * @return True if equal within tolerance
	 */
	public static boolean equal(double a, double b) {
		return (Math.abs(a - b) <= DELTA);
	}
}