views:

91

answers:

2

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?
A: 

Perhaps you can do something like:

static <K, V> SortedMap<K,V>
subMapInclusive(SortedMap<K,V> map, K from, K to) {
  SortedMap<K,V> result = map.subMap(from, to);
  V last = map.get(to);
  if (last != null) result.put(to, last);
  return result;
}

EDIT: also TreeMap seems to have a subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) method; perhaps you can use that instead of a SortedMap.

Andrei Fierbinteanu
This wouldn't work because the definition of submap is that it is a view of the map, specifically in the API: "The returned map will throw an IllegalArgumentException on an attempt to insert a key outside its range." which would necessarily be true in the case of adding to.
M. Jessup
I didn't think about that. If you don't want to keep that property of the result I think you could do SortedMap<K,V> result = new TreeMap<K,V>(); result.putAll(map.subMap(from, to));but it's not exactly the prettiest thing.Otherwise you could try using NavigableMap which directly extends SortedMap and has the method with booleans (which is were TreeMap inherits it from). It really seem like it's a bad call from the designers that SortedMap doesn't also have the method with the booleans.
Andrei Fierbinteanu
+2  A: 

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);
}
M. Jessup
Nice thinking outside the box!
polygenelubricants