Comparable !

[Frank Jacobsen]

I need to sort a List that contains objects that looks like this:

public class HistoriskViewbean implements Comparable {
String sortme;
}

I have many of this objects in a List....

I have to sort this list Asc and Dec by the String in the fastes way....

Do anyone have some good examples of sorting a list of objects ???


Frank

[KR Campbell]

Won't Collections.sort(List l) do this for you?

Ken

[Don Kiddick]

and for reverse order you could try

Collections.sort(list, Collections.revereOrder());

[Frank Jacobsen]

NO !

My class have other fields

public class HistoriskViewbean implements Comparable {
int date;
int date1;
String sortme;
String test;
}

Sorry my object looks like this, and i have to sort asc and dec on number 3 field that is a String....

Frank

[Peter den Haan]

java.util.Collections.sort(List) - will sort your objects by their natural sorting order.

java.util.Collections.sort(List, Comparator) - in case you want something other than the natural sorting order.

- Peter

[Anurag Mishra]

Hi Frank,

Please chk this I think I have done this,

the class you need to implement the comparable interface
and override method
public int compareTo(Object objToSort)


eg
public class testCLASS implements Comparable
{

public int compareTo(Object objToSort)
{


}


}

[KR Campbell]

Originally posted by Frank Jacobsen:
NO !

Frank

I think maybe 'YES !'. You are implementing Comparable, so use your compareTo method to compare the number three field. I believe that Collections.sort() should use this method to make the comparison.

Ken

[Anurag Mishra]

Hi Frank,

Please chk this I think I have done this,

the class you need to implement the comparable interface
and override method
public int compareTo(Object objToSort)
// in above method pass ur object and return integer values based on
value see the example // here sched_offset is value in ur object which is used to sorting......

eg
public class testCLASS implements Comparable
{

public int compareTo(Object objToSort)
{
testCLASS cmpValue = (testCLASS) objToSort;
if(cmpValue.sched_offset < sched_offset )
return 1;
else if(cmpValue.sched_offset > sched_offset)
return -1;
else
return 0;
}


}

[Jeroen Wenting]

You still need to implement Comparable for a meaningful comparison to happen though...

Comparable is indeed the method called by sort(), unless a Comparator is used.

Overriding compareTo is relatively easy but takes a bit of thought to determine what actually influences the sort order.
Which fields are relevant for example, and in what order?
Is there a need to possibly reverse the sortorder, or change the relevance of the fields?

Keep track of boundary conditions.
If a null is passed in, what do you do? Do you throw an Exception, or return something (and if so, what?).
If the object passed in is the wrong type, how do you handle it?

