метод сравнения Java нарушает его генподряд

Question

При выполнении Collection.sort using обычай компаратор я получаю java.lang.IllegalArgumentException: Comparison method violates its general contract

Я понимаю, что это проблема в связи с тем, что этот метод не является транзитивным. В моем компараторе вызывается несколько методов, и я идентифицировал фрагмент кода, который нарушает это правило. Однако я не могу это исправить и не вижу проблемы с ним.

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

Ваш метод сравнения нарушает требование транзитивности, если ISapInstance.getName() имеет менее чем три жетона.

Скажем, у вас есть три экземпляра ISapInstance:

• а - с именем, которое имеет три маркера элемента
• б - с именем, которое имеет два маркера элемента
• C - с именем, имеет три маркера элементов и чья token[2] значение отличается от того из

Теперь, если вы называете метод сравнения с a и b или с b и c, метод сравнения возвращает 0 для обоих вызовов.

Чтобы удовлетворить правила транзитивности, ваш метод сравнения также должен возвращать 0, если он вызывается с a и c. Но поскольку у обоих есть имена с более чем двумя токенами и разные значения для token[2], он будет возвращать что-то отличное от 0, если оно подготовлено, как описано.

---

Та же проблема возникает с этими трех случаями:

(все экземпляры имеют то же значение для маркеров [2])

• а - с именем, которое имеет четыре маркера элементов
• b - с именем, имеющим три символьных элемента
• c - с именем, имеющим четыре элемента токена и значение которого token[3] отличается от значения

---

Чтобы исправить это, ваш компаратор не должен возвращать 0, если только один из экземпляров имеет менее трех маркеров или если третий маркер одно и то же, и только один имеет ровно три лексемы.

Например:

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; 
} 

Answer 2

Представьте ситуацию, когда ISapInstances иметь следующее количество жетонов.

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

Это приводит к a = b и b = c (потому что minLength является 2), поэтому a должен быть равен c, но это не обязательно верно, если мы сравним a и c непосредственно.

Answer 3

Похоже, проверки длины вызывают эту проблему, и если вы проверяете длины, чтобы избежать ArrayIndexOutOfBoundsExcpetion. Существует еще один способ, который не включает проверки длины.

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); 
} 

ВЫВОД

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 

Очевидно, что таким образом упорядочение является транзитивным. Однако он сравнивает токены с последним. Вы можете решить, подходит ли это для вашего приложения.