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.

1 public java.util.Iterator iterator() {
2 return new ArrayIterator(this);
3 }

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.

 1 /** Iterator associated with an ArrayList. */
 2 public class ArrayIterator implements java.util.Iterator {
 3
 4 /** List being traversed. */
 5 private ArrayList list;
 6
 7 /** Index of the last element returned by next(). */
 8 private int previous;
 9
10 /** The Iterator begins ready to visit element 0. */
11 public ArrayIterator(ArrayList list) {
12 this.list = list;
13 previous = -1;
14 }
15
16 public boolean hasNext() {
17 return (previous + 1) < list.size();
18 }
19
20 public E next() {
21 previous++;
22 return list.get(previous);
23 }
24
25 public void remove() {
26 list.remove(previous);
27 previous--;
28 }
29
30 }

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).

Go Fish

Players: 25

Object: To collect the most sets of four cards of the same rank.

Setup: Deal a hand of seven cards to each player.

Play: On your turn, first draw a card from the deck if your hand is empty. Ask any other player for cards of a particular rank. That player must give you all of the cards of that rank from his hand, which are added to your hand. If he doesn't have any cards of that rank, he tells you, "Go Fish," and you draw a card from the deck. If you complete a set of four cards of the same rank, remove all four cards from your hand and score one set. If you get a card of the rank you want (either from another player or by fishing from the deck), you get another turn. Otherwise, play passes to the next player.

