There are three main objectives that this lab helps us meet:
In lab3, we learned about creating abstract classes and extending them in different ways and providing distinct implementations. We also learned about building generic stacks and queues that held any subclass of Object. In this lab, you will be introduced to the concept of interfaces that are pure design tools in Java. Interfaces only allow for identifying methods and constants, no implementation, thus, they are very similar to abstract classes. They do, however, provide further flexibility in design than a simple class hierarchy which I hope to show here.
I have developed an interface named Keyed that you will use. This interface can be implemented by all classes that we wish for their objects to be identified uniquely through a key value. This characteristic is important when dealing with ordered collections, we need to be able to distinguish and compare our objects that we keep in such a collection. Also, for us, it means that we won't have to just build a class for a binary search tree that holds integers, we will build one that holds any keyed object.
We will also work with an interface named orderedCollection that allow us to maintain uniquely keyed objects. I have designed a Binary Search Tree class and a Hash Table class that implement Ordered Collection. They both need their update methods implemented which you will do in this lab. I hope that you will understand why the concept of keyed is important in these Collections. Binary Search Trees and Hash Tables differ from stacks and queues in that they care about uniqueness of elements that they hold, in neither case, can we allow duplicates. Making sure that all objects held in ordered collections adhere to the Keyed interface enable ensure uniqueness.
Once, you finish building these ordered collections, we can compare their behavior for adding, removing, and finding values. Of course, there are many variations to hash tables, so, our results won't be complete, but, I think, you will learn something!
To complete the lab you will implement a dictionary application where an end-user could update and query the dictionary. You will use the interfaces and the classes that we have built.
cd public-html/classes/csc241
cp -r ~mohammad/public-html/classes/csc241/Collection/ . -- don't forget the dot or the -r.
ls -R List. The list should look like:
Collection/:
Keyed.class hashNode.class orderedCollection.class
Keyed.java hashNode.java orderedCollection.java
Tree.class hashTable.class testCollection
Tree.java hashTable.java treeNode.class
duplicateException.class notFoundException.class treeNode.java
duplicateException.java notFoundException.java
Collection/testCollection:
test1.class test2.class testKeyed.class
test1.java test2.java testKeyed.java
java test1 tree and
java test1 hash 10
java test2 tree and
java test2 hash 10
I have left the implementation of the update method in Tree and hashTable for you. In each case, you must use the key from the parameter x to locate the object in the collection and replace your finding with the new version. Imagine, if we have implemented Keyed with an employee class. Suppose employees have IDs, names, addresses, etc. In a collection that keeps employee objects, the update method allows us to update a given employee's information. So, for example, we could use find to get the employee object, modify the address in it and use update to replace the object in the Collection. Modify test2 to test your update methods.
To effectively compare performances for hash tables and binary search trees you need a bigger pool of data. Just inserting 100 or so elements and performing 100 or so operations on the collections will not give you a definitive conclusion on their performance. Here, I want you to modify the test2.java program to test for inserting 10,000 elements and 1,000 operations. Two thing that you should not over look:
Run the test program for tree and hash. What happens if you use a size argument that is larger than just 10 when testing the hash version? How much time did the test program take in the different runs that you made? Be sure to indicate in your email, how many times you ran the program, with what arguments, and what your results were.
Can the performance of Tree be improved by not performing the find method before actually performing insert, or delete, or update? understand that if you don't use find, your algorithms for each of those operations have to be modified to throw the correct exception themselves. For example, you must ensure that duplicates are not inserted into the tree and the duplicateException is thrown. You need to test any changes that you make with output to make sure they worked correctly (not for 10,000 elements). But, once you know they work correctly, you need to test the tree performance and report your finding.
Build a dictionary application program. Your dictionary program provides a user with the following options:
I have put a data file together for you in
public-html/classes/csc241/Collection/testCollection/ named
lab5.dat. This file contains words and meanings in a simple format.
You need to develop a class dictionaryEntry that implements
Keyed. This class must have two fields: word and
meaning. It needs
to provide methods that return these fields. The obvious choice for the
key method is to return word. You need to think
about what other methods or constructors you need for this class. The
dictionary application will need dictionaryEntry and
either the hashTable or the Tree implementation of
orderedCollection. Since the
data file has words that are already sorted, the tree version will not work
optimally, do you know why?
Your application should follow the algorithm given below:
1) Build a collection from the words and meanings in the data file
2) loop forever
3) Provide a menu (1. Find Word, ..., 5. Quit) and get choice
4) switch choice
5) case 1: prompt for and read a word; find; output meaning
or a NOT FOUND message.
break
6) case 2: prompt for and read a word and meaning; add; output
success or failure.
break
7) case 3: prompt for and read a word to delete; remove, output
success or failure
break
8) case 4: prompt for and read a word and a new meaning; update,
output success or failure
break
9) case 5: return