Iterator Pattern

Photo by Eva Blue on Unsplash

Iterator Pattern

ยท

4 min read

The Iterator design pattern is a well-known and often-used pattern. It allows us to access elements in a collection without the need to know about the underlying storage details. We get this functionality from an object known as an iterator of the collection.

Different languages support creating iterators when working with collections. Check out this article for an example of using iterators in the Rust language. In the JVM land, a language like Java has the concept of a collections framework. In the framework, we find a Set, a List, and a Deque among other types. All these types define a Collection of elements that can be iterated. Their difference lies in how elements are stored and retrieved.

All Java collections conform to the Iterable interface. This interface requires that any object that conforms to it, provide an implementation that will return an instance of an Iterator:

public interface Iterator<E> {

    boolean hasNext();

    E next();

    ...
}

The idea behind this definition is that for any iterator, we can:

  • Check if there's a next element in the iteration

  • Ask for the next element

By combining these two operations, we can traverse any generic collection without consideration of how the elements are stored and for any number of elements.

If we call iterator.hasNext() and it returns false, what happens if we call iterator.next()? ๐Ÿค”

While we can directly invoke the above traversal methods to advance an iteration, most JVM languages offer iteration syntactic sugar that decomposes to these calls on an Iterator. Let us consider the following example:

fun main() {
    val numbers = listOf(1, 2, 3, 4)

    for (number in numbers) {
        println(number)
    }
}

The byte code result of compiling the above snippet shows a couple of INVOKEINTERFACE calls to methods on the Iterator interface. Decompiling this byte code, we get the stripped-out listing below:

List numbers = CollectionsKt.listOf(new Integer[]{1, 2, 3, 4});
Iterator var2 = numbers.iterator();

while(var2.hasNext()) {
  int number = ((Number)var2.next()).intValue();
  System.out.println(number);
}

We see that the compiler extracts an Iterator from our numbers collection and replaces the for-loop construct with a while-loop. It then invokes hasNext() to check the existence of the next element. If this returns true, a call to next() retrieves the next element in the collection and we act on it. These last two steps are executed numbers.size() times. This is the typical use case of the iterator pattern for built-in collection types. Let's look at a use case in Android.

Iterating on Android Fragments

Android facilitates building UI by composing several standalone UI portions. When we create these modular UI portions, we bind them to a Fragment and add these fragment instances to an Activity.

The following snippet shows a method that retrieves ids of all fragments added to an Activity.

class SomeActivity : AppCompatActivity() {

    fun fragmentIds(): List<Int> = 
        supportFragmentManager
            .fragments
            .map(Fragment::getId)
}

It might not be obvious that the iterator pattern is in use here. But if we dig into the map(...) call, we find that it is an extension function that iterates and maps elements in an Iterable according to the given transform function. There are a couple more such extensions that add operators applicable to the implementations of Iterable.

As seen, we are oblivious to how the fragments are stored in the FragmentManager. Our algorithm receives each added fragment, extracts its id, and adds this id to a list of fragment ids. This operation is powered by the iterator pattern.

Countries of Africa

As a final example, let's look at a Compose desktop app with a custom implementation of the iterator pattern.

https://ontheworldmap.com/africa/africa-political-map.jpg

https://ontheworldmap.com/africa/africa-political-map.jpg

The African continent has 54 countries. In our sample code, each country is represented by a couple of properties such as its name, flag etc. We model the continent using a type, Africa, as shown below. By conforming to Iterable, we can iterate through all constituent countries of Africa. We can achieve this by defining an internal iterator, CountryIterator, and returning its instance for a call to iterator() on Africa. In our implementation, we maintain the state of the iteration using the nextIndex property.

class Africa(private val countries: Countries) : Iterable<Country> {

    override fun iterator(): Iterator<Country> = CountryIterator(countries)

    private class CountryIterator(private val countries: Countries) : Iterator<Country> {

        private var nextIndex = if (countries.isEmpty()) -1 else 0

        override fun hasNext(): Boolean = nextIndex in countries.indices

        override fun next(): Country {
            if (!hasNext()) throw NoSuchElementException("No more countries")
            return countries[nextIndex].also {
                nextIndex += 1
            }
        }
    }
}

We then iterate through all countries, adding a corresponding CountryRow item in the LazyColumn for each country.

LazyColumn {
    val iterator = africa.iterator()
    while (iterator.hasNext()) {
        val country = iterator.next()
        item(key = country.code) {
            CountryRow(country = country)
        }
    }
}

This creates the country UI listing as shown:

Get the full source on GitHub.

Conclusion

We can iterate over a collection multiple times, create iterators that mutate the collection, iterate an ordered collection backward and so much more. The iterator pattern is a welcome addition to our set of patterns for software design.

Happy coding!

Did you find this article valuable?

Support Charles Muchene by becoming a sponsor. Any amount is appreciated!