Utilities - Data Structures and Problem Solving Using Java - page 499

have the current identifier. Let us see how the loop body works. There are two
cases:

1. The current identifier is in the map. In this case, lines gives a refer-

ence to the List of line numbers, and the new line number is added to
the end of the List .

2. The current identifier is not in the map. In this case, lines 16 and 17

a dd current to the map with an empty List . Thus the call to add
appends the new line number to the list, and as a result, the List con-
tains the single line number, as desired.

Once we have built the map, we merely iterate through it by using an
enhanced for loop on the underlying entry set. The map is visited in key-
sorted order because the map is a TreeMap . Each time a map entry appears, we
need to print out information for the identifier currently being examined by
the map iterator.
Recall that an entry set iterator looks at Map.Entry s; in Map.Entry , the key is
given by the method getKey , and the value is given by the method getValue .
Thus the identifier being scanned is given by thisNode.getKey( ) , as shown at
line 30. To access individual lines, we need a list iterator; the iterator at
line 27 refers to the line numbers of the current entry.
We print the word and the first line number at lines 30 and 31 (we are
guaranteed that the list is not empty). Then, so long as we have not reached the
end of the list, we repeatedly output line numbers in the loop that extends from
line 34 to 35. We print out a newline at line 36. We do not provide a main pro-
gram here because it is essentially the same as that shown in Figure 11.10.
The use of a map in this manner, in which the key is something simple
and the value is a list or some other collection is quite common. The exercises
detail several other examples that make use of this idiom.

The output is
obtained by using a
map traversal and
an enhanced for
loop on the entry
set. A list iterator is
used to get the line
numbers.

summary

In this chapter we presented implementations of two important utilities: text
compression and cross-referencing. Text compression is an important tech-
nique that allows us to increase both effective disk capacity and effective
modem speed. It is an area of active research. The simple method described
here—namely, Huffman's algorithm—typically achieves compression of 25 per-
cent on text files. Other algorithms and extensions of Huffman's algorithm per-
form better. Cross-referencing is a general approach that has many applications.