CSC 241- Lab 5 (Due May 11, 2001) [60 Points]

Theme ...

You will learn ...

In this lab, you will work with the Set Package. I developed two interfaces that you need to become familiar with. I have already implemented the Set interface with a Tree class and a hashTable class. This interface represents collection classes that hold unique objects.

The elementType interface needs to be implemented by any class where its objects are going to be stored in our in a set. Such objects in adhering to the elementType interface must provide a key method that uniquely identify them. This characteristic is important when dealing with sets, we need to be able to distinguish and compare our objects that we store in them. With the ability to identify elements uniquely and compare them, we are enabled to store them in a way where we can find them quickly.

Create directories and copy some files

  1. cd public-html/classes/csc241
  2. cp -r ~mohammad/public-html/classes/csc241/Set/ . -- don't forget the dot or the -r.
  3. From public-html/classes/csc241 directory, type ls -R Set. The list should look like: 
    Set:
Set.java                 duplicateException.java  hashNode.java            notFoundException.java   treeNode.java
Tree.java                elementType.java         hashTable.java           testSet

Set/testSet:
elementForTest.java  test1.java
test2.java

Compile all Java files and run the test program

  1. Use javac *.java in each directory to compile all of the above .java files.
  2. Run the program that tests the two implementation of Set.

Change how size is figured out

Currently, both hashTable and Tree implement the size() method by returning the size_ field. size is declared in both classes on top and incremented when we add elements and decremented when we remove elements.

In both cases, Tree and hashTable, get rid of size_ declarations and any statements that manipulate it.

For Tree, the size() method's body will simply be replaced with the line: return size(root_);. Which means you need to write a recursive size method with a treeNode parameter that returns the size (i.e. number of nodes in the tree). Think about the following when writing this method:

For hashTable, the size() method's body will need one loop that goes through all array cells and an inner loop where for each array cell, you iterate through each node in the chain off of that cell. Each node visited causes you to add one to a temporary size variable which is returned after the completion of the outer loop.

change test1 and test2 to display the result of the call to size(), and test to make sure it correctly counts the elements in for both tree and hashTable.

Develop a Rolodex Application

You will develop a rolodex application program that provides users with the following options:

  1. Find someone's phone number.
  2. Add a name/phone number.
  3. Remove a name and its phone number from the rolodex.
  4. Change someone's phone number.

rolodexEntry

in order to develop the application program, you will need to first develop a rolodexEntry class that implements elementType. This class must have two fields: name and phone number. It needs to provide the appropriate methods required by the elementType interface. The key method must return the name. The stringView must return a string that follows this template: The name is:XXXXXX with the phone number:XXXXXXXX

Write a simple, but meaningful constructor for this class.

rolodexApp

Rolodex application keeps name/phone numbers in either a hashTable or a Tree. Your application should follow the algorithm given below:

  1. construct either a tree or hashTable.
  2. loop forever
    1. Provide a menu (1. Find Name, ..., 6. Quit) and get choice
    2. switch choice
      1. case 1: prompt for and read a name; find; output phone number or a NOT FOUND message. break
      2. case 2: prompt for and read a name and phone number; add an entry. output success or failure. break.
      3. case 3: prompt for and read a name to delete. remove an entry. output success or failure. break.
      4. case 4: prompt for and read a name and a new phone number. remove the old entry. insert a new entry. output success or failure. break.
      5. case 5: Display partial/full list (ONLY IF DOING THE EXTRA CREDIT)
      6. case 6: return.
    3. End Switch
  3. End Loop

What to Turn In

Submit your updated Tree.java, hashTable, rolodexApp.java and rolodexEntry.java.

Extra Credit--10 extra points

Include the additional option to the rolodex application: 5. Display partial/full list

This option enables the user to either see all names/phone numbers or a partial set of them.

The user needs to be prompted for a partial name/*. Lets assume the user response is stored in w. If w is a "*", all name/phone numbers are displayed, otherwise, the subset of the elements whose name start with the content of w are displayed. For example, if w is "la", all names in the rolodex that start with the substring la are displayed. Keep in mind that the toArray returns all elements from the set in an array, so you can use it to return all name/phone numbers and selectively display what you need.