Big Java / Java Concepts Lab 22

Implementing Generic Classes

1.

Modify the class Pair<T, S> so that it implements Comparable<Pair<T, S>>. To compare a pair with another, you compare the first element (using compareTo). If they are equal, you should compare the second elements and return the result of their comparison. If the first elements are not equal, the compareTo method returns the result of first.compareTo(other.first).


2.

Create a PairTester class that tests the class you just created. Create a new TreeSet and add pairs to it. The pairs should consist of people names (last name, first name). At the end, iterate through the set and print its contents. If your Pair class was correctly implemented, the output should be displayed in alphabetic order (because a TreeSet implements a set using a binary search tree). Be sure to try a few pairs with the same last name.


3.

What happens if you try to add a Pair<String, Integer> to the set? What happens if your try to create a Pair<String, Rectangle>? Try it out and explain.


4.

Turn the MinHeap class in Section 21.9 of your textbook into a generic class. The bound of the type variable should extend the generic Comparable interface:

public class MinHeap<E extends Comparable>

You need not understand the inner workings of the MinHeap class in order to carry out this exercise. Simply change methods such as

public Comparable peek()
into
public E peek()
so that the user of the generic class need not apply any casts. Be sure to change the type of the elements instance field to ArrayList<E>.

What is the code for your modified class?


5.

A heap (in this case, a min-heap) can be used as a priority queue. Modify the following program so that it uses your generic MinHeap class and it uses Pair<Integer, String> instead of the class WorkOrder.


/**
   This program demonstrates the use of a heap as a priority queue.
*/
public class HeapTester
{
   public static void main(String[] args)
   {
      MinHeap q = new MinHeap();
      q.add(new WorkOrder(3, "Shampoo carpets"));
      q.add(new WorkOrder(7, "Empty trash"));
      q.add(new WorkOrder(8, "Water plants"));
      q.add(new WorkOrder(10, "Remove pencil sharpener shavings"));
      q.add(new WorkOrder(6, "Replace light bulb"));
      q.add(new WorkOrder(1, "Fix broken sink"));
      q.add(new WorkOrder(9, "Clean coffee maker"));
      q.add(new WorkOrder(2, "Order cleaning supplies"));

      while (q.size() > 0)
         System.out.println(q.remove());
   }
}


6.

In the previous exercise, could you have replaced the WorkOrder class with Pair<String, Integer>? (e.g. q.add(new Pair<String, Integer>("Shampoo carpets", 3));). Explain your answer.

Generic Methods

7.

Add a generic getRandomElement method to the ArrayUtil class of your textbook that returns a random element from an array of type E[].

(Use a static random number generator, and generate a random integer between 0 and a.length - 1.)

What is the code for your generic method?



8.

Add a generic getRandomPair method to the ArrayUtil class. It should return a randomly chosen pair, with the first index less than the second index. For example, if called with the array ["A" "B" "C" "D"], then a pair ("A", "B"), ("A", "C"), ("A", "D"), ("B", "C"), ("B", "D"), ("C", "D") is chosen with equal probability.

What is the code for your generic method?


10.

Write a tester class that tests the static methods you created. What is the code for your tester class?

Constraining Type Variables


11.

In the ArrayUtil class, write generic methods

void saveToFile(E[] a, String filename) throws IOException
E[] loadFromFile(String filename) throws IOException, ClassNotFoundException

The first method saves the elements of the given array to an ObjectOutputStream. The second method loads an array of objects from an ObjectInputStream.

When writing the type variable of the method, you should take into consideration that the elements of the array must implement the Serializable interface.



12.

Write a tester program for your previous class. Create an array of strings and add several strings to it. Save the list to a file, afterwards read them from the file and display them on screen.



13.

What happens if you don't supply the Serializable bound for the elements of the array list?

First change your tester program so that the elements of the array are of type Pair<String, String>. Try it out and explain.

Then, change your class to remove the Serializable bound, use your modified tester program and try it out. Explain.

Overcoming Limitations of Java Generics


14.

Generic classes and methods were added to Java several years after the language became successful. The language designers decided to use the type erasure mechanism because it makes it easy to interface generic code with legacy programs. As a result, you may run into some programming restrictions when you write generic code.

For example, you cannot construct an array of a generic type. The following method, which tries to grow an array, would be wrong:


public static <E> E[] grow(E[] a)
{
   E[] newArray = new E[2 * a.length + 1]; // ERROR
   for (int i = 0; i < a.length; i++)
      newArray[i] = a[i];
   return newArray;
}

To see why this is a problem, carry out the type erasure process, as if you were the compiler.

What would be the result?





15.

A tempting workaround would be to create an array of objects, like this:

public static <E> E[] grow(E[] a)
{
   E[] newArray = (E[]) new Object[2 * a.length]; // ERROR
   for (int i = 0; i < a.length; i++)
      newArray[i] = a[i];
   return newArray;
}

Try out this "solution". What happens when you call

String[] original = {"Hello", "World"};
String[] grown = ArrayUtil.grow(original);


16.

To solve this problem, you need to find out the type of the array a and make a new array of the same type.

You can get the type of the components of a by calling
Class cl = a.getClass().getComponentType();
The object cl is a descriptor for the component type. For example, when a is a String[] array, then cl describes the String type.

Now use the newInstance method of the java.lang.reflect.Array class to make a new array of the type cl. You still need to cast the result as E[] (and you will still get a warning), but now you are no longer lying.

What is the code for your modified grow method?


17.

Write a tester class for the grow method.
What is the code of your tester class?