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.

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

a_{n}x^{n} + a_{n-1}x^{n-1}+
... + a_{1}x + a_{0},

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
^{5}- 3x^{2}+ 7 is a polynomial of degree (order) 5 with leading coefficient 12. -3x^{2}+ 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.

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);

}

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.

}

}

In this package, implement the following visitors.

- 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.

- 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.

- 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.

`EvalHorner`

to evaluate the host polynomial at a "point" x using Horner's algorithm:

a_{n}x^{n}+ a_{n-1}x^{n-1}+ ... + a_{1}x + a_{0}= ((..(a_{n}x + a_{n-1}) x^{ }+ a_{n-2})x^{ }+ a_{n-3})x + ... + a_{1})x + a_{0 }

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.

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.

dxnguyen@cs.rice.edu Please let us know of any broken links Revised Oct 23, 2000