Как выполнять запросы с включенным диапазоном, когда поддерживается только полуоткрытый диапазон (аля SortedMap.subMap) - PullRequest
Новая
       8

Как выполнять запросы с включенным диапазоном, когда поддерживается только полуоткрытый диапазон (аля SortedMap.subMap)

2 голосов
/ 18 мая 2010

Вкл. SortedMap.subMap

Это API для SortedMap<K,V>.subMap:

SortedMap<K,V> subMap(K fromKey, K toKey): Возвращает вид части этой карты, ключи которой находятся в диапазоне от fromKey включительно до toKey, исключая.

Эта всеобъемлющая нижняя граница, исключительная комбинированная верхняя граница («полуоткрытый диапазон») - это то, что распространено в Java, и, хотя она имеет свои преимущества, она также имеет свои причуды, как мы скоро увидим.

Следующий фрагмент иллюстрирует простое использование 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}"

Последняя строка важна: 7=Seven исключен из-за исключительной верхней границы subMap. Теперь предположим, что нам на самом деле нужна верхняя граница включительно , тогда мы можем попытаться написать вспомогательный метод, подобный этому: 

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

Затем, продолжая приведенный выше фрагмент, мы получим: 

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}

Необходимо сделать пару ключевых замечаний:

  • Хорошей новостью является то, что нам не важен тип значений, но ...
  • subMapInclusive предполагает, что Integer ключи для to + 1 работают.
    • Универсальная версия, которая также принимает, например, Long Ключи невозможны (см. Связанные вопросы)
    • Не говоря уже о том, что для Long нам нужно сравнить с Long.MAX_VALUE вместо
    • Перегрузки для числовых примитивов в штучной упаковке Byte, Character и т. Д., Как ключи, все должны быть написаны индивидуально
    • Специальная проверка должна быть сделана для toInclusive == Integer.MAX_VALUE, потому что +1 переполнится, а subMap выдаст IllegalArgumentException: fromKey > toKey
  • Это, вообще говоря, слишком уродливое и чрезмерно конкретное решение
    • А как насчет String ключей? Или какой-то неизвестный тип, который может даже не быть Comparable<?>?

Таким образом, вопрос заключается в следующем: можно ли написать общий метод subMapInclusive, который принимает SortedMap<K,V> и K fromKey, K toKey и выполняет subMap запросы с включенным диапазоном?

Похожие вопросы

Вкл. NavigableMap

Следует отметить, что существует перегрузка NavigableMap.subMap, которая принимает две дополнительные переменные boolean, чтобы указать, являются ли границы включающими или исключающими. Если бы это было доступно в SortedMap, то ничего из вышеперечисленного даже не спросили бы.

Поэтому работа с NavigableMap<K,V> для запросов с включенным диапазоном была бы идеальной, но в то время как Collections предоставляет служебные методы для SortedMap (среди прочего), нам не предоставляется такая же роскошь с NavigableMap .

Похожие вопросы

В API, обеспечивающем только исключительные запросы верхнего диапазона

  • Подсвечивает ли это проблему с исключительными запросами верхнего диапазона?
  • Как в прошлом выполнялись запросы с включенным диапазоном, когда единственная доступная функциональность - исключительная верхняя граница?

Ответы [ 3 ]

3 голосов
/ 18 мая 2010

Вот моя реализация для общей включающей подкарты. Здесь я предполагаю, что, поскольку карты отсортированы, временная сложность хвостовой карты будет низкой, поэтому задача состоит в том, чтобы начать с хвоста и посмотреть на возвращенные ключи, а затем на основе этих ключей либо взять хвост, обычную подкарту, или подкарту со следующим ключом: 

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);
}
1 голос
/ 11 февраля 2014

Как насчет использования Guava's Maps.filterKeys? 

Maps.filterKeys(map, Range.closed(0, 4)); //includes 1 and 3
Maps.filterKeys(map, Range.closed(3, 7)); //includes 3, 5, and 7

Аргументы предиката Range должны реализовывать Comparable, но вы также можете использовать Predicates.in для фильтрации по коллекции: 

Set<Integer> filterSet = Sets.newHashSet();
filterSet.add(3);
filterSet.add(5);
filterSet.add(7);
Maps.filterKeys(map, Predicates.in(filterSet)); //includes 3, 5, and 7
0 голосов
/ 18 мая 2010

Возможно, вы можете сделать что-то вроде: 

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

РЕДАКТИРОВАТЬ: также TreeMap, кажется, имеет subMap (K fromKey, логическое fromInclusive, K toKey, логическое toInclusive) метод; возможно, вы можете использовать это вместо SortedMap.

...