// Code by Will Guaraldi - guaraldi@ccs.neu.edu
// Version 1.0 11/9/2006
// Created for CSG260 Fall 2006 with Karl Lieberherr
package edu.neu.ccs.satsolver;

/**
 * This class implements polynomials of at most degree 3.  This is
 * used by appmean to approximate mean.
 *
 * Code is heavily influenced on Daniel's implementation which we
 * saw in class.  Having said that, I'm not sure how else it could
 * be implemented.
 */
public class Polynomial implements PolynomialI {

  /**
   * Exception that we occasionally throw when we're asked to do
   * things against our contract.
   */
  public static class PolynomialException extends Exception { 
    public PolynomialException(String msg) {
      super(msg);
    }
  }

  /**
   * Holds 256 polynomials--one for each R.
   */
  public static Polynomial[] m_polys;

  /**
   * Statically pre-compute all the polynomials that we'll need.
   */
  static {
    m_polys = new Polynomial[256];

    for(int r=0; r < 256; r++) {
      int q0, q1, q2, q3;
      Polynomial p;

      // NOTE: since all of our Rs have rank 3, we treat them
      // all as such.
      q0 = Relation.q(r, 0);
      q1 = Relation.q(r, 1);
      q2 = Relation.q(r, 2);
      q3 = Relation.q(r, 3);
      p = new Polynomial(q3 - q2 + q1 - q0,
                         q2 - (2 * q1) + (3 * q0),
                         q1 - (3 * q0),
                         q0);

      m_polys[r] = p;
    }
  }

  public final double m_x3; // a x^3
  public final double m_x2; // b x^2
  public final double m_x1; // c x
  public final double m_x0; // d

  private Polynomial(double x3, double x2, double x1, double x0) {
    m_x3 = x3;
    m_x2 = x2;
    m_x1 = x1;
    m_x0 = x0;
  }

  /**
   * This is a convenience method because so many things are
   * in terms of int.
   */
  private Polynomial(int x3, int x2, int x1, int x0) {
    this((double) x3, (double) x2, (double) x1, (double) x0);
  }

  public static Polynomial getPolynomial(PolynomialI poly) {
    if (poly instanceof Polynomial) {
      return (Polynomial) poly;
    }

    return new Polynomial(poly.getCoefficient(3),
                          poly.getCoefficient(2),
                          poly.getCoefficient(1),
                          poly.getCoefficient(0));
  }

  /**
   * Factory method (sort of) that returns the correct Polynomial
   * instance.  The internal members of the Polynomial are
   * accessable, but they are final, so you can't change them.
   */
  public static Polynomial getPolynomial(int r) {
    return m_polys[r];
  }
  
  /**
   * This returns the derivative of this polynomial.
   */
  public Polynomial derivative() {
    return new Polynomial(0, 3 * m_x3, 2 * m_x2, m_x1);
  }

  /**
   * Takes an x and computes the polynomial for that x.
   */
  public double compute(double x) {
    return (((((m_x3 * x) + m_x2) * x) + m_x1) * x) + m_x0;
  }

  public double eval(double x) {
    return compute(x);
  }

  /**
   * Adds this polynomial to an input polynomial producing
   * a new polynomial instance.
   */
  public Polynomial add(Polynomial p) {
    return new Polynomial(p.m_x3 + m_x3,
                          p.m_x2 + m_x2,
                          p.m_x1 + m_x1,
                          p.m_x0 + m_x0);
  }

  /**
   * Returns a polynomial multiplied by a double.
   */
  public Polynomial multiplyByDouble(double n) {
    return new Polynomial(m_x3 * n,
                          m_x2 * n,
                          m_x1 * n,
                          m_x0 * n);
  }
  
  /**
   * This solves for polynomial = 0 and returns the solutions.
   *
   * For polynomials of degree 1, this returns an array of
   * one element which has the single solution.
   *
   * For polynomials of degree 2, this returns an array of
   * two elements--one for each solution.
   *
   * Note, it only handles polynomials of degree 2 and 1.
   */
  public double[] solveForZero() throws PolynomialException {
    if (m_x3 != 0) {
      throw new PolynomialException("Cannot solve polynomials of degree 3.");
    }
    
    // if there is no a term, then we don't need the
    // quadratic formula.
    if (m_x2 == 0) {
      // skip division by zero solutions
      if (m_x1 == 0) {
        return new double[0];
      }
      double[] solutions = new double[1];
      solutions[0] = (0.0 - m_x0) * 1.0 / m_x1;
      return solutions;
    }

    double sqrt_num = (m_x1 * m_x1) - (4.0 * m_x2 * m_x0);
    if (sqrt_num < 0) {
      return new double[0];
    }

    double sqrt_part = Math.sqrt(sqrt_num);
    
    double[] solutions = new double[2];
    
    solutions[0] = (0.0 - m_x1 + sqrt_part) / (2.0 * m_x2);
    solutions[1] = (0.0 - m_x1 - sqrt_part) / (2.0 * m_x2);
    
    return solutions;
  }

  public double getCoefficient(int degree) {
    if (degree == 0) {
      return m_x0;
    } else if (degree == 1) {
      return m_x1;
    } else if (degree == 2) {
      return m_x2;
    } else if (degree == 3) {
      return m_x3;
    }
    throw new IllegalArgumentException("Degree should be between 0 and 3.");
  }

  /**
   * A polynomial is equal to another polynomial iff the
   * coefficients are all the same.
   */
  public boolean equals(Object o) {
    if (o instanceof Polynomial) {
      Polynomial p = (Polynomial) o;

      return p.m_x3 == m_x3 && p.m_x2 == m_x2 && 
        p.m_x1 == m_x1 && p.m_x0 == m_x0;

    }
    return false;
  }

  /**
   * Hash code so that we can hash these if we ever need to.
   */
  public int hashCode() {
    return toString().hashCode();
  }

  /**
   * toString method so that polynomials are easier to debug.
   */
  public String toString() {
    return "" + m_x3 + "x^3 + " + m_x2 + "x^2 + " + m_x1 + "x + " + m_x0;
  }
}