Max element - Sun's answer VS mine

Question

After reading Sun's documentation on Generics I moved to the Q and E section at http://docs.oracle.com/javase/tutorial/java/generics/QandE/generics-questions.html.

For Q8 -

Write a generic method to find the maximal element in the range [begin, end) of a list.

the code I wrote is:

private static <T extends Comparable<T>> T max(List<T> l, int i, int j) {
    List<T> sublist = l.subList(i, j);
    System.out.println("Sublist "+sublist);
    int c = 0;T max = null;
    for(T elem: sublist) {
        if(c == 0 || max.compareTo(elem) < 0) {
            max = elem;
        } ++c;
    }
    return max;
}

and Sun's answer is:

public static <T extends Object & Comparable<? super T>>

    T max(List<? extends T> list, int begin, int end) {

    T maxElem = list.get(begin);

    for (++begin; begin < end; ++begin)
        if (maxElem.compareTo(list.get(begin)) < 0)
            maxElem = list.get(begin);
    return maxElem;
}

Can someone please tell me with an example how Sun's version is better than mine?

EDIT: I want to compare the efficiency of the 2 solutions mainly on the basis of Type parameters/bounds used in the method declaration and not the logic e.g. in what situation(s) Sun's version is better for a caller of the function? Basically I don't understand why you need <T extends Object & Comparable<? super T> and List<? extends T> as used by Sun and not what I have used.

An example is much appreciated as I have been overwhelmed with theory. (Sorry if that sounds rude but I don't mean to be).

Thanks in advance, Mustafa

Answer 1

There are two separate generics questions here.

Why use an intersection type used?

That is, why does the solution use T extends Object & Comparable<T> instead of the more straightforward T extends Comparable<T>? (I've elided the wildcards in this section; I'll cover them below.)

I don't believe that Object & Comparable<T> is any different from Comparable<T> within the type system, since every object extends Object. That is, there is no type T that extends Comparable<T> that doesn't also extend Object & Comparable<T>.

There is a difference, though. An intersection type erases to the first component of the intersection, so T extends Object & Comparable<T> erases to Object whereas T extends Comparable<T> erases to Comparable. Consider two alternative declarations of the max method:

<T extends Comparable<T>> T max1(List<T> list) { ... }

<T extends Object & Comparable<T>> T max2(List<T> list) { ... }

If you dump the signatures of these methods using javap -s you can see the internal signatures showing the erased types:

<T extends java/lang/Comparable<T>> T max1(java.util.List<T>);
  Signature: (Ljava/util/List;)Ljava/lang/Comparable;

<T extends java/lang/Object & java/lang/Comparable<T>> T max2(java.util.List<T>);
  Signature: (Ljava/util/List;)Ljava/lang/Object;

Who cares about the erased type? The JVM does. The JVM finds methods based on matching the argument types and the return type. So the erased return type is potentially significant.

And in fact, it is significant from a binary compatibility standpoint. Prior to Java SE 5, when generics were introduced, the Collections.max method was declared and had the erased signature as follows:

public static Object max(Collection coll)
  Signature: (Ljava/util/Collection;)Ljava/lang/Object;

In Java SE 5 and later, the declaration and erased signature were:

public static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll)
  Signature: (Ljava/util/Collection;)Ljava/lang/Object;

Crucially, the erased signature is the same.

If instead the Java SE 5 declaration weren't declared using an intersection type, it would look like this:

public static <T extends Comparable<? super T>> T max(Collection<? extends T> coll)
  Signature: (Ljava/util/Collection;)Ljava/lang/Comparable;

This would be a binary incompatibility. Binaries compiled against old versions of the JDK would refer to a version of max that returns Object. If run against a JDK with this alternate, incompatible declaration, the only version of max would return Comparable instead, resulting in a NoSuchMethodError being thrown at link time.

Thus, the use of <T extends Object & Comparable<T>> is really to control the erasure of this declaration, which is driven by binary compatibility considerations. The tutorial seems somewhat misleading on this point. The actual declaration of Collections.max in Java SE is this way for binary compatibility. But if you were declaring this method for the first time, I don't believe that it would be useful to use an intersection type this way.

Why are wildcards used in the declaration?

That is, instead of:

static <T extends Comparable<T>> T max(List<T> list)

why are wildcards used:

static <T extends Comparable<? super T>> T max(List<? extends T> list)

Here, wildcards are necessary for the method to be used more flexibly in the presence of subtyping. Consider the following:

class A implements Comparable<A> { ... }

class B extends A { }

List<B> bList = ...;
B bMax = max(bList);

If the non-wildcarded declaration were used, there would be no T that matches. In order to make this work, Comparable<? super T> is necessary. This allows T to be inferred as B and everything works.

I must admit that I haven't been able to find an example that shows why List<? extends T> is required in this case. This example works fine if the parameter is declared simply List<T>. It may be that List<? extends T> is used for documentation purposes, to indicate that elements are only retrieved from the list, and that the list is not modified. (For more information on this, see Bloch's Effective Java in the generics chapter where he discusses PECS -- "Producer Extends, Consumer Super"; or Naftalin and Wadler's Java Generics and Collections where they discuss the "Put and Get Principle".)

---

Links:

Why is T bound by Object in the Collections.max() signature?

Angelika Langer's FAQ entry

Java Generics: What is PECS?

Why do we need bounded wilcard in Collections.max() method