Dictionaries - Data Structures and Abstractions with Java - page 484

A Problem Solved: A Concordance of Words

An index provides a way to locate the occurrence of certain words within a larger document.
For example, the index to this topic is an alphabetical listing of words paired with the page
numbers on which the words occur. For this problem, we will create a simpler kind of index—
called a concordance —to all the words in a text file. Instead of page numbers, a concordance
provides the line numbers that contain a particular word.

19.18

Let's begin by looking at an example of a concordance. Suppose that a text file contains only
these lines:
Learning without thought is labor lost;
thought without learning is perilous.
The following concordance of all the words in the file indicates the line numbers in which the
words occur:
is 1 2
labor 1
learning 1 2
lost 1
perilous 2
thought 1 2
without 1 2
Although a word can appear in several lines of the file, it appears only once in the concordance.
Like the previous word-frequency example, this feature of the concordance suggests that we use a
dictionary whose search keys are the words in the concordance. But unlike the word-frequency
example, the value associated with each of these words is a list of line numbers. Since the line
numbers are sorted, we could use the ADT sorted list. However, by processing the lines in the file in
order, we can add the line numbers to the end of an ordinary unsorted list and achieve a sorted order.

19.19

A class Concordance to represent the concordance and the class FrequencyCounter from the previous
example are quite similar in their design and implementation. In fact, the use of these classes is virtually
identical. By replacing FrequencyCounter with Concordance in Listing 19-4 of Segment 19.12, you
will have a client for Concordance .
Listing 19-6 contains an outline of the class Concordance . Note the similarities to the outline of
FrequencyCounter given in Listing 19-5 of Segment 19.13. The major difference, other than the
implementations of the methods, is the data type of the value of each dictionary entry. Since the value
is a list of Integer objects, and since we will want to traverse each list to display the line numbers, we
give the value a data type of ListWithIteratorInterface<Integer> . Segment 15.17 of Chapter 15
defined this interface as having the method getIterator as well as the methods of ListInterface .

LISTING 19-6

An outline of the class Concordance

import java.util.Iterator;
import java.util.Scanner;
public class Concordance
{

private DictionaryInterface<String, ListWithIteratorInterface<Integer>>
wordTable;