Assignment 9

DUE: Monday May 30, 11 pm
(10% penalty for late submission, up to 1 day late)

Changes, Errata and Helpful Hints

Any changes to this document, typically due to an error on the part of the author, will be logged here.

Collaboration

Collaboration is strongly ENCOURAGED within a programming team, but the program you submit must still represent YOUR OWN original work. Teams should work on the algorithm together, and help debug/test each others code. However, copying code from ANY outside source (any book, current or past students, past solutions, web sites, etc.) is STRICTLY FORBIDDEN. Copy and Paste from another solution, including the solution of a team mate will incur a stiff penalty.

Problem Definition

Your book provides you with an implementation of a linked list. Although the books implementation serves as a good example, it is a bit rough around the edges to be considered truely usable. For this assignment you will implement a better linked list which is designed to hold integers.

The implementation in you book has a handful of problems. To begin with it uses assert statements to handle boundry conditions. This is fine when you are testing a piece of code, but production code should try to recover gracefully from undesirable situations rather than abort the program. Your list will eliminate the need for assert statments. Second, the list allocates dynamic memory, but never releases it when the list is deconstructed. This is a huge problem that you will address in your list. Third, the iterator provided with the list is weak and cumbersome. You will write an iterator for your list class that closely mirrors the iterators for the standard template library containers.

For this assignment you will also be able to earn some extra credit if you choose to do so. To get extra credit you must also implement a reverse iterator for your list. Some portions of the header files that you download contain code relating to the extra credit. This code has been commented out. If you implement the extra credit you will need to uncomment this code. The description of each class will tell you what you need to uncomment in order to implement the extra credit.

The Node Class

Your node class will be very similar to the class provided by the book, the only real difference is that you need to implement a destructor for your node class. Also you might notice that the constructors are private. This prevents a node from being instantiated outside of the context of a linked list.

The declaration of the node class is as follows:

//! \class LlNode
//! \brief A class which is to be used as the nodes of a linked list.
class LlNode
{
  // The following classes and functions may access the private members of
  // this class
  friend class Llist;
  friend class LlIterator;
  friend class LlReverseIterator;

 private:
  //! \brief Default constructor for the LlNode class.
  LlNode();

  //! \brief Constructor for the LlNode.
  //! \param value The data the node should contain.
  LlNode( const int value );

  //! \brief Destructor for the LlNode class.
  ~LlNode();

  int data;                     //!< The value contained by the node
  LlNode *prev;                 //!< The node before this node
  LlNode *next;                 //!< The node after this node

};

There is no need for you to alter the interface of this class. Therefore you should not alter this file.

The List Class

Your list class will make some improvements to the list class presented in the book. In addition to being more robust, your class will also include increased functionality. Although it is not necessary, I highly recommend implenting your list with a fake head and fake tail. Doing so will not only make the implementation of the list easier, but it will also make it much easier to deal with the off-the-end iterator, as well as the off-the-beginning iterator if you choose to do the extra credit.

In addition to writing the list class, you must also overload the insertion operator so that when it is used on a list, the elements contained in the list are printed out separated by a space.

The declaration of the list class is as follows:

//! \class Llist
//! \brief Class which implements a linked list.
class Llist
{
 public:
  // Allow a LlIterator to be refered to as an Iterator and an
  // LlReverseIterator to be refered to as a ReverseIterator
  typedef LlReverseIterator ReverseIterator;
  typedef LlIterator Iterator;

  //! \brief Default constructor for the Llist class.
  Llist();

  //! \brief Destructor for the Llist class.
  ~Llist();

  //! \brief Add an element to the end of the list.
  //! \param value The value to add to the end of the list.
  //! \return void.
  void push_back( const int value );

  //! \brief Add an element to the beginning of the list.
  //! \param value The value to add to the beginning of the list.
  //! \return void.
  void push_front( const int value );

  //! \brief Insert an element into the list.
  //!
  //! The element is inserted in front of the element pointed to by pos.
  //! After completion pos still points to the same element that it originally
  //! pointed to.
  //! \param pos An iterator pointing to the position in which to
  //!        insert the new element.
  //! \param value The value to add to the list.
  //! \return void.
  void insert( const Iterator & pos, const int value );

  //! \brief Remove an element from the list.
  //!
  //! The parameter is altered to point to the next element in the list.
  //! \param pos An iterator poiting to the element to be removed.
  //! \return An Iterator which points to the next element in the list.
  Iterator & erase( Iterator & pos );

  //! \brief Return the number of elements in the list.
  //! \return The number of elements in the list.
  unsigned int size() const;

  //! \brief Return whether the list is empty.
  //! \return Whether the list is empty.
  bool empty() const;

  //! \brief Return an iterator to the first element in the list.
  //! \return An Iterator to the first element in the list.
  Iterator begin() const;

  //! \brief Return an off the end iterator.
  //! \return An off the end iterator.
  Iterator end() const;

  //! \brief Return an iterator to the first element in the list.
  //! \return An Iterator to the last element in the list.
  // ReverseIterator rbegin() const;

  //! \brief Return an off the end iterator.
  //! \return An off the ( front ) end iterator.
  // ReverseIterator rend() const;

