Get values for keys within a range in Java

Question

Suppose I have a map in Java which looks like this:

{ 
 39:"39 to 41",
 41:"41 to 43",
 43:"43 to 45",
 45:">=45"
}

If the keys are in sorted order(either using treemap or linkedhashmap).Now if i try to get a value which is >=39 and <41.Then I should get the String "39 to 41".How do I do this efficiently?

Answer 1

I'm not sure that's going to be easy. One suggestion would be to "fill in the gaps", ie put in a value 40->"39 to 41" etc etc. I suppose that will only be possible if you know the whole range of numbers possible in the map.

Or mabybe something that overrides the get to check to see if the value is in the map, and expanding out until it finds something. I'm not sure that's going to be possible in its current guise, as you'd have to end up parsing the value strings.

Answer 2

You can recursively look for lower boundary.

public String descriptionFor(int value) {
    String description = map.get(value);
    return description == null ? descriptionFor(value--) : description;
}

You will need to have a minimum boundary.

Answer 3

With a sorted map, you could do something like that:

SortedMap<Integer,String> head = map.headMap(value+1);
if (head.isEmpty()) {
    return null;
} else {
    return head.get(head.lastKey());
}

Answer 4

You'd have to implement such a map yourself, I believe. You're right that it would have to be sorted; the implementation of get would have to iterate through the keys until it finds the largest key that is less than or equal to the argument.

If you subclass TreeMap it would initially appear that you can get this working via simply overriding the get() method. However, to maintain as much of the Map contract as possible you'll have to override other methods for consistency.

And what about e.g. containsKey()? Does your main contain a mapping for 40? If you return false, then a client can decide not to call get() based on this information; for these reason (and the formal definition) you have to return true. But then it makes it hard to determine whether the map "really contains" a given mapping; if you're looking to do something such as update without overwriting anything that already exists.

The remove() method might be tricky too. From my reading of the interface,

// Calling map.remove "Removes the mapping for a key from this map if it is present."
map.remove(x);

// Now that the mapping is removed, I believe the following must hold
assert map.get(x) == null;
assert map.containsKey(x);

Acting consistently here would be very tricky. If you have a mapping from 35-40 for example, and you call remove(38), then as I understand it you'd have to return null for any subsequent gets for the key 38, but return the aforementioned mapping for keys 35-37 or 39-40.

---

So while you can make a start on this by overriding TreeMap, perhaps the whole concept of Map is not quite what you want here. Unless you need this behaviour to slot into existing methods that take Map, it might be easier to create it yourself as a distinct class since it's not quite a Map, the way you're defining it.

Answer 5

Try Java 6 java.util.NavigableMap. http://download.oracle.com/javase/6/docs/api/java/util/NavigableMap.html.

In special use floorKey/floorEntry.

By example: floorKey(40) should return 39. floorEntry would return the value you are looking for.

Answer 6

It looks like you want more than a SortedMap; you want a NavigableMap! Specifically you can use the floorKey operation.

Here's an example:

    NavigableMap<Integer,String> map =
        new TreeMap<Integer, String>();

    map.put(0, "Kid");
    map.put(11, "Teens");
    map.put(20, "Twenties");
    map.put(30, "Thirties");
    map.put(40, "Forties");
    map.put(50, "Senior");
    map.put(100, "OMG OMG OMG!");

    System.out.println(map.get(map.floorKey(13)));     // Teens
    System.out.println(map.get(map.floorKey(29)));     // Twenties
    System.out.println(map.get(map.floorKey(30)));     // Thirties
    System.out.println(map.floorEntry(42).getValue()); // Forties
    System.out.println(map.get(map.floorKey(666)));    // OMG OMG OMG!

Note that there are also ceilingKey, lowerKey, higherKey, and also …Entry instead of …Key operations as well which returns a Map.Entry<K,V> instead of just the K.