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 fromfromKey
, inclusive, totoKey
, 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
assumesInteger
keys forto + 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 againstLong.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, andsubMap
would throwIllegalArgumentException: fromKey > toKey
- A generic version that also takes e.g.
- This, generally speaking, is an overly ugly and overly specific solution
- What about
String
keys? Or some unknown type that may not even beComparable<?>
?
- What about
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
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?