Searching the maximal element in an array with generics

Question

Task:

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

Answer:

public final class Algorithm {
    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 you explain how to use this method, please? And what is the difference with the following signature:

public static <T extends Comparable<T>> 
    T max(List<? extends T> ar, int begin, int end) { ... }

I don't understand the *"Which types can i use?"* part of your question. — NPE, Mar 15 '14 at 10:33
You can use any type that extends the Comparable interface, otherwise it's not guaranteed to have a `compareTo` function. — oschlueter, Mar 15 '14 at 10:34
@BoristheSpider yup, just read the link you provided and deleted my comment... I learn something new every day — fge, Mar 15 '14 at 10:35
Why the downvote? This is a good question, it confuses even seasoned Java developers. — Boris the Spider, Mar 15 '14 at 10:35
@BoristheSpider: I think this has the potential to be a good question. However, right now I don't think it is particularly well articulated (what does "Which types can i use?" even mean?) [I did not downvote BTW.] — NPE, Mar 15 '14 at 10:36
The other part of the question is, I suppose, why `Comparable super T>` and not `Comparable` — fge, Mar 15 '14 at 10:37

score 1 · Answer 1 · edited May 23 '17 at 10:25

Problem: the difference between public static <T extends Object & Comparable<? super T>> and public static <T extends Comparable<T>>

First part: why extends Object?

As very well explained in this answer, this is used for backwards compatibility reason with pre-1.5 APIs. So, if you don't have this problem, you can remove that.

Second part: why Comparable<? super T> and not Comparable<T>?

Let us take two classes A and B, with B inheriting A. You make both implement Comparable, but the logic for natural ordering is the same in A and B. As a result, you will write class definitions as:

public class A implements Comparable<A> {}

public class B extends A {}

Therefore, B implements Comparable<A>, not Comparable<B>. If it did the latter, you wouldn't be able to sort a List<A> where elements of the list were both of types B and A. Hence the super.

An example from the JDK: java.util.Date and java.sql.Date. The latter inherits the former. And you will see that java.sql.Date implements Comparable<**java.util.Date**>

score 1 · Accepted Answer · edited May 23 '17 at 12:27

I assume there are two questions here:

Why the bounds Object is required
Why to use Comparable<? super T> instead of Comparable<T>.

For the first question, it is not really required to give explicit Object bounds, but it may depend upon how you want the erasure of your method look like. With explicit Object bound, your type parameter will be erased to Object, and without that, it will be erased to Comparable. Most of the time, you won't find any need to give explicit bound, but this may be required for API compatibility as already explained in this post.

As for second question, using Comparable<? super T> is often a good idea, if you want to pass a list to List<T>, where T is comparable. Why? Suppose you have a class:

class Employee implements Comparable<Employee> { }

and a subclass:

class PartTimeEmployee extends Employee { }

and you want to pass a List<PartTimeEmployee> to a List<T>. It might seem straight-forward, and easy not before you realise that your PartTimeEmployee doesn't really implement a Comparable<PartTimeEmployee> but a Comparable<Employee>. So, what you do is, change the bounds of T to:

T extends Comparable<? super T>

.. and then you can pass a List<PartTimeEmployee>, as it satisfies the bound now.

The reason why you've to do this is to do with, erasure (Again?). Yes. On first seeing that error, you might jump off your chair and quickly make PartTimeEmployee comparable too by doing this:

class PartTimeEmployee extends Employee implements Comparable<PartTimeEmployee>

...but hey, you're doing wrong there. Java generics doesn't allow you to implement or extend from two different parameterized instantiation of same generic type. You're saying that, PartTimeEmployee implement both Comparable<Employee> and Comparable<PartTimeEmployee>. With this, you would have two methods in your PartTimeEmployee:

compareTo(PartTimeEmployee)
compareTo(Employee)

and after erasure, both of them will become:

compareTo(Object)
compareTo(Object)

and you've duplicate methods now. That is why it's illegal.

However in this case, since you have a List<? extends T> as parameter type, I think you might well do with Comparable<T>, because then when you pass a List<PartTimeEmployee>, T will be inferred as Employee, and hence will satisfy the bound.

Searching the maximal element in an array with generics

2 Answers2