帶可變鍵的Java TreeMap

我試圖在Java中實現Fortune's algorithm，爲避免編寫AVLTree，我決定使用帶有BeachNode鍵的TreeMap。 BeachNode有以下代碼：帶可變鍵的Java TreeMap

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

所以它通過執行中途改變相交的getX（）方法返回依賴於掃描線 - 的本高度的值。

我的第一個問題： （我相當肯定的答案是肯定的，但平和的心態將是很好）

如果我保證任意兩個BeachNodes A和B，正負號（ A.compareTo（B））保持不變，而A和B在沙灘樹中，TreeMap仍然會運行，儘管compareTo的基礎變化了嗎？

我的第二個問題：

我怎樣才能確保這樣的合同是服從？

請注意，在Fortune's algorithm中，我們跟蹤兩個交點之間的掃掠線位置 - 當掃掠線到達其中一個位置時，其中一個交點被刪除。

這意味着海灘樹中的兩個交叉點A和B將永遠不會交叉位置，但在CircleEvent期間，A.compareTo（B）將返回0-干擾處理CircleEvent。在CircleEvent期間，合同將僅被簡短地打破，這將刪除一個交叉點。

這是我在StackOverflow上的第一個問題，如果它不好或不完整請告訴我，我會盡我所能糾正它。

來源

2015-04-30 Monkooky

根據TreeMap documentation，樹會根據compareTo方法排序，因此允許任何未在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應留不同，不會他們不相等？如果我錯了，希望理解算法的人可以幫助你解決這個問題。

來源

2015-05-01 02:21:28

帶可變鍵的Java TreeMap

回答

相關問題