Design Patterns: Iterator Pattern

no_mkd

I. What is the Iterator Pattern?

Use an iterator to encapsulate the traversal details of collection objects, allowing callers to traverse collections through a unified interface.

The iterator also provides certain protection for collection objects. To traverse a collection, just call the iterator's methods. We don't need to know (and don't have to know) the internal data management method of the collection.

II. An Example

Suppose there is a set of custom objects, and we don't know what collection object is used to maintain them. It could be Array, List, or something else. Our job is to traverse this set of objects (or add some extra processing based on the traversal). Think about how we can implement this?

First, determine the type of the collection object, then handle each differently. For each different collection type, we need a different loop to handle it. Although these loop blocks have only subtle differences, we still have to provide a loop to handle them... If there are 100 different collection types, we may have to use 100 similar loops to implement traversal, undoubtedly resulting in a large amount of redundant code. So we need a unified entry point, hoping to turn n loops into one highly adaptable loop. The iterator is the unified entry point we've been longing for:

Iterator Interface

package IteratorPattern;
/**


@author ayqy


Define iterator
*/
public interface Iterator {
/**

@return Whether there is a next element in the collection
/
public abstract boolean hasNext();
/*
@return Return the next element in the collection
*/
public abstract Object next();
}

We also need to implement some concrete iterators to implement traversal details:

Array Iterator:

package IteratorPattern;
/**


@author ayqy


Implement array iterator
*/
public class ArrayIterator implements Iterator{
MyObject[] arr;//Custom object array
int index = 0;//Current index
public ArrayIterator(MyObject[] arr){
this.arr = arr;
}
@Override
public boolean hasNext() {
if(index < arr.length && arr[index] != null)
return true;
 return false;

}
@Override
public Object next() {
MyObject mo = arr[index];
index++;
 return mo;

}
}

P.S. Note the concrete implementation of the hasNext method in the Array iterator

List Iterator:

package IteratorPattern;
import java.util.List;
/**


@author ayqy


Implement List iterator
*/
public class ListIterator implements Iterator{
List<MyObject> list;//Collection object
int index = 0;//Current index
public ListIterator(List<MyObject> list){
this.list = list;
}
@Override
public boolean hasNext() {
if(index < list.size())
return true;
 return false;

}
@Override
public Object next() {
MyObject mo = list.get(index);
index++;
 return mo;

}
}

With these concrete iterators, we only need one loop to get it done:

/**
 * Print all content of the collection
 * @param iter Iterator of the collection
 */
private static void printObjs(Iterator iter){
	while(iter.hasNext()){
		System.out.println(iter.next().toString());
	}
}

III. Java's Support for Iterator

Due to the convenience and necessity of iterators, Java provided support for Iterator after version 1.5. Currently, many collection objects support Iterator, such as Set, List, Map, SortedSet, SortedMap, HashSet, TreeSet, ArrayList, LinkedList, Vector, etc.

The only thing that doesn't support iterators might be arrays (except for special ones like stacks and queues). Above we implemented a custom Iterator interface. Actually, Java itself provides this interface (java.util.Iterator), but the difference is:

The Java.util.Iterator interface defines three methods (in addition to hasNext and next methods, there's also a remove method):

If a collection object is unwilling to provide a remove method, it doesn't matter. We can throw an exception to refuse implementation, like this:

package IteratorPattern;
/**


@author ayqy


Implement array iterator using Java's provided Iterator interface
*/
public class JavaArrayIterator implements java.util.Iterator{
MyObject[] arr;//Custom object array
int index = 0;//Current index
public JavaArrayIterator(MyObject[] arr){
this.arr = arr;
}
@Override
public boolean hasNext() {
if(index < arr.length && arr[index] != null)
return true;
 return false;

}
@Override
public Object next() {
MyObject mo = arr[index];
index++;
 return mo;

}
@Override
public void remove() {
//Throw operation not supported exception
throw new UnsupportedOperationException();
}
}

The iterator calling method remains completely unchanged:

/**
 * Print all content of the collection
 * @param iter Iterator of the collection
 */
private static void printObjs(java.util.Iterator iter){
	while(iter.hasNext()){
		System.out.println(iter.next().toString());
	}
}

IV. Implicit Calling of Iterators

Many languages support for each (or for in) loops, whose internal implementation calls the iterator to complete traversal. Of course, this is just a small piece of common knowledge. More importantly, learn the design principles of iterators and define your own iterators when needed.

V. Extension

The Iterator Pattern itself is relatively simple. We may not even need to define our own iterators anymore (the iterator interfaces provided by APIs can almost meet our needs).

But when iterators are combined with the Composite Pattern, they can do something incredible (will be introduced in detail in the Composite Pattern, click me to jump>>)