Iterating Over Collections

17. Iterating Over Collections

Key concepts

Ordered (Indexed) Collections
Unordered Collections
Iteration Abstracted
Common Iteration Idioms

Introduction

Let's take another look at the CompactDisc class we developed in a previous lesson. Suppose we want to add a method to the CompactDisc class that will print out the name of every song on the disc. We can say how we would do this in English:

Walk through the collection of songs, printing the name of each one.

In this lesson we'll apply the concept of iteration to the management and processing of collections.

Ordered Collections

Let's start by revisiting the way that we can access the items of a ArrayList. Suppose we have an ArrayList that we know contains three Strings and we want to print out each of them. We can do this as follows:

output.println(nameList.get(0));  
output.println(nameList.get(1));  
output.println(nameList.get(2));

This works, but is tedious if the list contains many items. More problematic, however, is the fact that it won't work if we don't know when we write our program how many items the list contains. The solution is to use iteration, which is a way to execute a variable number of statements. Since we know how to ask an ArrayList how many items it contains, we can write a counting loop that accesses each item of our ArrayList sequentially, from zero up to the number of items in the ArrayList:

int numNames = nameList.size();
for (int i=0; i<numNames; i++) {
  output.println(nameList.get(i));
}

In English, this fragment of code implements the following algorithm:

For each item of the list, print it.

Remember that the items in the ArrayList live at indices 0 to size-1. A very common error is to iterate over items 0 to size:

int numNames = nameList.size();
for (int i=0; i<=numNames; i++) {
  output.println(nameList.get(i));
}

Unordered Collections: The Easy Way

What about iterating over the items in an unordered collection? Remember, the items in an unordered collections are just that, unordered -- that is, there is no first, last, or in general, i-th element. However, if we can find a way to make an ordered collection out of the items in our unordered collection, then we can reuse the pattern we learned above. By inspecting the full interface for some of the Java collection classes, we see that we can do the following:

HashMap someTable = new HashMap();
// assume we add some items here...

// the keySet() method on HashMaps returns a Set of the keys of the map
Set keys = someTable.keySet();

// now we can create and initialize a new ArrayList with that collection
ArrayList list = new ArrayList(keys);

// and now we can iterate
for (int i=0; i<list.size(); i++) {
  // Access the values of the map with:  someTable.get(list.get(i))
}

In other words, we ask the HashMap for a Set of its keys and then create a new ArrayList (initialized by the elements of that collection) and exploit its indexability to access the values of the HashMap. While this is a roundabout method of approaching the problem, it does work, and it requires only that we understand a single pattern for iterating over collections.

Iteration Abstracted: an Iterator

It turns out that there is a more general purpose way to iterate over collections in Java, achieved by a decoupling of the concept of iteration from the collection itself. To support a uniform model of iteration over the items of any kind of collection in Java, we may ask a collection for an object that allows us to sequentially access the items in that collection. In general, such an object is called an iterator. Java provides a couple of different kinds of iterators, but we'll just look at one called, appropriately enough, Iterator:

public interface Iterator {

  /** Answer the next Object and advance the iterator. */
  public Object next();

  /** Answer true if the iterator has more elements. */
  public boolean hasNext();
}

We can ask a HashMap for an iterator enumeration of all of its keys as follows:

// Create a HashMap and add some mappings
HashMap map = new HashMap();
map.put("Willa", "Cather");
map.put("Raymond", "Carver");

// Now get the Set of its keys
Set keys = map.keySet();

// Now get an iterator over this set:
Iterator iter = keys.iterator();

Since an Iterator does not provide us with a notion of size, or indexed access, it is not natural to use a counting loop when processing an Iterator. A while-loop, however, will do the trick nicely:

// Create a HashMap and add some mappings
HashMap map = new HashMap();
map.put("Willa", "Cather");
map.put("Albert", "Camus");
map.put("Raymond", "Carver");

// Now get the iterator and iterate over it
Iterator iter = map.keySet().iterator();

while (iter.hasNext()) {
  Object aKey = iter.next();
  output.println(aKey + " " + map.get(aKey));
}

In English, the above fragment expresses the following algorithm:

First, get all of the keys in the map.
Next, while there are still keys, get the next key and print out the
  key and the associated value from the map.

If we ran the program, the output might look like this. Notice that the order presented here bears no relation to the order in which these things were originally inserted into the table -- the HashMap makes no guarantees about the order in which it stores its mappings.

Raymond Carver
Albert Camus
Willa Cather

Finally, by inspecting the interface for the class ArrayList, we see that ArrayLists are also willing to provide us with Iterators we can use to iterate over their contents. Here's an example:

ArrayList names = new ArrayList();
names.add("Bob");
names.add("Bill");
names.add("Susan");

// Now get an Iterator and iterate over it
Iterator iter = names.iterator();

while (iter.hasNext()) {
  Object item = iter.next();
  output.println(item);
}

The great thing about using iterators is that we learn one pattern for iterating over the items inside of a collection and can reuse that style of iteration for all of Java's collection classes.

Common Idioms

At this point, we're ready to classify common patterns of iteration over collections. It turns out that perhaps 90% of loops over collections fall into one of three categories: simple traversal, reduction, and filtering.

The loops we've seen so far are examples of simple traversals. They simply walk over the collection, doing something to or with each item. We can write the pattern as follows:

Iterator iter = <collection>.iterator();
while (iter.hasNext()) {
  Object item = iter.next();
  <do something with the current item>
}

A reduction is a loop that aims to reduce, or distill some piece of information out of the elements in the collection. Examples include finding the largest (or smallest) element, finding a specific element, summing the values of the elements. Suppose we have an ArrayList called names that contains Strings, and we wish to find the longest one:

String longest = null;
Iterator iter = names.iterator();
while (iter.hasNext()) {
  String name = (String)iter.next();
  if (longest == null || longest.length() < name.length()) {
    longest = name;
  }
}

Notice the null check in the if statement inside of the loop. On the first iteration, we have not yet determined the current longest string, so we must check for that. Suppose we want to sum the lengths of all of the Strings in the array:

int totalLength = 0;
Iterator iter = names.iterator();
while (iter.hasNext()) {
  String name = (String)iter.next();
  lotalLength = totalLength + name.length();
}

Both of these loops "boil down" the items in the collection, reducing them to a single piece of information, be it the longest element or the sum of the sizes, or whatever we choose. Here is the pattern for a reduction loop:

<set up initial bindings for the essence>
Iterator iter = <collection>.iterator();
while (iter.hasNext()) {
  Object item = iter.next();
  <rebind the essence based on the current item>
}

A final idiom for collection iteration is one that filters out certain elements of interest. Generally this means collecting the elements that pass a test into a new collection. Suppose we want to collect all of the elements in our ArrayList of Strings that are even in length:

ArrayList evens = new ArrayList();
Iterator iter = someArrayList.iterator();
while (iter.hasNext()) {
  String name = (String)iter.next();
  if (name.length() % 2 == 0) {
    evens.add(name);
  }
}

The above loop tests every element for "even-ness". If the element is even, it is added to a second collection, called "evens". In general, filtering loops tend to look like this:

ArrayList passedTheTest = new ArrayList();
Iterator iter = <collection>.iterator();
while (iter.hasNext()) {
  Object item = iter.next();
  <conditionally add item to the passedTheTest collection>
}

When writing a loop that iterates over a collection, it's useful to ask yourself "Does the iteration fit into a pattern I already know?" Chances are that it will. Understanding and practicing these few patterns will make writing most collection iterations a breeze.