An implementation I created for one class (I've written dozens in the last few months, to go with a sorted List class I built for a webapp) runs like this:

public int compareTo(Object o)
{
if (o == null) return 1;
if (o.getClass() != this.getClass()) throw new UnsupportedOperationException("cannot compare to objects that are not of Class Constante");
if (((Constante)o).getKey().equals(this.getKey()))
return -((Constante)o).getValue().compareTo(this.getValue());
else
return -((Constante)o).getKey().compareTo(this.getKey());
}

key and value are both Strings in this case, but could be of any datatype (as long as they themselves implement compareTo of course).
Instead of an UnsupportedOperationException IllegalArgumentException might be a more logical choice to throw, I'm somewhat undecided on that.

null instances (if they exist) will using this method always appear smaller than any others.

[Peter den Haan]

Originally posted by Jeroen Wenting:

public int compareTo(Object o)
{
if (o == null) return 1;
if (o.getClass() != this.getClass()) 
throw new UnsupportedOperationException("cannot compare to objects that are not of Class Constante");
if (((Constante)o).getKey().equals(this.getKey()))
return -((Constante)o).getValue().compareTo(this.getValue());
else
return -((Constante)o).getKey().compareTo(this.getKey());
}

Hmmm. Best not use this as a general template.

This compareTo implementation does not correctly implement the compareTo() contract. Specifically, it fails on x.compareTo(y) must throw an exception iff y.compareTo(x) throws an exception if x or y are null. Like any contract violation, this will cause undefined behaviour in Collections.sort(), TreeSet, and so on; specifically, they may or may not throw NullPointerExceptions in the presence of null elements. If you want to get consistent behaviour for nulls, use a Comparator.

It also violates the contract by not throwing a ClassCastException if classes are mutually incompatible for comparison.

It does not honour The Liskov substitution principle in the sense that it will refuse to work as soon as you try to sort a non-homogeneous list with some subtypes thrown in.

It critically depends on compareTo() being consistent with equals() in the key, which is recommended and happens to be true for Strings, but if you're presenting this as a general compareTo template you should be aware that this is not necessarily the case.

Ok, that means I should stick my neck out and come up with something that I think works better, I guess

public int compareTo(Object that) {
   return compareTo((Constante)that);
}
public int compareTo(Constante that) {
   int cf = this.getKey().compareTo(that.getKey());
   if (cf == 0) {
      cf = this.getValue().compareTo(that.getValue());
   }
   return cf;
}

- Peter
[ June 04, 2004: Message edited by: Peter den Haan ]

[KR Campbell]

I have a question, then. This all seems rather complicated. Why can't he just wrap the compareTo() method of his String sortMe field?

public class HistoriskViewbean implements Comparable {
    int date;
    int date1;
    String sortme;  // Field Frank wants to sort on
    String test;
 
    public int compareTo(Object o1)
    {
        if(o1 instanceof HistoriskViewbean)
        {
            return sortme.compareTo(o1.sortme);
        }
        else
        {
            throw new ClassCastException();
        } 
    }
}
 

[Peter den Haan]

Originally posted by KR Campbell:
Why can't he just wrap the compareTo() method of his String sortMe field?

Oh, you most certainly can, and even simpler than you thought because the JVM will do the ClassCastException for you:

public int compareTo(Object that) {
   return compareTo((HistoriskViewbean)that);
}
public int compareTo(HistoriskViewbean that) {
   return this.sortme.compareTo(that.sortme);
}

Sorry, you'll have to forgive me my preference for covariant compareTo() and equals() methods; I find them easier on the eye and they may save you a couple of CPU cycles as well. If you need to sort in multiple ways, you're better off writing a Comparator:

public class SortmeComparator implements Comparator {
   public int compare(Object o1, Object o2) {
      return compare((HistoriskViewbean)o1, (HistoriskViewbean)o2);
   }
   public int compare(HistoriskViewbean hvb1, HistoriskViewbean hvb2) {
      return hvb1.getSortme().compareTo(hvb2.getSortme());
   }
   public boolean equals(Object obj) {
      return obj instanceof SortmeComparator; // all SortmeComparators are equal
   }
}

Now if "sortme" can be null things start to get a bit more elaborate. Keep in mind the contract for Comparator, specifically that sgn(compare(x, y)) == -sgn(compare(y, x)) even if x and/or y are null. I would not recommend coding this yourself; rather, use the Commons Collections ComparatorUtils. The nullHighComparator() and nullLowComparator() calls will decorate any existing Comparator that doesn't handle nulls to make it correctly handle null values. There's also a reversedComparator() in there

- Peter

[Stan James]

If you need to sort on a variety of keys, you can make a variety of comparators, or put a switch in your comparable. If it's Monday, sort on field1, Tuesday sort on field2, etc. I recently had one like this to sort on multiple fields:

int r = this.field1.compareTo(that.field1);
if (r==0)
    r = this.field2.compareTo(that.field2);
if (r==0)
    r = this.field3.compareTo(that.field3);
return r;

BTW: Somebody mentioned supporting Liskov Substitution by comparing to subtypes. In general, it's pretty hard to make hashcode(), equals() and compareTo() behave consistently between any two different types in a way that makes any sense. (You really oughtta do all three if you're going to do any of them.) I doubt I'd try it.

[Peter den Haan]

Originally posted by Stan James:
[...] I recently had one like this to sort on multiple fields: [...]

If it gets out of hand, the Commons Collections (see reference above) has some neat utility classes to chain comparators like this.

BTW: Somebody mentioned supporting Liskov Substitution by comparing to subtypes. In general, it's pretty hard to make [...] compareTo() behave consistently between any two different types in a way that makes any sense. [...] I doubt I'd try it.

