6.170 / Spring 2001 / Lab 4: Inheritance and Collections

Handout B4

• Purpose
• Setup
• Overview
• Exercise 1: Extend the capabilities of HashMap
• Exercise 2: Writing a custom iterator
• Exercise 3: Fun with Collections

Purpose

Setup

Overview of Inheritance

First, we will subclass HashMap to create MultiHashMap. To introduce the ability to store multiple elements while leaving the contracts for existing methods the same we will create two new methods, getAll and putAll, and override any methods necessary to implement the ability to map multiple values. Our method of doing this will be to let the superclass HashMap maintain a mapping from a key to a collection of values, rather than the actual values that are requested. MultiHashMap should not need to maintain any extra state beyond what is stored by its superclass. For this extension, get and put will have the same contracts as for HashMap. That is, put will return the previous value associated with a given key, or null if there was no mapping for key. And get will return the most recently associated value with the given key. Overriding get and put is enough to create a working HashMap that associates multiple values, however to make MultiHashMap implement MultiMap we will need to add two other methods, contains(Object key, Object value) and remove(Object key, Object value). While implementing this class, you might find java.util.LinkedList useful.

• Exercise #1: Extending HashMap

  
  Please open the MultiHashMap.java file. Your goal is to extend the java defined HashMap class to add the ability to store multiple objects. To do this, you will need to both add new methods and override two from HashMap. You will need to implement the getAll(Object key) and putAll(Object key, Collection values) methods, as well as the contains(Object key, Object value) and remove(Object key, Object value) methods. You will also need to override (redefine methods that were defined higher in the inheritance tree) the get, and put methods. The external behaviour of the get and put methods should be the same as in HashMap, but internally they should facilitate the ability to keep track of multiple associations. The only place where MultiHashMap should differ from HashMap externally is in its compliance with the MultiMap interface. To test if your implementation is correct, try compiling and running the file MultiHashMapTest.java.

Now we have a working version of a HashMap that can store multiple values. However, without overriding the values, containsValue, and entrySet methods with very special care, our MultiHashMap cannot be substituted whenever a HashMap is needed. The problem is that HashMap promises that entrySet and values will return collections that should be backed by the HashMap (changes to the collections should change the HashMap), but we have changed the value that is stored to one the user is not expecting. The very nature of HashMap relies on the fact that one key can only be associated with one value. With a lot of work and care a subclass that stores multiple values could be made, and it could be substitutable for HashMap. However, mapping multiple values to a single key is unnatural to the purposes of HashMap, and any gains that would be made by subclassing HashMap would be lost by trying to make it both substitutable and functional. Since our MultiHashMap breaks the contract of substitutability, we will have to look for another solution.

An alternative to subclassing is to encapsulate HashMap into a CollectionMap. Encapsulation was done by having CollectionMap hold an instance of a HashMap, and redirecting calls to our class to the internally stored HashMap. This allows the added feature of "abstraction by parameterization" for which kind of Collection we use to store the multiple keys. The CollectionMap constructor has a parameter that will let that instance of CollectionMap know what kind of Collection it should use to store the multiple values. The encapsulating class CollectionMap is provided for you. You don't need to understand how the production of new Collections is done, but if you are curious how the creation of classes based on a prototype is done feel free to examine the code and experiment.

The next exercise involves writing a customized iterator to let users access all values stored in our CollectionMap. The specified methods that our iterator has to implement are: public Object next(); public boolean hasNext(); public void remove(). For this exercise, we do not plan to support the remove function (an optional operation as defined by the java.util.Iterator interface) and so it will suffice to throw an UnsupportedOperationException as its body. (Remember that even though we don't plan on supporting the remove method, the interface requires that our class have such a method defined.) The goal of this iterator is to return each and every value stored in our CollectionMap one element at a time. One approach to creating such an iterator would be to iterate through the entire map, iterating through each Collection of values.

• Exercise #2: Writing a custom Iterator

  
  Please open the CollectionMap.java file. This time your job is to finish implementing the Iterator class ValuesIter. As an inner class of CollectionMap, ValuesIter can access any member variables of CollectionMap (including private access ones), as well as any of CollectionMap's methods. This iterator should return each value the number of times it appears as a value (i.e. if there is a String value that has 4 keys mapping to it, it should be returned 4 times). Again, to test if your implementation is working correctly, try running "java lab4.IterTest". Good luck!

• Exercise #3: Fun with Collections

  
  The final exercise is optional and for entertainment purposes only. Look at the Test.java file, and try to figure out what it's doing. Compile it and run it, then view the output, and how the different collections print to the standard output. Experiment with Collections not currently represented by Test.java and try to figure out why they are similar or different to the other Collection outputs. Create your own examples and methods, and have fun experimenting with the different benefits and trade-offs that the Collection types represent. Try to come up with examples of where you would want one specific type of Collection to be used over another. If you're really feeling adventurous, look at Class, Constructor, Method, and Field.

Encapsulation is the method of having one class contain an instance of another class that does all the actual work. The encapsulator (also known as a "wrapper" for the encapsulated class) acts as a filter between incoming calls and outgoing results. For instance, the object Integer is a wrapper for a primitive int. When the Integer method compareTo is called, it is the internal int's which are being compared.

Collection is an interface defined in Java version 1.2. It is the abstract idea of a group of Objects. As noted below in the Inheritance Tree (where interfaces are marked in italics, as well as lines on both the top and the bottom of the box, and classes are marked by normal text and a single line across the top of the box), List and Set are both sub-interfaces of Collection. List extends Collection by introducing the notion of an order to the group, while Set is the abstract notion of a set, a group of elements with no duplicates. All subclass relations are marked by a vertical connection, and all implementation relations are marked by a horizontal one.

The class java.util.Collections provides many useful static methods for use in dealing with Collections, Lists, and Sets. Some notable ones are: sort, binarySearch, min, and max.

Iterators are classes that allow the user to step through the elements contained by some type of collection. Iterator classes can be thought of as little parasites latching on to another class that contains elements, and obtaining each element sequentially (with each next call), then moving forward to the next one. They are so useful that the interface for Collection specifies that any class that wants to implement Collection must first have a method that returns an iterator that will step through each element. Closely related to Iterator is the java.util.Enumeration class. In fact, Iterator is just an update to Enumeration with the added (optional) remove operation, and shorter method names.