James Madison University, Fall 2020

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.

The following documentation will be useful for completing this lab:

Java Generics Tutorial (through Wildcards)
java.util.Iterator
org.junit.jupiter.api.Assertions

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,key-value pairs (username and password), 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.

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 paramaters. This is an example of "test driven development": we are writing the tests before we develop the required functionality.
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.
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.
Uncomment the other test cases in PairTest.
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.

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 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.)
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, but this is the rare case where ignoring the warning is OK.

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".
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.

Building a collection

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

The collection that we are building here is a multiset (also called a bag). A multiset is an unordered collection of elements that may or may not be distinct. That is, a multiset is a set, but each item can be added repeatedly. These repeated adds should be represented in the multiset's size and contents. For instance, consider a multiset of integers such that we add 1, 2, 1, and 1 (in that order). The size of this multiset is four: three copies of "1" and one copy of "2".

Actually storing multiple copies of each object would be inefficient, particularly if the objects are large in size. Instead, each Multiset will internally consist of an array of Pair objects. One field of the Pair is a single copy of the object. The other field is a counter that keeps track of the number of copies that have been added. Consequently, adding a copy of an object just involves incrementing the counter of the approparite Pair object. Removing involves decrementing the counter. If the counter drops to 0, then the Pair should be removed from the array.

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

OPTIONAL: Comment out all test cases but the first. Iteratively uncomment more test cases as you implement more of Multiset.
Implement the add() and size() methods in the Multiset class. Make sure that add() returns false if the item cannot be added because there is no room remaining in the array.
Once all of the tests for add() and size() are passing, proceed with the contains() and remove() methods.
BONUS QUESTION: Note that these two methods take an Object parameter instead of the generic parameter type E. Why is it acceptable to use an Object here but not for add()?

Iterators

One common pattern with collections is to iterate over the elements and perform some common action on each. The Iterator and Iterable interfaces provide a standard approach for doing this. You can read about these two interfaces in the Java documentation:

An Iterator provides the methods hasNext() and next() for retrieving one element at a time, while an Iterable object provides an iterator() method that returns an Iterator, possibly using an anonymous inner class:

public Iterator<E> iterator() {
  return new Iterator<E>() {
    // Include the contents of a class declaration here
    // Calling iterator() on the containing class will return
    // an object that satisfies the Iterator<E> interface.
  }; // Do NOT forget the ; here, since this is the end of the iterator() return statement
}

The inner implementation of the iterator() method defines the behavior of actually stepping through the elements. As shown in MultisetDriver.java, you can call this method to get an Iterator instance that you can control with hasNext() and next(). The advantage of wrapping this in the Iterable interface is that you can use the Java for-each loop structure (for (Integer in : set)) instead of calling the methods explicitly.

OPTIONAL: While debugging the next step (build an Iterator), run the MultisetDriver to see how it behaves.
Implement the required Iterator methods in the inner class for the iterator() method.It is not necessary to provide an implementation of the remove method.
Throw exceptions as specified in the Iterator API.

Submitting

Create src.zip of the following files and upload it to Autolab: Pair.java, PairDriver.java, PairTest.java, Multiset.java, and MultisetDriver.java. Do NOT upload the Multiset.java JUnit test cases.

WARNING: When you create your src.zip file, make sure you are only archiving the individual files and not their containing directory. If you archive their directory (for example, the zip file contains src/Multiset.java, src/MultisetTest.java, etc.), then the Java code must contain the appropriate package structure (e.g., package src;). The Autolab configuration is not set up with this package structure.