将Java TreeMap代码迁移到Scala？
我正在将我的Java代码库迁移到纯Scala，我被on this one piece of code卡住了。我有一个IntervalMap的实现，这是一种数据结构，可以让你高效地将范围[from,to]映射到values，其中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)操作。<代码>H224<代码>G225
那么，如何才能最好地将我的代码迁移到Scala？这些情况下的最佳实践是什么？我真的不想写我自己的树实现。有没有一种我不知道的更地道的IntervalMaps编写方式？或者有没有什么值得信赖的库？或者，Scala的TreeSet和不存在的TreeMaps在这里简直就是一团糟。当然，我可以在Scala中只使用java语言的TreeMap，但是这太丑陋了，而且我失去了所有Scala集合的特性，那么我还不如使用Java。
下面是我当前的Java代码：https://gist.github.com/pathikrit/5574521
回答 4
Stack Overflow用户
发布于 2015-06-26 05:19:19
Scala2.12终于有了mutable.TreeMap：https://github.com/scala/scala/pull/4504
Stack Overflow用户
发布于 2013-05-14 23:37:21
不幸的是，答案是只使用Java TreeMap类。
Scala没有自己的副本，这是最值得注意的例外之一。它与Java兼容的原因之一是，您不必重新发明每个轮子。
你仍然想使用Scala的原因是，并不是你写的每一段代码都是关于这个TreeMap的。您的IntervalMap可以是一个Scala IntervalMap；您只需在内部使用Java TreeMap来实现它。或者，您可以在Scala中使用不可变版本，对于不可变版本，它现在执行得相当好。
也许在2.11或2.12中会有一个可变的TreeMap；它需要有人来编写它，测试它，优化它，等等，但我不认为有哲学上的反对。
Stack Overflow用户
发布于 2015-04-19 22:51:10
1)在内部使用不可变的TreeMap有什么问题？它或多或少与可变树映射一样有效，所有操作都在O(log )中完成。
2)在Scala版本中，没有ceilingKey和floorKey，而是具有from和to方法，它们的功能基本相同，但返回整个子树而不是单个条目。
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]，并添加一些文档。
https://stackoverflow.com/questions/16538641
复制相似问题