Comp 212 Homework 3
Polynomials

Due Monday, Oct 30, 2000 10:00 AM.

This homework illustrates the use of abstraction to implement polynomial and turn it into what is coined as a "component software".  It makes use of the visitor pattern, the composite pattern, and the abstract factory pattern.

Polynomials

A polynomial of one variable, p(x),  is an expression of the form

a_nxⁿ + a_n-1x^n-1+ ... + a₁x + a₀,

where n is a non-negative integer, a_k  (k = 0.. n) are numbers, and a_n is a number not equal to 0. 

n is called the degree (or order) of p(x),a_k  (k = 0.. n) are called the coefficients of p(x), and a_n is called the leading coefficient of p(x). 

For examples:

• p(x) = 12x⁵ - 3x² + 7 is a polynomial of degree (order) 5 with leading coefficient 12.  -3x² + 7 is called the lower order polynomial for p(x).
• p(x) = 7 is a polynomial of degree 0 with leading coefficient 7.   This is an example of a constant polynomial.  It has no lower order polynomial.

We can describe polynomials  in the following manner.  There is an abstraction called polynomial.  A constant polynomial is a polynomial with a leading coefficient and degree (order) 0.  A non-constant polynomial is a polynomial with a leading coefficient, a non-zero degree, and a lower order polynomial.  The polynomial's intrinsic behavior is to provide the clients with its degree -getDegree (), its leading coefficient - get LeadCoef (), and its lower order polynomial (if any) - getLowerPoly ().  Polynomials can be viewed as having an immutable linear recursive structure and can be implemented using the composite pattern.  All extrinsic algorithms on polynomials can be implemented as visitors to polynomials. 

Your task is to design a system of classes to implement polynomials as prescribed below.

Implementation Details

package poly:

In this package, define the following two abstrat classes and one inteface.

/**
* Represents the set of all polynomials of one variable with real coefficients.
*/
public abstract class APolynomial
{
    /**
    * @return the String representation of this APolynomial.
    */
    public String toString ()
    {
        // student to write code uisng anonymous classes.
    }
    /**
    * @return the leading coefficient of this APolynomial.
    */
    public abstract double getLeadCoef();

    /**
    * @return the degree (or order) of this APolynomial.
    */
    public abstract int getDegree ();

    /**
    * @return the lower ordered polynomial of this APolynomial, if any.
    * @exception throws java.util.NoSuchElementException if the referencing polynomial is a constant.
    */
    public abstract APolynomial getLowerPoly ();

    /**
    * The hook method for this APolynomial to call on its IAlgo visitors.
    * @param algo an algorithm on this APolynomial.
    * @param input the input needed by algo.
    * @return the output object for algo.
    */
    public abstract Object execute(IVisitor algo, Object input);
}

/**
* Abstract polynomial algorithms as visitors to APolynomial.
*/
public abstract interface IVisitor
{
    /**
    * Algorithm for the case of constant polynomials.
    * @param poly a constant polynomial.
    * @param input an input object needed by this IVisitor.
    */
    public abstract Object forConst(APolynomial poly, Object input);

    /**
    * Algorithm for the case of non-constant polynomials.
    * @param poly a non-constant polynomial.
    * @param input an input object needed by this IVisitor.
    */
    public abstract Object forNonConst(APolynomial poly, Object input);
}

/**
* Abstract factory to properly manufacture concrete instances of Apolynomial.
*/
public abstract class APolyFactory
{
    /**
    * Creates a constant polynomial with a given coefficient.
    * @param coef the coefficient for the constant polynomial to be created.
    * @return a constant polynomial with coefficient coef.
    */
    public abstract APolynomial makeConstPoly(double coef);

    /**
    * Creates a non-constant Polynomial with a given leading coefficient, a given degree,
    * and a given lower order polynomial.
    * Checks for legal input parameters.
    * Ignores zero leading coefficient.
    * @param coef the leading coefficient (may be 0).
    * @param degree the degree, >= 0.
    * @param lowPoly != null, the lower ordered polynomial with degree < degree.
    * @return a non-constant Polynomial with appropriate leading coefficient, degree, and lower order term.
    * @exception throws IllegalArgumentException if conditions on degree and lowerPoly are violated.
    */
    public abstract APolynomial makePoly(double coef, int degree, APolynomial lowerPoly);
}

