The Data Structures Library in Java

JDSL Tutorial

Previous Lesson
Table of Contents
Next Lesson


Lesson 4: Triage

This program allows the user to enter, in a text field, the name of a medical patient, and to associate a triage priority with each patient. The user can, at any time, remove the top-priority patient from the PriorityQueue. A second version of the Triage program highlights some additional features of the PriorityQueue and JDSL Locators.

New concepts covered:


View the Triage.java and Triage2.java files.
To run the demo programs, type java Triage or java Triage2 in a shell.

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.


Previous Lesson
Table of Contents
Next Lesson
Problems, comments?

Last modified: Sat Apr 19 16:54:05 CEST 2003