Binary search trees - Data Structures and Problem Solving Using Java - page 751

the key/value pair. For a TreeSet , the object turns out to be Comparable , and
applies the TreeSet comparator to the key. Details of this will be discussed later.
Many of the map routines translate into operations on the underlying set,
as shown at lines 28-35. The basic routines get , put , and remove , are shown in
Figure 19.79. These simply translate into operations on the set. All require a
call to makePair to create an object of the same type as those in theSet ; put is
representative of the strategy.
The tricky part of the MapImpl class is providing the ability to obtain the
views of the keys and values. In the MapImpl class declaration in Figure 19.78,
we see that keySet , implemented at lines 75 and 76, returns a reference to an
instance of an inner class named KeySetClass , and values , implemented at
lines 77 and 78, returns a reference to an instance of an inner class named
ValueCollectionClass . KeySetClass and ValueCollectionClass have some com-
monality, so they extend the generic inner class named ViewClass . These three
classes appear in lines 82 to 87 of the class declaration, and their implementa-
tion is shown in Figure 19.80.
In Figure 19.80, we see that in the generic ViewClass , calls to clear
and size are delegated to the underlying map. This class is abstract
because AbstractCollection does not provide the iterator method speci-
fied in Collection , and neither does ViewClass . The ValueCollectionClass
extends ViewClass<ValueType> and provides an iterator method; this method
returns a newly constructed instance of the inner class ValueCollectionIterator
(which of course implements the Iterator interface). ValueCollectionIterator
delegates calls to next and hasNext and is shown in Figure 19.81; we discuss it
shortly. KeySetClass extends ViewClass<KeyType> , but since it is a Set , it must
provide the (nonstandard) getMatch method in addition to the iterator
method. Because the KeySet class will not itself be used to represent a Map , this
method is not needed, so the implementation simply throws an exception. We
also provide a remove method to remove the associated key/value pair from the
underlying map. If this method is not provided, the default that is inherited
from AbstractCollection uses a sequential search, which is grossly inefficient.
Figure 19.81 completes the MapImpl class by providing implementations
of KeySetIterator and ValueCollectionIterator . Both maintain an iterator that
views the underlying map, and both delegate calls to next , hasNext , and remove
to the underlying map. In the case of next , the appropriate part of the
Map.Entry object being viewed by the map's iterator is returned.
With MapImpl written, TreeMap turns out to be simple, as shown in
Figure 19.82. Most of the code centers around the definition of the private
inner class Pair , which implements the Map.Entry interface by extending
MapImpl.Pair . Pair implements Comparable , using the comparator on the key if
one is provided, or downcasting to Comparable .