CS 240: Algorithms and Data Structures
James Madison University, Fall 2021

Introduction

The goal of this lab is to explore key features of the Java Collection framework. The framework uses generics to support parameterized collections with strong type enforcement. Collection classes also provide iterators so that client code can loop through elements in the collection using Java's enhanced for-loops.

Portions of this lab were developed by Prof. Michael Kirkpatrick.

Exercises

Generic Pair Class

To get started, we will develop a generic 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.

Get started by opening the following two files in your preferred IDE:

Take a minute to read the provided code. This code compiles and passes the test, but we want to change both files to make appropriate use of generics. After reading the code in PairTest.java, complete the following steps.

  1. Change the testPairIntegerInteger method so that the Pair is parameterized for two Integers. In other words, instead of this: 
    	    Pair pair = new Pair(1, 2);
    pair should be declared and instantiated like this: 
    	    Pair<Integer, Integer> pair = new Pair<Integer, Integer>(1, 2);
    or like this: 
    	    Pair<Integer, Integer> pair = new Pair<>(1, 2);
    Next, eliminate the unnecessary casts to Integer in the calls to assertEquals. Note that your tests will not compile at this point. You still need to modify the Pair class to accept type arguments. This is an example of "test driven development": we are writing the tests before we develop the required functionality.
  2. Implement the next two test methods in a similar manner. You may select any values you prefer. Note that assertEquals requires a third parameter for comparing doubles.
  3. Edit the Pair class to use generics so that it passes these three test cases. Note that all uses of Object should be replaced with a generic parameter. Object should not appear anywhere in the finished class.
  4. Uncomment the other test cases in PairTest.
  5. Fix the code in Pair to pass these test cases.

Benefits of Generics

To see the benefits of using generics, open the PairDriver.java file. Read the largestStadium method, then complete the following steps.

  1. The provided code compiles, but there is a logic error in the main method that will cause the driver to crash when largestStadium is passed the stadiums array. Find the problem but DON'T fix it. (Don't panic if you aren't sure what the error is. It should become clear in the next step.)

  2. Add type arguments so that the Pair instances all have String for the first object and Integer for the second.

    Note that attempting to instantiate an array as follows will not compile: 

    	        Pair<String, Integer>[] stadiums = new Pair<String, Integer>[3];
    (If you are interested in why, check out this blog post.) Instead we need to instantiate the array without type arguments: 
    	   Pair<String, Integer>[] stadiums = new Pair[3];
    This will result in a warning along the lines of "Type safety: The expression of type Pair[] needs unchecked conversion to conform to Pair<String,Integer>[]", which can be suppressed using the @SuppressWarnings("unchecked") annotation. NOTE: 99% of the time ignoring or suppressing warnings is a BAD IDEA. This is a rare exception.

    Re-compile and observe the difference. At this point, the compiler should catch the logic error discussed in step 1. This is a key advantage of generics. They allow us to create classes that can work with any type, while still enforcing type expectations. This is why generic classes are sometimes referred to as "type-safe". Go ahead and fix the error now and test the resulting code.

  3. BONUS QUESTION: After adding the generics, can you remove the explicit casting in largestStadium? Why or why not? If you can, then go ahead and do so.

Iterators

Now that you have a completed generic Pair class, you will 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 unfinished methods according to the provided comments.

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

Create a src.zip file containing following files and upload it to Autolab:

WARNING: When you create your src.zip file, make sure you are only archiving the individual files and not their containing directory.