CS635: Assignment 3

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

Assignment 3
Due March 11

1. External FilterIterator. Implement a FilterIterator class. The class implements the same interface as an Iterator in your language. However you construct a FilterIterator on another iterator. You also provide the FilterIterator a filter, which is used to filter out some of the elements of in the stream. A filter implements an interface with one method:

interface Filter {
boolean accept( Object value);
}

The accept method returns true if the FilterIterator is to accept the object value. If it returns false the FilterIterator ignores the object value.

For example assume that StartsWithVowelFilter class is implemented so that accept( aString) returns true if aString starts with a vowel and false if it does not. We then have the following Java example.

ArrayList names = new ArrayList();
names.add( “Sam” );
names.add( “Able”);
names.add( “Adam”);
names.add( “Brian”);
Iterator onNames = names.iterator();
FilterIterator vowelNames = 
   new FilterIterator(
      onNames, 
      new StartsWithVowelFilter());
while ( vowelNames.hasNext() ) {
   System.out.println( vowelNames.next());
}

This will print out

Able
Adam

Note one has to be careful with the hasNext() in the FilterIterator. The following will illustrate.

ArrayList names = new ArrayList();
names.add( “Sam” );
names.add( “Brian”);
Iterator onNames = names.iterator();
FilterIterator vowelNames = 
   new FilterIterator(
      onNames, 
      new StartsWithVowelFilter());

At this point vowelNames.hasNext() will return false.

Implement FilterIterator on the iterator interface in your language. Since Smalltalk already has a filtering iterator implement your FilterIterator on a Readstream. Everyone can implement the StartsWithVowelFilter for testing your FilterIterator.

2. Stream Adapter. A Reader, InputStream and ReadStreams are a type of iterator. However the interface for the streams is different than the interface for an iterator. Write an adaptor that operations on a stream and provides an iterator interface.

C# and Java have a well-defined external iterator interface. So in these languages create an Adaptor class that accepts a stream or reader on a string. The adaptor class implements the iterator interface in your language. For example in Java the interface is the methods hasNext() and next().

C++ does not have standard streams so replace streams with get() method on ifstream on a file. You can use either the iterator interface used in STL or the Java interface for iterators.

Some of you may be tempted to read all the elements in the stream, put them in a collection and then use the iterator for that collection. This violates the part of the semantics of a stream. If I have a stream on a 100 MB file the stream only reads from the disk the characters requested (plus a small amount of buffering).

In Smalltalk streams already implement the iterator interface. So implement an adapter that provides the Java interface for an iterator on a stream.

3. In this problem we will use a Chain-of-Responsibility like solution finding substrings in a string with wild characters. We will use the characters “*” and “.” for wild characters. The character “.” matches any single character. The character “*” matches zero or more characters. So “c.t” with match “cat”, “cbt”, etc. While “c*t” with match “ct”, “cat”, “caat”, “cbt”, “casdert” and many others. Now a Match object will find the first match of a pattern in a string. For example:

match = new Match( “c.t” );
startIndex = match.findFirstIn( “cacacat”);

startIndex will be 4. Recall in C based languages the index of the first element in a string is zero, while in Smalltalk the index of the first element is 1. So in a Smalltalk version findFirstIn: would return 5 in the above example.

Now it is not too hard to implement a pattern matcher. For practice we will use a chain of objects to do the matching. There will be one object in the chain for each character in the pattern. I will use “ca.t” to illustrate. The chain for this pattern will contain at least four objects. The first object (head) in the chain is special. It needs to find the first occurrence of the character c in the target string and pass the target string and the location in the string to the next object in chain. If the next object in the chain reports success, then the head of the chain returns the location of the pattern. If the next object reports failure to match, the head object needs to find the second occurrence of c in the string. The head object will try all occurrences of c in the string until a match is found or it is determined that the pattern is not in the string. The second object in the chain behaves slightly differently. It is given a position and the string from the head object. If the next character is an “a” it passes the request to match to the next object in the chain. It then reports to the head object the result returned by the rest of the chain. If the next character is not an “a” it returns failure to the head chain.

You will need to think about the how to implement the objects that handle the wild characters. Also there are several ways to handle the end of the chain.

4. Command. Write a command class to add an element to a collection. You can use your favorite collection class in your language. The command has to support undo. Also write a command class that removes an element from a collection. It also has to support undo.

5. Proxy. Implement a proxy to the collection class used in problem 4. The proxy needs to support undo. If you perform N adds and removes on the collection the proxy has to undo all N operations in the correct order. You do not have to support redo.

Grading

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

What to Turn in
Turn in hard copy of your code and unit tests.

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.

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 26-Feb-04