Debug "Comparison method violates its general contract!"

Question

I have an own, relatively sophisticated string comparator and a large list of strings (~100 strings, already tried to reduce but then the problem is not reproducible) where sorting them produces the above error when trying to sort with Java 7. I guess, that the rule

if a < b and b < c then a < c

might be violated. What is the best way to find out a sample which violates the contract?

Don't reduce the list; reduce the *comparator* instead, stepwise while reproducing the error with the same input set. Then post the *minimal* comparator which still suffers from the problem. At that point, however, it may become obvious to you. — Marko Topolnik, Aug 21 '13 at 18:24
Post the comparator code. This type of error can usually be found by inspection. — Jim Garrison, Aug 21 '13 at 18:27
@RohitJain For an example code see: http://stackoverflow.com/questions/18364904/debug-comparison-method-violates-its-general-contract#comment52365577_18376717 — Torsten, Aug 27 '15 at 06:30

score 6 · Accepted Answer · answered Aug 22 '13 at 09:35

6

OK, I did it the brute-force-way: 3 nested loops to compare 3 values with each other and verifying the above rule. Now found a sample where the rule is violated.

answered Aug 22 '13 at 09:35

Thomas S.

5,804
5
37
72

4

@Buffalo And it goes a little something like this: for (Node node1 : nodes1) for (Node node2 : nodes2) for (Node node3 : nodes3) if (node1.compareTo(node2) < 0 && node2.compareTo(node3) < 0 && node1.compareTo(node3) > 0) alertVioaltionOfContract(node1,node2,node3); – Torsten Aug 27 '15 at 06:29

score 1 · Answer 2 · edited Aug 21 '13 at 18:59

1

add debug message at start of your compare() method and to equals() / hashcode() methods (you are overriding them right?)

edited Aug 21 '13 at 18:59

Smern

18,746
21
72
90

answered Aug 21 '13 at 18:22

Leos Literak

8,805
19
81
156

what is wrong with this reply that you down voted? you would have problematic value in a minute – Leos Literak Aug 21 '13 at 19:03
The equals and hashcode methods should not be used when using a comparator. – Thomas S. Aug 22 '13 at 08:49
You are right, that custom comparator might not need them. But it does not hurt to override them. – Leos Literak Aug 22 '13 at 09:35
1

Overriding them does not help anything to resolve this particular problem. – Thomas S. Aug 22 '13 at 09:36
True, that was irrelevant idea. But debug message does. – Leos Literak Aug 22 '13 at 09:47

Jaco-Ben Vosloo · Answer 3 · 2021-05-20T08:46:49.583

When faced with a similar problem the only way to deep-dive the problem and find the set of A, b and c that violates the general contract, is to use loops.

Suppose you have a list that needs sorting and a custom comparator that is violating its contract you can find the objects using something like below

for (int i = 0; i < list.size(); i ++) {
                for (int j = 0; j < list.size(); j ++) {
                    for (int k = 0; k < list.size(); k ++) {
                        Objects a = list.get(i);
                        Objects b = list.get(j);
                        Objects c = list.get(k);
                        if (comparator.compare(a, b) < 0
                                && comparator.compare(b, c) < 0
                                && comparator.compare(a, c) > 0) {
                            System.out.print(("Error...1");
                            System.out.print((a + ", " + i);
                            System.out.print((b + ", " + j);
                            System.out.print((c + ", " + k);
                        }
                        if (comparator.compare(a, b) > 0
                                && comparator.compare(b, c) > 0
                                && comparator.compare(a, c) < 0) {
                            System.out.print(("Error...2");
                            System.out.print((a + ", " + i);
                            System.out.print((b + ", " + j);
                            System.out.print((c + ", " + k);
                        }
                        if (comparator.compare(a, b) == 0
                                && comparator.compare(b, c) == 0
                                && comparator.compare(a, c) != 0) {
                            System.out.print(("Error...3");
                            System.out.print((a + ", " + i);
                            System.out.print((b + ", " + j);
                            System.out.print((c + ", " + k);

                        }
                            
                    }
                }
            }

I have used this method many times before, especially when you are unable to find the logical errors in your coding through inspection.

I also found this answer on another post that has a general class you can use

https://stackoverflow.com/a/35000727/4019094

Debug "Comparison method violates its general contract!"

3 Answers3