The Assignment:

Implement a polynomial class that uses a doubly-linked list to store the polynomial's terms. Each node of the list holds the coefficient and exponent for one term. The terms are kept in order from smallest to largest exponent. Each polynomial also maintains a pointer to the most recently accessed node.

Purposes:

Ensure that you can write a class that uses a linked list.

Before Starting:

Read Sections 5.1 to 5.3 and 5.5.

Complete the previous assignment of a polynomial that uses a dynamic array to store its coefficients (www.cs.colorado.edu/~main/projects/chap04c.html).

Due Date:

Thursday, Oct 12. If you run into problems, you may submit the work on Friday with no penalty. You may also submit on Saturday or Sunday with a penalty of 5 points per day. No submissions allowed after Sunday.

Files that you must write:

1. poly2.h: The header file for the new polynomial class. Start with our our version of poly2.h and add your name and email address at the top.
2. poly2.cxx: The implementation file for the new polynomial class.

Other files that you may find helpful:

1. polytest2.cxx: A simple interactive test program.
2. polyexam2.cxx: A non-interactive test program that will be used to grade the correctness of your polynomial class.

The Polynomial Class with a Linked List
Discussion of the Assignment

As indicated above, you will revise the polynomial class to use a doubly-linked list to store. You'll need to copy your poly1.cxx to a new file poly2.cxx and make these changes:

1. Change the namespace to main_savitch_5, and change the include statement to include poly2.h. Also include <cstdlib> (which has NULL).

2. Delete the DEFAULT_CAPACITY constant.

3. Look at the new polynode class in poly2.h and look at the new private member variables for the polynomial class:

       private:
   	polynode *head_ptr;             // Head pointer for list of nodes
   	polynode *tail_ptr;             // Tail pointer for list of nodes
   	mutable polynode *recent_ptr;   // Pointer to most recently used node
   	unsigned int current_degree;    // Current degree of the polynomial
   

   The meaning of the mutable keyword will be covered in class. But a brief explanation now: Our plan is to keep the recent_ptr always pointing to the most recently-used node. For example, when we call the coefficient member function, we will move the recent_ptr to point to the node that contains the requested exponent. With a normal member variable, we could not do this (since the coefficient is a const member function and it is forbidden from changing normal member variables). So, the meaning of the mutable keyword is to indicate that changing the member variable does not change the value of the polynomial in a meaningful way (and therefore, the compiler will let const member functions change a mutable variable).
4. In your poly2.cxx, write a clear description of how the member variables of a polynomial are used. The head_ptr and tail_ptr are the head and tail pointers for a doubly-linked list of nodes that contain the polynomial's terms in order from smallest to largest exponent. To make certain operations simpler, we will always keep a node for the zero-order (x^0) term. But other nodes are kept only if the coefficient is non-zero. We always maintain recent_ptr as a pointer to some node in the list--preferably the most recently used node. The degree of the polynomial is stored in current_degree (using zero for the case of all zero coefficients).

5. Delete the reserve member function (and delete any places where you called the reserve function).

6. The poly2.h header file contains a prototype for a private member function that will make it easier to implement everything else:

       // A private member function to aid the other functions:
       void set_recent(unsigned int exponent) const;
   

   The set_recent function will set the recent_ptr to the node that contains the requested exponent. If there is no such exponent, then recent_ptr should be set to the last node that is still less than the specified exponent. Note that set_recent is a const member function, but that it can still change the mutable recent_ptr member variable. My implementation of set_recent used three cases:
   • If the requested exponent is zero, then set recent_ptr to the head of the list.
   • Else if the exponent is greater than or equal to the current degree, then set recent_ptr to the tail of the list.
   • Else if the exponent is smaller than the exponent in the recent node, then move the recent_ptr backward as far as needed.
   • Else move the recent_ptr forward as far as needed.

7. Implement the new constructors, destructor, and assignment operator.

   The default constructor should start by creating a valid empty polynomial (with a head node that has exponent and coefficient of zero). Then call assign_coef to set the one term.

   The copy constructor should also start by creating a valid empty polynomial. Then have a loop tht steps through the terms of the source (using source.next_term). Each term of the source is placed in the polynomial (using assign_coef).

   The assignment operator first checks for a self-assignment, then clears out the terms (using the clear function). Finally, have a loop (similar to the copy constructor) to copy the terms of the source.

8. Implement the new assign_coef function. After calling set_recent(exponent), my implementation had these cases:
   • If there is a zero coefficient and exponent greater than current degree (return with no further work).
   • Else if there is currently no node for the given exponent (so that recent_ptr->exponent( ) is less than the new exponent).
   • Else if the coefficient is non-zero or the exponent is zero (in both these cases, we just change the coefficient of a node).
   • Else if the exponent equals the current degree. In this case, the coefficient is zero (otherwise we would have hit the previous case), so we remove the tail node, set the recent_ptr to the new tail, and reduce the current degree.
   • Else...in this last case we must have a new zero coefficient for a node that is neither the head nor the tail. We just remove this node and set the recent_ptr to the next node in the list. Modify the other polynomial member functions to use the dynamic array.

9. Rewrite next_term
and previous_term so that they each start with set_recent(exponent). Hint for next_term: Start by calling set_recent(e). Normally, the right answer is then in the node after recent_ptr (but there is one exception that you should handle). Hint for previous_term: Start by checking the special case where e is zero. Then call set_recent(e-1). Normally, the right answer is then in the recent_ptr node (but again, there is one exception that you need to handle--the case where the node has exponent and coefficient of zero).
10. Revise any other functions that access the member variables directly. In my implementation, this was only clear and coefficient. I told you that it would save work to avoid accessing those member variables directly!