Address Book BST

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, and quit.

A sample run of the program may look like:

Add a name (n)
Look up a name (l)
Update address (u)
Delete an entry (d)
Display all entries (a)
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)
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)
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)
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)
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)
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)
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)
Quit (q)
-> a

Genghis Khan
Khentii Aimag, Mongolia
Helen Mirren
Hollywood, California

Add a name (n)
Look up a name (l)
Update address (u)
Delete an entry (d)
Display all entries (a)
Quit (q)
-> q

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 program continues displaying the menu and taking commands until the user chooses quit.

This address book will not store its contents in a file which can be read later so, other than as a programming exercise, it is quite useless.

Names and addresses will occupy a single line so all user input (including user response to the menu items) is taken using nextLine() from the Scanner class. 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.

Internals

You will write a class Table which will store "entries", which are (key/value) pairs of Strings, in a binary search tree. Code for the BST is provided for you. Since you can only store one value in a node of the BST a class Entry is also provided for you. You will notice that the compareTo() method of Entry compares only the Key fields.

The Table class

You will write a class: public class Table Key extends Comparable Key, Value which will store entries which are Key/Value pairs. A Key/Value pair will be used to create an instance of the class Entry which will be stored in the BST. Table will have public methods:

• public boolean insert(String key, String value) Inserts a new entry to the table. If an entry already exists with the given key value make no insertion but return false.
• public String lookUp(String key) Looks up the entry with the given key and returns the associated value. If no entry is found null is returned.
• public boolean delete(String key) Deletes the entry with the given key. If no entry is found returns false.
• public boolean update(String key, String newValue) Replaces the old value associated with with the given key with the newValue string.
• public void displayAllEntries() Prints out the entries of all pairs. in the table.

insert(), lookUp(), delete() and update() will use the corresponding binary search tree operations. You will implement displayAllEntries() by calling the traverse() method.

You may add any more methods you need to the Table class but they must be private. The only public methods are those listed above.

You will notice that this Table class is not specifically an address book but just stores and operates on pairs of strings. You will implement your address book as an instance of Table and will implement the address book operations, listed at the beginning of this page, using public methods of Table.