CODEWITHSUNDEEP
javasortingcollectionscomparator
math_law
math_law

Reputation: 391

Java Collections sort: DEBUG/VERBOSE the RootCause of "Comparison method violates its general contract:" errors

There are definately numerous examples of Collections.sort problems which can not be solved easily with self investigation or DEBUGGING. Is there a way to DEBUG and verbose, which 3 objects / comparions are causing the following error ? Namely MyObject1, MyObject2 and MyObject3. How can we debug them without getting help from google/stackoverflow ? 

java.lang.IllegalArgumentException: Comparison method violates its general contract!
        at java.util.TimSort.mergeHi(TimSort.java:895)
        at java.util.TimSort.mergeAt(TimSort.java:512)
        at java.util.TimSort.mergeCollapse(TimSort.java:435)
        at java.util.TimSort.sort(TimSort.java:241)
        at java.util.Arrays.sort(Arrays.java:1512)
        at java.util.ArrayList.sort(ArrayList.java:1454)
        at java.util.Collections.sort(Collections.java:175)

Here is my code hitting this

Collections.sort(sorted, new Comparator<MyObject>() {
    @Override
    public int compare(MyObject m1, MyObject m2) {
        // Actual energy comparison :-
        // THE higher the energy, the earlier in the list
        float delta = m1.getTotalEnergy() - m2.getTotalEnergy();

        if (delta > 0) {
            return 1;
        } else if (delta < 0) {
            return -1;
        } else {
            return 0;
        }
    }
});

Again, I would like to see all the Objects involved in this violation. MyObject1,2 and 3. I am not asking what is wrong in the above code. I already asked and get answered of it Java Collections sort: Comparison method violates its general contract Here I am asking how can I DEBUG/MONITOR these kind of errors myself.

Upvotes: 1

Views: 1627

Answers (4)

Stuart Marks
Stuart Marks

Reputation: 132460

For debugging problems like this I'd recommend a logging-style appraoch.

The problem with inspecting or printing out the values passed to the comparator at the time of the exception is that the result for these values might not actually be incorrect. However, it might be inconsistent with earlier, incorrect results.

You could use println or an actual logging framework. Or, since your data set is quite large (if I recall correctly from your other question) you could log the compared elements and results to an internal data structure and then dump it out in whatever form you like after the sort throws the exception.

If the last comparison is between MyObject1 and MyObject2, then search backward in the log for other comparisons involving these objects. There might be a direct conflict with another comparison between these two objects, or there might be an intermediate MyObject3. Or, unfortunately, there might be an arbitrarily long chain of dependencies that you have to follow before you find the conflict:

mo1 < mo2 < mo3 < ... < moN < mo1

But all the information about what caused the inconsistency should be in the log file, somewhere.

Upvotes: 1

bsiamionau
bsiamionau

Reputation: 8229

Exception is pretty self-descripting, violation of contract occures when provided Comparator is not transitive. Why isn't your Comparator transitive? Because you're providing not accurate subtraction of float values. It's normal for Java and other programming languages. In other words, you're assuming that 0.1 - 0.1 will produce 0, but it won't.

It appears that result of your subtraction is pretty verbose and couldn't be strictly compared to 0. For example, if you're trying to sort Collection with 2 objects with the same totalEnergy value, provided compare method will return value greater than zero for both object1.compareTo(object2) and vice versa.

I can suggest you to use BigDecimal instead of float, it provides more accurate computations.

@Override
public int compare(MyObject m1, MyObject m2) {
    BigDecimal bd1 = BigDecimal.valueOf(m1.getTotalEnergy());
    BigDecimal bd2 = BigDecimal.valueOf(m2.getTotalEnergy());
    return bd1.compareTo(bd2);
}

See also:

Debugging proccess:

Dive into the sources of JDK. If you take a short look at java.util.TimSort.mergeHi(int base1, int len1, int base2, int len2) method (where java.lang.IllegalArgumentException is being thrown), you will see that exception is thrown when the next condition is not observed:

[mergeHi] Merges two adjacent runs in place, in a stable fashion. The first element of the first run must be greater than the first element of the second run (a[base1] > a[base2]), and the last element of the first run (a[base1 + len1-1]) must be greater than all elements of the second run.

Check which elements violate this rule and, most likely, you'll find discrepancy.

Upvotes: 4

Christian
Christian

Reputation: 395

It seems that your sorting is not strict. Is your getTotalEnergy() time-dependent, i.e. does is give different results over time?

In my eyes your comparison looks right, but you could try with

Collections.sort(sorted, new Comparator<MyObject>() {
    @Override
    public int compare(MyObject m1, MyObject m2) {
        return (int) Math.sign(m1.getTotalEnergy() - m2.getTotalEnergy());
    }
});

Do I miss something or could you simply debug your comparison with

System.out.println("comparing: " + m1.getTotalEnergy() + " <-> " + m2.getTotalEnergy());

The last line printed should give you your invalid data.

Upvotes: 0

Guy Bouallet
Guy Bouallet

Reputation: 2125

You can use you IDE's debugger and set an exception beakpoint on java.util.TimSort.

Upvotes: 0

Related Questions