Why is my simple comparator broken?

Question

I have a class, which I have simplified to this:

final class Thing {
    private final int value;
    public Thing(int value) {
        this.value = value;
    }
    public int getValue() {
        return value;
    }
    @Override public String toString() {
        return Integer.toString(value);
    }
}

I want to sort an array of this thing. So I have created a simple copmarator:

private static final Comparator<Thing> reverse = new Comparator<Thing>() {
    public int compare(Thing a, Thing b) {
        return a.getValue() - b.getValue();
    }
};

I then use the two argument form of Arrays.sort.

This works fine for my test cases, but sometimes it goes all wrong with the array ending up in a strange but repeatable order. How can this be?

score 20 · Accepted Answer · answered Mar 03 '09 at 23:44

Integer overflow… or more precisely, underflow.

Instead, do an explicit comparison:

private static final Comparator<Thing> reverse = new Comparator<Thing>() {
    public int compare(Thing a, Thing b) {
      int av = a.getValue(), bv = b.getValue();
      return (av == bv) ? 0 : ((av < bv) ? -1 : +1);
    }
};

Using subtraction is fine if you are sure that the difference won't "wrap around". For example, when the values in question are constrained to be non-negative.

score 15 · Answer 2 · answered Mar 03 '09 at 23:43

15

You cannot use minus to create the comparison. You'll overflow when the absolute difference exceeds Integer.MAX_VALUE.

Instead, use this algorithm:

int compareInts( int x, int y ) {
  if ( x < y ) return -1;
  if ( x > y ) return 1;
  return 0;
}

I like to have this function in a library for such purposes.

answered Mar 03 '09 at 23:43

Jason Cohen

81,399
26
107
114

For a moment I was going to point you to the static method in Integer. But it isn't there... – Tom Hawtin - tackline Mar 03 '09 at 23:55
2

@Tom: `Integer.valueOf(x).compareTo(y);` is the most succinct way I can think of. Strange how Double has the static `compare()` method and the other number types don't. – Grundlefleck Feb 24 '10 at 09:29
2

@Grundlefleck: True! But of course my method is much faster to execute because it doesn't create a new `Integer` instance. – Jason Cohen Feb 28 '10 at 15:15

score 5 · Answer 3 · answered Mar 04 '09 at 07:08

5

try

System.out.println(Integer.MAX_Value - Integer.MIN_VALUE);

This needs to return a positive number as MAX_VALUE > MIN_VALUE but instead prints -1

answered Mar 04 '09 at 07:08

Peter Lawrey

525,659
79
751
1,130

score 5 · Answer 4 · answered Mar 04 '09 at 07:59

5

When comparing Java primitives, it is advisable to convert them to their Object counterparts and rely on their compareTo() methods.

In this case you can do:

return Integer.valueOf(a.getValue()).compareTo(b.getValue())

When in doubt, use a well-tested library.

answered Mar 04 '09 at 07:59

mustpax

1,408
13
20

4

Bit of an overhead there (for non-small values). – Tom Hawtin - tackline Mar 04 '09 at 13:58

score 3 · Answer 5 · answered Mar 03 '09 at 23:44

3

What kind of numbers do you throw in there? If your numbers are large enough, you could wrap through the MIN/MAX values for integers and end up in a mess.

answered Mar 03 '09 at 23:44

Uri

88,451
51
221
321

score 2 · Answer 6 · answered Mar 03 '09 at 23:47

2

If a's value is very negative and b's value is very positive your answer will be very wrong.

IIRC, Int overflow silently wraps around in the JVM

-- MarkusQ

answered Mar 03 '09 at 23:47

MarkusQ

21,814
3
56
68

Why is my simple comparator broken?

6 Answers6

Linked