Game End: The game ends when all thirteen sets have been scored. The player with the most sets wins.

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.

 1 import java.util.Scanner;
 2
 3 /** The game of Go Fish. */
 4 public class GoFish {
 5
 6 /** For reading from the console. */
 7 public static final Scanner INPUT = new Scanner(System.in);
 8
 9 /** The computer's hand of Cards. */
10 private GoFishHand computerHand;
11
12 /** Number of sets of four the computer has laid down. */
13 private int computerScore;
14
15 /** The Deck. */
16 private Deck deck;
17
18 /** The player's hand of Cards. */
19 private GoFishHand playerHand;
20
21 /** Number of sets of four the player has laid down. */
22 private int playerScore;
23
24 /** Shuffle the Deck and deal seven Cards to each player. */
25 public GoFish() {
26 computerScore = 0;
27 playerScore = 0;
28 deck = new Deck();
29 deck.shuffle();
30 computerHand = new GoFishHand();
31 playerHand = new GoFishHand();
32 for (int i = 0; i < 7; i++) {
33 playerHand.add(deck.deal());
34 computerHand.add(deck.deal());
35 }
36 }
37
38 /** Create and play the game. */
39 public static void main(String[] args) {
40 System.out.println("Welcome to Go Fish.");
41 GoFish game = new GoFish();
42 game.play();
43 }
44
45 }

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().

 1 /** Play until either the player or the computer wins. */
 2 public void play() {
 3 while (playerScore + computerScore < 13) {
 4 while ((playerScore + computerScore < 13)
 5 && (playerTurn())) {
 6 }
 7 while ((playerScore + computerScore < 13)
 8 && (computerTurn())) {
 9 }
10 }
11 System.out.println("The computer made " + computerScore
12 + " sets");
13 System.out.println("You made " + playerScore + " sets");
14 if (playerScore > computerScore) {
15 System.out.println("You win!");
16 } else {
17 System.out.println("The computer wins");
18 }
19 }

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)

 1 /**
 2 * Take a turn for the player. Return true if the player has earned
 3 * a bonus turn.
 4 */
 5 public boolean playerTurn() {
 6 if (playerHand.isEmpty() && !(deck.isEmpty())) {
 7 playerHand.add(deck.deal());
 8 }
 9 System.out.println("
" + this);
10 System.out.print("Which card will you ask for? ");
11 char cardName = INPUT.nextLine().toUpperCase().charAt(0);
12 int rank;
13 if (cardName == 'A') {
14 rank = Card.ACE;
15 } else if (cardName == 'T') {
16 rank = 10;
17 } else if (cardName == 'J') {
18 rank = Card.JACK;
19 } else if (cardName == 'Q') {
20 rank = Card.QUEEN;
21 } else if (cardName == 'K') {
22 rank = Card.KING;
23 } else {
24 rank = cardName - '0';
25 }
26 boolean bonusTurn = computerHand.give(rank, playerHand);
27 if (!bonusTurn) {
28 System.out.println("Go fish");
29 Card card = deck.deal();
30 System.out.println("You draw: " + card);
31 playerHand.add(card);
32 if (card.getRank() == rank) {
33 bonusTurn = true;
34 }
35 }
36 int sets = playerHand.meldSets();
37 playerScore += sets;
38 if (sets > 0) {
39 System.out.println("You lay down " + sets
40 + " sets, bringing your total to "
41 + playerScore);
42 }
43 return bonusTurn;
44 }

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

 1 /**
 2 * Take a turn for the computer. Return true if the computer has
 3 * earned a bonus turn.
 4 */
 5 public boolean computerTurn() {
 6 if (computerHand.isEmpty() && !(deck.isEmpty())) {
 7 computerHand.add(deck.deal());
 8 }
 9 System.out.println("
" + this);
10 int rank = ((int)(Math.random() * 13)) + 1;
11 char rankCharacter = new Card(rank,
12 Card.HEARTS).toString().charAt(0);
13 System.out.println("The computer asks for " + rankCharacter);
14 boolean bonusTurn = playerHand.give(rank, computerHand);
15 if (!bonusTurn) {
16 System.out.println("Go fish");
17 Card card = deck.deal();
18 computerHand.add(card);
19 if (card.getRank() == rank) {
20 bonusTurn = true;
21 }
22 }
23 int sets = computerHand.meldSets();
24 computerScore += sets;
25 if (sets > 0) {
26 System.out.println("The computer lays down " + sets
27 + " sets, bringing its total to "
28 + computerScore);
29 }
30 return bonusTurn;
31 }

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.

1 public String toString() {
2 String result = "There are " + deck.size()
3 + " cards in the deck
";
4 result += "The computer has " + computerHand.size() + " cards
";
5 return result + "Your hand: " + playerHand;
6 }

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.

1 import java.util.Iterator;
2
3 /** Hand of cards for the game of Go Fish. */
4 public class GoFishHand extends ArrayList {
5 }

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.

 1 /**
 2 * Remove all Cards of the specified rank and add them to the hand
 3 * taker. Return true if at least one Card was given.
 4 */
 5 public boolean give(int rank, GoFishHand taker) {
 6 boolean foundAny = false;
 7 Iterator iter = iterator();
 8 while (iter.hasNext()) {
 9 Card card = iter.next();
10 if (card.getRank() == rank) {
11 iter.remove();
12 taker.add(card);
13 foundAny = true;
14 }
15 }
16 return foundAny;
17 }

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

 1 /**
 2 * Remove all sets of four same-rank Cards from this GoFishHand.
 3 * Return the number of sets.
 4 */
 5 public int meldSets() {
 6 // Count number of Cards of each rank
 7 int[] rankCount = new int[14]; // Initialized to zeroes
 8 for (Card c : this) {
 9 rankCount[c.getRank()] += 1;
10 }
11 // Remove cards in complete sets
12 int cardsRemoved = 0;
13 Iterator iter = iterator();
14 while (iter.hasNext()) {
15 if (rankCount[iter.next().getRank()] == 4) {
16 cardsRemoved += 1;
17 iter.remove();
18 }
19 }
20 // Return number of complete sets
21 return cardsRemoved / 4;
22 }

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

 1 Welcome to Go Fish.
 2
 3 There are 38 cards in the deck
 4 The computer has 7 cards
 5 Your hand: [ 5c 6s 6h 4d Js Qc 8d ]
 6 Which card will you ask for? 5
 7
 8 There are 38 cards in the deck
 9 The computer has 6 cards
10 Your hand: [ 5c 6s 6h 4d Js Qc 8d 5s ]
11 Which card will you ask for? 6
12 Go fish
13 You draw: 7h
14
15 There are 37 cards in the deck
16 The computer has 6 cards
17 Your hand: [ 5c 6s 6h 4d Js Qc 8d 5s 7h ]
18 The computer asks for 4
19
20 There are 37 cards in the deck
21 The computer has 7 cards
22 Your hand: [ 5c 6s 6h Js Qc 8d 5s 7h ]
23 The computer asks for Q
24
25 There are 37 cards in the deck
26 The computer has 8 cards
27 Your hand: [ 5c 6s 6h Js 8d 5s 7h ]
28 The computer asks for 4
29 Go fish
30
31 There are 36 cards in the deck
32 The computer has 9 cards
33 Your hand: [ 5c 6s 6h Js 8d 5s 7h ]

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

Exercises

5.24	Modify ArrayIterator so that next() tHRows a java.util.NoSuchElementException if the associated ArrayList has no more elements to visit.
5.25	Modify ArrayIterator so that remove() throws a java.util.IllegalStateException when appropriate. (Hint: Add a boolean field removeAvailable which is set to true by next() and to false by remove(). What is the initial value of this field?)
5.26	Rewrite the toString() method for ArrayList (Figure 5-29) so that it uses an Iterator rather than directly accessing the fields.
5.27	In meldSets() (Figure 5-47), why does the array rankCount have 14 elements instead of 13?