java - 这个比较器可能有什么问题？

Question

我正在

"Exception in thread "AWT-EventQueue-0"
java.lang.IllegalArgumentException: Comparison method violates its general contract!"

此比较器出现错误。它在 PriorityQueue 中使用。

public class NodeFPQComp implements Comparator<Node> {

    @Override
    public int compare(Node arg0, Node arg1) {
        int result=0;

        if (arg0.getF() - arg1.getF() > 0) result = 1;
        if (arg0.getF() - arg1.getF() < 0) result = -1;

        return result;  
    }

}

getF() 是一个 float 值，永远不会接近限制，因此这里不存在溢出问题。
它只是返回另外两个 float 的总和:

public float getG() {
        return this.G;
    }

    public float getH() {
        return this.H;
    }

    public float getF() {
        return getG() + getH();
    }

这是使用它的队列:

openList = new PriorityQueue<Node>((int) gridSizeX()*gridSizeY()/10, new NodeFPQComp());

我想要的是让队列(A-Star 寻路)接受多个具有相同值(相同 f 值)但不同标识( map 上不同节点/方 block )的对象。

奇怪的是，路径查找仍然有效，但为什么我会遇到异常？那个比较器怎么会不工作呢？我缺少什么？难道是在将对象添加到队列后更改 getF() 所依赖的值(这种情况在 a-star 中经常发生)会以某种方式弄乱它吗？

这是完整的堆栈跟踪:

Exception in thread "AWT-EventQueue-0" java.lang.IllegalArgumentException: Comparison method violates its general contract!
    at java.util.TimSort.mergeLo(Unknown Source)
    at java.util.TimSort.mergeAt(Unknown Source)
    at java.util.TimSort.mergeCollapse(Unknown Source)
    at java.util.TimSort.sort(Unknown Source)
    at java.util.TimSort.sort(Unknown Source)
    at java.util.Arrays.sort(Unknown Source)
    at java.util.Collections.sort(Unknown Source)
    at javax.swing.SortingFocusTraversalPolicy.enumerateAndSortCycle(Unknown Source)
    at javax.swing.SortingFocusTraversalPolicy.getFocusTraversalCycle(Unknown Source)
    at javax.swing.SortingFocusTraversalPolicy.getFirstComponent(Unknown Source)
    at javax.swing.LayoutFocusTraversalPolicy.getFirstComponent(Unknown Source)
    at javax.swing.SortingFocusTraversalPolicy.getDefaultComponent(Unknown Source)
    at java.awt.FocusTraversalPolicy.getInitialComponent(Unknown Source)
    at java.awt.DefaultKeyboardFocusManager.dispatchEvent(Unknown Source)
    at java.awt.Component.dispatchEventImpl(Unknown Source)
    at java.awt.Container.dispatchEventImpl(Unknown Source)
    at java.awt.Window.dispatchEventImpl(Unknown Source)
    at java.awt.Component.dispatchEvent(Unknown Source)
    at java.awt.EventQueue.dispatchEventImpl(Unknown Source)
    at java.awt.EventQueue.access$200(Unknown Source)
    at java.awt.EventQueue$3.run(Unknown Source)
    at java.awt.EventQueue$3.run(Unknown Source)
    at java.security.AccessController.doPrivileged(Native Method)
    at java.security.ProtectionDomain$1.doIntersectionPrivilege(Unknown Source)
    at java.security.ProtectionDomain$1.doIntersectionPrivilege(Unknown Source)
    at java.awt.EventQueue$4.run(Unknown Source)
    at java.awt.EventQueue$4.run(Unknown Source)
    at java.security.AccessController.doPrivileged(Native Method)
    at java.security.ProtectionDomain$1.doIntersectionPrivilege(Unknown Source)
    at java.awt.EventQueue.dispatchEvent(Unknown Source)
    at java.awt.SequencedEvent.dispatch(Unknown Source)
    at java.awt.EventQueue.dispatchEventImpl(Unknown Source)
    at java.awt.EventQueue.access$200(Unknown Source)
    at java.awt.EventQueue$3.run(Unknown Source)
    at java.awt.EventQueue$3.run(Unknown Source)
    at java.security.AccessController.doPrivileged(Native Method)
    at java.security.ProtectionDomain$1.doIntersectionPrivilege(Unknown Source)
    at java.security.ProtectionDomain$1.doIntersectionPrivilege(Unknown Source)
    at java.awt.EventQueue$4.run(Unknown Source)
    at java.awt.EventQueue$4.run(Unknown Source)
    at java.security.AccessController.doPrivileged(Native Method)
    at java.security.ProtectionDomain$1.doIntersectionPrivilege(Unknown Source)
    at java.awt.EventQueue.dispatchEvent(Unknown Source)
    at java.awt.EventDispatchThread.pumpOneEventForFilters(Unknown Source)
    at java.awt.EventDispatchThread.pumpEventsForFilter(Unknown Source)
    at java.awt.EventDispatchThread.pumpEventsForHierarchy(Unknown Source)
    at java.awt.EventDispatchThread.pumpEvents(Unknown Source)
    at java.awt.EventDispatchThread.pumpEvents(Unknown Source)
    at java.awt.EventDispatchThread.run(Unknown Source)

Answer 1

“契约”意味着compare方法应该是总排序。 (编辑)此应该也与equals(Object obj)方法一致(即使可能没有严格强制)以确保数据结构(例如TreeSet、 TreeMap) 的行为符合您的预期，因为它们可能基于比较和 equals 方法。

确保您已检查这些内容。

总排序手段

• a.compareTo(a) >= 0，对于每个 a
• a.compareTo(b) >= 0 和 b.compareTo(a) >= 0 意味着 a 是“相等”到b，对于每个a,b；这意味着如果 a.compareTo(b) == 0，则 b.compareTo(a) == 0
• a.compareTo(b) >= 0 和 b.compareTo(c) >= 0 意味着 a.compareTo(c) >= 0，对于每个 a,b,c

很容易给出反例，其中 compare 方法返回 {0,1,-1} 并且不与总排序一致，因此请特别检查。