Solution for
Programming Exercise 10.1
THIS PAGE DISCUSSES ONE POSSIBLE SOLUTION to
the following exercise from this on-line
Java textbook.
Exercise 10.1:
The WordList program from Section 10.3 reads a text file
and makes an alphabetical list of all the words in that file.
The list of words is output to another file. Improve the
program so that it also keeps track of the number of times that
each word occurs in the file. Write two lists to the output
file. The first list contains the words in alphabetical order.
The number of times that the word occurred in the file should
be listed along with the word. Then write a second list to the
output file in which the words are sorted according to the number of
times that they occurred in the files. The word that occurred
most often should be listed first.
Discussion
In the original WordList program, the words from the file are stored in
an array of Strings. For this exercise, we also need to keep track
of the number of times a given string has been encountered in the file.
One possibility would be to add an array of ints to store the
counts. This would be using "parallel arrays" to store the data.
Another approach is to create a small class to hold the word and its
associated counter. Then the data can be stored in an array of objects
belonging to that class. In my program, I used the latter approach.
The class that I defined to hold the data for a word is:
class WordData {
// A little class to hold the data for one word.
String word; // The word (in lower case letters).
int count; // The number of times the word has been found.
WordData(String w) {
// Constructor creates an object with the specified word
// and with the counter initialized to 1.
word = w;
count = 1;
}
}
Note that I've included a constructor to make it easy to create
objects of type WordData. This constructor will be used
whenever a new word is encountered in the file for the first time.
At that time, the
count should be one. The constructor takes care of
this detail. After that, each time we encounter the word again, the
count for that word is increased by 1. Aside from this,
the process of reading the file and storing the data in the array
is essentially the same as it was in the WordList program.
You can check the differences -- shown in red -- in the main()
routine and the insertWord() subroutine in the solution that
is given below. In insertWord, note in particular that
the word in position pos in the array is words[pos].word,
while the frequency counter for that word is words[pos].count.
For example, the command for adding 1 to the count is
"words[pos].count++;".
Since the list of words is output twice, I've written a subroutine,
putWordList(), that writes the words to an output stream. I've
tried to make the output reasonably neat by outputting the words in
a column that is 15 spaces wide. The other subroutine that I've
added is sortByFrequency(), which will rearrange the words
in the array so that they are in order of decreasing frequency.
This routine is called by the main program before the word list is
printed for the second time. The sorting routine uses a
standard Insertion Sort algorithm, as given in
Section 8.4, except that it sorts
into decreasing order instead of increasing.
The Solution
Significant changes from WordList.java are shown in
red.
/*
This program lets the user specify a text file for input and a file
for output. All the words are read from the input file. Words are
converted to lower case. The program makes a list of all the words
that occur in the file, along with the number of times that each
word occurs. The words and word frequencies are printed to an
output file. The list is printed twice: once in alphabetical order
and once in order of decreasing frequency. A word in this program is
defined to be any sequence of letters.
This class depends on the non-standard classes TextIO and TextReader.
*/
import java.io.*;
class WordData {
// A little class to hold the data for one word.
String word; // The word (in lower case letters).
int count; // The number of times the word has been found.
WordData(String w) {
// Constructor creates an object with the specified word
// and with the counter initialized to 1.
word = w;
count = 1;
}
}
public class WordFrequencies {
static WordData[] words; // An array to hold the words from the file.
// Note that the array will be expanded as
// necessary, in the insertWord() subroutine.
static int wordCount; // The number of words currently stored in
// the array.
public static void main(String[] args) {
TextReader in; // A stream for reading from the input file.
PrintWriter out; // A stream for writing to the output file.
String inputFileName; // Input file name, specified by the user.
String outputFileName; // Output file name, specified by the user.
words = new WordData[10]; // Start with space for 10 words.
wordCount = 0; // Currently, there are no words in the array.
/* Get the input file name from the user and try to create the
input stream. If there is a FileNotFoundException, print
a message and terminate the program. */
TextIO.put("Input file name? ");
inputFileName = TextIO.getln().trim();
try {
in = new TextReader(new FileReader(inputFileName));
}
catch (FileNotFoundException e) {
TextIO.putln("Can't find file \"" + inputFileName + "\".");
return;
}
/* Get the output file name from the user and try to create the
output stream. If there is an IOException, print a message
and terminate the program. */
TextIO.put("Output file name? ");
outputFileName = TextIO.getln().trim();
try {
out = new PrintWriter(new FileWriter(outputFileName));
}
catch (IOException e) {
TextIO.putln("Can't open file \"" + outputFileName + "\" for output.");
TextIO.putln(e.toString());
return;
}
/* Read all the words from the input stream and insert them into
the array of words. Reading from a TextReader can result in
an error of type TextReader.Error. If one occurs, print an
error message and terminate the program. */
try {
while (true) {
// Skip past and non-letters in the input stream. If an
// end-of-stream has been reached, end the loop. Otherwise,
// read a word and insert it into the array of words.
while ( ! in.eof() && ! Character.isLetter(in.peek()) )
in.getAnyChar();
if (in.eof())
break;
insertWord(in.getAlpha());
}
}
catch (TextReader.Error e) {
TextIO.putln("An error occurred while reading from the input file.");
TextIO.putln(e.toString());
return;
}
/* Output the words in alphabetical order. */
out.println("Words in alphabetical order, with the number of occurrences:");
out.println("-----------------------------------------------------------");
out.println();
putWordList(out);
/* Sort the list of words according the frequency with which
they were found in the file, and then output the list again. */
sortByFrequency();
out.println();
out.println();
out.println("Words in order of frequency:");
out.println("---------------------------");
out.println();
putWordList(out);
if (out.checkError()) {
TextIO.putln("Some error occurred while writing to the output file.");
TextIO.putln("The output might be missing, incomplete, or corrupted.");
}
else {
TextIO.putln("Done.");
}
} // end main()
static void insertWord(String w) {
// Insert the word w into the array of words, unless it already
// appears there. If the word already appears in the list,
// add 1 to the counter for that word. The words in the array are in
// lower case, and w is converted to lower case before it is processed.
// Note that the words in the array are kept in alphabetical order.
// If the array has no more space to hold w, then it is doubled
// in size.
int pos = 0; // This will be the position in the array where w belongs.
w = w.toLowerCase();
/* Find the position in the array where w belongs, after all the
words that precede w alphabetically. If a copy of w already
occupies that position, then it is not necessary to insert
w, so just add 1 to the counter associated with the word
and return. */
while (pos < wordCount && words[pos].word.compareTo(w) < 0)
pos++;
if (pos < wordCount && words[pos].word.equals(w)) {
words[pos].count++;
return;
}
/* If the array is full, make a new array that is twice as
big, copy all the words from the old array to the new,
and set the variable, words, to refer to the new array. */
if (wordCount == words.length) {
WordData[] newWords = new WordData[words.length*2];
System.arraycopy(words,0,newWords,0,wordCount);
words = newWords;
}
/* Put w into its correct position in the array. Move any
words that come after w up one space in the array to
make room for w. Create a new WordData object to hold
the new word. */
for (int i = wordCount; i > pos; i--)
words[i] = words[i-1];
words[pos] = new WordData(w);
wordCount++;
} // end insertWord()
static void putWordList(PrintWriter output) {
// Write the list of words from the words array, along with their
// associated frequencies, to the output stream specified in the
// parameter to this subroutine. Words are output in a column
// that is 15 spaces wide. If an individual word is longer than
// 15 spaces, the output won't be quite so neat.
for (int i = 0; i < wordCount; i++) {
output.print(" ");
output.print(words[i].word);
for (int space = words[i].word.length(); space < 15; space++)
output.print(" ");
output.print(" ");
output.println(words[i].count);
}
} // end putWordList()
static void sortByFrequency() {
// Use insertion sort to sort the words in the list so that they
// are in order of decreasing frequency. (Note that insertion sort
// has the following neat property: In a group of words that all
// have the same frequency, the words will remain in alphabetical
// order after the words have been sorted by frequency.)
for (int i = 1; i < wordCount; i++) {
WordData temp = words[i]; // Save the word in position i.
int location; // An index in the array.
location = i - 1;
while (location >= 0 && words[location].count < temp.count) {
// Bump words that have frequencies less than the frequency
// of temp up one space in the array.
words[location + 1] = words[location];
location--;
}
words[location + 1] = temp; // Put temp in last vacated space.
}
} // end sortByFrequency()
} // end class WordFrequencies
[ Exercises
| Chapter Index
| Main Index
]
