更新后Scala :: TreeMap不平衡？

Question

我想做的是能够在TreeMap中调整项目的键顺序,所以

• 我可能能够通过一些"静态"数据找到一个对象,这些数据不会改变
• 对象的位置(如果地图被展平)应该尊重它的"优先级"

以下测试用例适用于numEntries = 6,但不适用于大于7的值.我不知道那里出了什么问题,但我怀疑这个树在更新/复制后会变得不合适.有人可以请一下建议 - 是我的错还是Scala 2.9中的TreeMap有某种错误？

如果循环更新

for (i <- 1 to (numEntries - 1)) {

换成了

for (i <- (numEntries - 1) to 1 by -1) {

一切正常.所以看起来这是TreeMap中的错误？

  import org.scalatest.FlatSpec
  import collection.immutable.TreeMap
  import org.junit.runner.RunWith
  import org.scalatest.junit.JUnitRunner

  @RunWith(classOf[JUnitRunner])
  class TreeMapTest extends FlatSpec {

    //val numEntries = 6;
    val numEntries = 10;

    sealed case class Entry(first: Option[Int], last: Int) extends Ordered[Entry] {

      def compare(that: TreeMapTest.this.type#Entry) = {
        if (first.isEmpty || that.first.isEmpty) {
          last compare that.last
        } else {
          (first.get compare that.first.get) match {
            case 0 => last compare that.last
            case x => x
          }
        }
      }

      def increase() = copy(first = Some(this.first.getOrElse(0) + 1))

    }

    type Container = TreeMap[Entry, Entry]

    "TreeMap" should "allow updates" in {
      var dataMap: Container = new Container() ++ (for (i <- 1 to numEntries) yield Entry(Some(0), i) -> Entry(Some(0), i))
      for (i <- 1 to (numEntries - 1)) {
        val key = new Entry(None, i)
        dataMap.get(new Entry(None, i)) match {
          case Some(e) =>
            val newEntry = e.increase()
            dataMap = (dataMap - key) + (newEntry -> newEntry)
          case None => fail("Can not find entry " + key)
        }
      }
    }

  }

Answer 1

我发现TreeMap基本操作中存在一个错误是非常不可能的- 在Scala 2.9.0之前有很多错误,但现在有一个强大的测试套件支持RedBlack,它是支持商店.

更有可能的是,您没有总订单就会出现问题.假设你有三个要素:

val a = Entry(Some(0), 3)
val b = Entry(Some(1), 0)
val c = Entry(None, 1)

那么以下是真的:

scala> a < b
res39: Boolean = true

scala> b < c
res40: Boolean = true

scala> c < a
res41: Boolean = true

所以你有一个周期,这意味着你的订购不是一个总的订单.TreeSet要求总排序(实际上,特征Ordered要求总排序 - 部分订单有特定的特征).

让我们再创建两个节点来说明导致问题的原因:

val d = Entry(Some(0), 1)
val e = Entry(Some(2), 4)

所以,d <a <b <e.一棵可能的树是:

      b
     / \ 
    a   e
   /
  d

现在,如果你尝试查找c在树中,您将首先比较c同b,发现c比我的大b.这意味着你只会看到正确的分支,包含e,你将永远找不到d.