迁移的Java TreeMap的代码Scala呢？(Migrating Java TreeMap c

我迁移我的Java代码库，以纯Scala和我被困在这一段代码。我有一个让你有效地映射范围的IntervalMap即数据结构的实现[from,to]到values在set ， delete和get操作都是O(log n) （从IntervalTree或线段树略有不同）。

此代码使用Java的java.util.TreeMaps同时迁移到Scala中，我遇到了2个大问题：

Scala有没有mutable.TreeMap -我决定用去解决它mutable.TreeSet （奇怪的是Scala有mutable.TreeSet但没有mutable.TreeMap ），用于存储密钥和辅助存储的值mutable.Map 。这是一个令人不快的技巧，但有没有更好的办法？
接下来的问题是Scala的mutable.TreeSet没有等价的java.util.TreeSet的ceilingKey ， floorEntry ， pollFirst ， pollLast这些都是O(log n)在Java操作。

所以，我怎么能尽我的代码迁移到Scala呢？什么是在这些情况下的最佳实践？我真的不想写我自己的树实现。是否有书面我不知道的IntervalMaps的更地道斯卡拉方式？或者是有一些著名的图书馆在那里？抑或斯卡拉简直与它，不论是否供TreeSet的和不存在的树状吸这里。 Ofcourse我可以只使用Java的TreeMap斯卡拉但这是丑陋，我失去所有的美好斯卡拉集功能，我还不如使用Java即可。

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

Answer 1:

答案是，不幸的是，只使用了Java TreeMap类。

Scala没有自己的一切的副本，这是最明显的例外之一。其中一个原因是Java兼容的，这样你就不必重新发明每一轮。

您仍想使用Scala的原因是， 不是每一位的代码你写的是关于这个TreeMap的 。你IntervalMap可以是斯卡拉IntervalMap ; 你只需要使用的Java TreeMap内部来实现它。或者你可以使用Scala中，它现在是一个不可改变的版本表现相当不错不可改变的版本。

也许在2.11或2.12将有一个可变TreeMap ; 它需要有人来写它，测试它，优化它，等等，但我不认为有一个哲学反对它呢。

Answer 2:

1）什么是与内部使用不可改变的树形图中的问题？这或多或少就像是可变的树地图有效率，它为O一切（log n）的。

2）在斯卡拉的版本，没有ceilingKey和floorKey ，而是一个有方法from ，并to该做的基本上是相同的，但返回一个整体，而不是子树单个条目。

全1部分：Java代码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]应补充一些文件。