CS 311 Fall 2009
Assignment 6

Assignment 6 is due at 5 p.m. Thursday, November 12. It is worth 25 points.

Procedures

This is a group assignment. Please work in a group of 2 or 3. Each group only needs to turn in a single copy of the assignment. Under normal circumstances, each will receive the same grade on the assignment.

E-mail answers to the exercises below to ffggc@uaf.edu, using the subject “DA6”.

• Your answers should consist of two files: slist.h, from Exercise A, and slstack.h, from Exercise B. These files (or an archive file containing them) should be attached to your e-mail message.
• Be sure to include the names of all group members in your e-mail.
• Suggestion: Cc the submission e-mail to all group members, so that I can reply to all indicating that it has been received.
• I may not read your homework e-mail immediately. If you wish to discuss the assignment (or anything else) with me, send me a separate message with a different subject line.

Note: Restrictions on extra public members are lifted, for this assignment. You may include public members in your classes, other than those specifically mentioned below. You may also write additional publicly available global functions. Because of compiler troubles, I recommend that you do NOT declare any friends in this assignment; if some data or functionality needs to be accessible to some other class, instead of making a friend, simply make the appropriate members public.

Exercises (20 pts total)

Exercise A — “Minimalist” Linked List Class Template

Purpose

In this exercise, you will write a Linked List. This will not be a full-featured package. It has those features required for testing, but its primary purpose is to be the basis for Exercise B.

You will also write a function to reverse your Linked List.

Instructions

Implement a C++ class template that manages a Linked List. The type of item in the list should be specified by the client. Be sure to follow the coding standards. All standards apply, with the exception noted above concerning extra public functions.

• Call your class template “SList”, so that, for example, an SList of doubles would be declared as a SList<double>.
• Implement your class template in file slist.h. Since this is a template, there should be no associated source file.
• Implementation.
  • The data must be stored in an actual Linked List (singly or doubly linked).
  • Linked List nodes must be separately allocated (in particular, do not store them in an array).
  You may decide other implementation issues however you want, within the constraints of the coding standards, and the rest of these requirements.
• Interface. Class SList must include at least the following public member functions:
  • Default ctor. Creates a Linked List of size zero.
  • Copy ctor. Copies a Linked List, as usual. The copy must contain completely separate data.
  • Copy assignment operator. Copies a Linked List, as usual. The copy must contain completely separate data.
  • Dctor. Does all necessary deallocation, destruction, and other necessary clean-up.
  • Function size. Returns the size of the Linked List. No parameters.
  • Function read. Given two input iterators (see Notes on Iterators, below) that specify a range, in the usual manner. Returns nothing. The value type of the iterators is assumed to be the same as that of the Linked List. When the function is done, the items in the range are contained in the Linked List, in the same order. Whatever data the Linked List previously contained have been discarded.
  • Function write. Given a single output iterator (see Notes on Iterators, below). Returns nothing. Writes the items in the Linked List to the iterator, in order. Assumes that the iterator references the beginning of a range with enough space.
  • Function reverse. No parameters. Returns nothing. After this function is executed, the Linked List contains the same data items, but in the reverse order.
    • Function reverse must not do any value-type operations; only manipulate pointers.
    • Function reverse must use only constant additional storage. In particular, function reverse must not be recursive.
  Other public member functions, member types, and data members may be added to the interface as you see fit.
• You may not use any C++ Standard Library classes in your implementation. (You may use simple types, like std::size_t.)
• You may not use any C++ Standard Library functions in your implementation, except for std::swap and std::iter_swap.
• All of the functions specified above should have the highest reasonable levels of efficiency and exception safety.
• All of the functions specified above must be exception-neutral; that is, exceptions thrown by value-type operations must propagate unchanged to the caller.
• You may not forbid any member function of the value type from throwing, except for the destructor.

Exercise B — Stack Template

Purpose

In this exercise, you will write a Stack that uses the Linked List from Exercise A to hold its data.

Instructions

