Comparison method violates its general contract while comparing java.util.Date

Question

I am getting error below:

Caused by: javax.faces.el.EvaluationException: java.lang.IllegalArgumentException: Comparison method violates its general contract!
    at javax.faces.component.MethodBindingMethodExpressionAdapter.invoke(MethodBindingMethodExpressionAdapter.java:101) [jboss-jsf-api_2.1_spec-2.1.28.SP1-redhat-1.jar:2.1.28.SP1-redhat-1]
    at com.sun.faces.application.ActionListenerImpl.processAction(ActionListenerImpl.java:101) [jsf-impl-2.1.28.redhat-10.jar:2.1.28.redhat-10]
    at javax.faces.component.UICommand.broadcast(UICommand.java:315) [jboss-jsf-api_2.1_spec-2.1.28.SP1-redhat-1.jar:2.1.28.SP1-redhat-1]
    at javax.faces.component.UIViewRoot.broadcastEvents(UIViewRoot.java:786) [jboss-jsf-api_2.1_spec-2.1.28.SP1-redhat-1.jar:2.1.28.SP1-redhat-1]
    at javax.faces.component.UIViewRoot.processApplication(UIViewRoot.java:1251) [jboss-jsf-api_2.1_spec-2.1.28.SP1-redhat-1.jar:2.1.28.SP1-redhat-1]
    at com.sun.faces.lifecycle.InvokeApplicationPhase.execute(InvokeApplicationPhase.java:81) [jsf-impl-2.1.28.redhat-10.jar:2.1.28.redhat-10]
    at com.sun.faces.lifecycle.Phase.doPhase(Phase.java:101) [jsf-impl-2.1.28.redhat-10.jar:2.1.28.redhat-10]
    at com.sun.faces.lifecycle.LifecycleImpl.execute(LifecycleImpl.java:118) [jsf-impl-2.1.28.redhat-10.jar:2.1.28.redhat-10]
    at javax.faces.webapp.FacesServlet.service(FacesServlet.java:593) [jboss-jsf-api_2.1_spec-2.1.28.SP1-redhat-1.jar:2.1.28.SP1-redhat-1]
    ... 29 more
Caused by: java.lang.IllegalArgumentException: Comparison method violates its general contract!
    at java.util.TimSort.mergeHi(TimSort.java:899) [rt.jar:1.8.0_65]
    at java.util.TimSort.mergeAt(TimSort.java:516) [rt.jar:1.8.0_65]
    at java.util.TimSort.mergeForceCollapse(TimSort.java:457) [rt.jar:1.8.0_65]
    at java.util.TimSort.sort(TimSort.java:254) [rt.jar:1.8.0_65]
    at java.util.Arrays.sort(Arrays.java:1512) [rt.jar:1.8.0_65]
    at java.util.ArrayList.sort(ArrayList.java:1454) [rt.jar:1.8.0_65]
    at java.util.Collections.sort(Collections.java:175) [rt.jar:1.8.0_65]

Below is my code for compare method. vo1.getAttribute() returns java.util.Date Object.

    @Override
    public int compare(DateComparableVO vo1, DateComparableVO vo2) {
        if (vo1 != null && vo1.getAttribute() != null && vo2 != null && vo2.getAttribute() != null) {
            return vo1.getAttribute().compareTo(vo2.getAttribute());
        }
        return -1;
    }

Is there anything wrong with my implementation of compare method?

In case of null scenario.

Why below code works without any issue.

package test;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Date;
import java.util.List;

public class TestMain {

    public static void main(String[] args) {
        List<Employee> employees = new ArrayList<Employee>();
        employees.add(new Employee(new Date()));
        employees.add(null);
        employees.add(new Employee(new Date()));
        employees.add(new Employee(new Date()));
        employees.add(null);
        employees.add(new Employee(new Date()));
        employees.add(null);
        System.out.println(employees.size());
        Collections.sort(employees, new EmployeeComparator());

    }

}

class Employee {


    private Date attribute;

    public Employee() {
        // TODO Auto-generated constructor stub
    }

    public Employee(Date attribute) {
        this.attribute = attribute;
    }


    public Date getAttribute() {
        return attribute;
    }

    public void setAttribute(Date attribute) {
        this.attribute = attribute;
    }

    @Override
    public String toString() {
        return "Employee [attribute=" + attribute + "]";
    }
}

class EmployeeComparator implements Comparator<Employee>{

    @Override
    public int compare(Employee vo1, Employee vo2) {
        System.out.println("VO1 : " + vo1 + " VO2 : " + vo2);

        if (vo1 != null && vo1.getAttribute() != null && vo2 != null && vo2.getAttribute() != null) {
            return vo1.getAttribute().compareTo(vo2.getAttribute());
        }
        return -1;
    }

}

Output