 private:
  // Allow a LlNode to be referred to as a Node
  typedef LlNode Node;

  unsigned int l_size;  //!< The number of elements in the list
  Node *head;           //!< A pointer to a fake first element of the list
  Node *tail;           //!< A pointer to a fake last element of the list
};

//! \brief Overloaded stream insertion operator for Llist objects.
//! \param out The stream on which to output.
//! \param llist The linked list to output.
//! \return The original output stream.
std::ostream & operator<<( std::ostream &out, const Llist &llist );

If you choose to implement the extra credit, you will need to uncomment the declaration of the methods rbegin() and rend() on lines 73 and 77 of the header file. Other than that you should not alter this file.

The Iterator Class

Your iterator class will overload operators rather than use standard method calls. It will also implement the begin() method which returns an iterator to the first item in the list, and the end() method which returns an off-the-end iterator. These two methods should behave like they do for container classes of the standard template library.

The declaration of the iterator class is as follows:

//! \class LlIterator
//! \brief Class which is to be used as an iterator for a linked list.
class LlIterator
{
  // The following classes and functions may access the private members of
  // this class.
  friend class Llist;

 public:
  //! \brief Default constructor for the LlIterator class.
  LlIterator();

  //! \brief Prefix increment operator for LlIterator.
  //! \return An iterator which points to the next node.
  virtual LlIterator operator++();

  //! \brief Postfix increment operator for LlIterator.
  //!
  //! A copy of the iterator sent as a parameter is returned, and the
  //! original iterator is pointed at the next node.
  //! \return A copy of the iterator sent as a parameter.
  virtual LlIterator operator++( int );

  //! \brief Prefix decrement operator for LlIterator.
  //! \return An iterator which points to the previous node.
  virtual LlIterator operator--();

  //! \brief Postfix decrement operator for LlIterator.
  //!
  //! A copy of the iterator sent as a parameter is returned, and the
  //! original iterator is pointed at the previous node.
  //! \return A copy of the iterator sent as a parameter.
  virtual LlIterator operator--( int );

  //! \brief Dereference a LlBaseIterator
  //! \return A reference to the data held by the element the
  //!         LlBaseIterator points to.
  int & operator*() const;

  //! \brief Compare two LlBaseIterators for equality.
  //!
  //! The LlBaseIterators are equal if they point to the same Node.
  //! \param other The LlBaseIterator to compare with.
  //! \return Whether the two LlBaseIterators are equal.
  bool operator==( const LlIterator & other ) const;

  //! \brief Compare two LlBaseIterators for non-equality.
  //!
  //! The LlBaseIterators are not equal if they do not point to the same Node.
  //! \param other The LlBaseIterator to compare with.
  //! \return Whether the two LlBaseIterators are not equal.
  bool operator!=( const LlIterator & other ) const;

 protected:
  // Make naming a little bit nicer.
  typedef LlNode Node;

  //! \brief Constructor for the LlIterator class.
  //! \param node The node for the iterator to point to.
  LlIterator( Node* const node );

  Node * position;      //!< The node which the iterator points to
};

You should not alter this file.

The Reverse Iterator ( Extra Credit )

In the framework you will the header file for the reverse iterator. For this implementation, the reverse iterator will inherit from the iterator class. Just so you know, this is different than how the STL implements their different iterator classes; but it does yield some interesting behavior that isn't possible with STL iterators. For instance, you can not use a STL reverse_iterator as an arguement to the insert or erase methods of an STL container; however, this will work with your reverse iterator because of the magic of polymorphism.

The declaration of the reverse iterator class is not included here.

The Test Harness

For this program you will need to write your own test harness in order to verify that you implementation works correctly. You are more than welcome to share test harnesses with one another over the mailing list.

Be very careful to test your implementations thoroughly; as the test program that we use for grading will likely do so.

What to Implement

For this assignment you will implement the 3 classes LlNode, Llist, and LlIterator. For extra credit you may also implement the LlReverseIterator class. If you do not choose to implement the extra credit, feel free to delete the files associated with the reverse iterator class. You will also need to write a test harness for your implementation so that you can test that it works correctly, but you need not turn your test harness in.

Assignment Framework

For this assignment a framwork will be provided for you which includes all of the files that are necessary for you to complete the assignment. The files included in the framework are the following:

You may download the framework here. To uncompress the framework archive you should type:

where <framework_file> is the name of the file that you downloaded.

What To Turn In

Submit your work electronically to the correct folder on the cs secure server. Don't forget to include the header template at the top of each file that you submit.

For this assignment you will turn in the following files:

• llnode.h
• llnode.cpp
• lliterator.h
• lliterator.cpp
• llist.h
• llist.cpp
• llreverseiterator.h -- ( If doing extra credit )
• llreverseiterator.cpp -- ( If doing extra credit )

Example

You may use the behavior of the STL list as an example.

Grading Rubric (10 pts total)

Only write a small portion of code before checking that it still compiles. This way when you get a syntax error, you can be fairly certain the error is in the part you just wrote.

The points for this assignment will be distributed as follows: