Solution for
Programming Exercise 12.5
THIS PAGE DISCUSSES ONE POSSIBLE SOLUTION to
the following exercise from this on-line
Java textbook.
Exercise 12.5:
One of the examples in Section 12.4 concerns the
problem of making an index for a book. A related problem is making
a concordance for a document. A
concordance lists every word that occurs in the document, and for each
word it gives the line number of every line in the document where
the word occurs. All the subroutines for creating an index
that were presented in Section 12.4 can also be used to create
a concordance. The only real difference is that the integers
in a concordance are line numbers rather than page numbers.
Write a program that can create a concordance. The document should
be read from an input file, and the concordance data should be written
to an output file. The names of the input file and output file should
be specified as command line arguments when the program is run.
You can use the indexing subroutines from Section 12.4, modified to
write the data to a file instead of to System.out. You
will also need to make the subroutines static. If you need
some help with using files and command-line arguments, you can find an
example in the
sample program WordCount.java,
which was also discussed in Section 12.4.
As you read the file, you want to take each word that you encounter
and add it to the concordance along with the current line number.
Your program will need to keep track of the line number. The end of each line
in the file is marked by the newline character, '\n'. Every time you encounter
this character, add one to the line number. One warning: The method
in.eof(), which is defined in the TextReader, skips over
end-of-lines. Since you don't want to skip end-of-line characters, you
should not use in.eof() -- at least, you should not use it
in the same way that it is used in the program WordCount.java.
The function in.peek() from the TextReader class returns
the nul character '\0' at the end of the file. Use this function
instead of in.eof() to test for end-of-file.
Because it is so common, don't include the word "the" in your
concordance. Also, do not include words that have length less than 3.
Discussion
Solving this exercise, for the most part, means collecting subroutines
that were presented in Section 12.4 into a complete program. The
subroutines addReference() and printIntegers() were copied
directly, as was the class AlphabeticalOrder. The printIndex()
subroutine was copied, with its name changed to printConcordance(). I
made a few cosmetic changes, such as changing references to "page" into
references to "line".
It remains to write the main() routine, which is similar in
outline to the main() routine in WordCount.java. One difference
is that we have to keep track of line numbers. We can do this by looking
for new-line characters as we skip over the characters between words. A
pseudocode algorithm can be given as:
Open the input and output files.
Let lineNum = 1.
Repeat:
while the next character is not end-of-file or a letter:
Read the next character.
If it is a new line character:
Add 1 to lineNum
// After the while loop, we are looking at either the end of file
// or at a letter that is the beginning of the next word.
If at end-of-file:
Exit from the loop.
Get the next word from the input file.
if the word is not "the" and has length > 2:
Add the word and lineNum to the concordance.
Print the concordance.
This can be translated directly to give the main() routine.
A subroutine for opening the input and output files is copied
directly from WordCount.java.
The Solution
/*
This program makes a concordance for a file. A concordance
lists all the words that occur in the file, along with all
the line numbers on which each word occurs. (Words of
length less than 3 are omitted, and "the" is omitted.) The
concordance is written to an output file. The names of the
input and output files must be specified on the command line
when the program is run. This program uses the non-standard
classes defined in the file TextReader.java.
*/
import java.util.*;
import java.io.*;
public class Concordance {
static 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 object to Strings.
String str2 = (String)obj2;
str1 = str1.toLowerCase(); // Convert to lower case.
str2 = str2.toLowerCase();
return str1.compareTo(str2); // Compare lower-case Strings.
}
}
static TextReader in; // An input stream for reading the input file.
static PrintWriter out; // Output stream for writing the output file.
static TreeMap index = new TreeMap(new AlphabeticalOrder());
// This TreeMap holds the concordance. Words from the file
// are used as keys in the map. The value associated with
// each word is a set that contains the line numbers on which
// the word occurs in the file. The set contains values
// belonging to the wrapper class, Integer.
public static void main(String[] args) {
openFiles(args); // Open input and output files.
int lineNum = 1; // The number of the line in the input
// file that is currently begin processed.
while (true) {
while (in.peek() != '\0' && ! Character.isLetter(in.peek())) {
// Skip over non-letter characters, stopping when
// end-of-file ('\0') or a letter is seen. If the
// character is an end-of-line character, add one
// to lineNum to reflect that fact that we are moving
// on to the next line in the file.
char ch = in.getAnyChar();
if (ch == '\n') {
lineNum++; // Start a new line.
}
}
if (in.eof()) {
// The end-of-file has been reached, so exit from the loop.
break;
}
String word = in.getAlpha(); // The next word from the file.
if (word.length() > 2 && !word.equalsIgnoreCase("the")) {
// Add the reference to word to the concordance, unless
// the word is "the" or the word has length <= 2.
addReference(word,lineNum);
}
}
printConcordance(); // Print the data to the output file.
if (out.checkError()) {
// Some error occurred on the output stream.
System.out.println("An error occurred while writing the data.");
System.out.println("Output file might be missing or incomplete.");
System.exit(1);
}
System.out.println(index.size() + " distinct words were found.");
}
static void openFiles(String[] args) {
// Open the global variable "in" as an input file with name
// args[0]. Open the global variable "out" as an output
// file with name args[1]. If args.length != 2, or if an
// error occurs while trying to open the files, then an
// error message is printed and the program will be terminated.
if (args.length != 2) {
System.out.println("Error: Please specify file names on command line.");
System.exit(1);
}
try {
in = new TextReader(new FileReader(args[0]));
}
catch (IOException e) {
System.out.println("Error: Can't open input file " + args[0]);
System.exit(1);
}
try {
out = new PrintWriter(new FileWriter(args[1]));
}
catch (IOException e) {
System.out.println("Error: Can't open output file " + args[1]);
System.exit(1);
}
} // end openFiles()
static void addReference(String term, int lineNum) {
// Add a line reference to the concordance. The
// concordance is stored in the global variable, index.
// The word term has been found on line number lineNum.
TreeSet references; // The set of line 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 line number and add it to the index, with
// the term as the key.
TreeSet firstRef = new TreeSet();
firstRef.add( new Integer(lineNum) );
index.put(term,firstRef);
}
else {
// references is the set of line references
// that we have found previously for the term.
// Add the new line number to that set.
references.add( new Integer(lineNum) );
}
}
static void printConcordance() {
// Print each entry from the concordance to the output file.
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 line references that
// it contains.
Map.Entry entry = (Map.Entry)iter.next();
String term = (String)entry.getKey();
Set lines = (Set)entry.getValue();
out.print(term + " ");
printIntegers(lines);
out.println();
}
}
static 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, since no comma
// is printed before the first integer.
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.
out.print(integer.intValue()); // Print the first item.
while (iter.hasNext()) {
// Print additional items, if any, with separating commas.
integer = (Integer)iter.next();
out.print(", " + integer.intValue());
}
}
} // end class Concordance
[ Exercises
| Chapter Index
| Main Index
]
