Sorting a subclass in Java

Question

Suppose a Superclass implements Comparable<Superclass>, such that Arrays.sort(ArrayOfSuperInstances); uses this compareTo(Superclass other) method to sort. Does this guarantee that an array of instances of Subclass extends Superclass will sort in the same way using Arrays.sort(ArrayOfSubInstances); ? (Assuming the compareTo is not overloaded in the subclass definition)

Or in other words, will Subclass by default inherit the compareTo method of its Superclass , so that one can blindly use Arrays.sort() knowing they will be sorted as superclasses would be?

Enciso

Answer 1

Yes -- that is the whole principle behind polymporphism, and specifically the Liskov substitution principle. Basically, if A is a subclass of B, then you should be able to use A anywhere you'd be able to use B, and it should essentially act the same as any other instance of B (or other subclasses of B).

So, not only will it happen, but it's almost always what you want to happen. It's usually wrong to compareTo in the subclass.

Why? Well, part of the Comparable<T> contract is that comparison is transitive. Since your superclass will presumably not know what its subclasses are doing, if a subclass overrides compareTo in such a way that it gives an answer different than its superclass, it breaks the contract.

So for instance, let's say you have something like a Square and a ColorSquare. Square's compareTo compares the two squares' sizes:

@Override
public int compareTo(Square other) {
    return this.len - other.len;
}

...while ColorSquare also adds a comparison for color (let's assume colors are Comparable). Java won't let you have ColorSquare implement Comparable<ColorSquare> (since its superclass already implements Comparable<Square>), but you can use reflection to get around this:

@Override
public int compareTo(Square other) {
    int cmp = super.compareTo(other);
    // don't do this!
    if (cmp == 0 && (other instanceof ColorSquare)) {
        ColorSquare otherColor = (ColorSquare) other;
        cmp = color.compareTo(otherColor.color);
    }
    return cmp;
}

This looks innocent enough at first. If both shapes are ColorSquare, they'll compare on length and color; otherwise, they'll only compare on length.

But what if you have:

Square a = ...
ColorSquare b = ...
ColorSquare c = ...

assert a.compareTo(b) == 0;  // assume this and the other asserts succeed
assert a.compareTo(c) == 0;
// transitivity implies that b.compareTo(c) is also 0, but maybe
// they have the same lengths but different color!
assert b.compareTo(c) == 1; // contract is broken!

Roberto

Thanks for confirming this, I understood this Liskov substitution principle (although I didn't know this term), but I felt uneasy because of the special role of comparables in Java... (i.e. I felt uncertain that the subclasses were still comparable as superclasses, and that comparing subclasses would really use the superclass Comparable interface). Is this LSP adhered to throughout the whole Java package hierarchy, or are there some exceptions? – Enciso

@Enciso Comparables, though very useful, are nothing special in as far as the language is concerned -- they're an interface like any other, and the usual rules apply as far as dynamic resolution. So if you call o.compareTo(...), and o is of a subclass where the superclass also implements compareTo, the subclass version will be called. If you want to compare types of the subclass (e.g., a bunch of ColorSquares) you're better off writing a custom Comparator. As for LSP in the JDK classes, I can't think of any times that it's violated, but it's possible. – Roberto

I guess Java is more consistent than I first thought! (In my situation I do indeed need the superclass compareTo, so no need to specialize the comparison.), again thanks – Enciso

The documentation only discusses transitivity in the case of x > y && y > z. Surprisingly, it doesn't cover a case where x = y && y > z. I wonder if that's an oversight. – Ard

@Ard It's actually explicitly not required: "It is strongly recommended, but not strictly required that (x.compareTo(y)==0) == (x.equals(y))" (emphasis in original). BigDecimal is an example of a JDK class that does not follow the recommendation; equality cares about scale (so 2.0 != 2.00) but its compareTo doesn't. – Roberto

@yshavit, I wasn't referring to the consistent-with-equals recommendation. I was taking issue with your transitivity example. By x = y I meant x.compareTo(y) == 0. Not that I disagree with your point. The question actually occurred to me as I was leaving a similar comment on another question. – Ard

@Ard Sorry, I misunderstood. In that case, I think the sgn stuff in the docs address that through its implications with the other requirements. I'm at work right now, so don't have time to validate that :) – Roberto

Answer 2

By default, if you haven't overriden compareTo, the implementation from it's superclass will be used.

---

Now come to best practice, and open up Effective Java^TM

The basic contract of compareTo (and same goes for equals method) are:

1. Reflexivity: x.compareTo(x) should always be 0,
2. Symmetry: x.compareTo(y) and y.compareTo(x) should always return opposite sign or 0,
3. Transitivity: if x.compareTo(y) > 0 and y.compareTo(z) > 0; then x.compareTo(z) > 0

And

...there is no way to extend an instantiable class with a new value component while preserving the compareTo contract, unless you are willing to forgo the benefits of object-oriented abstraction

Update (thanks to yshavit)

So, you must know what you're dealing with. Ideally, I'd write a compareTo in subclass as well, it may or may not use superClass's compareTo. (sorry for the confusion that I have created)

Implementing compareTo or equals in your subclass, you will be breaking either symmetry or transitivity. Refer Item: 7, Effective Java^TM. It suggests that there is no way to extend a class and override the equals method (which has same contract as compareTo) to it something differently:

There is simply no way to extend an instantiable class and add an aspect while preserving the equals contract. There is, however, a fine workaround. Follow the advice of Item 14, “Favor composition over inheritance.” Instead of having ColorPoint extend Point, give ColorPoint a private Point field and a public view method (Item 4)

Fixture

Dont you mean superclass, not subclass? – Virescent

@Virescent ah, I was in hurry... just went to look into Effective Java. Thanks for pointing out. – Fixture

What would the compareTo in the subclass do? It would only be able to treat the other object as that of the superclass, or it'll break transitivity. It can only use this.* fields and methods available to the superclass, for the same reason. So, how would its implementation differ from that of the super class? – Roberto

Answer 3

It should, unless your compareTo is overridden or if calls some method that is overridden. A better question would show what happened when you tried, and what your concern is.

Moradabad

Answer 4

Yes, the behavior would be same as you are not overriding the compareTo method, but then make sure your subclass does not alter any attributes in a way that can break break the code in compareTo() method implemented in super class

Augustin