1

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.

MMAdams
  • 1,508
  • 15
  • 29
math_law
  • 391
  • 1
  • 4
  • 16
  • if getTotalEnergy is computed every time, then you might have numerical problems (for instance you change order of operators, like sum all elements, etc) – gawi Jan 19 '15 at 12:05
  • It might be misunderstood. I am not asking what is wrong in the above code. I already asked and get answered of it http://stackoverflow.com/questions/28004269/java-collections-sort-comparison-method-violates-its-general-contract , Here I am asking how can I DEBUG/MONITOR it myself. – math_law Jan 19 '15 at 12:07

4 Answers4

4

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.

Community
  • 1
  • 1
bsiamionau
  • 8,099
  • 4
  • 46
  • 73
  • you are still expalining the description of "compare" and "transivitiy" which is well documented in Javadocs. I am asking , what 3 or more objects are violating this rule. It is the "real values" (Nulls/NaNs ...) that makes this exception even the code seems valid as in my above example. – math_law Jan 19 '15 at 12:49
  • @math_law, please, reread my answer. I've described example when your code will produce transitivity violation (case when 2 of your objects have "the same" value). Isn't it persuasive enough for you? Let me repeat my asnwer, you code is not valid, try to rewrite it with BigDecimal, or, even better, compare float values using some small measurement error as it described in [this question](http://stackoverflow.com/questions/1088216/whats-wrong-with-using-to-compare-floats-in-java). – bsiamionau Jan 19 '15 at 13:04
  • @zdvh I am not really interested to solve this problem. I already did ! ( refer to the link in question description) what I am trying to see is how to DEBUG those kind of errors and clearly verbose what values/objects are violating any transivitity etc rules for sort. Any ideas ? – math_law Jan 19 '15 at 13:43
  • 1
    While I understand you explain mechanics for the comparison this anwer is not describing "the how" of implementing such a solution. – math_law Feb 05 '15 at 11:40
1

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.

Stuart Marks
  • 127,867
  • 37
  • 205
  • 259
0

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

Guy Bouallet
  • 2,099
  • 11
  • 16
  • Hmm simple but inspiring. Let me try/catch and print objects (during exception) , which is aganist the intended ordering... – math_law Jan 19 '15 at 12:57
  • If you step into the TimeSort class and inspect the values of the variables with your debugger, you should be able to find out the root cause of what is going on. The code is probably not obvious http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8-b132/java/util/TimSort.java but I'm sure it will give you clues. – Guy Bouallet Jan 19 '15 at 13:01
  • Hey wait, how can I display the values/objects m1 and m2 whenever this exception is thrown ? :) Assuming this is a remote exception ( i.e. no Debuggin is possible) can you suggest a try/catch block so I can print logs with the values of objects ? – math_law Jan 19 '15 at 13:04
  • when setting an exception breakpoint, the context is still available when the exception is fired. I'm assuming you reproduce the bug on your developement environment, at least writing unit tests to make sure it is fixed and avoid similar regressions. – Guy Bouallet Jan 19 '15 at 13:10
0

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.

Christian
  • 395
  • 2
  • 13
  • Hmm simple but inspiring. Let me try/catch and print objects (during exception) , which is aganist the intended ordering... – math_law Jan 19 '15 at 12:55