Search code examples
scalatreesetred-black-tree

scala treeset fails to remove element

I'm using a scala.collection.mutable.TreeSet and I'm running into a problem, where it fails to remove an element when -= is called.

My code:

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
}

The following example shows, that (18,46) is not removed. Up until that point the removing worked perfectly. I have other test cases, which work perfecly and other cases where this problem does not happen until about 100 iterations are reached. I've got the same result with the immutable implementation of TreeSet.

Part of the output:

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)
Solution

  • Thanks to everyone for your answers! The ordering was related to the problem, so it helped a lot to find the error.

    Clarification:

    I'm implementing a lot of my code base fully functional. For this algorithm it was not possible for several reasons. Also: If there was a PriorityQueue, that had an updateElement() function, I would have used that instead of the TreeSet for better performance and to avoid the problem I ran into.

    My solution:

    As said: I have to implement it mutable and mostly imperative. The problem was in those lines of code

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

    Removing somePosition from discovered is making use of the ordering, which was changed in the line above. So when the RB tree tries to delete the element it does not find it anymore. The following code is working for all test cases

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

    If there is a better data structure than TreeSet in vanilla scala for this task I would love to switch to that.