How to do inclusive range queries when only half-open range is supported (ala SortedMap.subMap)
- by polygenelubricants
On SortedMap.subMap
This is the API for SortedMap<K,V>.subMap:
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.
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?
Related questions
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?
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.
Related questions
Writing a synchronized thread-safety wrapper for 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?
