The Data Structures Library in Java

JDSL Tutorial

Previous Lesson
Table of Contents
Next Lesson


Lesson 5: Phone Book

This simple phone number database supports insertion and removal of names and corresponding phone numbers, and allows the user to retrieve a phone number by entering a name. The program demonstrates some capabilities of the JDSL's Dictionary and OrderedDictionary interfaces.

New concepts covered:


The entire PhoneBook.java file can be viewed by clicking here.
To run this demo program, type java PhoneBook in a shell.

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.


Previous Lesson
Table of Contents
Next Lesson
Problems, comments?

Last modified: Mon Aug 16 10:12:50 EDT 1999