TimSort not working for particular data set

**Keith Willenson** · September 11th, 2017, 01:31 PM

In the attached file, I have a dataset and Java code. When I use the code marked as "Not working" it fails. I have been using this code for quite a while with no problem. It is only on this particular data set (so far) that it fails. The failure is:

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)

Using jdk1.8.0_121, Eclipse development environment

I have tested for

a.compareTo(b) == -(b.compareTo(a))

and I find no failures.

Sorting the data with a TreeSet works. TimSort does not work. (Again, for this particular dataset)
The code (as written) is dependent on ArciMath, see code for url

**BinaryDigit09** · September 13th, 2017, 11:06 AM

I can safely say that whenever it appears to work using TreeSet, you're actually getting lucky (or rather, unlucky). Java sort methods make no guarantees that they will detect every violation of the Comparable contract, but they do so on a best-effort basis to try and help. I trust that you've thoroughly tested all combinations of 'a' and 'b' in your reverse compareTo evaluations, but did you check for the same thing by calling compareToXY instead of compareTo? I have a strong suspicion that compareToXY is not playing by the rules.

**Keith Willenson** · September 13th, 2017, 11:47 AM

Sorry for the confusion. That is a good suspicion. I had it too. I really did not check compareTo(). I tested compareToXY() .

In the code

 public static Comparator<Point> xyPointComparator = new Comparator<Point>() {
 
    @Override
    public int compare(Point p1, Point p2)
    {
        int cmp = p1.compareToXY(p2);
        return cmp;
    }

There were some lines I removed. It used to look like this:

 public static Comparator<Point> xyPointComparator = new Comparator<Point>() {
 
    @Override
    public int compare(Point p1, Point p2)
    {
        int cmp = p1.compareToXY(p2);
        int cmp2 = p2.compareToXY(p1);
        if (cmp != -cmp2)
        {
            System.err.println("xyPointComparator comparable violates contract for p1  " + p1 + "  p2 " + p2);
        }
        return cmp;
    }

This produced no errors for the data set for either TreeSet or TimSort.

Thread: TimSort not working for particular data set

LinkBack

Thread Tools

Display

TimSort not working for particular data set

Re: TimSort not working for particular data set

Re: TimSort not working for particular data set

Similar Threads

[SOLVED] problem in crearting a Set object(Set here refers to java.util.Set)

Using a mutator method to set data to an array element

Working on reading / editing file data for my program.. Need HELP!

List methods add(int k, Data data), set(int k, Data data), remove(int k)

HttpURLConnection with POST data URLEncoder.encode not working i think