Sample Assignment: Cleaning Up the Polynomial Class
(Chapter 3)



Data Structures and Other Objects Using C++
Third Edition
by Michael Main and Walter Savitch
ISBN 0-321-19716-X

NO DYNAMIC ARRAYS YET!
We won't yet incorporate dynamic arrays into our polynomial. Read on to see why...

The Assignment:
For this assignment, you must first complete the preliminary polynomial from the previous assignment. That was probably your first significant class implementations and it contains a number of potential pitfalls. So, for this assignment, you will take a careful look at your polynomial implementation, clean up any mistakes or inefficiencies, and also make sure that the work is in a good form for future modification.

The new work has only one new member function, and one modification to an existing member function.

When you submit this assignment, it will be graded by the TA for correctness and adherance to the items listed below.

Bonuses:
There are two possibilities of bonuses. In order to earn either of these bonuses, you will need to have 100% attendance in class over the next few weeks (or let me know ahead of time if you have an unavoidable conflict):
  1. If your initial submission of the polynomial needed very few changes, then the instructors may assign bonus points to that homework!
  2. If your initial submission of the polynomial got very few points from Dora (or no points at all) and you fix those problems for this assignment, then the instructors may give some of those lost points back to you.

Purposes:
Ensure that you have done your best possible job on your first significant class. Also, to make sure that your class is set up in a way that will make future modifications easy.

Cleaning Up the Polynomial Class Using a Fixed Array

The Constructor
Simplify your constructor to just these steps:
  1. Check the precondition with assert.
  2. Fill the array with zeros. Use the fill_n function from <algorithm>, as shown here:
    fill_n(coef, CAPACITY, 0.0);
  3. Set the current_degree to zero.
  4. Use the assign_coef function to set the specified term.

add_to_coef
Simplify to just two steps:
  1. Check the precondition with assert.
  2. Call assign_coef to change the specified term in the right way.

clear
Make sure that this function sets current_degree to zero.

assign_coef
This one must check its precondition and then set coef[exponent] to equal the new coefficient. Since this function has change the coef array, it is now responsible for making sure that current_degree is still correct. There are two cases that you must check:
  1. If the exponent is greater than the current_degree, and the coefficient is not zero, then the degree has just increased to exponent.
  2. Another possibility is that the degree has dropped. This occurs when the coefficient of the current_degree has been reset to zero. My suggestion is to handle the resetting with a small loop. The loop continues as long as the current_degree is above zero, and the coef[current_degree] is equal to zero. In this case, reduce the current_degree by one. Eventually the loop will end (when the current_degree drops to zero, or when you find a non-zero term).

Maintaining the right value for current_degree
Check to make sure that the only functions that directly change the coef array are the constructor, clear and assign_coef. Because of this, these are also the only functions that ever need to change the private member variable current_degree.

