只支持半开范围时如何执行包含范围查询（ala SortedMap.subMap）

本文介绍了只支持半开范围时如何执行包含范围查询（ala SortedMap.subMap）的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

在 SortedMap.subMap

这是

在 NavigableMap

值得一提的是， a 重载，它需要两个额外的 boolean 变量来表示边界是包含还是独占。如果这已经在 SortedMap 中可用，那么以上都不会被问到。

在包含范围查询中使用 NavigableMap< K，V> 会很理想，但是 Collections 提供了实用方法对于 SortedMap （除别的以外），我们没有提供与 NavigableMap 相同的奢侈品。

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

这是否突出显示了独占上限范围查询的问题？

过去只有当独占上限是唯一可用函数时，包含范围查询是如何完成的lity？

解决方案

以下是我对一般包容性子图的实现。在这里，我假设由于地图是排序的，因此tailmap的时间复杂度会很低，所以诀窍是先从尾部开始，然后查看返回的键，然后基于这些键采用尾部，常规子图，或使用下一个键的子图：

  static 的SortedMap< K，V> 
 subMapInclusive（SortedMap< K，V> map，K from，K to）{
 if（to == null）return map.tailMap（from）; 
 
 //关键字to或以后出现什么？ 
迭代器< K> keys = map.tailMap（to）.keySet（）。iterator（）; 
 
 //没什么，只需要尾巴地图。 
 if（！keys.hasNext（））返回map.tailMap（from）; 
 
 K key = keys.next（）; 
 
 //找到的第一个项目不是那么常规的子图将工作
 if（！to.equals（key））return map.subMap（from，to）; 
 
 //在地图中
 
 //它不是最后一个键
 if（keys.hasNext（））返回map.subMap（from， keys.next（））; 
 
 //它是最后一个键
返回map.tailMap（from）; 
}

On SortedMap.subMap

This is the API for SortedMap<K,V>.subMap:

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.

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}"

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:

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
This, generally speaking, is an overly ugly and overly specific solution
What about String keys? Or some unknown type that may not even be Comparable<?>?

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?

On NavigableMap

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.

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.

On API providing only exclusive upper bound range queries

Does this highlight a problem with exclusive upper bound range queries?
How were inclusive range queries done in the past when exclusive upper bound is the only available functionality?

解决方案

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）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！

subMap