CS 635 Advanced Object-Oriented Design & Programming Spring Semester, 2002 Assignment 2
	Assignment Index         © 2002, All Rights Reserved, SDSU & Roger Whitney San Diego State University -- This page last updated 30-Jan-02

---

Assignment
Object, Iterators & Linked List
Due Feb 12.
The goal of this assignment is to implement the Null Object and iterator 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 from part 3 to determine if an item is in the list using your iterator.

7. Use your iterator to compute the sum of a linked list of integers.

Grading

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

Proper implementation of Patterns. The goal of the assignment is to better understand the iterator and null object pattern. So 30% of your grade is on producing a proper implementation of the two 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 5% 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?

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?

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

---

    visitors since 30-Jan-02