java - 将 Java TreeMap 代码迁移到 Scala？

Question

我正在将我的 Java 代码库迁移到纯 Scala 并且我被困在这一段代码上。我有一个 IntervalMap 的实现，即一个数据结构，它可以让您有效地将范围映射[from,to]到,和操作values所在的位置（与 IntervalTree 或 SegmentTree 略有不同）。setdeletegetO(log n)

这段代码使用 Java java.util.TreeMaps，在迁移到 Scala 时，我遇到了两个大问题：

Scala 没有mutable.TreeMap- 我决定通过使用mutable.TreeSet（奇怪的是 Scala 有mutable.TreeSet但没有mutable.TreeMap）来存储键并将值存储在辅助中来绕过它mutable.Map。这是一个令人不快的黑客行为，但有没有更好的方法？
下一个问题是 Scalamutable.TreeSet没有java.util.TreeSet's ceilingKey, floorEntry,等价物pollFirst，pollLast它们都是O(log n)Java 中的操作。

那么，我怎样才能最好地将我的代码迁移到 Scala？在这些情况下，最佳实践是什么？我真的不想编写自己的树实现。有没有更惯用的 Scala 方式来编写我不知道的 IntervalMaps？或者那里有一些著名的图书馆？或者 Scala 只是用它的 gimped TreeSet 和不存在的 TreeMaps 简单地吸吮这里。当然，我可以只TreeMap在 Scala 中使用 Java，但这很丑，而且我失去了所有漂亮的 Scala 集合功能，我还不如使用 Java。

这是我当前的 Java 代码：https ://gist.github.com/pathikrit/5574521

score 13 · Accepted Answer

不幸的是，答案是只使用 JavaTreeMap类。

Scala 没有自己的一切副本，这是最值得注意的例外之一。它与 Java 兼容的原因之一是您不必重新发明每个轮子。

您仍然想使用 Scala 的原因是，并非您编写的每一段代码都与这个 TreeMap 相关。你IntervalMap可以是 Scala IntervalMap；您只需在内部使用 JavaTreeMap来实现它。或者您可以在 Scala 中使用不可变版本，它现在对于不可变版本的性能相当不错。

也许在 2.11 或 2.12 中会有一个 mutable TreeMap；它需要有人编写、测试、优化等，但我认为拥有它没有哲学上的反对意见。

score 3 · Accepted Answer

1) 在内部使用不可变 TreeMap 有什么问题？它或多或少与可变树映射一样有效，在 O(log n) 中完成所有操作。

2) 在 Scala 版本中，没有ceilingKeyand floorKey，而是有一个方法from， andto本质上是一样的，但是返回一个完整的子树而不是单个条目。

Java 代码的完整 1:1 端口：

import scala.collection._
import scala.collection.immutable.TreeMap

case class Segment[T](start: Int, end: Int, value: T) {
  def contains(x: Int) = (start <= x) && (x < end)
  override def toString = "[%d,%d:%s]".format(start, end, value)
}

class IntervalMap[T] {
  private var segments = new TreeMap[Int, Segment[T]]
  private def add(s: Segment[T]): Unit = segments += (s.start -> s)
  private def destroy(s: Segment[T]): Unit = segments -= s.start
  def ceiling(x: Int): Option[Segment[T]] = {
    val from = segments.from(x)
    if (from.isEmpty) None
    else Some(segments(from.firstKey))
  }
  def floor(x: Int): Option[Segment[T]] = {
    val to = segments.to(x)
    if (to.isEmpty) None
    else Some(segments(to.lastKey))
  }
  def find(x: Int): Option[Segment[T]] = {
    floor(x).filter(_ contains x).orElse(ceiling(x))
  }

  // This is replacement of `set`, used as myMap(s,e) = v
  def update(x: Int, y: Int, value: T): Unit = {
    require(x < y)
    find(x) match {
      case None => add(Segment[T](x, y, value))
      case Some(s) => {
        if (x < s.start) {
          if (y <= s.start) {
            add(Segment[T](x, y, value))
          } else if (y < s.end) {
            destroy(s)
            add(Segment[T](x, y, value))
            add(Segment[T](y, s.end, s.value))
          } else {
            destroy(s)
            add(Segment[T](x, s.end, value))
            this(s.end, y) = value
          }
        } else if (x < s.end) {
          destroy(s)
          add(Segment[T](s.start, x, s.value))
          if (y < s.end) {
            add(Segment[T](x, y, value))
            add(Segment[T](y, s.end, s.value))
          } else {
            add(Segment[T](x, s.end, value))
            this(s.end, y) = value
          }
        } else {
          throw new IllegalStateException
        }
      }
    }
  }

  def get(x: Int): Option[T] = {
    for (seg <- floor(x); if (seg contains x)) yield seg.value
  }

  def apply(x: Int) = get(x).getOrElse{
    throw new NoSuchElementException(
      "No value set at index " + x
    )
  }

  override def toString = segments.mkString("{", ",", "}")
}

// little demo
val m = new IntervalMap[String]
println(m)
m(10, 20) = "FOOOOOOOOO"
m(18, 30) = "_bar_bar_bar_"
m(5, 12) = "bazzz"
println(m)

for (x <- 1 to 42) printf("%3d -> %s\n",x,m.get(x))

结果：

{}
{5 -> [5,12:bazzz],12 -> [12,18:FOOOOOOOOO],18 -> [18,20:_bar_bar_bar_],20 -> [20,30:_bar_bar_bar_]}
  1 -> None
  2 -> None
  3 -> None
  4 -> None
  5 -> Some(bazzz)
  6 -> Some(bazzz)
  7 -> Some(bazzz)
  8 -> Some(bazzz)
  9 -> Some(bazzz)
 10 -> Some(bazzz)
 11 -> Some(bazzz)
 12 -> Some(FOOOOOOOOO)
 13 -> Some(FOOOOOOOOO)
 14 -> Some(FOOOOOOOOO)
 15 -> Some(FOOOOOOOOO)
 16 -> Some(FOOOOOOOOO)
 17 -> Some(FOOOOOOOOO)
 18 -> Some(_bar_bar_bar_)
 19 -> Some(_bar_bar_bar_)
 20 -> Some(_bar_bar_bar_)
 21 -> Some(_bar_bar_bar_)
 22 -> Some(_bar_bar_bar_)
 23 -> Some(_bar_bar_bar_)
 24 -> Some(_bar_bar_bar_)
 25 -> Some(_bar_bar_bar_)
 26 -> Some(_bar_bar_bar_)
 27 -> Some(_bar_bar_bar_)
 28 -> Some(_bar_bar_bar_)
 29 -> Some(_bar_bar_bar_)
 30 -> None
 31 -> None
 32 -> None
 33 -> None
 34 -> None
 35 -> None

Segment应该设置类，private[yourPackage]应该添加一些文档。

score 0 · Accepted Answer

您似乎想使用漂亮的 Scala 集合功能。我认为你不需要重新实现你的课程。

你见过scala.collection.JavaConversions吗？

您可能会使用包装器遵循类似的方法，然后相应地实现您想要的方法。您可能需要更有创意地定义地图，然后使用您的地图类型独有的方法，但这应该没什么大不了的。

我希望这能给你一个想法。如果您需要更多指导，请告诉我，我可以为您提供帮助（看起来您已经有一段时间没有问过了）。

score 0 · Accepted Answer

0

Scala 2.12mutable.TreeMap终于有了：https ://github.com/scala/scala/pull/4504

于 2015-06-25T21:19:19.337 回答

java - 将 Java TreeMap 代码迁移到 Scala？

4 回答 4

Related

Reference