Several months ago now we had an introduction to design patterns by William Mitchell.

As you can tell from the name, the iterator has a lot to do with iteration, so were going to look at both of those first and perhaps see where iteration could use some improvement. The iterator design pattern is so useful that lots of language support it in various and differing ways.  I’ve prepared examples in these four languages and we will hopefully be able to step through them in a debugger to see how they work.

So, here we go.

Probably everyone who knows a C-style language will recognize the “for” statement here as an example of iteration.  It has been with us since the 70s or before.  It is used so often that other loops like “while” and “do while” are rare.  If you use BASIC, there you will have “for i=1 to SIZE” and a “next.” Object-oriented languages, especially C++, have kept this syntax in part for backward compatibility.  Java made an improvement in that arrays are aware of their length, but did not go much beyond that.  In many cases it is easier for the programmer to stick to the procedural recipe than to improve on it.  Let’s see what kinds of potential problems this can cause.

A proposed solution to these problems and others is the iterator.  This is how the gang of four define an iterator: “… a way to access the elements of an aggregate object [collection] sequentially without exposing its underlying representation.”  We will extend this to mean not just an aggregate object, but any aggregate object and also open it up non-sequential access.  There are, for example, iterators that return random elements of a collection.

The first problem that I notice is that this loop really only applies to arrays.  Other data structures have their own idiomatic ways of accessing their members.  If the data structure changes, we can still use the “for” statement, but the details will have to change.

Let’s look at how some of the problematic examples of iteration might look if we used an iterator instead.  Here we have different iterators to traverse different kinds of structures: array, linked list, tree, and queue.  Since they all use the same method, next(), we can define an interface or abstract class and use that for traversal. In C++ we can override operator++ and use it instead of next() so that we stay compatible with the old procedural code.

If we have to do very many different things with the data structure, then the traversal code is duplicated and this violates the once and only once principle.  In C, this could be avoided using a function pointer and a callback.  For the min and max examples, some sort of state has to be stored as well.  This is somewhat complicated, especially for beginners.

Internal iterators can be used to remove the duplicated traversal code.  We’ll distinguish internal and external iterators shortly.

This is code similar to what we had a few months ago in a demonstration of JUnit and some eXtreme Programming methods, except that code was even more complicated: there was no function “between”.  Instead, there were another six to ten lines of code here.  The code did both the traversal and the processing and therefore violates the single responsibility principle.

Internal iterators can help separate traversal and processing code.  In this example we have an internal iterator which provides tax bracket pairs two at a time so that the tax calculation code need not concern itself with traversal.

Here is an example of a problem that I used to try to solve in BASIC.  It is a brute force solution of the equation “hocus + pocus = presto”.  On old computers this would take several days to solve and there was no way to exit this program and continue it later because there is no good way to jump into the middle of it.  The state is contained in transient variables. 

In this example, the state of the search is encapsulated in this variable hocusPocusPrestoOdometer, which can be copied, stored, reset, and so on.  It is a bookmark in the list of possible values for h, o, c, u, and s.

Here are some of the design goals according to the Design Patterns book.  The first three we sort of talked about already. An example of the fourth is if we want to go either forward or backward through a collection. While doing this, we don’t want to compilcate the interfaces of collections.  For example, we don’t want to have to add push() and pop() to strings so that they can act as queues, and prev() and next() so they can act like linked lists, and so on.

Here is a simple, somewhat more concrete example taken from Design Patterns.  For the List class there is an iterator class called ListIterator, which knows about its list.  It keeps track of an index, which gives the current position in the list.  It returns the element at that index upon request and it knows when all elements have been processed.  The interface is adequate for writing the loop.  This is an external iterator because the client code controls the traversal with iterator.Next().

With an internal iterator, the client code does not control the iteration.  Here something unseen is calling Next() and CurrentItem(), but we’ll see shortly that C# really uses an external iterator behind the scenes.

Here are a few issues that you can think about as we look at some concrete examples.  For the most part, these issues all have relatively good solutions.

My conclusion here isn’t very bold.  These four languages support iterators either through syntax or libraries and it’s not as complicated as one might think.  The standard OO adoption process is effective.  Use what’s there to get started, then begin making your own, and finally move away from the procedural version, iteration, and toward the object-oriented solution, iterators instead.

Here is an example program found in a published book that desperately needs some iterators.  If you ever wonder why your computer is so slow, you might guess that it is trying to divide every single number nearly twice by both five and seven.  I’d like to see who can come up with a better way and maybe we can offer a prize for the best solution.