7
VO1 : null VO2 : Employee [attribute=Fri Aug 18 11:51:11 SGT 2017]
VO1 : Employee [attribute=Fri Aug 18 11:51:11 SGT 2017] VO2 : null
VO1 : Employee [attribute=Fri Aug 18 11:51:11 SGT 2017] VO2 : Employee [attribute=Fri Aug 18 11:51:11 SGT 2017]
VO1 : Employee [attribute=Fri Aug 18 11:51:11 SGT 2017] VO2 : null
VO1 : Employee [attribute=Fri Aug 18 11:51:11 SGT 2017] VO2 : Employee [attribute=Fri Aug 18 11:51:11 SGT 2017]
VO1 : null VO2 : null
VO1 : null VO2 : Employee [attribute=Fri Aug 18 11:51:11 SGT 2017]
VO1 : null VO2 : Employee [attribute=Fri Aug 18 11:51:11 SGT 2017]
VO1 : Employee [attribute=Fri Aug 18 11:51:11 SGT 2017] VO2 : Employee [attribute=Fri Aug 18 11:51:11 SGT 2017]
VO1 : Employee [attribute=Fri Aug 18 11:51:11 SGT 2017] VO2 : Employee [attribute=Fri Aug 18 11:51:11 SGT 2017]
VO1 : null VO2 : null
VO1 : null VO2 : Employee [attribute=Fri Aug 18 11:51:11 SGT 2017]
VO1 : null VO2 : null

Am I missing some important part in understanding compare

ajb · Accepted Answer · 2017-08-18T04:45:14.157

The "contract" for comparison is that the comparison function has to define a total order. One of the requirements of a total order is "asymmetry", which basically means that if a < b, then b > a. In Java terms, this means that if compare(a,b) (or a.compareTo(b)) returns a result < 0, then compare(b,a) (or b.compareTo(a)) must return a result > 0. Your comparison function doesn't obey this rule; if x.getAttribute() is non-null and y.getAttribute() is null, then compare(x,y) returns -1 and compare(y,x) also returns -1. TimSort sometimes notices this and throws an exception when it spots a comparison that doesn't return what it expects.

Another way to look at it: you have to decide beforehand what order you want things to be in if there are "special" values in the input (except that if you want objects to be compare as "equal", the order doesn't matter). Suppose your input contains objects whose getAttribute() is null, and objects whose getAttribute() is non-null. Where do you want the ones with the null attribute to appear in the output? How do you want them to be ordered? "I don't care" is not an option. Let's say you want all the null-attribute ones to come last, but you don't care about how the null-attribute objects are ordered. Then you need to write your comparison function so that

an object with a non-null attribute < an object with a null attribute;
an object with a null attribute > an object with a non-null attribute;
two object with null attributes are treated as equal (comparison function returns 0).

If you want the null ones to appear first in the array, then the < and > in the first two points would be reversed. If you want two objects with null attributes to be ordered based on some other attribute, then write your comparison function so that it does that, but you'll still need to decide where the ones with the null attribute appear relative to the ones with the non-null attribute. Maybe it doesn't matter which one you choose. But you have to choose something, and you have to write your comparison function to return the result based on what you've chosen.

P.S.: There's no particular reason why your second code snippet with Employee works and the first one doesn't. Your comparator in the second case is just as wrong as in the first one. However, TimSort doesn't look at every pair of elements to make sure the comparison meets the contract (that would make it an O(n²) algorithm). I'm not familiar with the details of TimSort, but I suspect that it only makes this check when it has a reason to compare two elements to see if the comparison is (perhaps) <0 or =0, and it "knows" that >0 should not be possible if the comparison function meets the contract. It's pretty cheap to check the result for >0 if it already has to make the comparison, but I doubt that TimSort calls comparators when it doesn't have to, since the execution time of a comparator is beyond its control. So the basic reason your second example works is "you got lucky".

score 6 · Answer 2 · answered Aug 18 '17 at 03:42

The blind -1 at the end means that null values aren't handled stably (and that breaks the merge sort algorithm). You could do something like

@Override
public int compare(DateComparableVO vo1, DateComparableVO vo2) {
    Date l = null, r = null;
    if (vo1 != null) {
        l = vo1.getAttribute();
    }
    if (vo2 != null) {
        r = vo2.getAttribute();
    }
    if (l == null && r == null) {
        return 0;
    } else if (l == null) {
        return -1;
    } else if (r == null) {
        return 1;
    }
    return l.compareTo(r);
}

score 3 · Answer 3 · answered Aug 18 '17 at 12:23

In addition to what the other answers have already pointed out, an alternative way to implement such a Comparator in java 8 is to compose it using the static factory methods, e.g:

Comparator<DateComparableVO> c = Comparator.nullsLast(
    Comparator.comparing(DateComparableVO::getAttribute,
        Comparator.nullsLast(Date::compareTo)));

or nullsFirst, depending on how you wish to treat null values. Whether this is more readable may be a matter of discussion, but it is self-documenting what the intended behavior regarding null values is.

If you know that there cannot be any null values, neither for the objects themselves nor for the attributes, this can be reduced to

Comparator<DateComparableVO> c = Comparator.comparing(DateComparableVO::getAttribute);

which will throw a NullPointerException when it does encounter a null value.

Comparison method violates its general contract while comparing java.util.Date

3 Answers3