package poly;
/**
* Represents the non-constant polynomial type.  Holds a postive degree (or order)
* and a polynomial of lower order.
 <pre>
 * Copyright 2000, by Dung X. Nguyen, All rights reserved.
 </pre>
* @author Dung X. Nguyen
*/
class NonConstPoly extends APolynomial
{
   /**
   * Data Invariant: 0 < _degree.
   */
	private int _degree;

   /**
	 * Data Invariant: _lowerPoly._degree < _degree.
	 * @SBGen Variable (,lower order polynomial,,64)
	 */
	private APolynomial _lowerPoly;

	/**
   * Initializes this NonConstPoly to the given coefficient, degree, and lower order
   * polynomial. Should be called only by PolyFactory.MakePoly (..) which checks for valid
   * input parameters.
   * @param coef the coefficient
   * @param degree the degree
   * @param lowPoly the lower ordered polynomial
   */
	NonConstPoly (double coef, int degree, APolynomial lowPoly)
	{
      _coef = coef;
      _degree = degree;
      _lowerPoly = lowPoly;
	}

	public int getDegree ()
	{
		 return _degree;
	}

	public APolynomial getLowerPoly ()
	{
		 return _lowerPoly;
	}

	/**
   * Compares this NonConstPoly's own degree with the degree of the APolynomial parameter
   * p and compute the sum according to the following 3 cases.
   <pre>
   * p.getDegree () < this.getDegree(): the sum consists of the highest order term of
   *   this NonConstPoly plus the sum of the lower order polynomial with p.
   * p.getDegree () == this.getDegree(): the coefficient of the highest order term of the sum
   *   is the sum of the two coefficients.  The lower order terms of the sum is the sum
   *   of the lower order polynomial of this NonConstPoly and the lower order polynomial of p.
   * p.getDegree () > this.getDegree(): the sum consists of the highest order term of
   *   p plus the sum of this NonConstPoly with the lower order polynomial of p.
   </pre>
   */
	public APolynomial add (APolynomial p)
	{
      double pCoef = p.getLeadCoef();  // avoid making repeated calls to getLeadCoef()
      int pDegree = p.getDegree();     // and getDegree().
      if (pDegree < _degree)
      {
         return PolyFactory.MakePoly (_coef, _degree, _lowerPoly.add (p));
      }
      if (pDegree == _degree)
      {
         return PolyFactory.MakePoly (_coef + pCoef, _degree, _lowerPoly.add (p.getLowerPoly()));
         // NOTE how the factory simplifies the code here.
      }
      return PolyFactory.MakePoly  (pCoef, pDegree, add (p.getLowerPoly()));
	}

	/**
	 * Evaluates the leading term then adds the result to the value of the lower order
    * polynomial at x.
	 */
	public double eval (double x)
	{
		 return _coef * Math.pow (x, _degree) + _lowerPoly.eval (x);
	}

   /**
   * Calls _lowerPoly.evalHornerHelp to compute the value, passing _coef as the
   * accumulated value, and _degree as the order of the enclosing higher order polynomial.
   */
	public double evalHorner (double x)
   {
      return _lowerPoly.evalHornerHelp (x, _coef, _degree);
   }

   /**
   * Returns the String ax^n + String representation of the lower order polynomial, where
   * a is the coefficient and n is the order of this NonConstPoly.
   */
   public String toString ()
   {
      return Double.toString (_coef) + "x^" + Integer.toString (_degree) + _lowerPoly.toString4LowerPoly ();
   }

   /**
   * Called by an APolynomial that contains this NonConstPoly as its lower order polynomial.
   * Returns  " + " followed by the String representation of this NonConstPoly.
   */
   protected String toString4LowerPoly ()
   {
      return " + " + toString ();
   }

	/**
   * Passes the constant parameter down to the lower order polynomial to add, and
   * returns a NonConstPoly whose leading coefficient and degree are the same as
   * those of this NonConstPoly and whose constant term is the sum of this NonConstPoly's
   * constant term with the constant parameter.
   */
	protected APolynomial addConst (double c)
   {
      return PolyFactory.MakePoly (_coef, _degree, _lowerPoly.addConst (c));
   }

   /**
   * Computes the new accumulated value and pass it on to _lowerPoly.evalHornerHelp to finish the job.
   *<pre>
   * The new accumulated value is computed according to the formula:
   *    new acc = acc * Math.pow (x, preDegree - _degree) + _coef
   *</pre>
   */
	protected double evalHornerHelp (double x, double acc, int preDegree)
   {
      return _lowerPoly.evalHornerHelp (x, acc * Math.pow (x, preDegree - _degree) + _coef,  _degree);
   }

   /**
   * Implements the long division algorithm as described in many high school algebra books.
   */
   protected QRPair divmodInto(APolynomial dividend)
   {
      int dividendOrder = dividend.getDegree();
	   if (dividendOrder < _degree)
      {
         return new QRPair (PolyFactory.ZeroPoly, dividend);
      }
      double quotientCoef = dividend.getLeadCoef() / _coef;  // quotient's leading coefficient.
      int quotientOrder = dividendOrder - _degree; // quotient's degree.
      APolynomial prod = multMonomial (-quotientCoef, quotientOrder);  // multiply the divisor by the negative of the first term of the quotient,
      APolynomial diff = dividend.add (prod);                          // and add the resulting product to the dividend.
      if (dividendOrder == _degree)
      {
         return new QRPair (PolyFactory.MakeConstPoly(quotientCoef), diff);
      }
      QRPair tempResult = divmodInto (diff);  // perform long division on diff.
      return new QRPair (PolyFactory.MakePoly(quotientCoef, quotientOrder, tempResult._quotient), tempResult._remainder);
   }

   /**
   * Multiply the coefficients, add the degrees, and recur on the lower order polynomial.
   */
   protected APolynomial multMonomial (double coef, int degree)
   {
      return PolyFactory.MakePoly (_coef * coef, _degree + degree, _lowerPoly.multMonomial (coef, degree));
   }
}