scala treesetが要素を削除できません

Question

scala.collection.mutable.TreeSetを使用していますが、-=が呼び出されたときに要素を削除できない問題が発生しています。 （18,46）が除去されないこと

val discovered = new TreeSet[Position]()(Ordering by { position => estimation(position) }) 
//Position is defined as: type Position = (Int, Int) 

discovered += start 
var x = 0 
while(!discovered.isEmpty){ 
    val current = discovered.head 
    println(discovered) 
    discovered -= current 
    println(discovered) 
    x += 1 
    println(s"$x $current") 

    [...] //Code to process current and discover new positions 
} 

次の例を示し、：

マイコード。その時点まで、取り外しは完全に機能しました。私は完璧に動作する他のテストケースと、約100回の反復に達するまでこの問題が発生しないその他のケースがあります。 TreeSetの不変実装でも同じ結果が得られました。出力の

パート：

TreeSet((22,42), (18,46), (21,44), (24,46), (22,47), (21,43), (21,47), (23,47), (24,47)) 
TreeSet((18,46), (21,44), (24,46), (22,47), (21,43), (21,47), (23,47), (24,47)) 
14 (22,42) 
TreeSet((18,46), (21,44), (22,41), (24,46), (22,47), (21,43), (21,47), (23,47), (24,47)) 
TreeSet((18,46), (21,44), (22,41), (24,46), (22,47), (21,43), (21,47), (23,47), (24,47)) 
15 (18,46) 
TreeSet((18,46), (21,44), (22,41), (24,46), (22,47), (21,43), (21,47), (23,47), (24,47), (17,46)) 
TreeSet((18,46), (21,44), (22,41), (24,46), (22,47), (21,43), (21,47), (23,47), (24,47), (17,46)) 
16 (18,46) 

Answer 1

あなたのお返事ありがとうございます！注文は問題に関連していたため、エラーを見つけるのに多くの手助けをしました。

説明：

私は多くのコードベースを完全に実装しています。このアルゴリズムでは、いくつかの理由で不可能でした。また、PriorityQueueにupdateElement（）関数があった場合は、パフォーマンスを向上させ、問題が発生しないようにTreeSetの代わりにTreeSetを使用します。

私のソリューション：

としては言った：私はそれが可変とほとんど不可欠実装する必要があります。問題はdiscoveredからsomePositionは、上記の行に変更された順序、を利用している取り外しコード

estimation(somePosition) = newScore 
if(alreadyDiscovered){ discovered -= somePosition } 
discovered += somePosition 

のこれらのラインでした。 RBツリーが要素を削除しようとしたとき、それはもはやそれを見つけません。 TreeSetのよりよいデータ構造は、私はそれに切り替えるのが大好きだ、このタスクのためのバニラScalaであった場合次のコードは、すべてのテストケース

if(alreadyDiscovered){ discovered -= somePosition } 
estimation(somePosition) = newScore 
discovered += somePosition 

のために働いています。

Answer 2

問題のコードが実行されている間、あなたの順序は安定していないことを、与えられた二つの要素間の関係は、（無効なツリーの内容を作り、変更される可能性がありますハッシュマップを更新するたびにツリーの要素が並べ替えられるとは期待していませんでしたか？）。

私は、あなたが完全に持っているものを捨て、最初からあなたのアプローチを考え直すことを検討するべきだと思います。機能的に実装することをお勧めします.Varsや可変構造の使用を避けてください。コードをよりきれいにするだけでなく、このような間違いを避けるのにも役立ちます。