java - 仅支持半开范围时如何进行包含范围查询(ala SortedMap.subMap)

Question

关于 SortedMap.subMap

这是 SortedMap<K,V>.subMap 的 API :

SortedMap<K,V> subMap(K fromKey, K toKey) : Returns a view of the portion of this map whose keys range from fromKey, inclusive, to toKey, exclusive.

这种包含下限和排他上限的组合(“半开范围”)在 Java 中很普遍，虽然它确实有它的好处，但它也有它的怪癖，我们很快就会看到。

以下片段说明了 subMap 的简单用法:

static <K,V> SortedMap<K,V> someSortOfSortedMap() {
    return Collections.synchronizedSortedMap(new TreeMap<K,V>());
}
//...

SortedMap<Integer,String> map = someSortOfSortedMap();
map.put(1, "One");
map.put(3, "Three");
map.put(5, "Five");
map.put(7, "Seven");
map.put(9, "Nine");

System.out.println(map.subMap(0, 4));
// prints "{1=One, 3=Three}"

System.out.println(map.subMap(3, 7));
// prints "{3=Three, 5=Five}"

最后一行很重要:7=Seven被排除在外，因为 subMap 的独占上限性质.现在假设我们确实需要一个包含上限，那么我们可以尝试编写这样的实用方法:

static <V> SortedMap<Integer,V>
subMapInclusive(SortedMap<Integer,V> map, int from, int to) {
    return (to == Integer.MAX_VALUE)
      ? map.tailMap(from)
      : map.subMap(from, to + 1);
}

然后，继续上面的代码片段，我们得到:

System.out.println(subMapInclusive(map, 3, 7));
// prints "{3=Three, 5=Five, 7=Seven}"

map.put(Integer.MAX_VALUE, "Infinity");
System.out.println(subMapInclusive(map, 5, Integer.MAX_VALUE));
// {5=Five, 7=Seven, 9=Nine, 2147483647=Infinity}

需要进行一些关键观察:

• 好消息是我们不关心值的类型，但是...
• subMapInclusive假定 Integer to + 1 的键上类。
  • 一个通用版本，也采用例如Long key 是不可能的(见相关问题)
  • 更不用说 Long 了，我们需要与 Long.MAX_VALUE 进行比较相反
  • 重载原始数字盒装类型 Byte , Character , etc 作为键，必须全部单独写
  • 需要对toInclusive == Integer.MAX_VALUE进行特殊检查，因为 +1会溢出，并且subMap会抛出 IllegalArgumentException: fromKey > toKey
• 一般来说，这是一个过于丑陋和过于具体的解决方案
  • 那String呢？ key ？或者一些甚至可能不是 Comparable<?> 的未知类型？

所以问题是:是否可以写一个通用的subMapInclusive采用 SortedMap<K,V> 的方法, 和 K fromKey, K toKey ，并执行包含范围 subMap有疑问吗？

相关问题

• Are upper bounds of indexed ranges always assumed to be exclusive?
• Is it possible to write a generic +1 method for numeric box types in Java?

---

关于 NavigableMap

应该提到的是有一个 NavigableMap.subMap 需要两个额外的重载 boolean变量来表示边界是包含的还是排他的。如果这在 SortedMap 中可用，那么以上都不会被问到。

所以使用 NavigableMap<K,V>对于包含范围的查询是理想的，但是 Collections为 SortedMap 提供实用方法(除其他外)，我们没有得到与 NavigableMap 相同的奢侈。 .

相关问题

• Writing a synchronized thread-safety wrapper for NavigableMap

---

在仅提供独占上限范围查询的API上

• 这是否突出了独占上限范围查询的问题？
• 过去，当独占上限是唯一可用的功能时，包含范围查询是如何完成的？

Answer 1

这是我对通用包含子图的实现。在这里，我假设由于映射是排序的，tailmap 的时间复杂度会很低，所以诀窍是从尾部开始并查看返回的键，然后基于这些键要么采用尾部，即常规子图，或带有下一个键的子图:

static <K, V> SortedMap<K,V>
subMapInclusive(SortedMap<K,V> map, K from, K to) {
    if(to == null) return map.tailMap(from);

    //What appears at key "to" or later?
    Iterator<K> keys = map.tailMap(to).keySet().iterator();

    //Nothing, just take tail map.
    if(!keys.hasNext()) return map.tailMap(from);

    K key = keys.next();

    //The first item found isn't to so regular submap will work
    if(!to.equals(key)) return map.subMap(from, to);

    //to is in the map

    //it is not the last key
    if(keys.hasNext()) return map.subMap(from, keys.next());

    //it is the last key
    return map.tailMap(from);
}