Scala范围/区间映射结构

Question

我有一个和能够将一系列键映射到值的数据结构中提到的问题几乎相同，但是针对的是Scala。

也就是说，我想要一个可变的一维非重叠区间[a[i], b[i])，它将映射到某种值v[i]。用于执行这种工作的标准底层数据结构是红黑树。

我希望它具有以下操作，最好所有操作的复杂度都为O(log n)：

• 通过指定其中任何一个点来查询并获取给定范围（起始、结束、存储值）或其缺失情况
• 向此结构中插入新范围
• 从结构中删除范围

因此，我认为目前有以下几种变体，它们都有缺点:

• 在Java的TreeMap之上自己构建容器-快速而简单，但由于缺乏适当的维护可能会在长期内变得糟糕
• 使用Guava的RangeMap-可能，但在Scala集合世界中可能会非常笨拙
• 尝试使用Scala的红黑树实现并自己构建，然而，我猜这将会非常困难，因为Scala的TreeMap仅限于不可变类型，并且缺少直接的查找方法，例如Java的TreeMapfloorEntry

我错过了什么吗？是否有任何类似Guava的、基于Scala API的、扩展基本Scala集合的、良好维护的集合扩展库？

强相关问题：

• 将Java TreeMap代码迁移到Scala？ - 提到“只需使用Java的TreeMap”并忘记其他任何东西
• 此问题的Java版本：
  • 可以将一系列键映射到值的数据结构
  • 整数间隔内的Hashtable键
  • 使用Java map进行范围搜索
  • Java-适合搜索区间的数据结构

- GreyCat

---

你需要这个用于任意可比较的值，还是只针对int/long范围？ - Rüdiger Klaehn

就我个人而言，我会将其用于虚拟内存范围的记账，因此我的应用程序将使用“long”范围，但我不认为在这里使用非泛型方法有太大意义——并不能提供巨大的性能或空间提升。 - GreyCat

你不能使用 map.from(x).firstKey() 代替 map.floorEntry 吗？ - maaartinus

@maaartinus：你可以这样做，但仍需要处理“immutable.TreeMap”，你最终会使用完整的实现或者用“mutable.TreeSet”+“mutable.Map”来模拟它。这会对内存使用产生重大影响并且对性能也有一定影响。可能不值得这么做。 - GreyCat

@wingedsubmariner：谢谢，我现在会在问题中澄清。这些范围本身是不重叠的，因此TreeMap在简单性方面已经足够了。 - GreyCat

Answer 1

我很可能会封装 Guava 的 RangeMap。你所需要的只是一个三个方法的类，背后可以隐藏非 Scala 风格的集合。

我很好奇自己编写基于 Java NavigableMap 的解决方案有多难，实际上相当简单：

• 定义一个包含（起始点、结束点、存储值）的类MyValue
• 使用映射将起始点映射到相应的MyValue

仅用40 行代码来实现，在 Java 中使用 Lombok（Scala 中可能更少），我不担心任何维护问题。我刚写了一个非常简单的测试。

- maaartinus