Really? I regularly find reason to do this. For example, in my current project there's a Message type that's Comparable (there are Comparators for different sorting orders as well). There are a number of different Message subtypes, but the subtype doesn't really affect the way the messages are sorted. It was not hard to make this behave consistently, to the contrary: there's a straightforward implementation of compareTo in Message which works regardless of the subtype.

If my comparators looked like the one shown by Jeroen above, I'd be stuck - I wouldn't be able to sort a heterogeneous list of Messages.

- Peter

PS. In case you wondered, Message also implements a consistent equals() and hashCode().
[ June 04, 2004: Message edited by: Peter den Haan ]

[Stan James]

Your example of sorting unlike things sounds pretty reasonable at first blush. But you could run into unpredictable results if compareTo says two objects are equal while hashcode or equals does not. I might be tempted to have unlike classes have a common comparable attribute. So

Apple.compareTo(Orange)

should throw some unlike classes exception, but

Apple.getWeight().compareTo(Orange.getWeight())

would work. You'd have to write your own comparator to get collections to sort them.

Would Apple.compareTo(Orange) == 0 ever be a good thing? Could it be a very bad thing, say causing a collection to replace one with the other instead of adding the new one?

[Peter den Haan]

Originally posted by Stan James:
Your example of sorting unlike things sounds pretty reasonable at first blush. But you could run into unpredictable results if compareTo says two objects are equal while hashcode or equals does not.

Ah, now I see where our understanding is diverging.

I am not suggesting sorting unlike things. The very fact that the things to sort have a common supertype tells you that they are not "unlike". In the messages example, you will typically be sorting on priority, date sent, that kind of stuff; aspects in which all messages are one of a kind. Or, taking your example, if Apple and Orange are both subtypes of Fruit and Fruit has a weight property, it makes perfect sense to create a Comparator that compares any Fruit based on weight. Nothing ambiguous, difficult, obscure or unpredictable about it. It's something you could easily do in the real world, so no surprise that it makes sense in the object world too.

Notice the pattern here. We're sorting Messages by date sent. We're comparing Fruit on weight. The comparison is based on attributes of (or available to) the common supertype. This is why there is no ambiguity and no problem. And this is exactly where the Liskov substitution principle kicks in: if I have a perfectly fine Comparator for Fruit, then it's still a perfectly fine comparator for Fruit even with the odd Apple and Orange subtype thrown in, provided I did my job right and these subclasses do behave themselves like proper Fruit.

So far, I've been skirting the issue a little bit by talking about Comparators rather than natural sorting, i.e. Comparables. You might point out that if I create a natural sorting order of Fruit based on just weight, a 250g apple is equal to a 250g orange. True. But that is beside the point. Even if we're comparing like for like we still have the same problem. A 250g apple is not equal to a 250g apple; they are two apples that happen to weigh the same. We need more information to get a consistent sense of identity. If you can do that for Apple, you can do that for Fruit as well. Identity can be defined in (or available to) the common supertype.

You do not get unpredictable results if compareTo is inconsistent with equals/hashCode. You get results that might confuse an unwary developer, which is why this is not recommended for the natural sorting order, but they are perfectly well-defined. For example, a HashSet will get different ideas about which objects are identical than a TreeSet if compareTo() is not consistent with equals() - it's all detailed in the javadoc. But all of this is a total red herring. As argued in the previous point there is no a priori reason why compareTo() should be inconsistent with equals() simply because your collection is heterogeneous.

After this I probably owe you a real-world use case. I'll go back to the Message example. The Messages in our system are stored in a database and have a synthetic primary key (a Long id). A single id sequence is used for all message types. Equality and hash code are both based on the id; the natural sorting order for Message is by date sent (most significant) and id (least significant). There are half a dozen message subtypes. Identity and order are mutually consistent and make sense both in the real world and in the object model. The presence of subtypes does not confuse the matter at all and is actually irrelevant.

Hope this helps,

- Peter
[ June 05, 2004: Message edited by: Peter den Haan ]

[Stan James]

I think I'll stick to my guns on this one. If onePoundApple.equals(onePoundOrange) things are just not right in the world. It's very tempting to cheat on compareTo() just for sorting by weight and say I'll never compare Apples to Oranges, but it makes Apple and Orange a very long debugging session waiting to happen in the next release.

I'd make a special single-use comparator that compares weights with an explicit name like FruitWeightComparator. Then on another day I can sort by freshness, color, orchard of origin, etc.

