将Java TreeMap代码迁移到Scala？
我正在将我的Java代码库迁移到纯Scala，我仍然坚持使用这一段代码 。 我有一个IntervalMap的实现，即一个数据结构，让你有效地将范围[from,to]映射到set ， delete和get操作都是O(log n) （与IntervalTree或SegmentTree略有不同）。
这段代码使用Java的java.util.TreeMaps ，在迁移到Scala时，我遇到了两个大问题：
-
Scala没有
mutable.TreeMap– 我决定通过使用mutable.TreeSet（奇怪的是Scala有mutable.TreeSet但没有mutable.TreeMap）来存储密钥并将值存储在辅助的mutable.Map。 这是一个令人不快的黑客，但还有更好的方法吗？ -
下一个问题是Scala的
mutable.TreeSet没有java.util.TreeSet的ceilingKey，floorEntry，pollFirst，pollLast等同于Java中的所有O(log n)操作。
那么，我怎样才能最好地将我的代码迁移到Scala？ 这些情况下的最佳做法是什么？ 我真的不想编写自己的树实现。 有没有更惯用的Scala编写IntervalMaps的方式，我不知道？ 或者那里有一些有信誉的图书馆？ 或者Scala只是简单地使用它的gimped TreeSet和不存在的TreeMaps来吮吸它。 当然，我可以在Scala中使用Java的TreeMap ，但这很难看，我失去了所有不错的Scala集合function，我不妨使用Java。
这是我目前的Java代码： https ： //gist.github.com/pathikrit/5574521
不幸的是，答案只是使用Java TreeMap类。
Scala没有自己的所有副本，这是最值得注意的例外之一。 与Java兼容的原因之一是您不必重新发明每一个轮子。
您仍然希望使用Scala的原因是您编写的所有代码都不是关于此TreeMap的 。 您的IntervalMap可以是Scala IntervalMap ; 您只需在内部使用Java TreeMap来实现它。 或者你可以在Scala中使用不可变版本，它现在对于不可变版本表现得相当不错。
也许在2.11或2.12中会有一个可变的TreeMap ; 它需要有人写它，测试它，优化它等等，但我不认为有这个有哲学上的反对意见。
1）内部使用不可变TreeMap有什么问题？ 它或多或少与可变树映射一样高效，在O（log n）中执行所有操作。
2）在Scala版本中，没有ceilingKey和floorKey ，而是有一个方法from和之间基本相同，但返回整个子树而不是单个条目。
完整的1：1 Java代码端口：
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] ，应该添加一些文档。
看起来你想要使用漂亮的Scala集合function。 我认为你不需要重新实现你的课程。
你见过scala.collection.JavaConversions吗？
您可以使用包装器遵循类似的方法，然后相应地实现您想要的方法。 您可能需要更具创造性，如何定义，然后使用您的地图类型独有的方法，但不应该是一个大问题。
我希望这会给你一个想法。 如果你需要更多的指导我可以告诉我，我可以帮助你（看起来你已经有一段时间了）。
Scala 2.12最近有了mutable.TreeMap ： https ： //github.com/scala/scala/pull/4504