• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Tim Cooke
  • Devaka Cooray
  • Ron McLeod
  • Jeanne Boyarsky
Sheriffs:
  • Liutauras Vilda
  • paul wheaton
  • Junilu Lacar
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Piet Souris
  • Carey Brown
  • Tim Holloway
Bartenders:
  • Martijn Verburg
  • Frits Walraven
  • Himai Minh

Comparison method violates its general contract Exception

 
Joseph Michael
Ranch Hand
Posts: 94
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi,

Sometimes we come across Comparison method violates its general contract exception in our code base.

This error may comes on contract violation.....

Any good java code snippet to understand this behavior or problem

Thanks
 
Paul Clapham
Sheriff
Posts: 27451
88
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
If you have actually come across that problem, then you have some code which illustrates it. So sure, go ahead and post that code and we'll happily discuss it.
 
Joseph Michael
Ranch Hand
Posts: 94
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Working Code

package com.company;

import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Comparator;

public class MainTest2 {
public static void main(String[] arg) {
sort(1,2, 1, 3, 1);

}

static void sort(Integer... ints) {
List<Integer> list = Arrays.asList(ints);
Collections.sort(list, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
if (o1 < o2) {
return -1;
} else {
return 1;
}
}
});
System.out.println(list);
}
}


Error Code which throws Contract Violation

import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Comparator;

public class MainTest {
public static void main(String[] arg) {
sort(3, 2, 2, 2, 2, 3, 2, 3, 2, 2, 3, 2, 3, 3, 2, 2, 2, 2, 2, 2, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1);

}

static void sort(Integer... ints) {
List<Integer> list = Arrays.asList(ints);
Collections.sort(list, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
if (o1 < o2) {
return -1;
} else {
return 1;
}
}
});
System.out.println(list);
}
}


Questions:

1) Why the contract violation is not thrown in 1st code and thrown in 2nd code ?

2) Will it occur in rare or edge case and we are not sure....

3) Will it occur When mutiple values are being sorted only this problem may arise...

Please let me know your thoughts
 
Campbell Ritchie
Marshal
Posts: 76856
366
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Please use the code button, so your code will be legible.
The correct question is, why doesn't the runtime notice that comparing 1 with 1 doesn't produce 0 from the compare() method? Maybe it is that you aren't comparing 1 and 1 anywhere in the sorting in the small array, whereas you are comparing 1 and 1 in the larger array. I can't remember when that sort of testing was introduced to throw that sort of exception.
 
Campbell Ritchie
Marshal
Posts: 76856
366
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
You might find this Oracle forums thread useful, or this tutorial‑like thread, when you have found the glaring mistake in it (). I found evidence of Collections#sort throwing that sort of exception in the Java7 documentation but not for Java6.
 
Stephan van Hulst
Saloon Keeper
Posts: 14498
325
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
It depends on the number of elements and how the elements are ordered before sorting them.

Sorting is done by a modified merge-sort algorithm. After splitting the array in two and sorting the two halves recursively, the sorted halves are merged back together. I imagine that during this merging step, the algorithm relies on the compare() method being transitive, and has the opportunity to test this. This will not always detect problems, just in certain situations.

For fewer elements than a certain threshold, elements aren't sorted by merge-sort, but by insertion-sort.
 
Rob Spoor
Sheriff
Posts: 22701
129
Eclipse IDE Spring VI Editor Chrome Java Windows
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The reason is simple, and Campbell hinted at it - your comparison implementation is wrong. If you compare 2 and 2, it will always return 1. That means that the second element is larger than the third (2 is not < 2 so 1 is returned), but the third is also larger than the second (same reasoning).

The solution is simple: return a negative number if the first argument is smaller (you got that), a positive number if the third argument is larger, and 0 if the arguments are equal. You're missing the last part.

A naive way of solving this:

Now this will work, but I call it naive because you're not using the tools that you're given by Oracle: Integer.compare(int, int). The solution becomes easier:

Note that o1.compareTo(o2) would do the same. In fact, you don't even need a comparator because Integer is already comparable; Collections.sort(list) (or since Java 8 list.sort(null)) will do the same.
 
Consider Paul's rocket mass heater.
reply
    Bookmark Topic Watch Topic
  • New Topic