Java, Sorting a massive ArrayList using a custom comparator sometimes throws iIllegalArgumentException

Question

I am sorting an 8k+ elements List using the following algorithms.

//sort by y coordinates using the topleft point of every contour's bounding box
Collections.sort(contourList, new Comparator<MatOfPoint>() {
    @Override
    public int compare(MatOfPoint o1, MatOfPoint o2) {
        Rect rect1 = Imgproc.boundingRect(o1);
        Rect rect2 = Imgproc.boundingRect(o2);
        int result = Double.compare(rect1.tl().y, rect2.tl().y);
        return result;
    }
} );


//sort by x coordinates
Collections.sort(contourList, new Comparator<MatOfPoint>() {
    @Override
    public int compare(MatOfPoint o1, MatOfPoint o2) {
        Rect rect1 = Imgproc.boundingRect(o1);
        Rect rect2 = Imgproc.boundingRect(o2);
        int result = 0;
        double total = rect1.tl().y/rect2.tl().y;
        if (total>=0.9 && total<=1.4 ){
            result = Double.compare(rect1.tl().x, rect2.tl().x);
        }
        return result;
    }
});

The problem is that, while sorting by Y coordinates (the first comparator) does not give any problem (I don't know at this point if it is only a matter of luck),

sorting by X coordinates (the second comparator) yelds this exception:

java.lang.IllegalArgumentException: Comparison method violates its general contract!

. I modified the algorithm adding what follows to print debug info:

DecimalFormat df = new DecimalFormat();
df.setMaximumFractionDigits(2);
log.debug("tot: {}; p1.x: {}, p1.y: {}; p2.x {}, p2.y {}",
        df.format(total),
        rect1.tl().x,
        rect1.tl().y,
        rect2.tl().x,
        rect2.tl().y);

, these are the last 10 entries before the exception occours:

tot: 0,85; p1.x: 81.0, p1.y: 1415.0; p2.x 429.0, p2.y 1657.0
tot: 0,78; p1.x: 81.0, p1.y: 1415.0; p2.x 677.0, p2.y 1820.0
tot: 0,75; p1.x: 81.0, p1.y: 1415.0; p2.x 703.0, p2.y 1879.0
tot: 0,78; p1.x: 81.0, p1.y: 1415.0; p2.x 1010.0, p2.y 1820.0
tot: 0,83; p1.x: 81.0, p1.y: 1415.0; p2.x 1250.0, p2.y 1708.0
tot: 0,85; p1.x: 81.0, p1.y: 1415.0; p2.x 1260.0, p2.y 1657.0
tot: 0,76; p1.x: 81.0, p1.y: 1415.0; p2.x 1282.0, p2.y 1867.0
tot: 0,82; p1.x: 81.0, p1.y: 1415.0; p2.x 1282.0, p2.y 1736.0
tot: 0,86; p1.x: 81.0, p1.y: 1415.0; p2.x 1282.0, p2.y 1649.0
tot: 0,76; p1.x: 81.0, p1.y: 1415.0; p2.x 1507.0, p2.y 1864.0
Exception in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract!
    at java.util.TimSort.mergeLo(TimSort.java:777)
    at java.util.TimSort.mergeAt(TimSort.java:514)
    at java.util.TimSort.mergeCollapse(TimSort.java:441)
    at java.util.TimSort.sort(TimSort.java:245)
    at java.util.Arrays.sort(Arrays.java:1512)
    at java.util.ArrayList.sort(ArrayList.java:1462)
    at java.util.Collections.sort(Collections.java:175)

I've never incurred in a problem like this, could someone provide both an explanation and a solution to make these algos reliable?

Thank you a lot in advance for your effort

Riccardo

Edit1: I've added the debug info as it follows:

static Comparator<MatOfPoint> contourXComparator() {

    return new Comparator<MatOfPoint>() {
        @Override
        public int compare(MatOfPoint o1, MatOfPoint o2) {
            Rect rect1 = boundingRect(o1);
            Rect rect2 = boundingRect(o2);
            int result = 0;
            double total = rect1.tl().y / rect2.tl().y;
            /* debug purpose */
            DecimalFormat df = new DecimalFormat();
            df.setMaximumFractionDigits(2);
            log.debug("tot: {}; p1.x: {}, p1.y: {}; p2.x {}, p2.y {}",
                    df.format(total),
                    rect1.tl().x,
                    rect1.tl().y,
                    rect2.tl().x,
                    rect2.tl().y);
            /* endof debug purpose */
            if (total >= 0.9 && total <= 1.4) {
                result = Double.compare(rect1.tl().x, rect2.tl().x);
            }
            return result;
        }
    };

Where did you add this print function? Near the beginning of your method or near the end? — Mark, Nov 29 '18 at 11:48
@RiccardoFinazzi Were you able to fix this issue. I am having the same problem. — Ismail Osunlana, Jul 23 '22 at 20:58

score 1 · Answer 1 · answered Nov 29 '18 at 11:59

Your second comparator is not transitive. Consider the three elements

a = (1,4)
b = (1,5)
c = (1,6)

(x,y) denotes the dimensions of their bounding rectangles.

According to your comparator a < b and b < c but a = c. From there you could deduce that a=c < b but at the same time a=c > b. You cannot sort with such an order, therefore the exception.

Sid Malani · Answer 2 · 2018-11-29T12:26:59.510

0

Your return a value consistently for a comparison. For example if you returned -1 for both A > B or B > A then there is no way a sort algorithm could work.

The main issue with the code is you have introduced an if block which violates the comparison because you may have a set of coordinates that you call equal even when they are not by returning a 0.

You could try sorting first just as you did for y and then filter out.

edited Nov 29 '18 at 12:26

answered Nov 29 '18 at 11:59

Sid Malani

2,078
1
13
13

Sorry I think I did not explain correctly. Let me try and rephrase it. – Sid Malani Nov 29 '18 at 12:07

Java, Sorting a massive ArrayList using a custom comparator sometimes throws iIllegalArgumentException

2 Answers2

Linked