Program 3

INFS 519
Program 3
due: December 5, 2013

The program

This program is an exercise in hashing. You will code a table using hashing and then an address book using this table. Some code is provided for you.

You will rewrite your address book program from Programs 1 and 2 with a more efficient table implementation. Details:

Your program will be a simple address book. It will store names (used as keys) and addresses that are associated with the names. The program will present the user a menu with a choice of operations: add a name (and address), look up a name (displaying the associated address), update the address for a name, delete an entry, display all entries, save to a file and quit.

If the user chooses add the program prompts for a name. If the name already exists in the address book a message is displayed to that effect and no change is made. Otherwise the program asks for an associated address and the new entry is made. If the user chooses look up he or she is asked for a name. The program will look up the entry for that name and display the associated address. If the user chooses update he or she is asked for a name. The name is looked up and the address displayed. The user is then prompted for a new address which is accepted and stored in place of the old address. For delete the user is asked for a name and the entry for that name is removed from the address book. In any of these cases (other than insert) if the name given by the user is not found an appropriate message is displayed. If the user selects display all all of the names and addresses in the address book are displayed (the order is not important). The program continues displaying the menu and taking commands until the user chooses quit.

As in Program 2 the program will first ask the user "Do you want to open a file? (y/n)." If the user answers "y" the program will ask for a file name, open and read the input file. Each pair of lines from the input file will be made an entry in the address book: a name line and an address line. If the user answers "n" the program will not open a file. In either case the program will continue as did Program 2. A "save" operation will also appear in the menu. When the user selects "save" the program will ask the user for the name of a file in which to write the address book, open the file and write the entire address book to the file. This operation will be very similar to the " Display all entries" operation.

Names and addresses will occupy a single line each (so all user input is taken using System.in.nextLine()). If the user enters a selection which is not in the menu the menu will be displayed again and the user is prompted again for a command. The names and addresses can be any strings -- your program need not check that they make any sense.

A sample run of the program may look like:

Do you want to open a file? (y/n) -> n Add a name (n) Look up a name (l) Update address (u) Delete an entry (d) Display all entries (a) Save to file (s) Quit (q) -> n Name: Genghis Khan Address: Khentii Aimag, Mongolia Add a name (n) Look up a name (l) Update address (u) Delete an entry (d) Display all entries (a) Save to file (s) Quit (q) -> n Name: Rasputin Address: St. Petersburg, Russia Add a name (n) Look up a name (l) Update address (u) Delete an entry (d) Display all entries (a) Save to file (s) Quit (q) -> n Name: Helen Mirren Address: London, England Add a name (n) Look up a name (l) Update address (u) Delete an entry (d) Display all entries (a) Save to file (s) Quit (q) -> l Name: Rasputin Address is St. Petersburg, Russia Add a name (n) Look up a name (l) Update address (u) Delete an entry (d) Display all entries (a) Save to file (s) Quit (q) -> u Name: Rutherford B. Hayes Rutherford B. Hayes is not in the book Add a name (n) Look up a name (l) Update address (u) Delete an entry (d) Display all entries (a) Read from a file (r) Write to a file (w) Save to file (s) Quit (q) -> u Name: Helen Mirren Old address is London, England New address: Hollywood, California Add a name (n) Look up a name (l) Update address (u) Delete an entry (d) Display all entries (a) Save to file (s) Quit (q) -> d Name to delete: Rasputin Add a name (n) Look up a name (l) Update address (u) Delete an entry (d) Display all entries (a) Save to file (s) Quit (q) -> a Name: Helen Mirren Address: Hollywood, California Name: Genghis Khan Address: Khentii Aimag, Mongolia Add a name (n) Look up a name (l) Update address (u) Delete an entry (d) Display all entries (a) Save to file (s) Quit (q) -> q

Internals

Your program will have Main class, a Record class and a Table class. Some of the Table class is provided. The Main class will create an instance of Table taking String for each of the type parameters T and U. It will use this for the address book where the first type parameter T will be an entry's name and the second U will be the corresponding address.

The Record class

You will write a Record class which uses two generic classes and has a field of each type:

public class Record <T, U> { private T key; private U data; // methods follow }

You will provide public T getKey(), public void setKey(T t), public U getData(), and public void setData(U u) methods. No constructor is necessary.

A public int hashCode() method and a public boolean equals(Record r) method must be supplied which will override the hashCode and equals methods inherited from Object. These methods will simply call (and return the values returned by) the hashCode and equals methods from T (the key class).

The Table class

public class Table<T extends Comparable<T>, U> will take two type parameters, T for the key and U for associated data. It will use a hash table to store Records (as described above).

Your hash table will use separate chaining as described in class. You will use a Node class (provided) which holds a Record and a next pointer for linking. The table will then use an array of pointers (references) to Node as head pointers to linked lists. Your hash function will map instances of Record to an index in this array and the Record will be placed in the corresponding list. The length of the array is up to you.

For a hash function you may use the hashCode() method from Record. Just modify the returned value to fit the range of index values for your pointer array.

The table will provide the usual operations as three public methods:

Record search(T k). Searches the table for a Record with key k. If found, a copy of the found Record is returned. Otherwise null is returned.
boolean insert(Record r). Inserts r into the table if there is no record already in the table with the same key and returns true. If the key already exists in the table false is returned.
boolean delete(T k). Finds a Record with key k, deletes it from the table, and returns true. If k does not exist in the table it returns false.

Several methods are provided for you which can be used to do a "traversal" of the hash table accessing each of the records by moving a cursor through the table. These methods are:

public void startList(). Places cursor on first node in table.
public Record nextRecord(). Advances cursor to next record in table and returns the (previous) current record -- requires cursor is not null.
public boolean hasNextRecord(). Determines whether any records remain to be listed.
private void advanceCursor(). Moves cursor to next node in the table or sets to null if at end of table.

Other than, perhaps, a constructor there will be no other public methods in this class.

To turn in