Iterator Design Pattern

By: Stephen Patrick | 12 Sep 2016 | Category: Java Iteration

Iterator

An iterator also known as an enumerator is a common design pattern. It is a data structure that is used to hide an underlying data structure and the interface used to process that data structure. An iterator provides a common interface to processing the elements of a data structure. Iteration is a common process performed with different data structures such as: string, array, collection etc. Normally, we use a java for loop to process the elements of an array for a specific purpose. However, sometimes we might want to provide a unified interface to process our custom data types, encapsulating our underlying data structures. Moreover, we might want greater flexibility in how we process the data, for example moving in a certain direction, skipping elements and / or ignoring data that does not meet specific criteria. In these cases and more the Iterator data structure is useful. Java provides a java.util.Iterator for just this purpose, but we will create our own Iterator implementation.

Iterator Interface

Firstly, we will define our iterator interface.

public interface Iterator<T> {
   boolean isDone();
   void first();
   void last();
   void next();
   void previous();
   T current();
}

Above we define our Iterator interface. The isDone method is used to track if iteration is complete. The first and last methods are used to move to the first and last elements. The next and previous methods move back and forth respectively. The current method returns the current item.

Iterable Inteface

Another interface that we will define is the Iterable interface. The purpose of this interface is to define a common interface for returning an iterator to a client. Any component that wishes to provide an iterator to its client will implement this interface.

public interface Iterable<T> {
   public Iterator<T> iterator();
}

List Iterator

We will create a list iterator to iterate a List data structure. The ArrayList and LinkedList are two common data structures used in java. One offers synchronization to a degree while the other offers no synchronization. Following a test first approach some tests will be created to drive the ListIterator that we are going to create. Firstly, the skeleton of our Unit Test class is created.

public class ListIteratorTest {
   private List<Integer> sampleList;

   @Before
   public void setUp() {
       sampleList = new LinkedList<Integer>();

       for (int i = 0; i < 5; i++) {
           sampleList.add(i + 1);
       }

       sampleList = Collections.unmodifiableList(sampleList);
   }

}

Above, we define the ListIteratorTest test class. In the setUp method a variable named sampleList is initialized. This class level variable holds the data that will be iterated within our tests. Next we create our first test to assert the isDone Method. The purpose of this method is to determine if there are more items to iterate, and when all elements are iterated the isDone method should return true.

   @Test
   public void IsDone() {
       ListIterator<Integer> iterator = new ListIterator<Integer>(sampleList);
       Assert.assertFalse("Expected not to be done", iterator.isDone());
       iterator.next();
       Assert.assertFalse("Expected not to be done", iterator.isDone());
       iterator.next();
       Assert.assertFalse("Expected not to be done", iterator.isDone());
       iterator.next();
       Assert.assertFalse("Expected not to be done", iterator.isDone());
       iterator.next();
       Assert.assertFalse("Expected not to be done", iterator.isDone());
       iterator.next();
       Assert.assertTrue("Expected to be done", iterator.isDone());
   }

In order for our code to compile we will begin to create our ListIterator implementation. The class contains default implementations for the Iterator interface. The list class variable holds the list data structure that we will iterate, and the current variable tracks the current iteration index.

public class ListIterator<T> implements Iterator<T> {
   private List<T> list;
   private int current = 0;

   public ListIterator(List<T> list) {
       this.list = Collections.unmodifiableList(list);
   }

   public boolean isDone() {
       return false;
   }

   //default method implementations
}

Next we run the isDone test which fails. In order for this test to pass we need to implement some methods of our List Iterator.

public boolean isDone() {
       if (current < 0 || current >= list.size()) {
           return true;
       }

       return false;
   }

   public void first() {
       current = 0;
   }

   public void next() {
       setCurrent(1);
   }

   public void previous() {
       setCurrent(-1);
   }

   protected void setCurrent(int step) {
       current = current += step;
   }

   public void last() {
       current = list.size() - 1;
   }

   public T current() {
       if (isDone()) {
           throw new IndexOutOfBoundsException("Iterator index out of bounds");
       }

       return list.get(current);
   }

After verifying the isDone test completes successfully, a test for the next method is created.

@Test
public void next() {
   ListIterator<Integer> iterator = new ListIterator<Integer>(sampleList);
   Assert.assertFalse("Expected not to be done", iterator.isDone());
   int testIndex = 0;
   while(!iterator.isDone()) {
       Assert.assertFalse("Expected not to be done", iterator.isDone());
       Assert.assertEquals(iterator.current(), sampleList.get(testIndex));
       iterator.next();
       testIndex ++;
   }
   Assert.assertTrue("Expected to be done", iterator.isDone());
}

A variable named testIndex is used to track the list index for testing purposes and to simplify the testing code. After confirming that our tests run successfully the implementation of the previous test method is started. However, the iteration process is similar to that of the next test method, so the code is refactored into its own custom assertion method.

protected void assertIteration(Iterator<? extends Object> iterator,
           boolean forward) {

       int testIndex = forward ? 0 : sampleList.size() - 1;

       while (!iterator.isDone()) {
           Assert.assertFalse("Expected not to be done", iterator.isDone());
           Assert.assertEquals(iterator.current(), sampleList.get(testIndex));
           if (forward) {
               iterator.next();
           } else {
               iterator.previous();
           }

           testIndex = forward ? testIndex + 1 : testIndex - 1;
       }

       Assert.assertTrue("Expected to be done", iterator.isDone());
   }

The next test method is updated to reflect these changes.

   @Test
   public void next() {
       Iterator<Integer> iterator = createTestIterator();

       Assert.assertFalse("Expected not to be done", iterator.isDone());
       assertIteration(iterator, true);
       Assert.assertTrue("Expected to be done", iterator.isDone());
   }

On successful execution of the unit tests, the previous test method is implemented.

   @Test
   public void previous() {
       Iterator<Integer> iterator = createTestIterator();

       iterator.last();
       Assert.assertFalse("Expected not to be done", iterator.isDone());
       assertIteration(iterator, false);
       Assert.assertTrue("Expected to be done", iterator.isDone());
   }

We add some more test methods to test our implementation such as iteration on an empty list, and to test error conditions. The code can be found here.

Decorator Design Pattern

Although, iteration could be performed in reverse order, we will create a new iterator that wraps an existing iterator and reverses the iteration order. The implementation follows the Decorator Design Pattern, in that we wrap and delegate to the underlying iterator.

public class ReverseIterator<T> implements Iterator<T> {

   private Iterator<T> iterator;

   public ReverseIterator(Iterator<T> iterator) {
       this.iterator = iterator;
       iterator.last();
   }

   public boolean isDone() {
       return iterator.isDone();
   }

   public void first() {
       iterator.last();

   }

   public void last() {
       iterator.first();
   }

   public void next() {
       iterator.previous();

   }

   public void previous() {
       iterator.next();

   }

   public T current() {
       return iterator.current();
   }
}

The implementation of the Reverse Iterator is quite simple. The iteration order is reversed by changing the order of calls to the underlying iterator. The implementation calls the opposite method of the underlying iterator i.e. calling next on the reverse iterator delegates to the previous method.

Our custom iterator implementation provides a number of advantages in that our code can return a custom iterator without affecting the client code. If there is a requirement to change the iteration order we can create a custom iterator for this task.

The code for this example can be found here and the test code is located here.