18

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

也就是说，我想要一个可变的非重叠一维范围[a[i], b[i])系统，它可以映射到某种值v[i]。完成此类工作的标准底层数据结构是红黑树。

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

  • 通过指定范围内的任何点来查询并获取给定范围（开始、结束、存储值）或缺少范围
  • 在此结构中插入一个新范围
  • 从结构中删除范围

所以，我想到目前为止，我看到了以下变体，所有这些变体都有其缺点：

  • 在Java 的 TreeMap上滚动你自己的容器- 快速且肮脏，但由于缺乏适当的维护，长期来看可能很糟糕
  • 使用 Guava 的RangeMap - 可能，但在 Scala 集合世界中会很尴尬
  • 尝试使用 Scala 的红黑树实现并尝试自己滚动，但是，我想这将非常困难，因为Scala 的 TreeMap是仅不可变的并且缺少简单的查找方法，例如 Java 的 TreeMapfloorEntry

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

密切相关的问题：

4

1 回答 1

2

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

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

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

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

于 2014-08-15T00:07:04.837 回答