java.lang.IllegalArgumentException: Metoda porównania narusza ogólny kontrakt

Question

Witam poniżej to moja metoda porównania mojego porównania. Nie jestem pewien, co jest nie tak. Sprawdziłem inne podobne pytania i odpowiedzi na temat przepełnienia stosu, ale nie jestem pewien, co jest nie tak z moją metodą, ale wciąż dostaję java.lang.IllegalArgumentException: Metoda porównania narusza ogólną umowę!

Każda pomoc będzie mile widziana

public int compare(Node o1, Node o2) 
{ 
    HashMap<Integer,Integer> childMap = orderMap.get(parentID); 
    if(childMap != null && childMap.containsKey(o1.getID()) && 
          childMap.containsKey(o2.getID())) 
    { 
     int order1 = childMap.get(o1.getID()); 
     int order2 = childMap.get(o2.getID()); 

     if(order1<order2) 
      return -1; 
     else if(order1>order2) 
      return 1; 
     else 
      return 0; 
    } 
    else 
     return 0; 
} 

Dodawanie wyjątku jestem coraz

java.lang.IllegalArgumentException: Comparison method violates its general contract! 
at java.util.TimSort.mergeLo(TimSort.java:747) 
at java.util.TimSort.mergeAt(TimSort.java:483) 
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) 

Answer 1

Twoja metoda compare() jest nie przechodnia. Jeśli A == B i B == C, wówczas A musi być równe C.

Rozważmy teraz przypadek:

Dla A, B i C załóżmy, że metoda containsKey() powrócić te wyniki:

• childMap.containsKey(A.getID()) powraca true
• childMap.containsKey(B.getID()) zostaje przywrócone false
• childMap.containsKey(C.getID()) powraca true

Weź również pod uwagę zamówienia na A.getId()! = B.getId().

Więc

1. A i B wróci 0, jako zewnętrzna if warunek będzie false =>A == B
2. B i C wróci 0, jak zewnętrznej if warunku zostanie false =>B == C

Ale, A i C, może zwrócić -1 lub 1, na podstawie testu wewnątrz bloku if. Tak więc, A != C. To narusza zasadę przechodniości.

Myślę, że powinieneś dodać jakiś warunek do swojego bloku else, który sprawdza podobnie jak w bloku if.

Answer 2

Myślę, że problem występuje w domyślnym przypadku. Rozważ zestaw węzłów A, B i C, gdzie identyfikatory to 'a', 'b' i 'c'.Zastanów się również, że swoim childMap, który zawiera informacje na temat zamawiania względną, ma następującą zawartość:

{ 'a' => 1, 'c' => 3 } 

Teraz, jeśli uruchomić metodę compare na A i B, wrócisz 0, wskazując, że A i B są równoważne. Co więcej, jeśli porównasz B i C, nadal zwrócisz 0. Jeśli jednak porównasz A i C, zwrócisz -1, wskazując, że A jest mniejsze. To narusza własność przechodniości the Comparator contract:

The implementor must also ensure that the relation is transitive: ((compare(x, y)>0) && (compare(y, z)>0)) implies compare(x, z)>0 .

Finally, the implementor must ensure that compare(x, y)==0 implies that sgn(compare(x, z))==sgn(compare(y, z)) for all z .

Nie można traktować „przedmioty, które nie mają przypisanego rozkaz” jako posiadające wartość „gdzieś niejasno w środku”, ponieważ algorytmy sortowania nie wiem gdzie je umieścić. Jeśli chcesz pozostać przy tym podejściu, wówczas w przypadku, gdy wartości nie ma na mapie, musisz przypisać stałą wartość jako numer porządkowy; coś takiego jak 0 lub MIN_INT jest rozsądnym wyborem (ale każdy wybór musi być udokumentowany w Javadoc dla compare!).