http://www.developer.com/

Back to article

Working With Design Patterns: Iterator


July 9, 2008

Iterator is a pattern? Come on, now! You've known how to step sequentially through a collection of objects since childhood. Programmer childhood, anyway.

Remember that the Design Patterns book, in which the iterator pattern was formally defined as part of a catalog of patterns, was published in 1995. No Java to speak of: C++ was the dominant OO language. Object-oriented development itself was new to most programmers.

C++ coders at the time typically would provide a custom mechanism to allow iteration against a collection. A programmer might provide prev and next methods to allow moving forward and backward through a linked list. For other collections, they might even expose a pointer to an encapsulated data structure, such as an array, and let the client figure out how to iterate it. In many cases, the solution for iteration involved exposing lots of specific details about the underlying collection implementation.

Smalltalk, also prevalent at the time, included a consistent set of internal iterators, afforded by its use of closures. An internal iterator controls the iteration across a collection, whereas an external iterator allows a client to control iteration. External iterators in general provide more flexibility, allowing the client to define particular iteration uses that the designers of the collection class might not have considered. In contrast, internal iterators simplify the work that client code must do.

Smalltalk programmers had it very easy. Faced with the need to iterate any kind of collection, they could always use one of the handful of standard iteration mechanisms (do:, select:, detect:, reject:, and inject:into:).

Java entered the scene with a minimal set of collection classes that supported external iteration. The original workhorse collection class Vector provided an elements() method that returned an Enumeration object. Clients could use this Enumeration object as the basis for iterating across a collection:

Vector names = new Vector();
names.add("Yossarian");
names.add("Minderbinder");
names.add("Clevinger");
for (Enumeration e = names.elements(); e.hasMoreElements(); ) {
   String name = (String)e.nextElement();
   // ...
}

Of course, the existence of this iteration mechanism didn't prevent programmers from bypassing it:

for (int i = 0; i < names.size(); i++) {
   String name = (String)names.get(i);
   // ...
}

Some developers to this day prefer this form of iteration, sometimes taking advantage of (possibly) slightly improved performance. But it's not as object-oriented, if that matters, because clients must understand the underlying representation of the list, never mind how simple it is in the case of Vector. If the programmer decides to change the collection to an unordered one (such as a set), the loop must be recoded.

With Java 2's collection class framework, Sun introduced a more robust set of collection classes that used a consistent set of interfaces and iterators. Enumeration was replaced with Iterator, and the method names simplified, to help make looping through a collection a bit more concise:

List names = new ArrayList();
names.add("Yossarian");
names.add("Minderbinder");
names.add("Clevinger");

for (Iterator it = names.iterator(); it.hasNext(); ) {
   String name = (String)it.next();
   // ...
}

Figure 1 shows a UML representation of the iterator pattern, as implemented in ArrayList from JDK 1.2 through JDK 1.4. Note that this is a simplified diagram, omitting some intermediary abstract classes and interfaces.

Figure 1: The iterator pattern.

Oddly, I still see Java programmers who choose to use Vector instead of ArrayList, and never mind that idea of assigning to an interface type, thank you but no thanks. If they claim an excuse other than "having a tough time kicking a ten-year-old habit," it might be that they want the synchronization that comes with Vector by default, although they could certainly use the synchronization wrappers in the collections framework. A more legitimate excuse I've heard is that they wanted control over the growth increment for Vector, something that disappeared with the newer ArrayList class.

Three different iteration techniques for traversing a list apparently was not enough. With Java 5, Sun introduced the enhanced-for loop, providing another mechanism for collection traversals:

List<String> names = new ArrayList<String>();
names.add("Yossarian");
names.add("Minderbinder");
names.add("Clevinger");

for (String name: names) {
   // ...
}

The enhanced-for loop takes advantage of the ability to bind a class to parameterized types, eliminating the need for any casting in the client solution. Even better, programmers can provide enhanced-for loop support in their classes by having them implement the Iterable interface:

class Menu implements Iterable<String> {
   private List<String> items = new ArrayList<String>();

   public void add(String item) {
      items.add(item);
   }

   @Override
   public Iterator<String> iterator() {
      return items.iterator();
   }
}

By having Menu implement Iterable, clients can code simple for-each loops to traverse all the menu items:

