Employ the Iterator class to streamline filtering

Iterator objects don't store objects the way arrays and linked lists do. See how using a filtering Iterator class can help you avoid wasted memory and decreased performance.

By using a filtering Iterator class, you can avoid the need to consume an Iterator’s contents to produce another Iterator that contains a subset of the original Iterator’s objects. For example, if you have an Iterator filled with objects and nulls, and you want only the nonnull objects, a filtering Iterator can streamline the process with a minimum of wasted time and memory.

Iterator objects
Iterator objects provide a great mechanism for representing a sequence of objects because they don’t store objects the way arrays do—nor do they store references to objects the way linked lists do. Instead, they simply provide methods that can be used to access objects provided by a separate object source. This reduces the memory they require by avoiding costly storage of duplicate objects. Passing Iterator objects as function parameters can also be faster than passing in a cloned List object, because the copies to be contained in the Iterator need not be created unless the receiving method decides to consume the Iterator fully.

Listing A contains the source code for a filtering Iterator class. This filtering Iterator takes the objects found in a source Iterator and filters them through a simple test provided at the time of object instantiation. Objects that pass the test are made available through the filtering Iterator’s own Iterator interface methods. Let’s look more closely at Listing A to see how the filtering Iterator works.

Filtering Iterator nuts and bolts
As the filtering Iterator implements the java.util.Iterator interface, it must provide implementations for the methods defined within that interface. Consequently, the remove, hasNext, and next methods are all present in the FilteringIterator class. The remove method simply throws an UnsupportedOperationException when invoked, as it is generally not useful in the case of a filtering Iterator.

The hasNext method handles the application of the filter. Inside it, a while loop iterates through the provided source Iterator until finding an object from the source that passes the filter’s test or the end of the source Iterator is reached. If an object that passes is found, a reference to it is stored in the next field and true is returned. If the end of the source Iterator is reached, the next field is left null and false is returned.

The next method calls the hasNext method to see whether more objects meeting the requirements imposed by the filter are available. When no more objects passing the filtering Iterator’s test are available, the next method throws a NoSuchElementException in accordance with the java.util.Iterator interface requirements. If a hasNext returns true, the next field is set to null and its previous value is returned.

It should be noted that no synchronization is done in this class. Like the Java collections classes, it’s generally best to leave synchronization up to the code that instantiates and uses your utility classes. Thus, if you want to access a single filtering Iterator instance from multiple threads, you’ll need to create synchronized wrapper methods yourself.

Absent in Listing A is the implementation of the filter that is applied by the hasNext method. Instead, you'll find an abstract method named accept, which takes an object and returns a Boolean. From its usage in hasNext, you can see that when accept returns true, the provided object passes the filter and is produced by the filtering Iterator. When accept returns false, the object is omitted from the series of objects.

Using the filtering Iterator
Providing an implementation for the accept method is easy to do at instantiation time through the use of an anonymous inner class. Listing B shows an example of usage for the FilteringIterator class. Notice how the body of the accept method is provided at the same time that the instance of the object is created. Anonymous inner classes have in their scope any field, including private, of the containing class and any final local variables and method parameters of the containing method.

In Listing B, you can see that the filtering Iterator as applied prevents any null values produced by the source Iterator from making it through to the returned Iterator. This filtering is done on the fly without ever storing all the contents of the source Iterator in memory at any one time.

The wrong way
Contrast the filtering Iterator solution to the one in Listing C. There, the full source Iterator is consumed in the process of filtering. Not only is this wasteful of memory in the case of a large Iterator, but it can also become an input/output (I/O) nightmare. If the source Iterator is an ObjectInputStream creating objects from data pulled across the network, the filter in Listing C will have to wait until the full series has been pulled local before a filtered Iterator can be provided. Conversely, the filtering Iterator can return an Iterator before even the first object has been pulled across the network and decoded.

The FilteringIterator class, along with the BufferedIterator class, can work together to make data flow within your application more stream-based. This, in turn, yields applications that can use less memory and can waste less time during IO operations.


Editor's Picks