Also, make sure that your degree function is just one simple line (return current_degree;--and since it is so simple, please move this to an inline function in the header file.

coefficient
This function has no precondition. For exponents above MAX_EX, it must always return the value zero.

Using the private member variables directly
There are two private member variables (coef and current_degree) and two public member constants (CAPACITY and MAX_EX). When you have implemented the suggestions shown above, you should check that these variables and constants are directly accessed in only a few functions (really!). Those functions are:
The constructor
add_to_coef
assign_coef
clear
coefficient
degree
operator *
(but only using MAX_EX in the assert)
If you find other spots that access things directly, please remove those now.

next_term
If you did the previous assignment early (before Sep 15, 2000), then you will need to make a small change to the next_term function. The new specification uses zero for the return value when there is no next term. Make this change to your function and to the documentation in poly0.h:
   unsigned int next_term(unsigned int e) const
     POSTCONDITION: The return value is the next exponent n which is LARGER
     than e such that coefficient(n) != 0.
     If there is no such term, then the return value is zero.
By the way, the reason for the choice of zero is that zero cannot otherwise be a valid answer from next_term (since there are no terms before the zero-order term).

previous_term
If you did the previous assignment before Sep 15, 2000, then you must add a new previous_term function to your class and to the documentation in poly0.h:
   unsigned int previous_term(unsigned int e) const
     POSTCONDITION: The return value is the next exponent n which is SMALLER
     than e such that coefficient(n) != 0.
     If there is no such term, then the return value is UINT_MAX
     from .

make_gif
The solution you submit must include the make_gif function from www.cs.colorado.edu/~main/chapter3/polygif.cxx. In order to use this function, you must #include <fstream>.

operator <<
I want you to use the previous_term function to greatly simplify your implementation of the output operator. Here is an outline of an implementation that should take under 40 lines to implement:
    ostream& operator << (ostream& out, const polynomial& p)
    {
	unsigned int i = p.degree( );
	double number;

	// Each iteration of this loop prints one term of the polynomial:
	do
	{
	    // Get the coefficient:
	    number = p.coefficient(i);

	    // Print a sign
            ...there are three possibilities:
            "-"   in front of the first term if it is negative
            " - " in front of other negative terms
            " + " in front of positive terms (except if it is first term)

	    // Get rid of any negative sign in the number:
	    number = fabs(number);
	    
	    // Print the number, variable x, and exponent
            ...print the number only when it is not 1.0 or it is the 
               constant term
            ...print the letter x only when the exponent is above zero
            ...print the exponent only when it is above one

	    // Move to the next lowest term:
	    i = p.previous_term(i);
	}   while (i != UINT_MAX);

	return out;     //return the output stream
    }

Use the type unsigned int
At any place that you use a variable for an exponent, the variable should be declared as an unsigned int.

Pattern for stepping through the terms
With a few exceptions, any loop that steps through the terms can follow a pattern along these lines:
    unsigned int i;
    i = 0;
    do 
    {
        ...code that processes the x^i term....
        i = next_term(i);
    }   while (i != 0);
For example, the eval function can use a loop along these lines (using the pow function from <cmath> to compute x to the i power:
    unsigned int i;
    double answer = 0;
    i = 0;
    do 
    {
        answer += coefficient(i) * pow(x, i);
        i = next_term(i);
    }   while (i != 0);
Here's a question for you: Why is it important to use a do-while loop in this example, rather than a simple while-loop or for-loop? The answer is that we start the control variable i at i=0, so that a while-loop or for-loop would immediately stop (with the condition (i != 0).

There are some exceptions that can use a simpler loop when it is okay to start at i=1 instead of i=0. For example, the loop in eval could be done this way instead:

    unsigned int i;
    double answer = coefficient(i); 

    // We have already put the zero term in the answer, so we can
    // start with the next term after that:
    for (i = next_term(0); i != 0; i = next_term(i))
    {
        answer += coefficient(i) * pow(x, i);
    }
As another example, in the derivative function, you can start i at one instead of zero. In derivative you might also prefer a for-loop such as:
    for (i = 1; i != 0; i = next_term(i))
        ...set the i-1 term of your answer...
What kind of loop will you use in the output operator (shown above) and the loop to lower current_degree in the assign_coef function?

Finally, the implementations of next_term and previous_term can use some simple for-loops to find the next or previous term.

Preconditions
Preconditions must be checked with an assert at the top of these functions: The constructor, add_to_coef, assign_coef, operator *.

Indentation and Style
Your program should be nicely indented and follow the style guidelines at www.cs.colorado.edu/~main/supplements/style.html . You can use emacs to do automatic indentation. The "pretty indent" command for my .emacs file is Escape-P. If this command doesn't seem to work on the PCs in the Unix lab, then try copying my .emacs file to your top directory with the command:
cp ~cs2270/.emacs .emacs
Notice that the period is part of the file name. This .emacs file is the initialization file used by emacs.

Warnings
Your code must compile with the -Wall option, producing no warnings. The one warning that is sometimes hard to get rid of is "control reaches end of non-void function". This means that the compile thinks that there is no return statement at the end of a function. You can usually fix this by simplifying your code. For example, this will produce a warning:
    double polynomial::coefficient(unsigned int exponent) const
    {
	if (exponent <= MAX_EX)
	    return coef[exponent];
	else
	    return 0.0;
    }
But this simpler version avoids the warning:
    double polynomial::coefficient(unsigned int exponent) const
    {
	if (exponent <= MAX_EX)
	    return coef[exponent];
	return 0.0;
    }