Dictionary Implementations - Data Structures and Abstractions with Java - page 507

Entry currentEntry = dictionary.get(keyIndex);
result = currentEntry.getValue();
currentEntry.setValue(value);

}
else // add new entry
{

Entry newEntry = new Entry(key, value);
dictionary.add(keyIndex, newEntry);
} // end if
return result;
} // end add

20.19

The private method locateIndex . To revise locateIndex , as given in Segment 20.12, to work
with a vector instead of an array, we modify the boolean expression in the while statement.
The resulting expression is similar to the boolean expression in the previous segment—it uses
Vector's method get —but it invokes compareTo instead of equals . Thus, the revised method
appears as follows:

private int locateIndex(K key)
{

// search until you either find an entry containing key or
// pass the point where it should be
int numberOfEntries = dictionary.size();
int index = 0;
while ( (index < numberOfEntries) &&
key.compareTo( (dictionary.get(index)).getKey() ) > 0 )
index++;
return index;
} // end locateIndex

The differences between this method and the array version are highlighted. In SortedArrayDictionary ,
numberOfEntries is a data field. Here it is a local variable set to dictionary.size() , the vector's size.
Implementations for the methods remove and getValue are similar to the implementation for
add , and we leave them as exercises.

20.20

An iterator for search keys. Our goal in providing iterators for the dictionary is to give the client
an easy way to traverse the search keys and their corresponding values. The interface for the dic-
tionary given in Segment 19.4 of the previous chapter specifies two iterators, one for search keys
and one for values. That chapter showed you how to use these iterators, and here we implement an
iterator for the search keys.
Recall that the interface java.util.Iterator specifies the methods hasNext , next , and
remove . We can define a private class KeyIterator that implements this interface and is internal to
the class SortedVectorDictionary . We then implement the public method getKeyIterator within
SortedVectorDictionary as follows:

public Iterator<K> getKeyIterator()
{

return new KeyIterator();
} // end getKeyIterator
The implementation of the class KeyIterator is shown in Listing 20-4. Vector 's iterator
dictionary.iterator traverses the entries in the vector dictionary and is the basis of this
implementation. Each entry in the vector is an instance of Entry , so we use Entry 's method
getKey to get each search key.
Iterator 's method remove is not relevant to the traversal of the search keys, so we do not sup-
port it. Instead we make remove throw an exception if it is invoked.