Scala范围/区间映射结构

Question

我有几乎相同的数据结构中提到的问题,可以将一系列键映射到值,但对于Scala.

也就是说,我希望有一个非重叠的1D范围[a [i],b [i])的可变系统,它将映射到某种值v [i].执行此类工作的标准基础数据结构是红黑树.

我希望它拥有的操作,最好是所有操作都应该具有O(log n)的复杂度:

• 通过指定其中的任何点来查询并获取给定范围(开始,结束,存储值)或缺少它
• 在此结构中插入新范围
• 从结构中删除范围

所以,我想到目前为止,我看到以下变种,所有这些都有其缺点:

• 在Java的TreeMap上滚动自己的容器- 快速而肮脏,但由于缺乏适当的维护而长期可能不好
• 使用Guava的RangeMap - 可能,但在Scala集合世界中会非常尴尬
• 尝试使用Scala的红黑树实现并尝试自己滚动,但是,我想这很难,因为Scala的TreeMap只是不可变的,并且错过了直接的查找方法,例如Java的TreeMapfloorEntry

我在这里错过了什么吗？是否存在使用Scala中心API扩展基本Scala集合的类似Guava的维护良好的集合扩展库？

强烈相关的问题:

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

Answer 1

我很可能会封装 Guava 的RangeMap. 您所需要的只是一个三方法类，您可以在其后面隐藏非 scalaish 集合。

我很好奇推出我自己的基于 Java 的解决方案有多难NavigableMap，而且它非常简单：

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

Java 和 Lombok 中只有40 行（Scala 中可能更少），我不会害怕任何维护。我只写了一个非常基本的测试。