Section 12.4
Programming with Collection Classes
IN THIS SECTION, we finish the chapter and the book by looking at a few programming examples that use the collection and map classes which were discussed in Sections 1, 2, and 3.
Symbol Tables
We begin with a straightforward but important application of Maps. When a compiler reads the source code of a program, it encounters definitions of variables, subroutines, and classes. The names of these things can be used later in the program. The compiler has to remember the definition of each name, so that it can recognize the name and apply the definition when the name is encountered later in the program. This is a natural application for a Map. The name can be used as a key in the map. The value associated to the key is the definition of the name, encoded somehow as an Object. A Map that is used in this way is called a symbol table.
In a compiler, the values in a symbol table can be quite complicated, since the compiler has to deal with names for various sorts of things, and it needs a different type of information for each different type of name. We will keep things simple by looking at a symbol table in another context. Suppose that we want a program that can evaluate expressions entered by the user, and suppose that the expressions can contain variables, in addition to operators, numbers, and parentheses. For this to make sense, we need some way of assigning values to variables. When a variable is used in an expression, we need to retrieve the variable's value. A symbol table can be used to store the variables' values. The keys for the symbol table are variable names. The value associated with a key is the value of that variable.
To demonstrate the idea, we'll use a rather simple-minded program in which the user types commands such as:
let x = 3 + 12 print 2 + 2 print 10*x +17 let rate = 0.06 print 1000*(1+rate)The only two commands that the program understands are "print" and "let". When a "print" command is executed, the computer evaluates the expression and displays the value. If the expression contains a variable, the computer has to look up the value of that variable in the symbol table. A "let" command is used to give a value to a variable. The computer has to store the value of the variable in the symbol table. (Note: The "variables" I am talking about here are not variables in the Java program. The Java program is executing a sort of program typed in by the user. I am talking about variables in the user's program. The user gets to make up variable names, so there is no way for the Java program to know in advance what the variables will be.)
In Section 11.5, we saw how to write a program, SimpleParser2.java, that can evaluate expressions that do not contain variables. The new program, SimpleParser5.java, is based on that older program. I will only talk about the parts that are relevant to the symbol table. Here is an applet that simulates the program:
The program uses a HashMap as the symbol table. A TreeMap could also be used, but since we don't have any reason to access the variables in alphabetical order, we don't need to have the keys stored in sorted order. The value of a variable is a double, but Java's collection and map classes can only hold objects. To get around this restriction, we have to use the wrapper class, Double. The variable's value, which is of type double is wrapped in an object of type Double. That object is stored in the HashMap, using the variable's name as the key.
Let symbolTable be the HashMap that is used as the symbol table. At the beginning of the program, we start with an empty map:
symbolTable = new HashMap();To execute a "let" command, the program uses the put() method to associate a value with the variable name. Suppose that the name of the variable is given by a String, varName. The command for setting the value of the variable to val would be:
symbolTable.put(varName, new Double(val));This associates the object new Double(val) with the key, varName. In the program SimpleParser5.java, you'll find this in the method named doLetCommand(). Just for fun, I decided to pre-define two variables named "pi" and "e" whose values are the usual mathematical constants pi and e. In Java, the values of these constants are given by Math.PI and Math.E. To make these variables available to the user of the program, they are added to the symbol table with the commands:
symbolTable.put("pi", new Double(Math.PI)); symbolTable.put("e", new double(Math.E));When a variable is encountered in an expression, the get() method is used to retrieve its value. Since this method returns a value of type Object, we have to type-cast the return value to Double. If the variable has never been given a value, then the get() method returns null. We have to handle this in some way; I will consider it to be an error:
Object symbolTableEntry = symbolTable.get(varName); if (symbolTableEntry == null) { ... // Throw an exception: Undefined variable. } Double value = (Double)symbolTableEntry; double val = value.doubleValue();The last line gets the double that is the actual value of the variable from the wrapper object. You will find this code, more or less, in a method named primaryValue() in the program SimpleParser5.java.
As you can see, aside from the necessity of using a wrapper class, Maps are really quite easy to use.
Sets Inside a Map
The objects in a collection or map can be of any type. They can even be collections. Here's an example where it's natural to store sets as values in a map.
Consider the problem of making an index for a book. An index consists of a list of terms that appear in the book. Next to each term is a list of the pages on which that term appears. To represent an index in a program, we need a data structure that can hold a list of terms, along with a list of pages for each term. Adding new data should be easy and efficient. When it's time to print the index, it should be easy to access the terms in alphabetical order. There are many ways this could be done, but I'd like to use Java's generic data structures and let them do as much of the work as possible.
We can think of an index as a Map that associates a list of page references to each term. The terms are keys, and the value associated with a given key is the list of page references for that term. A Map can be either a TreeMap or a HashMap, but only a TreeMap will make it easy to access the terms in sorted order. The value associated with a term is a list of page references. How can we represent such a value? If you think about it, you see that it's not really a list in the sense of Java's generic classes. If you look in any index, you'll see that a list of page references has no duplicates, so it's really a set rather than a list. Furthermore, the page references for a given term are always printed in increasing order, so we want a sorted set. This means that we should use a TreeSet to represent a list of page references. The values that we really want to put in this set are of type int, but once again we have to deal with the fact that generic data structures can only hold objects. We have to wrap each value of type int in an object belonging to the wrapper class, Integer.
To summarize, an index will be represented by a TreeMap. The keys for the map will be terms, which are of type String. The values in the map will be TreeSets. The TreeSet corresponding to a term contains Integers which give the page numbers of every page on which the term appears.
To make an index, we need to start with an empty TreeMap, look through the book, inserting every reference that we want to be in the index into the TreeMap, and then print out the data from the TreeMap. Let's leave aside the question of how we find the references to put in the index, and just look at how the TreeMap is used. The TreeMap can be created with the command:
TreeMap index = new TreeMap();Now, suppose that we find a reference to some term on some page. We need to insert this information into the index. To do this, we should look up the term in the index, using index.get(term). The return value is either null or is the set of page references that we already have for the term. If the return value is null, then this is the first page reference for the term, so we should add the term to the index, with a new set that contains the page reference we've just found. If the return value is non-null, we already have a set, and we should just add the new page reference to the set. Here is a subroutine that does this:
void addReference(String term, int pageNum) { // Add a page reference to the index. TreeSet references; // The set of page references that we // have so far for the term. references = (TreeSet)index.get(term); // Type-cast! if (references == null){ // This is the first reference that we have // found for the term. Make a new set containing // the page number and add it to the index, with // the term as the key. TreeSet firstRef = new TreeSet(); firstRef.add( new Integer(pageNum) ); index.put(term,firstRef); } else { // references is the set of page references // that we have found previously for the term. // Add the new page number to that set. references.add( new Integer(pageNum) ); } }The only other thing we need to do with the index is print it out. We are going to have to print out sets of Integers. Let's write a separate subroutine to do that:
void printIntegers( Set integers ) { // Assume that all the objects in the set are of // type Integer. Print the integer values on // one line, separated by commas. The commas // make this a little tricky. if (integers.isEmpty()) { // There is nothing to print if the set is empty. return; } Integer integer; // One of the Integers in the set. Iterator iter = integers.iterator(); // For traversing the set. integer = (Integer)iter.next(); // First item in the set. // We know the set is non-empty, // so this is OK. System.out.print(integer.intValue()); // Print the first item. while (iter.hasNext()) { // Print additional items, if any, with separating commas. integer = (Integer)iter.next(); System.out.print(", " + integer.intValue()); } }Finally, we need a routine that can iterate through all the terms in the map and print each term along with its list of page references. There are no iterators for maps. To iterate through a map, we need to use one of the Set views of the map. Since we want to print both the keys and the values, it's most efficient to use the entry set of the map. Here's the subroutine:
void printIndex() { // Print each entry in the index. Set entries = index.entrySet(); // The index viewed as a set of entries, where each // entry has a key and a value. The objects in // this set are of type Map.Entry. Iterator iter = entries.iterator(); while (iter.hasNext()) { // Get the next entry from the entry set and print // the term and list of page references that // it contains. Map.Entry entry = (Map.Entry)iter.next(); String term = (String)entry.getKey(); Set pages = (Set)entry.getValue(); System.out.print(term + " "); printIntegers(pages); System.out.println(); } }This is not a lot of code, considering the complexity of the operations. The only really tricky part is the constant need for type-casting and the need to use wrapper objects for primitive types. Both of these are necessary because of the nature of generic programming in Java, that is, the fact that generic data structures hold values of type Object.
I have not written a complete indexing program, but the subroutines presented here are used in a related context in Exercise 12.5.
Using a Comparator
There is a potential problem with our solution to the indexing problem. If the terms in the index can contain both upper case and lower case letters, then the terms will not be in alphabetical order. The ordering on String is not alphabetical. It is based on the Unicode codes of the characters in the string. The codes for all the upper case letters are less than the codes for the lower case letters. So, for example, terms beginning with "Z" come before terms beginning with "a". If the terms are restricted to use lower case letters only (or upper case only), then the ordering would be alphabetical. But suppose that we allow both upper and lower case, and that we insist on alphabetical order. In that case, our index can't use the usual ordering for Strings. Fortunately, it's possible to specify a different method to be used for comparing the keys of a map. This is a typical use for a Comparator.
Recall that a Comparator is an object that implements the Comparator interface and defines the method:
public int compare(Object obj1, Object obj2)This method can be used to compare two objects. It should return an integer that is positive, zero, or negative, depending on whether obj1 is less than, equal to, or greater than obj2. We need a Comparator that will compare two Strings based on alphabetical order. The easiest (although not most efficient) way to do this is to convert the Strings to lower case and use the default comparison on the lower case Strings. The following class defines such a comparator:
class AlphabeticalOrder implements Comparator { // Represents a Comparator that can be used for // comparing Strings according to alphabetical // order. It is an error to apply this // Comparator to objects that are non-strings. public int compare(Object obj1, Object obj2) { String str1 = (String)obj1; // Type-cast objects to Strings. String str2 = (String)obj2; str1 = str1.toLowerCase(); // Convert to lower case. str2 = str2.toLowerCase(); return str1.compareTo(str2); // Compare lower-case Strings. } }To solve our indexing problem, we just need to tell our index to use an object of type AlphabeticalOrder for comparing keys. This is done by providing the Comparator object as a parameter to the constructor. We just have to create the index with the command:
TreeMap index = new TreeMap( new AlphabeticalOrder() );This does work, but I've concealed one technicality. Suppose, for example, that the program calls addReference("aardvark",56) and that it later calls addReference("Aardvark",102). The words "aardvark" and "Aardvark" differ only in that one of them begins with an upper case letter. When we insert them into the index, do they count as two different terms or as one term? The answer depends on the way that a TreeMap tests objects for equality. In fact, TreeMaps and TreeSets always use a Comparator object or a compareTo method to test for equality. They do not use the equals() method. The Comparator that is used for the TreeMap in this example returns the value zero when it is used to compare "aardvark" and "Aardvark", so the TreeMap considers them to be the same. Page references to "aardvark" and "Aardvark" are combined into a single list. This is probably the correct behavior in this example. If not, some other technique must be used to sort the terms into alphabetical order.
Word Counting
The final example also deals with storing information about words. In Section 10.3, we looked at WordList.java, a program that makes a list of all the words in a file. In Section 2, we did the same thing using generic data structures. Now, we extend the problem so that instead of just listing the words, the program also counts the number of times each word occurs in the file. The output consists of two lists, one sorted alphabetically and one sorted according to the number of occurrences, with the most common words at the top and the least common at the bottom. The same problem was assigned in Exercise 10.1 and solved without using generic data structures.
As the program reads an input file, it must keep track of how many times it encounters each word. We could simply throw all the words, with duplicates, into a list and count them later. But that would require a lot of storage and would not be very efficient. A better method is to keep a counter for each word. The first time the word is encountered, the counter is initialized to 1. On subsequent encounters, the counter is incremented. To keep track of the data for one word, the program uses a simple class that holds a word and the counter for that word. The class is a static nested class:
static class WordData { // Represents the data we need about a word: the word and // the number of times it has been encountered. String word; int count; WordData(String w) { // Constructor for creating a WordData object when // we encounter a new word. word = w; count = 1; // The initial value of count is 1. } } // end class WordDataThe program has to store all the WordData objects in some sort of data structure. We want to be able to add new words efficiently. Given a word, we need to check whether a WordData object already exists for that word, and if it does, we need to find that object so that we can increment its counter. A Map can be used to implement these operations. Given a word, we want to look up a WordData object in the Map. This means that the word is the key, and the WordData object is the value. (It might seem strange that the key is also one of the instance variables in the value object, but in fact this is probably the most common situation: The value object contains all the information about some entity, and the key is one of those pieces of information.) After reading the file, we want to output the words in alphabetical order, so we should use a TreeMap rather than a HashMap. This program converts all words to lower case so that the default ordering on Strings will put the words in alphabetical order.
When the program reads a word from a file, it calls words.get(word) to find out if that word is already in the map, where words is a variable that refers to the TreeMap. If the return value is null, then this is the first time the word has been encountered, so a new WordData object is created and inserted into the map with the command words.put(word, new WordData(word)). If words.get(word) is not null, then it's the WordData object for this word, and the program only has to increment the counter in that object. Here is the subroutine that is used to read the words from the file:
static void readWords(TextReader inStream, Map words) { // Read all words from inStream, and store data about them in words. try { while (true) { while (! inStream.eof() && ! Character.isLetter(inStream.peek())) inStream.getAnyChar(); // Skip past non-letters. if (inStream.eof()) break; // Exit because there is no more data to read. String word = inStream.getAlpha(); // Read one word from stream. word = word.toLowerCase(); WordData data = (WordData)words.get(word); // Check whether the word is already in the Map. If not, // the value of data will be null. If it is not null, then // it is a WordData object containing the word and the // number of times we have encountered it so far. if (data == null) { // We have not encountered word before. Add it to // the map. The initial frequency count is // automatically set to 1 by the WordData constructor. words.put(word, new WordData(word) ); } else { // The word has already been encountered, and data is // the WordData object that holds data about the word. // Add 1 to the frequency count in the WordData object. data.count = data.count + 1; } } } catch (TextReader.Error e) { System.out.println("An error occurred while reading the data."); System.out.println(e.toString()); System.exit(1); } } // end readWords()After reading the words and printing them out in alphabetical order, the program has to sort the words by frequency count and print them again. To do the sorting using a generic algorithm, I defined a Comparator class for comparing two word objects according to their frequency counts:
static class CountCompare implements Comparator { // A comparator for comparing objects of type WordData // according to their counts. This is used for // sorting the list of words by frequency. public int compare(Object obj1, Object obj2) { WordData data1 = (WordData)obj1; WordData data2 = (WordData)obj2; return data2.count - data1.count; // The return value is positive if data2.count > data1.count. // I.E., data1 comes after data2 in the ordering if there // were more occurrences of data2.word than of data1.word. // The words are sorted according to decreasing counts. } } // end class CountCompareGiven this class, we can sort the WordData objects according to frequency by copying them into a list and using the generic method Collections.sort(List,Comparator). The WordData objects are the values in the map, words, and words.values() is a Collection that contains all these values. The constructor for the ArrayList class lets you specify a collection to be copied into the list when it is created. So, we can create a List containing the word data and sort that list according to frequency count using the commands:
ArrayList wordsByCount = new ArrayList( words.values() ); Collections.sort( wordsByCount, new CountCompare() );You should notice that these two lines replace a lot of code! It requires some practice to think in terms of generic data structures and algorithms, but the payoff is significant in terms of saved time and effort.
The only remaining problem is to print the data to the output file. We have to print the data from all the WordData objects twice, first in alphabetical order and then sorted according to frequency count. The data is in alphabetical order in the TreeMap, or more precisely, in the values of the TreeMap. We can use an Iterator for the value collection, words.values(), to access the words in alphabetical order. Similarly, the words are in the ArrayList wordsByCount in the correct order according to frequency count, so we could use an Iterator for the ArrayList to access and print the data according to frequency count. Since we have to do essentially the same thing twice, we might as well write a subroutine to do it:
static void printWords(PrintWriter outStream, Collection wordData) { // wordData must contain objects of type WordData. The words // and counts in these objects are written to the output stream. Iterator iter = wordData.iterator(); while (iter.hasNext()) { WordData data = (WordData)iter.next(); outStream.println(" " + data.word + " (" + data.count + ")"); } } // end printWords()This is a generic subroutine. Since its second parameter is of type Collection, it can be applied to the collection words.values() as well as to the collection wordsByCount. This is the last piece needed for the program. You can find the complete program in the file WordCount.java.
With this section, we reach the end of Introduction to Programming Using Java. It has been a long journey, but I hope a worthwhile one and one that has left you prepared to move on to more advanced study of Java, programming, and computer science in general. Good luck and have fun!
End of Chapter 12
[ Previous Section | Chapter Index | Main Index ]