CODEWITHSUNDEEP
javasortingcomparisoncomparator
amp
amp

Reputation: 12352

Understand comparison method when sorting a collection

I have the following piece of code to sort a collection of Items that have a label property:

Collections.sort(myList, new Comparator<ListItem>() {
            @Override
            public int compare(ListItem lhs, ListItem rhs) {
                Crashlytics.log(Log.DEBUG, TAG, "lhs.getLabel(): " + lhs.getLabel() + " | rhs.getLabel(): " + rhs.getLabel());
                if (lhs.getLabel() == null || rhs.getLabel() == null) {
                    return 0;
                }
                return lhs.getLabel().compareTo(rhs.getLabel());
            }
        });

I have some crash reports with the following stacktrace:

Caused by java.lang.IllegalArgumentException: Comparison method violates its general contract!
       at java.util.TimSort.mergeLo(TimSort.java:777)
       at java.util.TimSort.mergeAt(TimSort.java:514)
       at java.util.TimSort.mergeForceCollapse(TimSort.java:457)
       at java.util.TimSort.sort(TimSort.java:254)
       at java.util.Arrays.sort(Arrays.java:1498)
       at java.util.ArrayList.sort(ArrayList.java:1470)
       at java.util.Collections.sort(Collections.java:201)
       at uk.co.aquanetix.activities.MyActivity.onCreate(MyActivity.java:59)
       at android.app.Activity.performCreate(Activity.java:7183)
       at android.app.Instrumentation.callActivityOnCreate(Instrumentation.java:1220)
       at android.app.ActivityThread.performLaunchActivity(ActivityThread.java:2910)
       at android.app.ActivityThread.handleLaunchActivity(ActivityThread.java:3032)
       at android.app.ActivityThread.-wrap11(Unknown Source)
       at android.app.ActivityThread$H.handleMessage(ActivityThread.java:1696)
       at android.os.Handler.dispatchMessage(Handler.java:105)
       at android.os.Looper.loop(Looper.java:164)
       at android.app.ActivityThread.main(ActivityThread.java:6944)
       at java.lang.reflect.Method.invoke(Method.java)
       at com.android.internal.os.Zygote$MethodAndArgsCaller.run(Zygote.java:327)
       at com.android.internal.os.ZygoteInit.main(ZygoteInit.java:1374)

I understand that this is related to the fact that the comparator method is not transitive, as explained here.

My problem is that I am not able to reproduce it. It only happens in some specific situation that I can't figure out.

As you can see, I am sending the label values to Crashlytics, so these are the values that were sent when the crash happened.

0 | 1545921010869 | D/MyActivity lhs.getLabel(): 14:49:22 | rhs.getLabel(): 13:21:22
1 | 1545921010870 | D/MyActivity lhs.getLabel(): 13:25:41 | rhs.getLabel(): 14:49:22
2 | 1545921010870 | D/MyActivity lhs.getLabel(): 13:25:41 | rhs.getLabel(): 14:49:22
3 | 1545921010870 | D/MyActivity lhs.getLabel(): 13:25:41 | rhs.getLabel(): 13:21:22
4 | 1545921010870 | D/MyActivity lhs.getLabel(): 14:53:26 | rhs.getLabel(): 13:25:41
5 | 1545921010870 | D/MyActivity lhs.getLabel(): 14:53:26 | rhs.getLabel(): 14:49:22
6 | 1545921010870 | D/MyActivity lhs.getLabel():  | rhs.getLabel(): 14:49:22
7 | 1545921010870 | D/MyActivity lhs.getLabel():  | rhs.getLabel(): 13:25:41

I built a list with those values (plus some items with empty strings) but no luck in reproducing it in my device/emulators.

My questions are:

Upvotes: 4

Views: 199

Answers (1)

Mureinik
Mureinik

Reputation: 311188

As you noted, this comparator isn't transitive. Consider three ListItems a, b and c with the labels "a", "b" and null, respectively. Using this comparator, compare(a, c) and compareTo(b, c) are both 0 since c.getLabel() is null, but compare(a, b) clearly isn't, thus breaking the rule of tansitivity.

To address this issue you can arbitrarily decide that ListItems with null labels will always go last (or first, for argument's sake. Just replace the 1s in the below code with -1s and vise-versa):

Collections.sort(myList, new Comparator<ListItem>() {
    @Override
    public int compare(ListItem lhs, ListItem rhs) {
        if (lhs.getLabel() == null) {
            if (rhs.getLabel() == null) {
                return 0;
            }
            return 1;
        }
        if (rhs.getLabel() == null) {
            return -1;
        }
        return lhs.getLabel().compareTo(rhs.getLabel());
    }
});

Note that if you're using Java 8 you can save a lot of this boilerplate code:

myList.sort(Comparator.comparing
            (ListItem::getLabel, Comparator.nullsLast(Comparator.naturalOrder())));

Upvotes: 5

Related Questions