• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

implementing Comparable with generics / inheritance

 
Ranch Hand
Posts: 90
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hello fellow ranchers, I've been puzzled how to implement Comparable regarding inheritance..

Lets say we have List defined as superclass and we wish to sort it using Collections.sort(List<T>), but meanwhile List contains both instances of superclasses and subclasses. Let's also assume that SubClass adds some field, which is relevant to the comparison process, but (of course) only when comparing subclasses. Therefore we need to make instanceof tests and cast objects to subclass when applicable..let's also say that Subclasses come "first"..example java code follows..



Now this *seems* to give correct results, but from my point of view it's ugly code. How comparing lists which may contain both subtypes and supertypes should be implemented? (Without Comparator). Surely my implementation can't be satisfactory? Or should we provide *some* hook / callback method which would then be called on compareTo-method? How should one solve this in a satisfactory way?
 
Bartender
Posts: 4568
9
  • Likes 2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
First point - I'd agree. That's not satisfactory. A superclass should never know anything about its subclasses, so for MyUpper to have any references to MySub is a poor design, in my opinion.

It's a little difficult to be sure with a made up example like this, rather than a real one, but my instincts say that this ordering probably isn't a natural ordering. In which case, although you could improve this using Comparable isn't the right way to go about it in the first place, and you ought to be using a Comprator.
 
Marshal
Posts: 28193
95
Eclipse IDE Firefox Browser MySQL Database
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I think this is a well-known problem in the OO Design area, although I had a quick google and I couldn't find a writeup about it. I do remember reading about it some time ago, though.

Basically it's an insoluble problem. It requires objects of every subclass of MyUpper to be able to compare themselves to objects of any other subclass. It's easy to figure out how to compare an object of one subclass to another object of the same subclass, but not how to compare it to an object of some other (unknown) subclass.

And the solutions you come up with to do that generally fail to follow the rule that a.compareTo(b) and b.compareTo(a) must have opposite signs.

As I recall, the article that I read basically threw up its hands and said not to do this.
 
Tapio Niemela
Ranch Hand
Posts: 90
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Paul Clapham wrote:I think this is a well-known problem in the OO Design area, although I had a quick google and I couldn't find a writeup about it. I do remember reading about it some time ago, though.

Basically it's an insoluble problem. It requires objects of every subclass of MyUpper to be able to compare themselves to objects of any other subclass. It's easy to figure out how to compare an object of one subclass to another object of the same subclass, but not how to compare it to an object of some other (unknown) subclass.

And the solutions you come up with to do that generally fail to follow the rule that a.compareTo(b) and b.compareTo(a) must have opposite signs.

As I recall, the article that I read basically threw up its hands and said not to do this.



Thanks Paul and Matthew for clear answers. So the way to go is Comparator of course for Objects which can't be ordered "naturally". Also "It requires objects of every subclass of MyUpper to be able to compare themselves to objects of any other subclass" is a nice point of view I didn't figure out in the firstplace :)
 
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Any chance of a link to the article, please, Paul?
 
Paul Clapham
Marshal
Posts: 28193
95
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I spent a bit more time googling without much more success. After I added "bloch" to my list of search terms I came up with things which linked to "Effective Java", but apparently the bit I was thinking of which was in that book was about it being hard to implement equals() correctly in the presence of subclassing. Which you're familiar with already, according to this Ranch thread.

I also came across blog entries which claimed that they had invented workarounds for the equals-plus-subclassing problem (basically the idea is that objects in two different subclasses must be unequal, roughly speaking), but those workarounds can't be extended to the compareTo case.
 
Campbell Ritchie
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
You will probably find the Bloch link amongst the links in this post. As far as I can remember, yes, Bloch says that using equals() on subclasses tends to breach the Liskov Substitution Principal
reply
    Bookmark Topic Watch Topic
  • New Topic