CS 311 Spring 2008
Assignment 6

Assignment 6 is due at 5 p.m. Thursday, April 17. It is worth 20 points.

Procedures

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 Exersise B. The two files (or a single archive file containing them) should be attached to your e-mail message.
• Be sure to include your name in your e-mail.
• 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.

Exercises (20 pts total)

Exercise A — Linked List Class Template

Purpose

In this exercise, you will write a Linked List. You will also write a function to reverse a Linked List.

Your Linked List will be used in the next exercise.

Instructions

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

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 now apply!

• 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 — Templated Stack

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 now apply!

• 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, include slist.h in the header for the Stack.
• Interface. Class SLStack must include the following public member functions, and no others:
  • 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 on the Stack.
  • Function push. Given a data item. Returns nothing. Pushes the given item on the Stack.
  • Function pop No parameters. Returns nothing. Removes the top item, if any, from the Stack.
    • How this function behaves if the Stack is empty, is up to you, but this must be documented.
• 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 input iterator is one that can only be read from, using “*iter++”. You can also compare equality or inequality of two input iterators.
• Similarly, an output iterator is one that can only be written to, using “*iter++”.
• 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

Many 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 & Grading

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 Spring 2008: Assignment 6 / Updated: 12 Apr 2008 / Glenn G. Chappell / ffggc@uaf.edu