Previous Lesson
Table of Contents
Next Lesson
As the name implies, the primary use of a Dictionary is to store elements so that they can be located quickly using keys. Like a PriorityQueue, a Dictionary is a Container of key-element pairs. However, although a total order relation on the keys is always required for a PriorityQueue, it is optional for a Dictionary. When a total order relation on the keys is actually defined, the data structure is called an OrderedDictionary, and it supports additional methods that refer to the ordering of the keys.
In this example, we explore the added capabilities of an OrderedDictionary.
We use the jdsl.core.ref.RedBlackTree class in our implementation.
Note that, as in the previous example with the PriorityQueue,
we must pass a JDSL Comparator to the data structure in its construtor.
We'll use the ComparableComparator described in Lesson
2.
//create the OrderedDictionary,
passing a Comparator to its constructor
od_ = new
jdsl.core.ref.RedBlackTree(new
ComparableComparator());
In the PhoneBook method addEntry(), we see how
key,element
pairs are inserted into the OrderedDictionary: This method is
called when the "add a name,number entry" button is clicked. The String
in the name_adder_ field is used as the key, and the String
(phone number) in the number_adder_ field is used as the element
to store. The key and element are then inserted into the OrderedDictionary.
public void addEntry(){
Object key
= name_adder_.getText();
Object element
= number_adder_.getText();
od_.insert(key,
element);
//now clear out those
text fields just to look nice
name_adder_.setText("");
number_adder_.setText("");
}
In the PhoneBook method findEntry(), we see how to retrieve
data using a key. (In this case, we're retrieving phone numbers by using
names as keys.) The following method is called when the "find the
phone number" button is clicked. The String in the name_query_
field is used as a search key. That key is passed as a parameter to the
Dictionary's
find(.) method. A Locator is returned
from the find(.) operation, and is stored as our current_entry_.
Then the displayCurrentEntry() helper method is invoked.
public void findEntry(){
Object key
= name_query_.getText();
// note that a JDSL
Locator is returned from the find(.) operation
current_entry_ = od_.find(key);
//this helper method
will display the data
displayCurrentEntry();
//now clear out the
name_query_ text field just to look nice
name_query_.setText("");
}
Now, if that was all our program did, a JDSL Dictionary (non-ordered)
would have sufficed. In that case, we probably would have used the
jdsl.core.ref.HashtableDictionary
as our implementation. But, in fact, this example program also utilizes
the before(.)and
after(.) methods of the OrderedDictionary
interface.
The following method is called when the "previous entry" button is clicked. It uses the OrderedDictionary method before(Locator).
public void getEntryBefore(){
//we want to see the
entry before the current_entry_
//note that
the before(.) method takes a Locator as a parameter
try{
jdsl.core.api.Locator prevEntry
= od_.before(current_entry_);
current_entry_ = prevEntry;
}
catch(jdsl.core.api.InvalidAccessorException
iae){}
//this would happen
if we tried calling before(.) using an invalid
//Locator for
current_entry_.
displayCurrentEntry();//Display
the current (valid or not) entry.
}
This next method is called when the "next entry" button is clicked. It
uses the OrderedDictionary method after(Locator).
public void getEntryAfter(){
//we want to see the
entry after the the current_entry_
//note that
the after(.) method takes a Locator as a parameter
try{
jdsl.core.api.Locator nextEntry
= od_.after(current_entry_);
current_entry_ = nextEntry;
}
catch(jdsl.core.api.InvalidAccessorException
iae){}
//this would happen
if we tried calling after(.) using an invalid
//Locator for
current_entry_.
displayCurrentEntry();//Display
the current (valid or not) entry.
}
Finally, we show the displayCurrentEntry() method, which uses two special,
invalid Locators that are defined in the Dictionary and OrderedDictionary
interfaces. These Locators are returned when queries fail -- when you try
to find(.) a key that is not present, or when you try to go before(.) the
first() Locator in the Dictionary, for example.
public void displayCurrentEntry() { String toDisplay = null; //if a find(.) operation was unsuccessful, it returned NO_SUCH_KEY if (current_entry_ == jdsl.core.api.Dictionary.NO_SUCH_KEY){ toDisplay = "No entry was found using that name as a key."; } //if before(.) or after(.) was requested, and there was no such entry else if (current_entry_ == jdsl.core.api.OrderedDictionary.BOUNDARY_VIOLATION){ toDisplay = "You've passed the beginning or end of the Dictionary."; } else{ toDisplay = (String)(current_entry_.key()) + " " + (String)(current_entry_.element()); } //put the string in the text field show_entry_.setText(toDisplay); }
Before ending this lesson, we should note that the Dictionary and OrderedDictionary interfaces both make use of the Locator design pattern. You will recall that in Lesson 4 we saw how Locators are useful as a "coat check" for a key,element pair that is contained in a KeyBasedContainer.
As in the PriorityQueue, key,element pairs can be
removed from the Dictionary by passing the appropriate Locator
to the remove(Locator) method. In this PhoneBook example,
we see that
Locators are used as parameters for the
before(Locator)
and after(Locator) methods. We should also note that the find(Object)
method returns a Locator. Consult the JDSL
documentation for more information about how to use
Locators
effectively.