Lab 8: Generics

1. Introduction

The goal of this lab is to practice writing generic classes. In class we have seen examples of generic linked lists. In this lab we will write a generic class that will be something similar to a HashMap. You will also be writing classes that implement two of the standard library's interfaces: Comparator and Iterator. These will give you a chance to work with inner (and even anonymous!) classes, too.

A map (also called a dictionary or associative array) associates keys with values. See the Map in Java's API as an example of the functionality.

We will use a simplified version of this interface in the lab, which we have called SimpleMap. Your main task in this lab is to implement this interface.

2. Set up

As usual, make a directory for this lab. Clone the repository with the starting code:

hg clone /cslab/class/csci245/lab8

Open Eclipse and make a new project from the existing source in your directory.

3. An anonymous inner class

First, take a look at the files in the example subdirectory. These both define a rather silly class that wraps an ordinary array of Strings, but provides a way get an iterator over it. In IterationArray.java, the iterator is made with a named inner class. Make sure you understand why this works, including how the iterator's methods can refer to a. Notice that there is a main() that you can run.

The second version, in IterationArray2.java, replaces that named inner class with an anonymous class. Look at the two files side-by-side (open them in two windows of an ordinary editor, if that helps) to see how the first changes into the second. Notice especially the following:

1. How are the instance variables in the anonymous class initialized?
2. What does the constructor call look like? How do you recognize that?
3. What happened to the implements keyword?

Be sure you understand the transformation applied here, because you'll need to do something similar later on.

4. Carrying on

Next, look at the driver program, SLMDriver.java, so that you see what the map will be used for. Basically it will be used to tally the frequencies of words in a file.

On the inside, your class will be a linked list. Think about how you would implement such a thing as a linked list, consider how it would need to be different from the linked lists we've already seen, and how the specific operations would be defined.

This map, however, will have a special feature. Java's HashMap orders associations in an unpredictable order— if you iterated through the key set, you would not get the keys in the same order that you added them, nor would there be any clear reason for the order that they would be iterated through. Your map, however, will take a Comparator<K> object in its constructor—that is, a comparator with the same type parameter as the map's key type. This will determine how the associations are ordered and what order the keys come when using keyIterator().

Note: resist the temptation to refer to your class as a hash map. The "hash" in "hashmap" refers to a specific way to implement a map (or set). We are not doing hashing in this lab. But we will learn about hashing later in the semester.

Finally, before you move on discuss with your partner and decide the basic structure of your classes. How will you implement the map as a linked list? What will your node class need to look like?

5. The SortedListMap class

Now, open SortedListMap, understand the parts of the code given to you (the nested Node class, the constructor, containsKey(), and get()).

Your task is to write the keyIterator() method. You have been supplied a start on an inner class SLMIterator, for which you will need to fill in whatever state it requires and the bodies of the hasNext() and next() methods.

You also need to write the put() method, which will have to use the Comparator that was passed to the constructor in order to figure out the order for the keys. To write put(), you just need to know that you can call compor.compare(k1, k2).

6. The comparator

When you are ready to test your SortedListMap, you'll also need to write a comparator. In this case, we want the key/value associations stored in alphabetical order of the keys. You will write a comparator for strings that performs that comparison. (The comparison itself is very easy, because String already has a compareTo() method which does exactly that comparison.)

However, instead of writing a plain old class that implements Comparator, practice nested classes by writing an anonymous inner class. Change the line in SLMDriver that reads

Map<String, Integer> tally = null; //new SortedListMap<String, Integer>(...your comparator...);

to

Map<String, Integer> tally = new SortedListMap<String, Integer>(...your comparator...);

except write your anonymous inner class in place of "...your comparator...".

7. The iterator, again

Replace the class SLMIterator with an anonymous local class in the method keyIterator().

8. Handing in

Make sure everything is committed to your repository. Then be sure that you are in the directory named lab8 and hand it all in with

/cslab/class/csci245/handin lab8 .

Don't miss the dot on the end of that.