3

One of my applications once threw an IllegalArgumentException stating that the Comparison method violates its general contract. I've found some sources detailing the problem like http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6804124 and http://www.oracle.com/technetwork/java/javase/compatibility-417013.html#source and wanted to fix this in my application.

But I can not reproduce the problem hence can not know if my fix is correct.

In my efforts to reproduce, I tried to simplify the problem as much as possible and came up with a little class that looks like this:

public class Sortee implements Comparable<Sortee>
{
  /** a value to sort by */
  public final int _x;

  public Sortee(int x)
  {
    _x = x;
  }

  public int compareTo(Sortee o)
  {
    return 1;
  }
}

I've also created an equivalent as Comparator:

public class SorteeIncorrectComparator implements Comparator<Sortee>
{
  public int compare(Sortee a, Sortee b)
  {
    return 1;
  }
}

In another class I created a List of Sortee objects and called the Collections.sort() variants to provoke the IllegalStateException:

private static void sort()
{
   List<Sortee> sortees = createSortees();

   Collections.shuffle( sortees );
   Collections.sort( sortees, new SorteeIncorrectComparator() );

   Collections.shuffle( sortees );
   Collections.sort( sortees );
}

But the IllegalStateException is never raised.

I've tried it on Linux and Windows and in eclipse on Windows with Java 1.7.0_21, 23.21-b01 and checked that property java.util.Arrays.useLegacyMergeSort is not set.

I thought that always returning 1 in the compare method should break the contract, as it is neither commutative nor transitive.

Why do I never get an IllegalStateException?

sys64738
  • 649
  • 5
  • 15
  • 1
    I'm not sure I see the benefit in writing completely fresh code to reproduce a problem which occurred in other code. Why not post the code that threw the exception and let us spot the mistakes? – Duncan Jones Jun 07 '13 at 14:59

3 Answers3

2
public static void main(String[] args) {
    Object[] array = new Object[37];
    for (int i = 0; i < array.length; i++) {
        array[i] = new Object();
    }
    Arrays.sort(array, new Comparator<Object>() {
        private int result[] = {1, 1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, 1, -1, -1, 1, -1, -1, 1, -1, 1, -1, 1, 1, 1, 1, -1, -1, 1, -1, -1, 1, -1, -1, -1, -1, -1, -1, -1, -1, 1, -1, 1, -1, 1, -1, -1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 1, -1, -1, 0, -1, -1, 0, -1, 0, 0, -1, 0, 0, -1, 0, 0, -1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, -1, -1, -1, -1, -1, -1, -1, -1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
        private int index;
        @Override
        public int compare(Object o1, Object o2) {
            return result[index++];
        }
    });
}
Ahmed Ashour
  • 5,179
  • 10
  • 35
  • 56
  • Ahmed, could you please explain your realization? result[] - is it random values or some logic is presented here? Thanks. – dnim Oct 10 '13 at 08:45
1

I was able to reproduce this when the comparator violates a=b and b=c -> a=c, then timsort seems to complain. My test was:

List<Integer> timSortTestList = new ArrayList<Integer>();
{
    for(int i=0; i<100; ++i) {
        timSortTestList.add(i);
        timSortTestList.add(i);
        timSortTestList.add(i);
    }
    Collections.shuffle(timSortTestList, new Random(42));
}
Comparator<Integer> broken = new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        if (Math.abs(o1-o2) < 10) {
            return Compare.EQUAL; // WRONG
        }
        return Ordering.natural().compare(o1, o2);
    }
};
Collections.sort(timSortTestList, broken); // throws up

Compare this question - perhaps there is a general rule when this happens.

Community
  • 1
  • 1
Dr. Hans-Peter Störr
  • 25,298
  • 30
  • 102
  • 139
  • Analysis in an answer of that question showed (if I interpret it correctly) that the sort method will never throw the exception when sorting short sequences. So the key part of your answer is that your list is 300 elements long. – Raedwald Jul 25 '14 at 09:30
  • The optimized merge sort `(Comparable)TimSort` will use a minimized version (using binarySort) if the array has less than `MIN_MERGE=32` entries. If you specify a few more elements it depends on the distribution of sort candidates if they hit the condition (i<10 never and i<20 always throws in the above code)... – eckes Mar 29 '16 at 22:00
0

My implementation actually was transitive.

I've changed the compare method to return random values and that raises the Exception.

sys64738
  • 649
  • 5
  • 15