JAVA_Runtime_Error :- Comparison method violates its general contract

Question

I am getting this error while I'm trying to sort the arraylist of nodes.I've tried most of the solutions, but none of them worked in my case.

java.lang.IllegalArgumentException: Comparison method violates its general contract!
at java.util.ComparableTimSort.mergeHi(ComparableTimSort.java:866)
at java.util.ComparableTimSort.mergeAt(ComparableTimSort.java:483)
at java.util.ComparableTimSort.mergeCollapse(ComparableTimSort.java:406)
at java.util.ComparableTimSort.sort(ComparableTimSort.java:213)
at java.util.Arrays.sort(Arrays.java:1312)
at java.util.Arrays.sort(Arrays.java:1506)
at java.util.ArrayList.sort(ArrayList.java:1454)
at j...

Code for this is

static class Node implements Comparable<Node>
{
    int key;
    int value;
    int double_value;

    public Node(int key , int value , int double_value)
    {
        this.key = key;
        this.value = value;
        this.double_value = double_value;
    }

    public int compareTo(Node node)
    {
        if(double_value < node.double_value)
            return 1;
        else if(double_value > node.double_value)
            return -1;

        return -1;
    }
}

It works for small inputs, but when the the number of inputs are large it gives this error. I've also read about the Transitivity rule in comparison method, but I can't figure out how it is applied in this case.

Thanks in advance.

You return -1 if two nodes have equal values, which means that a node can be simultaneously less than and greater than some other node, depending on in which order you compare. This indeed violates contract of `Comparable.compareTo` (and common sense is violated as well, for that matter). For simple case of comparing doubles, prefer `Double.compare` method instead. — M. Prokhorov, May 23 '17 at 18:07
Your `compareTo` never returns `0` to indicate they are the same, and you should also override `equals()` so two Nodes holding the same double_value `n1.equals(n2)` returns true. When you override equals you should also override `hashcode()` — Stephen P, May 23 '17 at 18:09
No underscores please! Follow the Java Naming Convention and replace `double_value` by `doubleValue`. — MC Emperor, May 23 '17 at 19:11
Identifiers should represent purpose and role, not (incorrectly) the implementation, and should be spelled according to the Java naming conventions. — Lew Bloch, May 23 '17 at 19:11

Stephen P · Accepted Answer · 2017-05-23T23:25:00.453

Since you are actually comparing int values (despite it being named double_value) you can have a very simple compareTo method

public int compareTo(Node node)
{
    return this.double_value - node.double_value;
}

You don't have to return -1, 0, or +1 — any negative or positive value will do.
The documentation for compareTo() says:

Compares this object with the specified object for order. Returns a negative integer, zero, or a positive integer as this object is less than, equal to, or greater than the specified object.

So

Node node1 = new Node(5, 5, 5);
Node node2 = new Node(7, 7, 7);
System.out.println( node1.compareTo(node2) );

will produce -2 because 5 is less than 7.

When you override compareTo you should also override .equals(Node other), and when you override equals you should also override hashCode().

Update for better safety per Chris Parker's comment, this goes back to using -1, 0, 1 for the results:

public int compareTo(Node other)
{
    final long m = (long) this.double_value = (long) other.double_value;
    return m < 0 ? -1 :
           m > 0 ?  1 :
           0;
}

Be cautious using subtraction for your comparison. Depending upon the numbers contained, you can exceed the value of a signed 32 bit integer, and overflow will cause an invalid return. — Chris Parker, May 23 '17 at 19:51
That is true @Chris ... you could end up with `Integer.MIN_VALUE - Integer.MAX_VALUE` which comes out incorrectly as `1`. You can cast to widen, like `long m = (long)a - (long)b;` to make it safer. — Stephen P, May 23 '17 at 23:20

JAVA_Runtime_Error :- Comparison method violates its general contract

1 Answers1