How to get previous and next entries in TreeMap

Question

I have a sorted map, and I'm looking need to find for some key the nearest 'before' and 'after' entries that full-fill some condition.

Entry findAfter(TreeMap map, Key key, Predicate p) {
    Entry e = map.higherEntry(key);
    while (e!=null && !p.test(e.getValue())
         e = map.higherEntry(e.getKey());
    return e;
}

This seems inefficient because higherEntry in O(logN). Is there a better way?

I wish TreeMap had map.nextEntry(e) that would work in O(1), but as far as I know, there isn't.

Answer 1

Check this: map.tailMap(key) gives you a SortedSet view of map containing all keys greater than or equal to key. map.tailMap(key).entrySet() would then get you a Set<Map.Entry> of all the entries in map whose keys are greater than or equal to key. According to the javadoc, an Iterator over that Set returns the entries in ascending key order.

So maybe something like this would work for you:

Entry findAfter(TreeMap map, Key key, Predicate p) {
    for (Entry e : map.tailMap().entrySet()) {
        if (p.test(e.getValue() && 
            !e.getKey().equals(key))
             return e;
    }
    return null;
}

An iterator over a subset of the keys has got to be a lot closer to O(1) than searching all the keys for each successively higher key.