Menu menu = new Menu();
menu.add("Beef Stroganoff");
menu.add("Filet Mignon");
menu.add("Rice with Tofu");

for (String item: menu) {
   // ...
}

The enhanced-for loop syntax is about as concise as Java could allow, at least until the possible introduction of closures in Java 7.

Exploring Enhanced-For

I appreciate the enhanced-for loop: Anything that makes the code more concise and expressive at the same time is good. But, it doesn't quite cover everything. If I want to iterate through the numbers 0 through 9, I'm still stuck with the classic C-style for the loop idiom:

for (int i = 0; i < 9; i++)
   ...

But, what if I considered representing the range as a new abstraction:

Sequence s = new Sequence(0, 9);

At that point, I could have the Sequence class implement Iterable<Integer>, thus supporting use of the enhanced-for loop:

for (int i: new Sequence(0, 9))
   ...

With the addition of auto-unboxing, this makes for a very concise client interface. Listing 1 shows the complete implementation for a Sequence class:

Listing 1: The Sequence class

import java.util.Iterator;

public class Sequence implements Iterable<Integer> {
   private int start;
   private int stop;
   private int increment = 1;

   public Sequence(int start, int stop) {
      this.start = start;
      this.stop = stop;
   }

   public Sequence(int start, int stop, int increment) {
      this(start, stop);
      this.increment = increment;
   }

   public Iterator<Integer> iterator() {
      return new SequenceIterator();
   }

   private class SequenceIterator implements Iterator<Integer> {
      private int count = start;
      public boolean hasNext() {
         return count <= stop;
      }

      public Integer next() {
         int result = count;
         count += increment;
         return result;
      }

      public void remove() {
         throw new UnsupportedOperationException();
      }
   }
}

The Sequence class also provides the ability to skip elements. A set of tests demonstrating use of the Sequence class appears in Listing 2.

Listing 2: SequenceTest

import static org.junit.Assert.*;
import org.junit.*;
import java.util.*;

public class SequenceTest {
   private List<Integer> ints;

   @Before
   public void createCollection() {
      ints = new ArrayList<Integer>();
   }

   @Test
   public void singleEntry() {
      verifySequence(new Sequence(0, 0), 0);
   }

   @Test
   public void twoEntries() {
      verifySequence(new Sequence(1, 2), 1, 2);
   }

   @Test
   public void multipleEntries() {
      verifySequence(new Sequence(5, 10), 5, 6, 7, 8, 9, 10);
   }

   @Test
   public void negativeNumbers() {
      verifySequence(new Sequence(-2, 2), -2, -1, 0, 1, 2);
   }

   @Test
   public void increment() {
      verifySequence(new Sequence(0, 5, 2), 0, 2, 4);
   }

   @Test
   public void incrementIncludesLimit() {
      verifySequence(new Sequence(0, 6, 2), 0, 2, 4, 6);
   }

   private void verifySequence(Sequence sequence,
      int... expectedValues) {
      for (int i: sequence)
         ints.add(i);
      assertEquals(expectedValues.length, ints.size());
      for (int i: expectedValues)
         assertTrue(ints.contains(i));
   }
}

What's the value? It affords more concise code, and there are benefits of Sequence being an object. You can pass around a sequence (and persist it), as opposed to having to pass around discrete numbers representing the range and other information, such as the step value. You also could extend its capabilities without altering code that uses a sequence. For example, you could provide the ability to suspend a sequence, and later have it resume where it left off.

Iteration is one of the more prevalent operations in computing. It's fitting that you find as concise, consistent, and expressive a manner to accomplish it. Sun has produced three Java collection iteration mechanisms to date, improving the solution each time. No doubt, you'll see another mechanism in the not-too-distant future.

About the Author

Jeff Langr is a veteran software developer with over a quarter century of professional software development experience. He's written two books, including Agile Java: Crafting Code With Test-Driven Development (Prentice Hall) in 2005. Jeff has contributed a couple chapters to Uncle Bob Martin's upcoming book, Clean Code. Jeff has written over 75 articles on software development, with over thirty appearing at Developer.com. You can find out more about Jeff at his site, http://langrsoft.com, or you can contact him via email at jeff at langrsoft dot com.

Sitemap | Contact Us

Thanks for your registration, follow us on our social networks to keep up-to-date