COMP2004 Programming Practice
2002 Summer School

Week 3 Monday Tutorial Exercises

Here is the List class from today's lecture, with a few minor changes. Most of today's questions relate to this code.
Compile the code one file at a time into .o files, and then link the .o files together into a program. Check that the program works. Notice how the Node and Iterator classes have been nested inside the List class and are private, so they can't be seen outside the List class.
Add a method
```
void List::insert_at_back(int value)
```
for inserting values to the end of the list. Modify the test program to test your changes.
Add a method
```
int List::remove_from_front()
```
for removing values from the start of the list. Modify the test program to test your changes.
Add a method
```
int List::remove_from_back()
```
for removing values from the end of the list. Modify the test program to test your changes.
Add a method
```
unsigned long List::count() const
```
which counts how many items are in the list by traversing it. Modify the test program to test your changes.
Add a method
```
unsigned long List::size() const
```
which returns how many items are in the list by storing an unsigned long variable in each List object and updating this variable every time a method causes the size of the list to change. Modify the test program to test your changes.
Modify the Iterator class to have one constructor which behaves in the same way as the original two constructors.
Make a copy of the Iterator class called ConstIterator. This should behave in the same way as the normal Iterator, except that:
- the operator* method returns const int & instead of int &
- the node member is stored as a const Node * instead of Node *
- there is an additional constructor
```
		ConstIterator(const Iterator &i);
		
```
  which converts a normal Iterator into a ConstIterator.
  This will require the Iterator class to define the ConstIterator class as a friend. This requires a forward definition which tells the compiler that the ConstIterator class hasn't been defined yet, but it will be later.
```
		// Forward definition, tell the compiler that ConstIterator exists
		// but hasn't been defined yet.
		class ConstIterator;

		class Iterator {
		// This line requires the above forward definition
		friend class ConstIterator;
			// rest of Iterator class goes here
		};

		class ConstIterator {
			// ConstIterator class goes here
		};
		
```
Modify the test program so that it attempts to use a ConstIterator to modify the values in the list. Observe the error messages the compiler gives you when you try to do this. Your List.cc should still compile, though.
Overload the List::begin() and List::end() methods with variants that return a ConstIterator. Notice that if you just do
```
Iterator begin();
Iterator end();
ConstIterator begin();
ConstIterator end();
```
then the compiler gives an error. This is because you cannot overload functions based on their return type (can you think of why?). However, if you do
```
Iterator begin();
Iterator end();
ConstIterator begin() const;
ConstIterator end() const;
```
then the compiler accepts the overloaded methods, and so it is possible to provide const and non-const versions of methods where it's appropriate.
Modify the test program so that the output_list() method is passed a const List & instead of a List &, ie:
```
void output_list(const List &list);
```
This is more correct, since output_list() shouldn't be allowed to modify the list being output.
However, notice now that you cannot get a non-const Iterator using a const List reference - the compiler complains that using the "begin()" and "end()" methods would ignore the "const" in "const List &". Modify the code for output_list() so that it uses a ConstIterator rather than an Iterator. Notice that now the "begin() const" and "end() const" methods are being used, which is allowed with the "const List &list".
Modify the class to be a doubly linked list. Modify both iterators to also have -- operators for moving backwards through the list (ie. be bidirectional iterators). Modify the test program to test these new iterators.
Modify the Iterator class to have the following static method
```
static Iterator Iterator::create_begin(const List &l);
```
which returns an Iterator which is at the start of the given List (don't use the List::front() method). Then create a similar static method
```
static Iterator Iterator::create_end(const List &l);
```
which returns an Iterator which is at the end of the given List (don't use the List::back() method). You may need to declare the Iterator class as being a friend of the List class. The methods Iterator::create_begin() and Iterator::create_end() are in some sense "pseudo-constructors", and the trick of using static methods to create objects with particular properties in this way is called the Named Constructor Idiom.
Make a copy of the Iterator class called ReverseIterator. This should behave in the same way as the normal Iterator, except that the ReverseIterator::operator++() method actually moves to the previous element in the list, and the ReverseIterator::operator--() method actually moves to the next element. Don't forget to do the create_begin() and create_end() methods.
Use this small test program to observe how changing the type of iterator can affect the actual iteration through the list.
Lastly, Assignment 1 is due at 5:00pm tomorrow, so you can spend any remaining time working on it.

COMP2004 Programming Practice 2002 Summer School

Week 3 Monday Tutorial Exercises

COMP2004 Programming Practice
2002 Summer School