Comparison method violates its general contract given a Comparator based on a Map

Question

I have been struggling with this problem: The following code implements a comparator that is based upon a Map. The Map maps objects of type Comparable to Integer values. Given two comparable objects, the comparator compares the values of these objects within the map. If any of the objects is not within the keyset of the map, 0 is returned by the comparator.

So the comparator should be transitive and reflexive. Yet, when I run the test case below in order to sort a vector of Integers, I get the following error:

java.lang.IllegalArgumentException: Comparison method violates its general contract!
at java.util.TimSort.mergeHi(TimSort.java:868)
at java.util.TimSort.mergeAt(TimSort.java:485)
at java.util.TimSort.mergeCollapse(TimSort.java:410)
at java.util.TimSort.sort(TimSort.java:214)
at java.util.TimSort.sort(TimSort.java:173)
at java.util.Arrays.sort(Arrays.java:659)
at java.util.Collections.sort(Collections.java:217) 
    at IndexComparatorTest.testSort(IndexComparatorTest.java:45)

I have tried reducing this problem further by excluding some elements from the list and the from the hashmap, yet removing any makes the problem disappear. Also I have started looking at Timsort.java, but this is kind of hard to understand.

Any ideas?

import org.junit.Test;

import java.util.*;

class MyComparator<N extends Comparable<N>> implements Comparator<N> {

    private final Map<N, Integer> node2index;

    public MyComparator(Map<N, Integer> node2Index) {
        this.node2index = node2Index;
    }

    @Override
    public int compare(N o1, N o2) {
        if (! node2index.containsKey(o1)) return 0;
        if (! node2index.containsKey(o2)) return 0;
        int result = Integer.compare(node2index.get(o1), node2index.get(o2));
        return result;
    }
}

public class IndexComparatorTest {

    @Test
    public void testSort() {
        Vector<Integer> toBeSorted = new Vector<>(Arrays.asList(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31));
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        hashMap.put(0, 5);
        hashMap.put(14, 6);
        hashMap.put(15, -2);
        hashMap.put(16, 4);
        hashMap.put(17, 1);
        hashMap.put(18, 8);
        hashMap.put(19, -12);
        hashMap.put(21, -3);
        hashMap.put(22, -13);
        hashMap.put(24, -19);
        hashMap.put(25, 2);
        hashMap.put(27, 7);
        hashMap.put(28, -6);
        hashMap.put(31, 0);
        hashMap.put(30, -4);
        Collections.sort(toBeSorted, new MyComparator<>(hashMap));
    }

}

Possible duplicate http://stackoverflow.com/questions/7849539/comparison-method-violates-its-general-contract-java-7-only — Asif Bhutto, Apr 29 '14 at 18:32
I think I know now what the problem is. It should be -1 and +1 instead of 0 and 0 in case the first or the second element is not in the map. — user152468, Apr 29 '14 at 18:40
That seems to be a problem, indeed. But also note that you should return 0 if *both* elements are not in the map, or else you violate symmetry. — Christian Semrau, Apr 29 '14 at 18:43

Christian Semrau · Answer 1 · 2014-04-29T19:03:58.327

As you found yourself, this comparator violates its contract. E.g. it tells you 0=1, 1=14, 0<14, which fails the requirement "the implementor must ensure that compare(x, y)==0 implies that sgn(compare(x, z))==sgn(compare(y, z)) for all z." A fix is to replace the compare method by this implementation:

@Override
public int compare(N o1, N o2) {
    if (!node2index.containsKey(o1) && !node2index.containsKey(o2)) return 0;
    if (!node2index.containsKey(o1)) return -1;
    if (!node2index.containsKey(o2)) return +1;
    int result = Integer.compare(node2index.get(o1), node2index.get(o2));
    return result;
}

Depending on whether you want non-mapped elements to be larger or smaller that the mapped elements, you may need to swap the -1 and +1.

score 0 · Answer 2 · answered Sep 04 '17 at 17:06

This might be a temporary problem, because of default sorting algorithm to use TimSort in place of MergeSort.

Try workaround to add JVM argument as : -Djava.util.Arrays.useLegacyMergeSort=true

This command will force JVM to use legacy MergeSort sorting algorithm.

Comparison method violates its general contract given a Comparator based on a Map

2 Answers2