Iterators

On many occasions we want to traverse a Listthat is, visit (do something with or to) each element. To give just a few examples, we might want to:

• Traverse a List of Integers and add each one to a running tally.
• Traverse a List of Doubles to find the maximum of the elements.
• Print each element of a List.
• Compare each element of a List with the corresponding element of another List.
• Traverse a List of URLs to verify that each one leads to a web page that still exists.

A method to accomplish any of these things has the same basic structure as the contains() and toString() methods from ArrayList (Figure 5-28 and Figure 5-29):

for (int i = 0; i < size; i++) { // Do something with data[i] }

Such a method would have to appear in the ArrayList class, because it directly accesses the fields data and size. We could write a method for each traversal we want to perform, but the ArrayList class is supposed to be general-purpose. Code for such specific tasks doesn't belong in this class.

A better approach is to produce an object called an iterator which allows us to traverse the List. An iterator has methods for three requests:

• "Are there more elements in the List?"
• "What is the next element?"
• "You know that last element you returned? Remove it from the List."

This abstract data type is formalized in the Iterator interface, which is in the java.util package.

The Iterator Interface

The Iterator interface in the java.util class specifies three methods: hasNext(), next(), and remove(). As shown in Figure 5-33, none of them take any arguments.

Figure 5-33. The Iterator interface is in the java.util package.

The hasNext() method returns true if there is a next element to be visited. The next() method returns the next element. These two methods are usually used in a loop like this:

java.util.Iterator iter = list.iterator(); while (iter.hasNext()) { // Do something with iter.next() }

We must be careful to invoke next() only once on each pass through the loop, because it both returns an element and advances the Iterator. If we say something like

if ((iter.next() != null) || (iter.next().equals(target))) { ... }

we will advance two elements at a timealmost certainly not what we want.

The remove() method removes the last item visited from the data structure associated with the Iterator. We should invoke this only after invoking next().

The documentation for the Iterator mentions that these methods can throw certain exceptions. (These will be left as exercises in our implementation.) The next() method throws a java.util.NoSuchElementException if there are no more elements to visit. This can be avoided by always checking hasNext() before invoking next().

The remove() method can throw a java.util.IllegalStateException if next() has never been invoked, or has not been invoked since the last invocation of remove(). (Only the last element returned by next() can be removed.) It is also legal to write an implementation of Iterator which does not support removal. In such a class, the remove() method does nothing but throw a java.util.UnsupportedOperationException.

The Iterable Interface

The Iterable interface requires one method, which returns an Iterator. The signature of this method is:

public Iterator iterator();

Our List interface extends Iterable, so any class implementing List (such as ArrayList) must provide this method. We will do so momentarily.

If a class implements Iterable, we can traverse an instance of that class using an enhanced for loop (Appendix A). For example, if numbers is an ArrayList, then we can compute its sum with this short code:

int sum = 0; for (int n : numbers) { sum += n; }

The ArrayIterator Class

The iterator() method in ArrayList has to return an instance of some class which implements Iterator. We will return an instance of the class ArrayIterator. An ArrayIterator knows about the ArrayList with which it is associated. In other words, an ArrayIterator is-a Iterator, but it has-a ArrayList (Figure 5-34).

Figure 5-34. An ArrayIterator is-a java.util.Iterator, but it has-a ArrayList. Strangely, the Iterable interface is in the java.lang package, not the java.util package.

The iterator() method for ArrayList (Figure 5-35) simply creates an instance of ArrayIterator.

Figure 5-35. The iterator() method from ArrayList.

An ArrayIterator needs two fields: the ArrayList it is traversing and an int indicating how far down the ArrayList it is. It turns out to be convenient to keep track of the index of the previously visited element. We therefore call this int previous.

To find the next element to return, we increment previous and invoke get(previous) on the ArrayList. To determine if there are more elements to visit, we simply compare this number with the size of the ArrayList.

To remove the most recently returned element, we invoke remove(previous) on the ArrayList. We also have to decrement previous, so that when we increment it in the next call to next(), it will be the index of the next unvisited element.

The code for the ArrayIterator class is given in Figure 5-36. Exceptions are left as exercises.

Figure 5-36. The ArrayIterator class.

Example: Go Fish

To illustrate the use of Lists and Iterators, we now write a program for the game of Go Fish (Figure 5-37).

This program is fairly elaborate, but we've already written most of the components. The game itself is represented by the GoFish class. An instance of GoFish contains a Deck of Cards. It also contains two hands of cards, one for the computer and one for the user. A hand of cards is a special kind of List, so we'll extend the ArrayList class with the class GoFishHand. The UML class diagram is given in Figure 5-38.

Figure 5-38. An instance of GoFish contains two GoFishHands and one Deck, both of which contain Cards. The GoFishHand class extends ArrayList.

The simple parts of the GoFish class are shown in Figure 5-39. On lines 33 and 34 of the constructor, we call the add() method which GoFishHand inherits from ArrayList.

Figure 5-39. Beginning the GoFish class.

In the play() method (Figure 5-40), we want to keep going until the sum of the players' scores is 13. The complicated details of taking a turn for either the computer or the user are moved off into other methods. These methods return a boolean value which is true if the player in question earned a bonus turn. This is the reason for the unusual structure of lines 47. Lines 45 are a loop with no body which runs until either all 13 sets have been claimed or playerTurn() returns false. The actual work is done in playerTurn(), which is invoked only if the logical and expression's first operand

playerScore + computerScore < 13

is false. Line 67 do the same thing with computerTurn().

Figure 5-40. The play() method invokes playerTurn() and computerTurn().

The lengthy playerTurn() method is given in Figure 5-41. Lines 68 have the player draw a card if the player's hand is empty. Line 9 prints the state of the gamewe'll have to remember to write a toString() method. The bulk of the method, lines 1025, deals with reading a rank from the user. Line 11 invokes the method toUpperCase() from the String class, making any lower-case letters in the input String uppercase. This allows the user to type either q or Q to indicate a queen.

Line 26 transfers the appropriate cards from the computer's hand to the player's hand. If no cards are transferred, lines 28 to 34 go fish, which might produce a bonus turn. The rest of the method deals with laying down sets.

The computerTurn() method (Figure 5-42) is similar, but the rank is chosen randomly. Lines 1112 are a clever trick for converting from a numerical rank to a character (which might be A, T, J, Q, K, or a digit). We have already written code to do this in the Card class. Rather than do all that work again, we create a Card of the rank in question. (We arbitrarily specify HEARTS because we don't care about the suit here.) We invoke the Card's toString() method to get a String representation of the Card. The character we want is character 0 in this String, which we get with the invocation charAt(0).

Figure 5-41. The playerTurn() method invokes give() and meldSets() on instances of GoFishHand.

(This item is displayed on page 146 in the print version)

Figure 5-42. The computer asks for a random rank.

All that remains in the GoFish class is toString() (Figure 5-43). This method implicitly invokes the toString() method from GoFishHand, which was inherited from ArrayList.

We can summarize our work so far with a detailed UML class diagram (Figure 5-44).

Both of the methods in the GoFishHand class involve Iterators, so we go ahead and import java.util.Iterator (Figure 5-45).

Figure 5-43. The toString() method for GoFish.

Figure 5-44. After writing GoFish, we know which methods we'll need in GoFishHand. The fields of the ArrayList class, and most of its methods, are not shown.

Figure 5-45. The GoFishHand class will make extensive use of Iterators.

The first method, give(), TRansfers all Cards of a given rank from one hand to another and returns a boolean indicating if any were transferred. Thus, myHand.give(7,yourHand) removes all of the 7s from myHand, adds them to yourHand, and returns TRue if there were any.

The cards to be given are found by iterating through the hand in question and examining the rank of each card (Figure 5-46).

The meldSets() method (Figure 5-47) traverses the current hand twice. In lines 710, it determines how many Cards there are of each rank. Thus, if this hand has two 6s, rankCount[6] is 2 at the end of line 10. This is an enhanced for loop. The second traversal, on lines 1319, removes all those cards for which the rank count is 4.

Our program is now complete, as verified by a sample game (Figure 5-48).

Figure 5-46. The give() method traverses the hand on which it is invoked.

Figure 5-47. The meldSets() method traverses the hand twice.

Figure 5-48. Beginning of a game of Go Fish.

Notice, incidentally, that we've stopped running into warnings about generic arrays. All of that ugliness is encapsulated inside the ArrayList class.

Exercises