why Comparator throws exception?

Question

I got an exception

java.lang.IllegalArgumentException: Comparison method violates its general contract!
at java.util.TimSort.mergeHi(TimSort.java:868)
at java.util.TimSort.mergeAt(TimSort.java:485)
at java.util.TimSort.mergeCollapse(TimSort.java:408)
at java.util.TimSort.sort(TimSort.java:214)
at java.util.TimSort.sort(TimSort.java:173)
at java.util.Arrays.sort(Arrays.java:659)
at Main.main(Main.java:64)

when using this code :

Arrays.sort(arr, new Comparator<Integer[]>(){  //arr is 2D array
        public int compare(Integer[] o1, Integer[] o2){
            return o1[2]==o2[2]?0:o1[2]>o2[2]?1:-1;
        }
    });

which I believe is related to not satisfying transitivity of comparison, but when I made a little change like this :

Arrays.sort(arr, new Comparator<Integer[]>(){  //arr is 2D array
        public int compare(Integer[] o1, Integer[] o2){
            return o1[2].compareTo(o2[2]); // here is the change
        }
    });

the exception is no longer generated. I can't understand an explanation of this issue as I'm sure that the Integer instance can be compared using relational operators (>, <, =) besides compareTo() method

Integer x = 1;
Integer y = 2;
System.out.println(x<y);

prints true as expected

can any body clarify ?

http://stackoverflow.com/questions/8327514/comparison-method-violates-its-general-contract — Petter Friberg, Feb 01 '16 at 21:57
`Integer` instances *are not* compared using relational operators. There is an implicit unboxing which occurs first. — Andy Turner, Feb 01 '16 at 21:58
What are the contents of your arrays? Are there any values outside of the [Integer cache range](https://docs.oracle.com/javase/8/docs/api/java/lang/Integer.html#valueOf-int-)? — rgettman, Feb 01 '16 at 22:00

Andy Turner · Accepted Answer · 2016-02-01T22:08:43.583

The problem is with:

o1[2]==o2[2]

This is comparing the Integers for identity. Equal instances are not necessarily identical. For example:

Integer a = new Integer(128);
Integer b = new Integer(128);
System.out.println(a == b);      // False, instances are not identical.
System.out.println(a.equals(b)); // True, instances are equal.

It should be:

o1[2].equals(o2[2])

Or, to handle o1[2] being null:

Objects.equal(o1[2], o2[2])

score 1 · Answer 2 · answered Feb 01 '16 at 22:00

1

since you are using Integer and not int, this is not valid:

o1[2]==o2[2]?0:o1[2]>o2[2]?1:-1;

you need to use equals or compareTo, not ==

answered Feb 01 '16 at 22:00

Nir Levy

12,750
3
21
38

score 0 · Answer 3 · answered Feb 01 '16 at 22:13

The array you are sorting is made up of Integer objects. These are different than just plain old integers.

A plain old integer is just a number sitting in memory.

An Integer object is a an instance of a class that fills the same role as a basic integer, but also has a bunch of methods and data associated with it. That's the difference between being a piece of data or being an object.

The == operator compares numbers in memory. In the case of an instance of an object, it will compare the locations in memory, not the values of the numbers as you intend.

For Integer (and other number-like) objects, you must use the compareTo() method instead.

Your solution here is to either use the compareTo() method as suggested, or change your array to plain old integers.

You could also leave it as Integer objects and then use the Integer.intValue() to get a plain old integer returned, and then you can use the == comparison. But that's quite convoluted, IMO.

why Comparator throws exception?

3 Answers3