17

I'm wondering if there's ever a valid use case for the following:

class Base {}

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

It seems to be a common pattern (see Collections for a number of examples) to accept a collection of type T, where T extends Comparable<? super T>.

But it seems technically impossible to fulfill the contract of compareTo() when comparing to a base class, because there's no way to ensure that another class doesn't extend the base with a contradictory comparison. Consider the following example:

class Base {
    final int foo;
    Base(int foo) {
        this.foo = foo;
    }
}

class A extends Base implements Comparable<Base> {
    A(int foo) {
        super(foo);
    }
    public int compareTo(Base that) {
        return Integer.compare(this.foo, that.foo); // sort by foo ascending
    }
}

class B extends Base implements Comparable<Base> {
    B(int foo) {
        super(foo);
    }
    public int compareTo(Base that) {
        return -Integer.compare(this.foo, that.foo); // sort by foo descending
    }
}

We have two classes extending Base using comparisons that don't follow a common rule (if there were a common rule, it would almost certainly be implemented in Base). Yet the following broken sort will compile:

Collections.sort(Arrays.asList(new A(0), new B(1)));

Wouldn't it be safer to only accept T extends Comparable<T>? Or is there some use case that would validate the wildcard?

shmosel
  • 49,289
  • 6
  • 73
  • 138
  • My gut says no (apples and oranges and all that), but the only reason you "might" consider this is if you NEVER wanted to compare the child classes in a different way then you do the parent class. Of course, you could always just call `super.compareTo` instead – MadProgrammer Jan 05 '16 at 02:45
  • I think you might want to clarify your title somewhat. I think the more interesting question raised in your post is "Why are methods in Collections declared to work on "T extends Comparable super T>" instead of "T extends Comparable"?" Obviously that isn't a great title, but I think a title directionally oriented like that could be better. – Others Jan 05 '16 at 02:51
  • I know Java `enum`s use their base class for a `Comparable`. All Java `enum`s derive from the `java.lang.Enum` base class which implements `Comparable`, where `E` is the child class (i.e., the enum you use). – markspace Jan 05 '16 at 02:59
  • @markspace, that's basically the opposite of what I'm asking about. `Enum.compareTo()` doesn't compare to its base; it compares instances of the same child. – shmosel Jan 05 '16 at 03:11

2 Answers2

11

This is a very good question. First, let's start with the reason why Collections use methods like

binarySearch(List<? extends Comparable<? super T>> list, T key)

Indeed, why not just

binarySearch(List<? extends Comparable<T>> list, T key)

The reason for this is the PECS principle: Producer Extends, Consumer Super. What does binarySearch do? It reads elements from the list and then compares them by passing their values to the compareTo function. Since it reads elements, the list acts as a producer, and hence the first part—Producer Extends. This one is obvious, so what about the Consumer Super part?

Consumer Super basically means that if you're only going to pass values to some function, you don't really care whether it accepts the exact type of your object or some superclass of it. So what the binarySearch declaration is saying is: I can look for anything as long as that anything can be passed to the compareTo method of the list elements.

In the case of sorting it's not that obvious, because the elements are only compared to each other. But even then, what if Base actually implements Comparable<Base> (and does the whole comparison) and A and B just extend Base without touching comparison in any way? Then you would be unable to sort lists of A and B because they don't implement Comparable<A> and Comparable<B> respectively. You'd have to reimplement the whole interface each time you subclass!

Another example: what if someone wanted to do a binary search on a list containing instances of some class that doesn't even extend your Base?

class BaseComparable implements Comparable<Base> {
    private final Base key;
    // other fields

    BaseComparable(Base key, ...) {
        this.key = key;
        // other fields initialization
    }

    @Override
    public int compareTo(Base otherKey) {
        return this.key.compareTo(otherKey);
    }
};

And now they want to use an instance of A as the key for this binary search. They can only do it because of the ? super T part. Note that this class has no idea about whether the key is an A or a B so it can't possibly implement Comparable<A/B>.

As for your example, I guess it is just an example of poor design. Unfortunately, I see no way of preventing such things without breaking the PECS principle and/or limiting already limited functionality of Java generics.

Community
  • 1
  • 1
Sergei Tachenov
  • 24,345
  • 8
  • 57
  • 73
0

The constraint 

    T extends Comparable<? super T>

should be be understood as

    T extends S, S extends Comparable<S>

A Comparable type is always self-comparing.

If X <: Comparable<Y>, it must be the case that X <: Y <: Comparable<Y>.

We could even "prove" that from the contract of compareTo(). Since the reverse y.compareTo(x) must be defined, it must be true that Y <: Comparable<A>, X<:A. Following the same argument, we have A <: Comparable<Y>. Then transitivity will lead to A=Y.

ZhongYu
  • 19,446
  • 5
  • 33
  • 61