Как получить предыдущие и следующие записи в TreeMap

Question

У меня есть отсортированная карта, и мне нужно найти для некоторого ключа ближайшие записи "до" и "после", которые полностью заполняют какое-то условие.

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

Это кажется неэффективным, потому что выше Entry в O(logN). Есть ли способ лучше?

Я хотел бы, чтобы TreeMap имел map.nextEntry(e), который работал бы в O(1), но, насколько я знаю, нет.

Answer 1

Проверь это: map.tailMap(key) дает вам SortedSet вид map содержит все ключи больше или равно key, map.tailMap(key).entrySet() тогда бы вам Set<Map.Entry> из всех записей в map чьи ключи больше или равны key, Согласно Javadoc, Iterator над этим Set возвращает записи в порядке возрастания ключа.

Так что, может быть, что-то вроде этого будет работать для вас:

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

Итератор по подмножеству ключей должен быть намного ближе к O(1), чем искать все ключи для каждого последовательно более высокого ключа.