The Set Interface

The game of Anagrams (Figure 11-1) involves three sets of Strings: the sets of words in front of each player and the set of legal words. There are also two collections of letters (the bag and the pool), but these are not sets, because the same letter may appear more than once in a given collection.

Anagrams

Players: 26.

Object: To be the first player with five words.

Setup: The game involves a large set of letter tiles. Each tile has a letter written on it. At the beginning of the game, all of the tiles are placed in a bag.

Play: On a turn, a player draws a tile from the bag and places it in a pool in the middle of the table. If the player can form a word of four or more letters from those in the pool, he takes those letters and forms the word in front of himself.

Alternately, a player may steal a word from another player. He must combine all of the letters in the stolen word with at least one letter from the pool to make a new word. The letters may be rearranged in the new word.

If a player cannot make or steal a word after drawing a tile, he must pass.

A transcript of the game in action is given in Figure 11-2.

Figure 11-2. Beginning of a game of Anagrams. On the last move, Player 1 steals the word 'ripe' by adding a 'z' to make 'prize.'

 1 Welcome to Anagrams.
 2
 3 To make a word from the pool, enter it.
 4 To steal a word, enter the new word, a space, and the word being
 5 stolen.
 6 To pass, just hit return.
 7
 8 PLAYER 1 TO PLAY
 9 Letters in pool:
10 r
11 Player 1's words: ( )
12 Player 2's words: ( )
13 Your play:
14
15 PLAYER 2 TO PLAY
16 Letters in pool:
17 ir
18 Player 1's words: ( )
19 Player 2's words: ( )
20 Your play:
21

22 PLAYER 1 TO PLAY 23 Letters in pool: 24 eir 25 Player 1's words: ( ) 26 Player 2's words: ( ) 27 Your play: 28 29 PLAYER 2 TO PLAY 30 Letters in pool: 31 eipr 32 Player 1's words: ( ) 33 Player 2's words: ( ) 34 Your play: ripe 35 36 PLAYER 1 TO PLAY 37 Letters in pool: 38 z 39 Player 1's words: ( ) 40 Player 2's words: ( ripe ) 41 Your play: prize ripe 42 43 PLAYER 2 TO PLAY 44 Letters in pool: 45 n 46 Player 1's words: ( prize ) 47 Player 2's words: ( )

An instance of the Anagrams class contains three instances of Set and two of LetterCollection (Figure 11-3). We will write the Set interface and the main Anagrams class in this section. The LetterCollection class is discussed in Section 11.4, as it foreshadows one of the Set implementations. Most of the rest of this chapter deals with implementing the Set interface. An efficient Set implementation is crucial for this game, because one of the Sets (the set of legal words) may contain hundreds of thousands of elements.

Figure 11-3. An instance of the Anagrams class contains three instances of implementations of the Set interface and two of LetterCollection.

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

A simple Set interface is shown in Figure 11-4. The Set interface in the Java collections framework specifies many additional methods, but this version will suffice for now.

Figure 11-4. A simple Set interface. Like the List interface in Section 5.3, it involves a generic type.

 1 /** A set of Objects. */
 2 public interface Set {
 3
 4 /** Add target to this Set. */
 5 public void add(E target);
 6
 7 /** Return true if this Set contains target. */
 8 public boolean contains(E target);
 9
10 /** Remove target from this Set. */
11 public void remove(E target);
12
13 /** Return the number of elements in this Set. */
14 public int size();
15
16 }

We now write the Anagrams class to illustrate the use of Sets. The easy parts are shown in Figure 11-5.

Figure 11-5. Easy parts of the Anagrams class.

 1 import java.util.*;
 2
 3 /** The game of Anagrams. */
 4 public class Anagrams {
 5
 6 /** For reading from the console. */
 7 public static final Scanner INPUT = new Scanner(System.in);
 8
 9 /** Letters in the bag. */
10 private LetterCollection bag
11
12 /** Letters in the pool. */
13 private LetterCollection pool;
14

15 /** Large set of legal words. */ 16 private Set words; 17 18 /** Words scored by player 1. */ 19 private Set words1; 20 21 /** Words scored by player 2. */ 22 private Set words2; 23 24 /** Create and play the game. */ 25 public static void main(String[] args) { 26 Anagrams game = new Anagrams(); 27 System.out.println("Welcome to Anagrams."); 28 System.out.println(); 29 System.out.println("To make a word from the pool, enter it."); 30 System.out.println("To steal a word, enter the new word, a" 31 + "space, and the word being stolen."); 32 System.out.println("To pass, just hit return."); 33 System.out.println(); 34 game.play(); 35 } 36 37 }

Next we write the play() and playTurn() methods (Figure 11-6).

