具有可变键的 Java TreeMap

Question

我试图实现 Fortune's algorithm在 Java 中，为了避免编写 AVLTree，我决定使用带有 BeachNode 键的 TreeMap。BeachNode 具有以下代码:

public abstract class BeachNode implements Comparable<BeachNode>{

static int idcounter=0;
int id;

public StatusNode(){
    //Allows for two nodes with the same coordinate
    id=idcounter;
    idcounter++;
}

@Override
public int compareTo(BeachNode s) {
    if(s.getX()<this.getX())
        return -1;
    if(s.getX()>this.getX())
        return 1;
    if(s.id<this.id)
        return 1;
    if(s.id>this.id)
        return -1;

    return 0;
}

public abstract double getX();
}

Intersection 的 getX() 方法返回一个值，该值取决于扫描线的当前高度 - 因此它会在执行过程中改变。

我的第一个问题:(我相当确定答案是肯定的，但安心就好了)

如果我确保对于任意两个海滩节点 A 和 B，signum(A.compareTo(B)) 在 A 和 B 位于海滩树中时保持不变，那么尽管 compareTo 基础发生了变化，TreeMap 是否仍能正常工作？

我的第二个问题:

我怎样才能确保遵守这样的契约(Contract)？

请注意，在 Fortune's algorithm 中，我们跟踪两个交叉点将在哪些扫掠线位置相遇——当扫掠线到达这些位置之一时，其中一个交点将被移除。

这意味着海滩树中的两个交叉点 A 和 B 永远不会交叉位置，但在 CircleEvent 期间 A.compareTo(B) 将返回 0 - 干扰处理 CircleEvent。在移除一个交叉点的 CircleEvent 期间，合约只会被短暂地打破。

这是我在 StackOverflow 上的第一个问题，如果问题不当或不完整请告诉我，我会尽力改正。

Answer 1

根据TreeMap documentation ，树将根据 compareTo 方法进行排序，因此允许任何未反射(reflect)在 a.compareTo(b) 符号中的更改。但是，您还需要实现一个与 compareTo 具有相同语义的 equals 方法。如果您已经有了 compareTo 方法，这就非常容易了:

public boolean equals(Object object) {
    if (!(object instanceof BeachNode)) {
        return false;
    }
    BeachNode other = (BeachNode) object;
    return this.compareTo(other) == 0;
}

并且，由于您要覆盖 equals，因此您应该覆盖 hashCode。这也很简单，因为您只使用几个字段来定义相等性。

public int hashCode() {
    int hash = 1;
    hash = (17 * hash) + (Double getX()).hashCode());
    hash = (31 * hash) + id;
    return hash;
}

我不确定你的第二个问题，但由于两个交叉点的 id 应该保持不同，它们不会相等吗？如果我错了，希望了解该算法的人可以帮助您解决这个问题。