java comparison method violates its general contract

Question

When doing a Collection.sort using a custom comparator I am getting a java.lang.IllegalArgumentException: Comparison method violates its general contract

I understand that this is a problem due to the fact that the method is not transitive. In my comparator, multiple methods are called and I identified the piece of code which violates this rule. However I am not able to fix it nor see the problem with it.

private int compareInstancesBelowChangeNumberStructureElements(ISapInstance pInstance1,
ISapInstance pInstance2) {
// Sort algorithm below change number structure elements
    String[] tokens1 =     pInstance1.getName().asString().split(COMPOUND_NAME_DELIMITER_REGEX);
    String[] tokens2 =      pInstance2.getName().asString().split(COMPOUND_NAME_DELIMITER_REGEX);

    if ((tokens1 == null) || (tokens2 == null)) {
      return 0;
    }

     int minLength = tokens1.length;
     if (tokens2.length < minLength) {
      minLength = tokens2.length;
     }

    if (minLength < 3) {
      return 0;
    }

// Compare criterion 1: node name or assembly group name
int compareValue = tokens1[2].compareTo(tokens2[2]);
if ((compareValue == 0) && (minLength >= 4)) {
  // Compare criterion 2: class name
  compareValue = tokens1[3].compareTo(tokens2[3]);
  if (compareValue == 0) {
    // Compare criterion 3: pos var name or assembly position name
    compareValue = tokens1[1].compareTo(tokens2[1]);
    if (compareValue == 0) {
      // Compare criterion 4: instance name
      compareValue = tokens1[0].compareTo(tokens2[0]);
    }
  }
}
return compareValue;
  }

Answer 1

Imagine situation where ISapInstances have next amount of tokens.

a -> 4
b -> 2
c -> 4

It leads to a = b and b = c (because minLength is 2), so a must be equal to c, but it is not necessary true if we compare a and c directly.

Answer 2

It seems the length checks are causing this problem and if you are checking lengths to avoid ArrayIndexOutOfBoundsExcpetion. There is another way that don't involve the length checks.

static class Tokens implements Comparable<Tokens> {
    private static final int N = 4;
    // Order in which we would like to compare the tokens.
    private static final int [] TOKEN_POS = {2, 3, 1, 0};

    // Reordered tokens
    private final String [] tokens = new String[N];

    // The comparator used to compare each token
    private final Comparator<String> cmp = Comparator.nullsFirst(String::compareTo);

    Tokens(String []tokens) {
        int i = 0;
        for (int p : TOKEN_POS) {
            // Place token to it's *correct* position
            // put null if tokens does not have enough elements
            this.tokens[i++] = p < tokens.length ? tokens[p] : null;
        }
    }

    @Override
    public int compareTo(Tokens o) {
        for (int i = 0; i < N; i++) {
            int c = cmp.compare(tokens[i], o.tokens[i]);
            if (c != 0) return c;
        }
        return 0;
    }

    @Override
    public String toString() {
        return "Tokens{" +
                "tokens=" + Arrays.toString(tokens) +
                '}';
    }
}

private static Tokens getCompareKey(String [] tokens) {
    return new Tokens(tokens);
}

private static void compareAndPrint(Tokens k1, Tokens k2) {
    System.out.println(k1 + " cmp " + k2 + " = " + k1.compareTo(k2));
}

public static void main(String [] args) {
    Tokens key1 = getCompareKey(new String[]{"1", "2", "3"});
    Tokens key2 = getCompareKey(new String[]{"1", "2", "3", "5"});
    Tokens key3 = getCompareKey(new String[]{"1", "3"});
    compareAndPrint(key2, key1);
    compareAndPrint(key1, key3);
    compareAndPrint(key2, key3);
}

OUTPUT

Tokens{key=[3, 5, 2, 1]} cmp Tokens{key=[3, null, 2, 1]} = 1
Tokens{key=[3, null, 2, 1]} cmp Tokens{key=[null, null, 3, 1]} = 1
Tokens{key=[3, 5, 2, 1]} cmp Tokens{key=[null, null, 3, 1]} = 1

It's obvious that this way the ordering is transitive. However it does compare the tokens down to the last one. You can decide whether it's a suitable ordering for your application.

Answer 3

Your comparison method violates the transitivity requirement if an ISapInstance.getName() has less than three tokens.

Say you have three instances of ISapInstance:

• a - with a name that has three token elements
• b - with a name that has two token elements
• c - with a name that has three token elements and whose token[2] value is different from that of a

Now if you call your comparison method with a and b or with b and c, the comparison method returns 0 for both calls.

To satisfy the transitivity rule, your comparison method must also return 0 if it is called with a and c. But since both have names with more than two tokens and different values for the token[2] it will return something different from 0 if prepared like described.

---

The same problem arises with these three instances:

(all instances have the same values for token[2])

• a - with a name that has four token elements
• b - with a name that has three token elements
• c - with a name that has four token elements and whose token[3] value is different from that of a

---

To fix this, your comparator must not return 0 if only one of instances has less then three tokens or if the third token is the same and only one has exactly three tokens.

For example:

private int compareInstancesBelowChangeNumberStructureElements(ISapInstance pInstance1,
            ISapInstance pInstance2) {
    // Sort algorithm below change number structure elements
    String[] tokens1 =     pInstance1.getName().asString().split(COMPOUND_NAME_DELIMITER_REGEX);
    String[] tokens2 =      pInstance2.getName().asString().split(COMPOUND_NAME_DELIMITER_REGEX);

    if (tokens1.length < 3) {
        return (tokens2.length < 3) ? 0 : -1;
    } else if (tokens2.length < 3) {
        return 1;
    }
    int minLength = tokens1.length;
    if (tokens2.length < minLength) {
        minLength = tokens2.length;
    }

    // Compare criterion 1: node name or assembly group name
    int compareValue = tokens1[2].compareTo(tokens2[2]);
    if (compareValue == 0) {
        if (tokens1.length < 4) {
            return (token2.length < 4) ? -1 : 0;
        } else if (tokens2.length < 4) {
            return 1;
        } else {
            // ... the remaining comparison operations
        }
    }
    return compareValue;
}