Figure 11-6. The play() and playTurn() methods make extensive use of methods from the Set interface.

 1 /** Play until someone gets five words. */
 2 public void play() {
 3 while (true) {
 4 System.out.println("PLAYER 1 TO PLAY");
 5 playTurn(words1, words2);
 6 if (words1.size() == 5) {
 7 System.out.println("Player 1 wins!");
 8 return;
 9 }
10 System.out.println("PLAYER 2 TO PLAY");
11 playTurn(words2, words1);

12 if (words2.size() == 5) { 13 System.out.println("Player 2 wins!"); 14 return; 15 } 16 } 17 } 18 19 /** Play one turn for the specified player. */ 20 public void playTurn(Set player, Set opponent) { 21 pool.add(bag.draw()); 22 System.out.println("Letters in pool: " + pool); 23 System.out.println("Player 1's words: " + words1); 24 System.out.println("Player 2's words: " + words2); 25 System.out.print("Your play: "); 26 String play = INPUT.nextLine(); 27 int spaceIndex = play.indexOf(' '); 28 if (spaceIndex != -1) { // Stolen word 29 String word = play.substring(0, spaceIndex); 30 if (!(words.contains(word))) { 31 System.out.println("Sorry, " + word + " is not a word."); 32 } else { 33 String stolen = play.substring(spaceIndex + 1, play.length()); 34 player.add(word); 35 opponent.remove(stolen); 36 pool.add(stolen); 37 pool.remove(word); 38 } 39 } else if (!(play.equals(""))) { // Regular play 40 if (!(words.contains(play))) { 41 System.out.println("Sorry, " + play + " is not a word."); 42 } else { 43 player.add(play); 44 pool.remove(play); 45 } 46 } 47 System.out.println(); 48 }

The play() method is a fairly simple loop that runs until one player has five words. This is detected by invoking the size() method from the Set interface.

The playTurn() method is more complicated. It begins by taking a letter out of the bag and adding it to the pool (line 21). After reading a line from the user (line 26), the method invokes the indexOf() method of the resulting String (line 27). This method returns the index of the first appearance of the specified character (a space), or 1 if that character does not appear.

If the line contains a space, it can be recognized as a command to steal a word (line 28). The line is separated into two words on lines 29 and 33 using the substring() method of the String class. For example, if play is "prize ripe" then play.indexOf(' ') returns 5, play.substring(0, 5) returns "prize", and play.substring(6, 10) returns "ripe".

The playTurn() method next verifies that the word is legal (line 30). If it is, the word is added to the player's set (line 34) and the stolen word is removed from the opponent's set (line 35). Finally, all the letters in the stolen word are added to the pool (line 36) and all the letters in the new word are removed from the pool (line 37). The net effect of these last two method invocations is to remove from the pool those letters which are in the new word but not in the stolen word.

Lines 3946 handle the simpler case of a regular play. Here, the method only has to verify that the word is legal, add it to the player's set, and remove the letters from the pool.

All that remains is the constructor (Figure 11-7). Lines 919 deal with reading words from a text file. (We'll discuss file handling in much more detail in Chapter 17.) The file must be called words.txt and must be in the directory from which the program is run. A good list of words can be found in the file /usr/share/dict/words on most Unix systems, including Mac OS X.

Figure 11-7. The constructor for the Anagrams class creates three Sets.

 1 /**
 2 * Read in the dictionary from the file "anagram-words" and create
 3 * the letters.
 4 */
 5 public Anagrams() {
 6 bag = new LetterCollection(true);
 7 pool = new LetterCollection(false);
 8 words = new HashTable("");
 9 try {
10 Scanner input = new Scanner(new java.io.File("words.txt"));
11 while (input.hasNextLine()) {
12 words.add(input.nextLine());
13 }
14 } catch (java.io.IOException e) {
15 e.printStackTrace();
16 System.exit(1);
17 }
18 words1 = new OrderedList();
19 words2 = new OrderedList();
20 }

Varying which class we use for words provides a striking example of the importance of an efficient Set implementation. Given a large words.txt file with tens or hundreds of thousands of words, the program as written takes at most a few seconds to start up. On the other hand, if we change line 8 to

words = new OrderedList();

(note that this constructor takes no argument), the program seems to hang. It would eventually finish, but only after an unacceptable amount of time. The program is unusable because it is so inefficient.

Changing line 8 to

words = new BinarySearchTree();

is just as bad in the likely event that words.txt is in alphabetical order. (We'll explain this behavior in Section 11.3.)

The impatient reader may think, "Why bother with these other, inefficient data structures? Let's cut to the chase and learn about hash tables!" The author offers the following reasons:

1. Working through ordered lists and binary search trees provides a vivid demonstration of how data structures may be correct but still not sufficiently efficient.
2. While the simple versions of these data structures are not efficient, more complicated variations are. For example, red-black trees (Chapter 14) are based on binary search trees.
3. There are some jobs for which hash tables are not the data structure of choice; a programmer must have a diverse toolkit.
4. As in a good film, the final revelation is more satisfying if suspense has been built up beforehand.

Exercises

11.1	Line 28 of Figure 11-6 seems a bit awkward. In general, it is clearer to say if (x == 1) { // do one thing } else { // do another thing }   than if (x != 1) { // do another thing } else { // do one thing }   which is equivalent. We might therefore be tempted to change the line to if (spaceIndex == -1) {   and to swap lines 2938 with lines 4045. Why does this not work?
11.2	Modify the Anagrams program to enforce the constraint that words must be at least four letters long. (This is not necessary if all shorter words are removed from the file words.txt.)
11.3	Modify the Anagrams program to prevent a player from "stealing" a word that the opponent doesn't actually have.

Ordered Lists