A Generic ArrayUtils

Our DynamicArray is generic and Student is comparable. The last piece is ArrayUtils, which still operates on the non-generic, int-based DynamicArray. Let’s make it generic too.

A type parameter for a static method

Start with the easy one: swap. It exchanges the elements at two positions and never compares them, so it works for any element type. Here is the generic version:

public static <T> void swap(DynamicArray<T> a, int i, int j) {
  T temp = a.get(i);
  a.set(i, a.get(j));
  a.set(j, temp);
}

There is a new piece of syntax here: the <T> before the return type. In this chapter so far, T came from the class header, class DynamicArray<T>. But ArrayUtils is not generic. It is a namespace of static methods that we never instantiate, so it has no class-level T to borrow. Instead, each static method declares its own type parameter, right before the return type. That <T> says “this method works for some type T, whatever the caller is using.”

The body changes the way you would expect: the temporary variable is now a T instead of an int.

Constraining T so we can compare

indexOfMin is the method that compares two elements with <:

if (a.get(i) < a.get(minIndex)) { ... }

We need to use compareTo instead of <.

if (a.get(i).compareTo(a.get(minIndex)) < 0) { ... }

This reads “the element at i comes before the element at minIndex,” using the negative/zero/positive convention.

But that line does not compile yet. We can only call compareTo on T if T actually has a compareTo, which means T has to implement Comparable. An arbitrary T might not, and the compiler cannot assume that it does. So we have to constrain the type parameter, and allow only types that are comparable:

public static <T extends Comparable<T>> int indexOfMin(DynamicArray<T> a, int from) {
  int minIndex = from;
  for (int i = from + 1; i < a.size(); i++) {
    if (a.get(i).compareTo(a.get(minIndex)) < 0) {
      minIndex = i;
    }
  }
  return minIndex;
}

The new part is <T extends Comparable<T>>. This is a bounded type parameter: it says “T can be any type, as long as it implements Comparable<T>.” With that bound in place, the compiler knows every T has a compareTo, so the call is allowed.

Notice that we bounded indexOfMin but not swap. The rule to follow is: add a bound only when the code actually needs it. swap never compares anything, so any T will do, and the unbounded <T> is right. indexOfMin calls compareTo, so it does need Comparable. If we bounded swap the same way, we would gain nothing, and we would stop a caller from swapping two elements of a type that does not implement Comparable.

swap and indexOfMin are done. selectionSort is the one left.