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

Introduction

The goal of this lab is to practice developing type-safe collection classes and iterators.

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

Exercises

Pair Class

In this activity we will be working with 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.

Download the following files. The first is our initial Pair implementation and the second is a driver class that illustrates its use. Take a few minutes to read both files. (Ignore the test file for now.)

Both of these files should compile with no errors or warnings, 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 later on in the lab.)

Generic Pair Class

Our existing Pair class is flexible: it can be used to store objects of any type. Unfortunately, it is both dangerous and inconvenient. It is dangerous because we may accidentally store an object of an unexpected type (as you saw above). It is inconvenient because we will usually need to cast objects retrieved from a Pair before they can be used.

We can address these issues by making our Pair class generic. Our improved class will accept two type parameters since we may want the type of the first element to be different from the type of the second. Complete the following steps.

  1. Run the unit tests from PairTest.java. All tests should pass.
  2. 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.
  3. 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.
  4. 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.
  5. Uncomment the other test cases in PairTest.
  6. Fix the code in Pair to pass these test cases.

Benefits of Generics

Take another look at the PairDriver.java file. Your IDE should now be showing multiple warnings indicating that you aren't using the Pair class correctly: no type arguments are being provided.

Complete the following steps.

  1. 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 in the PairDriver main method. 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 logic error now and test the resulting code.

  2. STOP AND THINK: 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.

Iterable Collection

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.

Submitting

Submit the following files through Canvas: