Sorting with respect to other items - Comparison method violates its general contract

Question

I'm tyring to sort an array of items in which an item should be brought to the beginning of the array if its id equals the id of a selected item (also belonging to the array). The sorting order of the rest of the elements is their distance from a given location.

I'm experiencing the dreaded java.lang.IllegalArgumentException: Comparison method violates its general contract! exception in my custom comparator, implemented like this:

Location location = ...; // may be null
Item selectedItem = ...; // may be null or an element of the array to be sorted

private final Comparator<Item> comparator = new Comparator<Item>() {
    @Override
    public int compare(Item p1, Item p2) {
        // if p1 is the currently selected item, bring p1 to the top
        // if p2 is the currently selected item, bring p2 to the top
        // else sort p1 and p2 by their distance from location
        if (selectedItem != null) {
            if (selectedItem.getId() == p1.getId()) { //id's are int and unique in the array
                return -1;
            } else if (selectedItem.getId() == p2.getId()) {
                return 1;
            }
        }

        if (location != null) { //location is an Android Location class instance
            Float distance1 = location.distanceTo(p1.getLocation());
            Float distance2 = location.distanceTo(p2.getLocation());
            return distance1.compareTo(distance2);
        } else {
            return 0;
        }
    }
};

I don't have an exact sequence to replicate the issue, but all observations of the error so far happen when selectedItem and location are not null (they may be both null).

Any hints?

Thanks

Are the IDs guaranteed unique or is it possible there is more than one Item with the same ID that is the same as selected ID? The whole thing is badly broken in that case. — Affe, May 15 '13 at 20:46
Please clarify. First you say that an item can have the same id as the selected item, also belonging to the array. Then you say that IDs are unique in the array. This is contradictory. — JB Nizet, May 15 '13 at 21:45
The array contains items with unique ids, e.g. 0 to 100. The selectedItem is an item extracted from that array, so that array[i] == selectedItem (object identity), and so also array[i].getId() == selectedItem.getId() (int equality). The goal is: if selectedItem is not null, produce a sorted array with the array item whose id is equal to selectedItem's, placed at the beginning. Otherwise, if selectedItem is null, sort array by distance. — Venator85, May 15 '13 at 21:59

score 1 · Accepted Answer · answered May 15 '13 at 20:37

1

I believe your issue is in the fact that, when equal to selectedItem, you do not return 0 when the two elements being compared are equal. In this way, comparing x to y will say x is greater, but comparing y to x says y is greater (assuming x and y are both equal to selectedItem). This can't be.

if (p1.getId() == p2.getId()) return 0;

answered May 15 '13 at 20:37

James Montagne

77,516
14
110
130

In this case, the comparison on distance will be performed, so this scenario should be correctly handled, right? – Venator85 May 15 '13 at 21:31
@Venator85 No. If `x = y = selectedItem` then `compare(x,y)` returns -1 and `compare(y,x)` returns 1. – James Montagne May 16 '13 at 01:08

score 0 · Answer 2 · edited May 23 '17 at 10:25

I think there's a hint to be found in the answer to this question: https://stackoverflow.com/a/8327575/338479

There are rules (the "contract") for comparators. One is that an object always compare equal to itself (compare() returns 0). Another is that if A>B and B>C, then A>C. Another is that B>A return the opposite result from A>B.

I'm not seeing any obvious violation to these rules in your comparator, but I'm not privy to the inner workings of your other code. Are there cases where your distanceTo() method could be violating the rules of this contract?

Is there any chance that location or selectedItem could be changing in the middle of the sort?

I don't think so. distanceTo() is a method of Android's Location class, and just calculates the distance in meters between two locations. Also, the entire sorting logic is always executed in the main thread. — Venator85, May 15 '13 at 22:06

Sorting with respect to other items - Comparison method violates its general contract

2 Answers2