package poly.composite:

In this package, implement the following concrete factory class.

public class PolyFactory extends APolyFactory
{
   // singleton PolyFactory.
   
    public APolynomial makeConstPoly (double coef)
    {
        // student to write code.
    }

    public APolynomial makePoly (double coef, int degree, APolynomial lowerPoly)
    {
        // student to write code.
    }

    /**
    * Private static nested class representing the constant polynomial type.
    */
    private static class ConstPoly extends APolynomial
    {
        // Make the zero polynomial unique and sharable.
        public final static ConstPoly ZeroPoly = new ConstPoly (0.0);

        private double _coef;

// student to write code for constructor and the inherited methods.
    }


    /**
    * Private static nested class representing the non-constant polynomial type.
    * Uses the composite pattern.
    */
    private static class NonConstPoly extends APolynomial
    {
        private double _coef;

        /**
        * Data Invariant: 0 < _degree.
        */
        private int _degree;

        /**
        * Data Invariant: _lowerPoly != null and _lowerPoly._degree < _degree.
        */
        private APolynomial _lowerPoly;

        /**
        * @param coef the coefficient != 0.
        * @param degree the degree, > 0.
        * @param lowPoly the lower ordered polynomial.
        */
        public NonConstPoly(double coef, int degree, APolynomial lowPoly)
        {// NO NEED to check for valis input parameters here.  The factory will do all checking.
            _coef = coef;
            _degree = degree;
            _lowerPoly = lowPoly;
        }

// student to write code for inherited methods.
    }
}

package poly.visitor:

In this package, implement the following visitors.

1. Add, a visitor to add a polynomial to the host and return the resulting sum polynomial.  Add should take an APolyFactory as input parameter to the constructor, and the right-hand-side polynomial operand as the input parameter.  Use anonymous inner classes as helpers.
   
2. Mul, a visitor to multiply a polynomial to the host and return the resulting sum polynomial.  Mul should take an APolyFactory as input parameter to the constructor, and the right-hand-side polynomial operand as the input parameter.  Use anonymous inner classes as helpers.
   
3. LongDiv, a visitor to perform long division on polynomials as described by the following.  The host polynomial is the divisor; the input parameter is the dividend polynomial; the result to be returned is the pair of quotient/remainder polynomials defined by:
   /**
   * Holds the quotient/remainder pair for polynomial long division.
   */
   public class QRPair
   {
       public APolynomial quotient;
       public APolynomial remainder;
   
       public QRPair (APolynomial q, APolynomial r)
       {
           quotient = q;
           remainder = r;
       }
   }
   LongDiv should take an APolyFactory as input parameter to the constructor.  Use anonymous inner classes as helpers.
   
4. EvalHorner to evaluate the host polynomial at a "point" x using Horner's algorithm:
   
   a_nxⁿ + a_n-1x^n-1+ ... + a₁x + a₀ = ((..(a_nx + a_n-1) x + a_n-2)x + a_n-3)x + ... + a₁)x + a₀
   
   You may use the standard double Math.pow (double a, double b)to compute a^b.  Look for java.lang.Math.pow in the JDK documentation.
   EvalHorner should take an APolyFactory and a double (the value x to be evaluated at) as input parameters to the constructor.  Use anonymous inner classes as helpers.

For each of the above problems, be sure to add test cases which cover all reasonable cases. For instance, the visitor EvalHorner should be tested on constant polynomials.  The client test program may be in the default (no-name) package.   Since polynomials are mathematical objects that are intrinsically immutable, all polynomials in this exercise should NOT be modified once they are manufactured by a factory.

As with all programs in this course, lack of good coding style (good style includes reasonable variable names, a header before each non-overridden function, reasonable indentation) will result in a substantial loss of points.

Submission

The homework is due Moday, Oct. 30, 2000 at 10 AM.  It is to be submitted electronically.   No late submission will be accepted.  The complete homework set should contain the following:

• An ASCII README file to indicate what you have and/or have not done, and to point out specific details that you feel we need to know when grading your work. 
• StructureBuilder's UML diagrams of all your class designs.
• All the Java source code necessary to compile and execute your test code.