Previous Lesson
Table of Contents
Next Lesson
In the last lesson, we explored the JDSL's PositionalContainer interface, and saw the usefulness of Positions to access the internals of Containers. In this lesson, you will learn about a second type of JDSL Container: the KeyBasedContainer. Specifically, we will explore one type of KeyBasedContainer: the PriorityQueue.
A PriorityQueue is a Container for storing a collection of prioritized elements, that supports arbitrary element insertion but supports removal of elements in order of priority. Each element inserted into the PriorityQueue is given a key, that is, a value by which the Container's objects can be compared and ranked.
KeyBasedContainers such as the PriorityQueue require a Comparator in order to compare elements according to their keys. The JDSL provides a number of useful Comparator classes, including the IntegerComparator and classes that create JDSL Comparators from Java Collections Compareable and Comparator classes.
For the first part of this lesson, we will examine the Triage program. Later in the lesson, we will explore the additional features provided in the Triage2 program. In both versions, we use the jdsl.core.ref.ArrayHeap as our implementation of PriorityQueue, and we pass it an IntegerComparator in its constructor:
//create the PriorityQueue, passing a Comparator to its constructor pq_ = new jdsl.core.ref.ArrayHeap(new jdsl.core.ref.IntegerComparator());In the Triage method enterPatient(), we see how key,element pairs are inserted into the PriorityQueue. This method is called when the "Add a patient" button is pressed The patient's name is retrieved from the text field, and used as as an element. The priority number is retrieved from the choice widget, and used as a key. Then the key and element are inserted, together, into the PriorityQueue.
protected void enterPatient(){ Object element = name_field_.getText(); int priority = Integer.parseInt(priority_chooser_.getSelectedItem(), 10); //remember that the key must be an Object, so make the int an Integer Object key = new Integer(priority); //Insert the data into the PriorityQueue pq_.insert(key, element); }In the Triage method getTopPatient(), we see how to extract the top-priority item from a PriorityQueue, using the removeMin() method. This method is called when the "Remove top patient" button is pressed. The top-priority patient is removed from the PriorityQueue, and patient's name displayed in a text field.
protected void getTopPatient(){
Object output;
//Remove the
top-priority item from the PriorityQueue
try{
output
= pq_.removeMin();
}
catch(EmptyContainerException
ece) {
output = "No patients
in queue.";
}
top_priority_patient_.setText((String)patient);
}
The PriorityQueue interface has some additional methods which were not used in the Triage program. For example, suppose you wanted to change a patient's triage status once that patient had already been entered into the PriorityQueue. In this case, you would use the PriorityQueue's replaceKey(Locator, Object) method. The PriorityQueue uses Locators to make such an operation possible.
Just as Positions proved useful in the previous example, to avoid a time-consuming examination of all the contents of a PositionalContainer. Locators likewise are useful for accessing contained items. A Locator acts as a "coat-check", a handle for keeping track of a key,element pair. In fact, the insert(Object,Object) method of any KeyBasedContainer returns a Locator for that pair. This "handle" can be used later to access that pair, to perform operations such as replaceKey(Locator,Object), or remove(Locator).
In the Triage2 program, we want to keep track of the patients that have been entered into the PriorityQueue, in order to access them later and change their triage priorities if necessary. We use an additional data structure, the Dictionary, to associate each patient-locator with a String. (The Dictionary interface is covered in detail in lesson 5.) That way, we can use the patient's String to access the patient-locator, and pass that Locator as a parameter to the PriorityQueue's replaceKey(.) method. Locators are an extremely useful tool for updating keys in a PriorityQueue.
Reading through the enterPatient() and
getTopPatient()methods
in Triage2, you will notice some minor additions, to take care of storing
patients and their Strings in the Dictionary. And here, in the method changePatientPriority(),
you can see how a patient-locator is accessed from the Dictionary,
and used to change a patient's priority in the queue. Note that a replaceKey(.)
operation is also performed on the Dictionary, since the patient-locator
must then be associated with its new String.
protected void
changePatientPriority(){
//
the String that's highlighted in the AWT list:
String
patientString = patient_list_.getSelectedItem();
//if a patient is
selected in the AWT list
if
(patientString !=
null){
//access
the patient-locator from the Dictionary
Locator
dictionaryLocator = dict_.find(patientString);
Locator
pqLocator = (Locator)dictionaryLocator.element();
int newPriority
= Integer.parseInt(change_priority_choice_.getSelectedItem(),
10);
Object
newKey = new
Integer(newPriority);
pq_.replaceKey(pqLocator,
newKey);//changes the priority-key in queue
//now
replace patientString w/ new one and change it in dict_
patientString = patientString(pqLocator);
dict_.replaceKey(dictionaryLocator,
patientString);
}
}
We will work with Locators again in the next example, which
covers another type of KeyBasedContainer, the OrderedDictionary.