Comp 170 Lab 4 - StringMap, Oct 5

Goals

Overview

We want to create a phonebook. A bunch of pairs <name,number>, both of type String, can be entered; at that point one can search the phonebook for a specific person's number. A new project "phonebook" is available here,. The central idea is the StringMap class. Once you complete this class, the Phonebook class should work properly.

The basic interface (which you are to implement) is the following:
  1. String lookup(String key): given a name key, returns the matching number string, or null if it's not found.
  2. boolean insert(String key, String value): inserts the name+number pair <key, value> into the Map; return true if successful. If the key is already there, do nothing but return false.
  3. void update(String key, String value): Adds <key,value> if key is not there; if key is associated with some other value, update it. 
  4. void printMap(): prints out the table of all <key,value> pairs that have been entered.
  5. String search(String sub): given a part of a name, sub, return the first matching key (notthe value!), or null if not found.
Note that update is somewhat more tricky than insert; you don't really need a separate insert, but it's much easier to write the former.

For lookup(key), you should write a while loop that returns the desired values.get(i) if you've found a match (using .equals()) for keys.get(i).  That is, you'll have a "while (i<keys.size())" loop, and in that loop an if-statement test for "keys.get(i).equals(key)". If it's true, return the corresponding values.get(i). If you get to the end of the loop, you have not found key, and so you should return null.

For insert, first test with lookup() to be sure the key isn't already there. If it is, return false. Otherwise, use .add() to add the key to keys and the value to values. As long as both inserts are done together like this, they will always be synchronized.

For printMap(), just write a loop (for-each is fine) to print each entry.

For search(), follow the model of lookup() except do the keys.get(i).contains(sub) test instead of .equals(). Also, return keys.get(i), not the entry from values. (The idea is that one first searches for the right name; one searches for the number only when one is sure the name is correct.)

Finally, for update(),  first do a lookup() (copy the loop from lookup(); don't just call it). If you finish the loop and do not find the target, use .add() as in insert() (instead of returning null). However, if you do find the target, at position i (that is, you have a match keys.get(i).equals(key)), then use values.set(i, value) to update the value, and then call return. You will probably do this within the if statement inside the while loop.

Try to avoid searching through the lists more than once for each operation.

As usual, email me your program.