实现排序映射和集合，使其实现 j.u.NavigableMap 和 NavigableSet 接口

Question

由于 Clojure 1.5 可能不再针对 JVM 5，因此添加对 (Concurrent)?Navigable(Map|Set) 接口的支持。这应涉及向 PersistentTreeMap 添加函数，降阶到红黑树以选择最接近的项。

Answer 1

评论由：michalmarczyk 提出

只是想指出，(链接：https://github.com/clojure/data.avl 文本：data.avl) 提供了这个功能，尽管是通过 Clojure 接口。实现 descendingMap 将是直接了当的，但它可能会使某些功能（我认为可能更有吸引力）的实现复杂化。如果有需要，我可以提供更多细节，但如果在 data.avl 的跟踪器上讨论可能更好。

在 PersistentTreeMap 中实现整个 NavigableMap 可能比看起来要复杂，因为我们可能希望 resulting 结构的 count 属性保持为 O(1)。当然，可以取消这个要求。

data.avl 集合在节点中存储排名信息；这使排名查询和可导航的映射操作可以在其返回值上实现 O(1) 的 count，但这以节点大小的代价为代价。我认为对于不同用例，有紧凑的 PTM 和功能更齐全但节点繁重的 data.avl 是有用的，尤其是因为 data.avl 在基本操作（如通过相同形状的路径访问节点；某些单独的树操作可能略慢，但 AVL 树通常较浅）方面非常快。

Answer 2

评论由：jafingerhut 提出

我还没有仔细检查，但似乎事实确实可能是这样的，即可以使用现有的 clojure.core/subseq 和 clojure.core/rsubseq 函数（加上 first、seq 等）实现 NavigableMap 和 NavigableSet 接口。

Answer 3

_评论由：michalmarczyk_发表_

{{subseq}} 和 {{rsubseq}} + {{first}} 解决了 {{NavigableMap}} 的“邻接查找”部分，但不是子映射方法。

在对红黑树进行子集操作时，完全可能在对数时间内完成，但正如我前面评论中提到的，如果你想要保持结果结构的 {{count}}（如果可能的话，则是 O(1)，或者至少显著优于 O(n)），这是不可能的。这是因为没有办法知道 BST 的任何子区间包含多少个节点，除非实际遍历或预先在节点（至少部分节点）中存储注释。

我在去年11月的 Conj 演讲中描述了一个可能的解决方案，我在某个地方有一个草图，但这不会提供 data.avl 那样的便利性——上述限制是根本性的；它可能适用于几乎不调用 {{count}} 的情况。


作为一个附加说明，data.avl 在它的测试用例中使用了一个基于 {{subseq}} 等的邻接查找实现，以作为直接用于 {{clojure.data.avl/nearest}} 的直接实现的理智性检查。该文件还包括了一个基于 {{subseq}} 的 {{subrange}}（data.avl 集合的通用子集函数）实现；正如你预期的那样，除了最小的输出大小外，它对几乎所有其他输出大小都极为缓慢。

Answer 4

参考：https://clojure.atlassian.net/browse/CLJ-1008（由 jim.blomo 报告）