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

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.

Answer 2

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 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());
}