CS 240: Algorithms and Data Structures
James Madison University, Spring 2020

Introduction

The goal of this lab is to explore the use of Java Generics by developing a Pair class that represents a 2-tuple. (Recall that a tuple is a finite ordered sequence of elements. A 2-tuple contains two elements, a 3-tuple contains three elements, an n-tuple contains n elements.)

A Pair class could be useful any time we need to store data that naturally occurs as an ordered pair: first and last name, two-dimensional coordinates, etc.

The challenge in designing this class is that we want to avoid specifying the element types in advance. The goal is to develop a single Pair class that may be used to store pairs of objects of any type.

Exercises

Object Elements

One possible design involves programming the Pair class so that the types of the two elements are declared as Object. Since every reference type in Java inherits from Object, this approach will give us the flexibility we want.

Open the following two classes in your favorite IDE:

Take a few minutes to read the code, then complete the steps below.

  1. The provided code compiles, but there is a logic error in the main method that will probably cause the driver to crash when largestStadium is passed the stadiums array. Find the problem and fix it.
  2. Complete the largestStadium method so that it conforms to the Javadoc comments. Test to make sure that it works as expected. (HINT: You will need to perform some casts when you retrieve the items from the tuple.)
  3. BONUS QUESTION: Why does this line of code compile? 
    stadiums[0] = new ObjectPair("Bridgeforth Stadium", 25000);
    Notice that the formal and actual parameter types don't match. The expected type of the second parameter is Object (a reference type) and the provided argument is 1 (a primitive value). If you don't know the answer to this question Google the term "Autoboxing".

Generics

  1. Create a copy of the ObjectPair class named Pair. Refactor this class to use Java generics. Your updated class should make it possible to independently specify the types of the first and second elements.
  2. Create a copy of the ObjectPairDriver class named PairDriver. Refactor this driver so that it uses your Pair class. The functionality should be unchanged. The resulting code should not include any cast operations.
  3. BONUS QUESTION: What happens if you re-introduce the problem that you fixed in step 1 from the previous section? Will the resulting code compile? Why do you think generic collection classes are sometimes called "type-safe" collections?
  4. BONUS QUESTION: List some reasons that the Pair class might be preferable to the ObjectPair class. Can you think of any situations where the ObjectPair class might be preferable?

Iterators

Now that you have a completed generic Pair class, create a minimally functioning collection of Pair objects. Open up the following files in your favorite IDE.

Take a few minutes to read the code, then complete the steps below.

  1. Declare a fixed-size array of Pair objects that uses generics. Declare additional members as needed to keep track of the number of Pairs added.
  2. Complete the constructor. Unfortunately, it isn't possible to directly instantiate an array of generic objects in Java. This won't compile: 
          pairs = new Pair<K, V>[CAPACITY];
    In this case, the easiest solution is to assign a "raw" pair array: 
          pairs = new Pair[CAPACITY];
    This will result in a warning along the lines of "Type safety: The expression of type Pair[] needs unchecked conversion to conform to Pair[]", which can be suppressed using the @SuppressWarnings("unchecked") annotation. NOTE: 99% of the time suppressing warnings is a BAD IDEA. This is a rare exception.
  3. Finish the addPair method. Return false if the array is already full.
  4. Implement the required Iterator methods. For remove, the Pair should be removed and all of the remaining elements should shift to the left one place.
  5. Throw exceptions as specified in the Java Iterator API.

Wildcards and Subclasses

Open up the following file in a simple text editor like vim, gedit or xed. (Don't open it in Eclipse!)

Comment each assignment statement with either:

// C (For "Will compile.")
or
// N (For "Will not compile.")

For those lines that will not compile, include an explanation of the problem. Once you have finished all of the statements, check your answers by attempting to compile the file. Comment out the non-compiling lines before submission.

Submitting

Submit all modified files as a zip file through Autolab:

The submitted file should be named generics.zip.

You may download the Web-CAT JUnit tests if you would like to test your code locally.