Implement a C++ class template that manages a Stack. The type of item in the Stack should be specified by the client. Be sure to follow the coding standards. All standards apply, with the exception noted above concerning extra public functions.

• Call your class template “SLStack”, so that, for example, an SLStack of doubles would be declared as a SLStack<double>.
• Implement your class template in file slstack.h. Since this is a template, there should be no associated source file.
• The data in your Stack should all be contained in a single data member, which is an SList. Do not duplicate the code for SList; instead, do “#include "slist.h"” in the header for the Stack.
• Interface. Class SLStack must include at least the following public member functions:
  • Default ctor. Creates an empty Stack.
  • Copy ctor. As usual.
  • Copy assignment. As usual.
  • Dctor. As usual.
  • Function empty. No parameters. Returns a bool indicating whether the Stack is empty.
  • Function top. No parameters. Returns a reference to the top item of the Stack. This should allow modification of the top item, for a non-const Stack, but not for a const Stack.
  • Function push. Given a data item. Returns nothing. Pushes the given value.
  • Function pop No parameters. Returns nothing. Pops the top item, if any.
    • How this function behaves when the Stack is empty, is up to you, but this must be documented.
  Other public member functions, member types, and data members may be added to the interface as you see fit.
• You may not use any C++ Standard Library classes in your implementation. (You may use simple types, like std::size_t.)
• You may not use any C++ Standard Library functions in your implementation, except for std::swap and std::iter_swap.
• All member functions should have the highest reasonable levels of efficiency and exception safety.
• All member functions must be exception-neutral; that is, exceptions thrown by value-type operations must propagate unchanged to the caller.
• You may not forbid any member function of the value type from throwing, except for the destructor.

Notes

About Iterators

Some facts:

• An output iterator is one that can only be written to, using “*iter++”.
• Similarly, an input iterator is one that can only be read from, using “*iter++”. You can also compare equality or inequality of two input iterators.
• Always pass iterators by value.

Thus, SList::read and SList::write will look something like this.

template <typename T>
class SList {

[ A LOT IS LEFT OUT HERE ]

public:
    template <typename InputIterator>
    void read(InputIterator first, InputIterator last)
    {
        [ CLEAR THE ITEMS IN THE LIST HERE ]
        while (first != last)
        {
            value_type val = *first++;
            [ PUT val INTO THE LIST HERE ]
        }
    }

    template <typename OutputIterator>
    void write(OutputIterator dest) const
    {
        for ( [ ??? ] ) // ITERATE THROUGH LINKED LIST, SOMEHOW)
        {
            value_type val;
            [ HERE, PUT NEXT LIST ITEM INTO VAL ]
            *dest++ = val;
        }
    }
};

About Friendship

Some C++ compilers do not correctly support friends that are templates. Therefore, I strongly suggest that you avoid declaring friends in this assignment.

If you need to give a global function or class access to some other class’s private members, you may, if you wish, make those members public. Thus, the usual requirements for the proper use of “private” are loosened, for this assignment.

Test Program

I have written a single test program for both exercises: da6_test.cpp. If you compile and run your package with this program (unmodified!), then it will test whether your code works properly.

Do not turn in da6_test.cpp.

Because of the single test program, the code for both exercises must at least exist, and must compile with the test program. Code that does not compile at all will not be graded.

Other Thoughts

If you do a good job on Exercise A (the Linked List), then Exercise B (the Stack) should be very easy. In particular, if the Linked List knows how to initialize, copy, and destroy itself properly, then the compiler-written default ctor and Big-Three functions should be fine, for the Stack class. That leaves empty, top, push, and pop, none of which is likely to be very difficult.

For the Linked List class, remember the swap trick for writing copy assignment. Also remember that it is probably easier to put necessary functionality into class SList than to have the Stack manage the internal details of the Linked List.

CS 311 Fall 2009: Assignment 6 / Updated: 7 Nov 2009 / Glenn G. Chappell / ffggc@uaf.edu