In this lab we will use list and stack classes to illustrate various aspects of class design and some common error encountered in the process, such as exposing the implementation, incorrect inheritance, failure to exploit polymorphism, lack of flexibility and extendibility, etc.

Work through the following steps, in order:

1. Copy the following lab files: create a workspace and then a project that incorporates these files.
• /dept/cs/cs230/www/labs/lab6/list.h
• /dept/cs/cs230/www/labs/lab6/listiter.h
• /dept/cs/cs230/www/labs/lab6/stack.h
• /dept/cs/cs230/www/labs/lab6/main.cpp
2. Const Trouble: Study the files carefully. The file list.h defines a list template class. It's a circular singly linked list with a dummy header node, like the one we used in lab3. Note the use of the current  node. It provides access to individual linked list nodes, and is updated in each operation that accesses the list (such as insert, delete, etc.)

Compile the program. You should get some compiler warnings about const arguments and their usage. Study the routines First() and Exhausted() in list.h. Do these functions respect the const properties? How would you fix the problem? Take some time to think about this, then read on!

3. Const Iterators: Now study the class ListIter designed to traverse the list nodes. Notice that this is a const iterator class, i.e., it is guaranteed to not modify the list it is iterating in any way. Fix the << operator so that it uses this iterator to print out individual list elements. Notice the similarity between the member functions of ListIter and the members used in <<. You should have to make only minor modifications to the code. Next, compile and run your program. Everything should be in order.
4. Stacks: Study the prototype of the class Stack. Recall that a stack is essentially a list with the restriction that inserts and removes can be performed in only one position, namely that beginning of the list, called the top. The fundamental operations are Push (insert at the top position), and Pop (delete from the top position). Now write the code for these two functions. Make use of the functions provided in the List class to accomplish this. Pay careful attention to the way current is used in List, and the way Insert() and Delete() work in List. Can you simply use these functions?  For example, uncomment the block of lines labeled //1 in main.cpp. Compile the code and run it. Does the stack work as expected, i.e., in LIFO (Last In First Out) order? What must change? (Hints: For the Push routine, you must make sure that you insert at the beginning of the list each time, i.e., the current pointer should be pointing at the dummy head before each insert; which function in List does this?).

After you have made the changes, uncomment the block of lines labeled //2 in main.cpp. Next, compile and run your program to make sure that Pop works (Hints: For the Pop routine, you must delete from the beginning of the list each time. For this you'll have to reset current pointer so that it points at the first list node before proceeding to do the delete. Also, you must return the value of the popped element to the caller).

5. Incorrect Polymorphism: Now uncomment the block marked //3 in main.cpp. ListLike is a pointer to a list like structure, i.e., it can point to both a List or a Stack type. In the first part it points to sint, a stack of ints. In the second part it points to int_list, a list of ints. Now, compile and run your program. Does the Insert work fine for sint? Make necessary changes to the code so that ListLike calls the correct version of Insert depending on whether it points to a Stack or a List.
6. Exposing Implementation: Everything is in order at this point. The Stack class is working properly. Nevertheless, there is a problem. We see that Stack is a public derived class of List, which means that it inherits all the public members of List including operations like Insert(), Delete(), and using a combination of ++operator and Current_Value(), we can access any element on the stack and delete or insert at any position. This violates the Stack specification, i.e., the access is only to the top element.

For example, uncomment the block //4 in main.cpp. Run your program. As you can see we were able to successfully delete element 2 from the Stack even though it was not the Top element.
What must you do to make sure that in main.cpp you disallow operations like sint.Delete()? Of course, in the implementation of Stack functions you can still see all of the list functions, but the user of Stack doesn't have access to them.

7. Inheritance: Change the inheritance of Stack to be of type private derived class of List. Try to compile your program. You'll get a bunch of errors. One of these says that you can no longer access Delete() from sint. Another error deals with the fact that sint can no longer use the output << operator of List, and the third kind of error is that ListLike can no longer point to a Stack class. This is precisely what we want. We want to continue using the List members in the implementation  of members of Stack, but we don't want any user of  Stack to use members of List. Now, comment out the block of code under the "Illustrating Polymorphism" and "Exposing Implementation" comments in main.cpp. Compile and run the code after implementing a new output routine for Stack. Note that you can simply call any List routine from within the member function.

At the conclusion of this lab, take a moment to review the following:

You have been introduced to various aspects of class design and some common error encountered in the process, such as exposing the implementation, incorrect inheritance, failure to exploit polymorphism. These concepts were illustrated through the use of the List and Stack classes (a specialization of List).

You have been made aware of const correctness, i.e., how to preserve const properties guaranteed by function declarations, by making sure that you do not inadvertently discard the const.

You have been re-introduced to derived container classes and the use of virtual functions. Virtual functions go hand-in-hand with polymorphism, i.e., when you need to call the right function (from the base class or one of the derived classes) at run time.

You have been introduced to the use of private derived classes to avoid exposing the implementation of a class in your program, and how the use of private derivation affects inheritance.