BTW: You started with compareTo() and I wound up with equals(), but for safety if a.compareTo(b) == 0 then a.equals(b) had better be true.

[Peter den Haan]

Originally posted by Stan James:
I think I'll stick to my guns on this one. If onePoundApple.equals(onePoundOrange) things are just not right in the world. [...] It's very tempting to cheat on compareTo() just for sorting by weight and say I'll never compare Apples to Oranges, but it makes Apple and Orange a very long debugging session waiting to happen in the next release.

I really don't think we disagree on that one Stan... or that I ever suggested it.

- Peter

[Stan James]

But we mentioned consistent equals, compareto and hashcode at the beginning. a.compareTo(b)==0 means a.equals(b)==true means a.hashcode==b.hashcode. My whole point was not to do one without the others. I'd suggest compareTo should fail if this and the argument object are not exactly the same class. instanceof and casting are not even sufficient with that rule.

[KR Campbell]

I hesitate to step back into such an erudite discussion ( which has been very interesting ) but where does this leave me if I want to compare a set of cars based on their top speed? Should compare(aNissanPrimera,anAudiA3) return something other than 0 if their top speeds match? The one is not equal to the other by normal definitions but where you are only interested in a particular aspect of a class might it not be permissible to loosen the restriction? The general contract does allow for this even though it does not recommend it.

Regards,
Ken

[Peter den Haan]

Originally posted by Stan James:
[...] I'd suggest compareTo should fail if this and the argument object are not exactly the same class. instanceof and casting are not even sufficient with that rule.

But Stan, you can't simply deny reality. I gave you a real life example of a class hierarchy that implements a natural order across different sub types, in a completely consistent fashion with equals() and hashCode(). Please point out where it doesn't satisfy the contracts, or where it doesn't make sense.

- Peter

[Peter den Haan]

Originally posted by KR Campbell:
[...] where does this leave me if I want to compare a set of cars based on their top speed? [...]

This would be dangerous to use as the natural sorting order because of the inconsistency with equals(). With Comparators, an inconsistency with equals() tends to cause much less confusion, although you should still be wary against using Comparator like that to construct, say, a TreeSet. Your example is about Comparators, so there is basically no problem for the cautious developer

If you would like consistency with equals(), then you can pull more information into the comparison, for example top speed, marque and model (in that order) until compare() is consistent with equals().

That would even allow you to make it the natural sorting order (ie Comparable). But usually the natural order is something that is inherent to the things you're modeling. Top speed does not sound like a very strong choice there, although it depends a little on the problem your system is solving.

- Peter
[ June 09, 2004: Message edited by: Peter den Haan ]

[Stan James]

I'm perfectly happy with a special purpose comparator to compare top speeds. It can compare cars, motorcycles, aircraft, animals, etc. that may or may not even be in a common class hierarchy, tho it will certainly be easier if they all implement one interface that lets you query speed.

It seems dangerous to have two objects compare as equal unless all their attributes match. If message1.equals(message2) because they have the same base class and the same timestamp, but one says "He is now here" and the other says "He is nowhere" it could be catastrophic to get the wrong one out of a collection at some point. This has been a long thread and I could easily have missed something important about your message processing, but I'd want to make sure that equals, compareto and hashcode take all significant attributes into account.

[Peter den Haan]

Originally posted by Stan James:
[...] It seems dangerous to have two objects compare as equal unless all their attributes match. [...]

That's an enlightening remark, and I think this assumption is underneath much of the discussion above. Two remarks.

The concept of equality generally depends on the problem domain. Let's say I have a Person, with an attribute "weight". I have a Person instance representing Stan James. Should Person(Stan James at 70kg).equals(Person(Stan James at 75kg))? It might or might not, depending entirely on the chunk of reality your objects represent.

There may be multiple concepts of equality popping up in your problem or your system, and only one of them can be implemented directly in your equals() methods. For example, in any RDBMS-based system, the database introduces a form of equality: the primary key. If it is a synthetic primary key, it's totally disconnected from any equality concepts in your problem domain. Still, it can make a lot of sense to have your objects' equals() method simply use the primary key.

In neither case, equality implies that "all their attributes match." Yet I would argue that there's nothing deeply wrong with that.

- Peter