Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 3 of 3

Thread: TimSort not working for particular data set

  1. #1
    Junior Member
    Join Date
    Sep 2017
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default TimSort not working for particular data set

    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
    Attached Files Attached Files

  2. #2
    Member
    Join Date
    Apr 2014
    Posts
    81
    Thanks
    3
    Thanked 6 Times in 6 Posts

    Default Re: TimSort not working for particular data set

    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.

  3. #3
    Junior Member
    Join Date
    Sep 2017
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: TimSort not working for particular data set

    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.
    Last edited by Keith Willenson; September 13th, 2017 at 12:25 PM.

Similar Threads

  1. [SOLVED] problem in crearting a Set object(Set here refers to java.util.Set)
    By arpansen in forum What's Wrong With My Code?
    Replies: 2
    Last Post: July 29th, 2014, 07:18 AM
  2. Using a mutator method to set data to an array element
    By MrPigeon in forum What's Wrong With My Code?
    Replies: 3
    Last Post: June 2nd, 2014, 08:50 AM
  3. Working on reading / editing file data for my program.. Need HELP!
    By travis07 in forum File I/O & Other I/O Streams
    Replies: 4
    Last Post: December 14th, 2013, 03:04 AM
  4. List methods add(int k, Data data), set(int k, Data data), remove(int k)
    By Enirox in forum Object Oriented Programming
    Replies: 3
    Last Post: September 20th, 2012, 06:43 AM
  5. Replies: 7
    Last Post: June 6th, 2012, 03:16 PM