How to do inclusive range queries when only half-open range is supported (ala SortedMap.subMap)

Posted by polygenelubricants on Stack Overflow See other posts from Stack Overflow or by polygenelubricants
Published on 2010-05-18T13:31:43Z Indexed on 2010/05/18 13:50 UTC
Read the original article Hit count: 453

Filed under:
|
|

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


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?

© Stack Overflow or respective owner

Related posts about java

Related posts about api-design