CMPU 102 - Assignment 8

CMPU 102 - Assignment 8
Phone Book using a Binary Search Tree

Assigned: Mon, Apr 21
Due: Mon, Apr 28

In this assignment you will:

Implement a phone book using the ABST (binary search tree) class hierarchy implemented in Lab 8.
Complete the classes Person and PhoneBook as outlined in the starter project.
Implement a pre-order traversal of the binary search tree that you will use to store the information in the phone book when you quit the application. You will restore the phone book to its previous state in main memory when you return to the application.
Be given Main and GUIMenu classes to drive your program with the following menu-driven user options:

add a person to his/her phone book,
remove a person from the phone book,
find a person by name in the phone book and return the desired number,
change the number of a person in the phone book,
store the information in the phone book in secondary storage, and
load the phone book back into main memory, restoring the tree structure to its previous form.

Use the submit102 script from the Linux prompt to hand in your project.

Summary: We have provided the starter project with most of the classes. You will complete the classes Person, and PhoneBook as instructed in the comments.

Download the starter project

Click here to download the starter project: Assign8.zip.
Save it in your cs102 directory.
Unzip the file.
You should be able to Open this as an existing project in NetBeans (described next)

Launch NetBeans and Open Project

From NetBeans, go to the File menu and select "Open Project" -- or click on the third button from the left on the button bar.
Navigate to your cs102 folder and select the folder named "Assign8"
The "Open Project Folder" button should be enabled. Click it to open the starter project.
The files you need to modify are: Person.java and PhoneBook.java.

The Person Class

This class has the following constructor and getter/setter methods:

Person(String name, String phoneNumber),
String getName( ),
String getPhoneNumber( ),
void setPhoneNumber(String number), and
String toString().

All of the methods are very straightforward. Your implementation of toString() should produce a string containing the name of the person and his or her phone number, as illustrated in the sample output shown below.

The PhoneBook Class

The instance variables for this class are an ABST tree, a PersonalNameComparator reference object, and a String containing the name of the phonebook text file. You will implement the following methods: (see the comments in PhoneBook.java for the purpose statements describing each method, and the paragraphs below for more complete descriptions)

a constructor, PhoneBook(),
void add(Person person),
void remove (Person person),
boolean contains(Person person),
boolean find(Traversal tr, Person p),
Traversal traversal(),
void changeNumber(Person p,String newNumber),
String displayEntries(Traversal tr),
void save(PrintWriter pw), and
void load(Scanner scan).

The PhoneBook is implemented using a binary search tree to hold its entries. Each entry is a Person object, and the key field will be the person's full name. The names will be listed as last, first in the Person object and will be entered in this fashion using the GUI menu. The constructor will initialize the two instance variables of the class -- the ABST concrete subclass and the Comparator. The add( ), remove( ), find( ), and contains( ) methods will be implemented by applying the appropriate ABST methods to the tree. Recall that class ABST implements the Traversal interface, and therefore both BSTNode and BSTLeaf can be returned as a Traversal. The method traversal( ) in this class is just going to return the tree. Method changeNumber( ) must ascertain that the Person object is found in the tree, and then change the phone number of that object to the new value. If the Person passed in as a parameter is not in the tree, an error should be thrown, but this will be unnecessary here, because a test for contains( ) is made in the MenuGUI before this method is called. In method displayEntries( ), you should return a string with line feeds separating each of the entries (sub-strings). The string returned by displayEntries( ) will produce an in-order arrangement of the display shown below.

In method save(), you must create a new PrintStream object at the beginning, so you have the file to write to; and you must close the PrintStream at the end of the method. This code is provided. You fill in the rest. To save your phone book, you must perform a pre-order traversal of the entries in the book and save the name and phone number of each Person during the pre-order visit. You will use a generic stack from the java.util library to hold ABST objects. In the pre-order traversal for this functional implementation, you begin by placing the tree (instance variable) on the stack. Then, while the stack is not empty, you remove the ABST object from the top of the stack (it should only be a BSTNode) and hold in a temporary store. Next check if first the right child is a BSTNode, and if so, place it on the stack. Do the same for the left child. After determining whether to push the right and left children of the node removed onto the stack, use method getData( ), that has been added to the BSTNode class, to retrieve the data from the node removed (remember to cast it as a Person) and have the PrintStream, ps, write the name and phone number to the input/output file. Put the name and phone number for each Person in the book on a single line with spaces between the name and number with no additional comments or punctuation.

In method load(), you must create a Scanner object to read the phonebook entries from the file, and close the scanner at the end of the method. (Don't hesitate to look up the Scanner class in the Java API if you're unsure how to use it.) Use the scanner you created in a while loop header to determine whether the file has more inputs. If so, read in the next line. Declare a second scanner to scan the line just read in (a String) and extract the last name (with comma), the first name, and the phone number from it. Repeatedly do this for each entry. For each line, use the first two sub-strings from the line to create a name string and then create a new Person object and add it to the phone book (the tree). Before beginning to scan in lines from the source file, you should create a new empty tree. Since the information for each person in the saved book was written to the source file during a pre-order traversal, the construction of the restored tree in method load will duplicate the previous tree exactly.

Finally

Complete the partially implemented classes as detailed above. Follow instructions included with the comments to implement each method.

Good luck!

When you complete your program and run it, a sample of the output should look like this. This is a print to the console of the entries in the phone book using a pre-order traversal (with Warren Spahn as the root node in the tree). The saved file will list the names and numbers in this order, but will just have the name and phone number. If you add a few names from the menu and then select show all, the output to the text area will have a similar appearance, but will be in an in-order listing.

init:

deps-jar:

compile:

run:

Name: Spahn, Warren Phone Number: 123-0987654

Name: Aaron, Hank Phone Number: 099-1010102

Name: Mays, Willie Phone Number: 222-1230987

Name: Mantle, Mickey Phone Number: 345-1234578

Name: Koufax, Sandy Phone Number: 222-3345667

Name: Ruth, Babe Phone Number: 009-9876543

BUILD SUCCESSFUL (total time: 5 minutes 16 seconds)

Submitting your solution

From a terminal window, type the following commands:

cd

cd cs102

submit102 Assign8