CS 635 Advanced Object-Oriented Design & Programming Spring Semester, 2004 Assignment 2
	Lecture Notes Index         © 2004, All Rights Reserved, SDSU & Roger Whitney San Diego State University -- This page last updated 27-Jan-04

---

Assignment 2
Null Object, Iterators, Visitor & Linked List
Due Feb 10.
The goal of this assignment is to implement the null object, iterator and visitor patterns.

In linked list and/or node methods one often has to check if the next pointer or reference is nil (or null). This can be avoided by adding a null object at the end of the linked list. In the linked list one also has to check if the first pointer or reference is nil. This can be avoided by adding a null object at the beginning of the list.

1. Implement a doubly linked list with null objects at the beginning and end of the list. So an empty list will contain two null objects.

2. Implement method(s) to add new items at the front of the list. Implement method(s) to add new items at the end of the list. Items can be any type of object.

3. Implement a method to determine if an item is in the linked list. This method is to return true if the item is in the list, and false if the item is not in the list. This method is to do its work by sending a message to null node in the front of the list. The nodes will pass the message on to the next node if needed. (Some people call this a recursive implementation.)

4. Implement a method to remove the first occurrence of an item in the linked list. If the item does not occur in the list throw an exception. This method is to do its work by sending a message to null node in the front of the list. The nodes will pass the message on to the next node if needed.

One common operation on a collection is to go through all the elements of the collection. One way to do this is using an iterator.

5. Implement an iterator to traverse the linked list from front to back. You can use either an internal or external iterator. In Java and C++ external iterators are easier to implement. In Smalltalk there is not much difference in the difficulty in implementing internal or external internal iterators.

6. Reimplement your test to determine if an item is in the list using your iterator.

7. Use your iterator to find all elements of a linked list that start with a vowel. It only makes sense to run this code on a linked list that contains strings.

8. Implement a visitor to visit a linked list containing strings and produce a collection of strings that are in the linked list and start with a vowel.

Grading

	Percent of Grade
Working Code	15%
Unit Tests	10%
Comments	10%
Quality of Code	15%
Proper implementation of Patterns	50%

Proper implementation of Patterns. The goal of the assignment is to better understand the iterator, null object and visitor patterns. So 50% of your grade is on producing a proper implementation of the patterns.

What to Turn in
Turn in hard copy of your code and unit tests. Smalltalk programmers can turn in change sets or parcels containing the code and unit tests on a floppy if they prefer.

Late Policy
The penalty for turning in the assignment late is 3% of the grade per day. Once solutions to the assignment have been posted or discussed in class no more late assignments will be accepted.

Questions for Thought
1. Internal iterators have proven very useful in Smalltalk, yet do not exist in C++ or Java. How would you implement an internal iterator in C++ or Java on your linked list? How easy would it be to use your internal iterator? For C++ take a look at the Boost Lambda library.

2. What do you see as the advantages and disadvantages of using the null object pattern in the linked list?

3. You have implemented operations of your linked list three different ways - directly (print and sum in assignment 1), recursive (#3 & 4 above) and via an iterator (#6 & 7 above). Which do you think is better? Why?

4. One problem with external iterators is that collection you are iterating over can change while the iterator still exists. This can put the iterator in an undefined state. (How?) One solution is to make the iterator robust, that is ensure that insertions and deletions do not change interfere with the iterator. (see page 261 of the text). How would you make your iterator robust?

5. Java introduced fail-safe external iterators in JDK 1.2. These iterators allow the collection being iterated over to be changed by the iterator. However, if the collection is changed not using the iterator then the next time you call a method on the iterator an exception is thrown. How would you implement a fail-safe iterator?

6. Which type of external iterator is better a robust or fail-safe? Why?

7. How would you implement a factory method to return a polymorphic external iterator? What is the advantage of doing this?

8. The text states that polymorphic iterators in C++ must be on the heap. Explain why this is true.

9. In Smalltalk one can use the method become: to turn object A into object B. That is object A will become an instance of the B's class. All previous references anywhere in your program to B will be changed to refer to A. B will be turned into a instance of A' class and all previous references to A will now refer to B. Is this possible in Java or C++?

10. One of the listed disadvantages on the NullObject pattern is that NullObject objects can not transform themselves into a RealObject. Does the become: method negate this disadvantage in Smalltalk?

11. You now have three different ways to find all strings in a linked list that start with a vowel. What are the pros and cons of each way?

Copyright ©, All rights reserved.
2004 SDSU & Roger Whitney, 5500 Campanile Drive, San Diego, CA 92182-7700 USA.
OpenContent license defines the copyright on this document.

---

    visitors since 27-Jan-04