How to sort a list of generic types in Java

Question

I have a set of classes that all share some common attributes, so I made them all extend a common base class, BaseEntity. So I have, for example Foo extends BaseEntity and Bar extends BaseEntity.

I also want lists of these Foo and Bar objects to be sortable, so I have implemented Comparable. I have the classes defined as Foo extends BaseEntity implements Comparable<Foo> and Bar extends BaseEntity implements Comparable<Bar>, and sorting of lists of Foos or Bars works as expected - and, of course, the details of the sorting are different in the different subclasses. But I can't work out how to make my sorting work when I don't know in advance whether I'll have Foos or Bars. This code, for example, fails to compile:

public class UtilityClass<T extends BaseEntity> {

  ...bunch of stuff...

  List<T> values;

  public List<T> sort() {
    Collections.sort(values);
    return values;
  }

  ...more methods...
}

with the error message Bound mismatch: The generic method sort(List<T>) of type Collections is not applicable for the arguments (List<T>). The inferred type T is not a valid substitute for the bounded parameter <T extends Comparable<? super T>>

I think the problem is that I am attempting to sort a list of BaseEntity objects, and BaseEntity itself doesn't implement Comparable. But now I face a problem: the only sensible thing to make BaseEntity objects comparable to is other BaseEntity objects, but when I add implements Comparable<BaseEntity> to BaseEntity, the compiler tells me that I've got problems now because my Foo class is trying to implement both Comparable<BaseEntity> and Comparable<Foo>, which evidently is not allowed.

I know I could sidestep this issue by dropping the implements Comparable<Foo> and just implementing Comparable<BaseEntity>, but then my compareTo methods will have to do ugly casting, and I thought that was exactly the sort of problem using generics was supposed to avoid.

What I really want to do is specify in the signature of BaseEntity that all its subclasses will be Comparable, but only to instances of the same subclass.

Any assistance gratefully received. Thanks!

Solution 1

Use an intersection type, like this:

public class MyList<T extends BaseEntity & Comparable<T>> {...}

That specifies that T must be both a BaseEntity and Comparable to itself.

Solution 2

Don't use Collections.sort(List<T>), use Collections.sort(Lst<T>, Comparator<? extends T>) instead. Write the comparation code in the comparator.

Solution 3

Try this:

static <T extends Comparable<? super T>> sort(T[] array);

This is the most general specification to accomplish the task. Basically, it asserts, that T is a type which can be compared to itself.

Comments

[Dave Mulligan]

The MyList class was just an example to show the error message. I chose a bad name :-(, this isn't actually a list of anything and instances of this class just need to perform the sorting, not actually be sortable themselves.

[Dolda2000]

I don't see why that would change the applicability of the answer, though. :)

[notXX]

because generics in java 5 is lame. the error 'like trying to implement both Comparable<BaseEntity> and Comparable<Foo>, which evidently is not allowed' obviously suggested it.

[Dave Mulligan]

Oh, yes, you're right. That Comparable<T> applies to T, not to MyList. Thank you thank you thank you.

[newacct]

for best results, use <T extends BaseEntity & Comparable<? super T>>

[Tushar Banne]

@newacct cn u explain what <T extends BaseEntity & Comparable<? super T>> actually does?

[newacct]

@TusharBanne: Comparable is a consumer and so should always be used with ? super wildcards, according to the PECS rule. Without the ? super wildcard, if you have a class that is comparable to itself, its subclass cannot be used as T here, even though it should be able to.