1

我想要做的是能够调整 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)
        }
      }
    }

  }
4

1 回答 1

7

我发现基本操作中几乎不可能存在错误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。

于 2012-08-28T14:45:57.333 回答