仅支持半开范围时如何进行包含范围查询(ala SortedMap.subMap) [英] How to do inclusive range queries when only half-open range is supported (ala SortedMap.subMap)

问题描述

这是 SortedMap.subMap:

SortedMapsubMap(K fromKey, K toKey) :返回此地图部分的视图，其键范围从 fromKey(含)到 toKey(不含).

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 中很普遍，虽然它确实有其优点，但它也有其怪癖，我们很快就会看到.

This inclusive lower bound, exclusive upper bound combo ("half-open range") is something that is prevalent in Java, and while it does have its benefits, it also has its quirks, as we shall soon see.

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

The following snippet illustrates a simple usage of 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 的上界是唯一的.现在假设我们实际上需要一个inclusive上限，那么我们可以尝试编写一个这样的实用方法:

The last line is important: 7=Seven is excluded, due to the exclusive upper bound nature of subMap. Now suppose that we actually need an inclusive upper bound, then we could try to write a utility method like this:

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);
}

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

Then, continuing on with the above snippet, we get:

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}

需要进行一些关键观察:

A couple of key observations need to be made:

• 好消息是我们不关心值的类型，但是...
• subMapInclusive 假定 Integer 键使 to + 1 起作用.
  • 一个通用版本，也需要例如Long 键是不可能的(见相关问题)
  • 更不用说对于Long，我们需要与Long.MAX_VALUE进行比较
  • 数字原始装箱类型Byte、Character等的重载，作为键，必须全部单独写入
  • 需要对toInclusive == Integer.MAX_VALUE进行特殊检查，因为+1会溢出，而subMap会抛出<代码>IllegalArgumentException: fromKey >toKey
  • The good news is that we don't care about the type of the values, but...
  • subMapInclusive assumes Integer keys for to + 1 to work.
    • A generic version that also takes e.g. Long keys is not possible (see related questions)
    • Not to mention that for Long, we need to compare against Long.MAX_VALUE instead
    • Overloads for the numeric primitive boxed types Byte, Character, etc, as keys, must all be written individually
    • A special check need to be made for toInclusive == Integer.MAX_VALUE, because +1 would overflow, and subMap would throw IllegalArgumentException: fromKey > toKey
    • String 键呢?或者某些未知类型甚至可能不是 Comparable?
    • What about String keys? Or some unknown type that may not even be Comparable<?>?

    所以问题是:是否可以编写一个通用的 subMapInclusive 方法，该方法采用 SortedMap 和 K fromKey, K toKey，并执行包含范围的 subMap 查询?

    So the question is: is it possible to write a general subMapInclusive method that takes a SortedMap<K,V>, and K fromKey, K toKey, and perform an inclusive-range subMap queries?

    • 是否总是索引范围的上限假定是排他性的?
    • 是否可以在 Java 中为数字框类型编写通用的 +1 方法?

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

    It should be mentioned that there's a NavigableMap.subMap overload that takes two additional boolean variables to signify whether the bounds are inclusive or exclusive. Had this been made available in SortedMap, then none of the above would've even been asked.

    因此使用 NavigableMap<K,V> 进行包含范围查询本来是理想的，但是 Collections 为 SortedMap 提供了实用方法code>(除其他外)，我们没有像 NavigableMap 那样奢侈.

    So working with a NavigableMap<K,V> for inclusive range queries would've been ideal, but while Collections provides utility methods for SortedMap (among other things), we aren't afforded the same luxury with NavigableMap.

    • 为 NavigableMap<编写同步线程安全包装器/code>
    • 这是否突出了独占上限范围查询的问题?
    • 当独占上限是唯一可用的功能时，过去如何完成包含范围查询?

    推荐答案

    这是我的通用包容性子图的实现.在这里我假设由于地图被排序，tailmap 的时间复杂度会很低，所以诀窍是从尾部开始并查看返回的键，然后基于这些键或者取一个尾部，常规子图，或带有下一个键的子图:

    Here is my implementation for a general inclusive submap. Here I am assuming that since the maps are sorted the time complexity of tailmap will be low, so the trick is to start with the tail and look at the keys returned, and then based on those keys either take a tail, the regular submap, or the submap with the next key:

    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);
    }
    

    这篇关于仅支持半开范围时如何进行包含范围查询(ala SortedMap.subMap)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！