The TAO of Java

Laboratory: A Simple Dictionary Implementation

Summary: In this laboratory, you will have an opportunity to enhance your understanding of the dictionary by exploring a vector-based implementation of dictionaries.

Contents:

• Exercises
  • Exercise 0: Preparation
  • Exercise 1: A Vector-Based Dictionary Implementation
  • Exercise 2: Preliminary Running Times
  • Exercise 3: Testing
  • Exercise 4: Correcting the Implementation
  • Exercise 5: Re-correcting the Implementation
  • Exercise 6: Deletion

Required Code Files:

• Dict.java (the interface)
• NoSuchKeyException.java (an exception to throw in calls to get)
• DictTester.java (a generic tester for Dict)
• KeyedValue.java (key/value pairs, used in many dictionary implementations).
• VectorBasedDict.java (a vector-based implementation of Dict)
• TestVBD.java (a tester for VectorBasedDict)

Exercises

Exercise 0: Preparation

In this laboratory, you will use a package entitled username.dict.

a. In a terminal window, type

/home/rebelsky/bin/tao dict

You should see messages about files being copied to a temporary directory.

b. Start Eclipse.

c. In Eclipse, build a project named Temp from /home/username/CSC152/Temp.

d. In the Temp project, you should see a package named username.dict. Drag that package to your Code project.

e. Delete the Temp project.

You can now work with the new package.

Exercise 1: A Vector-Based Dictionary Implementation

Look at VectorBasedDict.java, a vector-based implementation of the Dict interface.

a. Describe, in your own words, how this implementation works.

b. What is the purpose of find in this code?

Exercise 2: Preliminary Running Times

Give an approximate but close upper bound on the running time of put and get. You may assume that the add method of the Vector class is a constant time method.

Exercise 3: Testing

Look at DictTester.java, a generic tester for Dict, and TestVBD.java, a tester customized for VectorBasedDict.

a. Explain what the tests do.

b. Compile and run TestVBD and confirm that it produces the results you expect.

Exercise 4: Correcting the Implementation

As you should have observed in the prior problem, the get method works well in most cases, but fails to return the new value when we change the value associated with a key. Why? Because the put method adds a new key/value pair to the end of the vector without first checking to see if vector already contains a key/value pair with the same key and the find method returns the index of the first key/value pair that matches the key.

One way to fix this problem is to change find. Update find so that it correctly finds the most-recently added pair, rather than the least-recently added.

Exercise 5: Re-correcting the Implementation

Of course, another problem with the decision (if it was a decision) to put in multiple key/value pairs is that the get method may have to search through significantly more than n pairs to find a matching key.

A better solution is, of course, to avoid putting two pairs in with the same key. Rewrite put so that it does not put in a second pair.

Exercise 6: Deletion

Update

• the Dict interface to add a remove(K key) method,
• the DictTester class to add a tests for that method (e.g., remove a key and see if you can still find the corresponding value; then reinsert a pair with the same key and see if it's still findable), and
• the VectorBasedDict to implement that method.

History

Sunday, 9 April 2006 [Samuel A. Rebelsky]

• Created, based on a series of older labs.