Assignment 2

Due Feb. 24

The binary search tree class in assignment one is a collection. Determine the correct location in your language’s collection class hierarchy. Find all methods that you need to implement in-order to add your class in the language’s collection class hierarchy. (C++ people get a pass on this problem as STL is painful to subclass.) Note we will only be interested in implementing one of these methods - see problem 4.

Make the parent of your binary search tree the parent determined in problem 1. Rename your existing methods to conform to the collection classes standards.

Use the Null Object pattern to add a null node to your tree to eliminate the need to check for null references or pointers in your tree.

Implement an iterator for your binary search tree. It is tempting to convert the tree into a collection and the then use the iterator from the collection. This is a quick trick that can be useful. However the point of this assignment is to help us understand how to implement patterns, which this trick will not help us do. So don’t use the trick.

Implement what we will for now will call DigitalSumFilterIterator. Using Java syntax the class will have the methods given below. One temptation here is to read all the elements into a collection, remove the ones that don’t have the correct digital sum and then return an iterator on that collection. This assumes that all the elements we are iterating over are all available at one time and will fit into memory. This is not always the case, for example one may be iterating over elements in a very large file. So do not use this trick either.

DigitalSumFilterIterator(Iterator input, int digitalSum) - constructor

boolean hasNext() - returns true it the iteration has more elements with the given digital sum.

next() - returns the next element in the iteration with the digital sum given in the constructor.

Implement a visitor for the binary search tree. The visitor is to find all nodes with a given digital sum. The tree does not have very many types of nodes so this is a rather strained use of the pattern. In the past students have been tempted to take short cuts when implementing the visitor pattern. In doing so they remove essential parts of the pattern. Be careful with this pattern. Also do not use your iterator from part 4. You can have the tree implement the traversal.

Grading

Item	Percent of Grade
Working Code	15%
Unit Tests	10%
Proper implementation of Patterns	60%
Quality of Code	15%

Proper implementation of Patterns. The goal of the assignment is to better understand the iterator, null object and visitor patterns. So 60% 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. Do not turn in Question for Thought listed below.

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

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.

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

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?

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?

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

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

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

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++?

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?

You now have three different ways to find all elements of a tree with a given digital sum. What are the pros and cons of each way?