Comp 170 Lab 4 - StringMap

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.

Because you are dealing with two separate lists, it is tricky to do this with a for-each loop; it is easier with a while loop.

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).  The loop will start with "while (i<keys.size())", and the body will contain 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, and you have not found key, you should return null. (The alternative findIndex() approach, below, would have a similar loop, but you'd return i and -1, respectively, for the found/not-found cases.)

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 to print each entry; that is, keys.get(i) and values.get(i).

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.) Because you're using only the keys list, it is possible to do this with a for-each loop if desired.

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.

As an alternative approach to update(), and lookup() as well should you desire, you can implement findIndex(String s), which returns the position (index) of s in keys, or returns -1 if not found. The body of lookup() now becomes
	int i = findIndex(s);
	if (i == -1) return null;
	else return values.get(i);	// corresponding position in values
With this approach in update(), you first find the index of s in keys as above, and then handle the two cases of s found or not found; neither case should require an additional loop of any form.

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

As usual, email me your program.