generic maximum function in Java [duplicate]

Question

I've read awesome "Effective Java" by Joshua Bloch. But one example in the books is left unclear to me. It's taken from chapter about generics, exact item is "Item 28: Use bounded wildcards to increase API flexibility".

In this item it's shown how to write the most universal and bulletproof (at the type system point of view) version of the algorithm of selection maximum element from collection using bounded type parameters and bounded wildcard types.

The final signature of the static method written looks like this:

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

And it's mostly the same as the one of Collections#max function from standard library.

public static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll) 

I understand why we need bounded wildcard in T extends Comparable<? super T> type constraint, but is it really necessary in type of the argument? It seems to me that it will be the same if we leave just List<T> or Collection<T>, isn't it? I mean something like this:

public static <T extends Comparable<? super T>> T wrongMin(Collection<T> xs)

I've written the following silly example of using both signatures and don't see any diferrence:

public class Algorithms {
    public static class ColoredPoint extends Point {
        public final Color color;

        public ColoredPoint(int x, int y, Color color) {
            super(x, y);
            this.color = color;
        }
        @Override
        public String toString() {
            return String.format("ColoredPoint(x=%d, y=%d, color=%s)", x, y, color);
        }
    }

    public static class Point implements Comparable<Point> {
        public final int x, y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
        @Override
        public String toString() {
            return String.format("Point(x=%d, y=%d)", x, y);
        }
        @Override
        public int compareTo(Point p) {
            return x != p.x ? x - p.x : y - p.y;
        }
    }

    public static <T extends Comparable<? super T>> T min(Collection<? extends T> xs) {
        Iterator<? extends T> iter = xs.iterator();
        if (!iter.hasNext()) {
            throw new IllegalArgumentException("Collection is empty");
        }
        T minElem = iter.next();
        while (iter.hasNext()) {
            T elem = iter.next();
            if (elem.compareTo(minElem) < 0) {
                minElem = elem;
            }
        }
        return minElem;
    }

    public static <T extends Comparable<? super T>> T wrongMin(Collection<T> xs) {
        return min(xs);
    }

    public static void main(String[] args) {
        List<ColoredPoint> points = Arrays.asList(
                new ColoredPoint(1, 2, Color.BLACK),
                new ColoredPoint(0, 2, Color.BLUE),
                new ColoredPoint(0, -1, Color.RED)
        );
        Point p1 = wrongMin(points);
        Point p2 = min(points);
        System.out.println("Minimum element is " + p1);
    }

So can you suggest an example where such simplified signature will be inacceptable?

P.S. And why the heck there is T extends Object in official implementation?

Answer

Well, thanks to @Bohemian I've managed to figure out what's the difference between them.

Consider the following two auxiliary methods

private static void expectsPointOrColoredPoint(Point p) {
    System.out.println("Overloaded for Point");
}

private static void expectsPointOrColoredPoint(ColoredPoint p) {
    System.out.println("Overloaded for ColoredPoint");
}

Sure, it's not very smart to overload method both for superclass and its subclass, but it let us see what type of return value was actually inferred (points is List<ColoredPoint> as before).

expectsPointOrColoredPoint(min(points));     // print "Overloaded for ColoredPoint"
expectsPointOrColoredPoint(wrongMin(points)); // print "Overloaded for ColoredPoint"

For both methods inferred type was ColoredPoint.

Sometimes you want be explicit about type passed to overloaded function. You may do it a couple of ways:

You can cast:

expectsPointOrColoredPoint((Point) min(points));     // print "Overloaded for Point"
expectsPointOrColoredPoint((Point) wrongMin(points)); // print "Overloaded for Point"

Still no difference...

Or you can tell compiler what type should be inferred using syntax class.<type>method:

expectsPointOrColoredPoint(Algorithms.<Point>min(points));     // print "Overloaded for Point"
expectsPointOrColoredPoint(Algorithms.<Point>wrongMin(points)); // will not compile

Aha! Here is the answer. List<ColoredPoint> can't be passed to function expecting Collection<Point> because generics are not covariant (unlike arrays), but can be passed to function expecting Collection<? extends Point>.

I'm not sure where or who may prefer to use explicit type parameter in such case, but at least it shows where the wrongMin may be inappropriate.

And thanks to @erickson and @tom-hawtin-tackline for answers about purpose of T extends Object constraint.

Answer 1

The difference is in the type returned, especially influenced by inference, whereby the type may be a type hierarchically between the Comparable type and the List type. Let me give an example:

class Top {
}
class Middle extends Top implements Comparable<Top> {
    @Override
    public int compareTo(Top o) {
        // 
    }
}
class Bottom extends Middle {
}

Using the signature you've provided:

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

we can code this without errors, warnings or (importantly) casts:

List<Bottom> list;
Middle max = max(list); // T inferred to be Middle

And if you need a Middle result, without inference, you can explicitly type the call to Middle:

 Comparable<Top> max = MyClass.<Middle>max(list); // No cast

or to pass to a method that accepts Middle (where inference won't work)

someGenericMethodThatExpectsGenericBoundedToMiddle(MyClass.<Middle>max(list));

---

I don't know if this helps, but to illustrate the types the compiler as allowed/inferred, the signature would look like this (not that this compiles, of course):

public static <Middle extends Comparable<Top>> Middle max(List<Bottom> list)

Answer 2

The difference between

T max(Collection<? extends T> coll)

and

T wrongMax(Collection<T> xs)

is that the return type of the second version is exactly the same as the collection's element type T, while in the first version T can be a super type of the element type.

The second question: the reason for T extends Object makes sure that T is a class and not an interface.

---

Update: A slightly more "natural" demonstration of the difference: Suppose you define these two methods:

static void happy(ColoredPoint p, Point q) {}
static void happy(Point p, ColoredPoint q) {}

And call the first one them like this:

happy(coloredPoint, min(points));
happy(coloredPoint, wrongMin(points));

The type inference engine could be able to deduce that in the first call the return type of min should be Point and the code would compile. The second call would fail to compile since the call to happy is ambiguous.

Unfortunately the type inference engine isn't powerful enough at least in Java 7, so in reality both calls fail to compile. The difference is that the first call can be fixed by specifying the type parameter as in Algorithms.<Point>min, while fixing the second call would require an explicit cast.

Answer 3

Not an easy one, but i'll try to be as specific as possible:

in T max(Collection<? extends T> coll) you could pass an argument like this List<Animal> or List<Cat> or List<Dog>, and in T wrongMax(Collection<T> xs) where T is Animal you can't pass as an Argument this List<Dog>, List<Cat> of course in Runtime you could add Cat or Dog objects in List<Animal> but in compilation time you wouldn't be able to pass a subclass of Animal in the Type of the List being passed as an argument in the wrongMax method, in the other hand, in the max method you could. Sorry for my english, i still learning it :), Regards.