Thursday, December 11, 2008

How not to implement Comparable

I have already blogged about the danger of numeric overflows. I recently came across this example in Java course materials (!!!):

public class Foo implements Comparable<Foo> {
private int number;
public int compareTo(Foo o) {
if (this == o) return 0;
return number - o.number;
}
}
How do you think Integer.MAX_VALUE compares to negative numbers? It will appear smaller. This reminds me of even worse case we encountered in a real codebase. Look at this:
public class Foo implements Comparable<Foo> {
private long id;
//...
public int compareTo(Foo o) {
if (this == o) return 0;
return (int)(id - o.id);
}
public boolean equals(Object o) {
return o != null && (o instanceOf Foo) && compareTo((Foo)o) == 0;
}
}
How do you think new Foo(8325671243L) and new Foo(25505540427L) compare? They are equal, but I will do it ala Weiqi Gao and leave you to find out why... :-)

4 comments:

Unknown said...

Very nice. Because of things like that I prefer explicit if()'s. (I will not say more than that to keep the riddle alive...)

Two other points:

(1) I guess you meant (o instanceof Foo), right?
(2) On top of the compareTo() issue, an equals() that requires only subclassing (rather than the stronger requirement of "exactly the same class") is likely to cause problem if overridden in subclasses.

Yardena said...

Hi Itay - you are right on both counts, thanks :-)
Yep, Better to stay with -1, 0, and 1, and to rely on logic rather than math.

Anonymous said...

a/2 - b/2 + (a&1) * (1 - 2*(a>>31)) - (b&1) * (1 - 2*(b>>31))
I wonder, if it actually works. Yes, I'm a nerd.

kirillkh said...

Haha, I've just realized this is the same as a/2 - b/2 + a%2 - b%2.
And no, it doesn't work. On the positive side, now I know, how mod is implemented.