2

の上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}

いくつかの重要な観察を行う必要があります。

  • 良いニュースは、値のタイプは気にしないということですが...
  • subMapInclusiveInteger動作するためのキーを想定していますto + 1。
    • Longたとえばキーも使用する一般的なバージョンは使用できません（関連する質問を参照）
    • 言うまでもなく、代わりLongに比較する必要がありますLong.MAX_VALUE
    • キーとしての数値プリミティブボックスタイプなどのオーバーロードは、Byteすべて個別に記述する必要がありますCharacter
    • オーバーフローしてスローされるためtoInclusive == Integer.MAX_VALUE、特別なチェックを行う必要があります+1subMapIllegalArgumentException: fromKey > toKey
  • これは、一般的に言って、過度に醜く、過度に具体的な解決策です
    • Stringキーはどうですか？または、そうでさえないかもしれないいくつかの未知のタイプComparable<?>？

したがって、問題は次のとおりです。、、、を取り、包括的範囲のクエリを実行する一般的なメソッドを作成することは可能ですかsubMapInclusive？SortedMap<K,V>K fromKey, K toKeysubMap

関連する質問

の上NavigableMap

境界が包括的であるか排他的であるかを示すためにNavigableMap.subMap2つの追加の変数をとるオーバーロードがあることに注意する必要があります。booleanこれがで利用可能になっていたらSortedMap、上記のどれも尋ねられなかったでしょう。

したがってNavigableMap<K,V>、包括的範囲クエリを使用するのが理想的でしたが、 （とりわけ）Collectionsユーティリティメソッドを提供しますが、と同じ贅沢を提供することはできません。SortedMapNavigableMap

関連する質問

排他的な上限範囲クエリのみを提供するAPIの場合

  • これは、排他的な上限範囲クエリの問題を浮き彫りにしますか？
  • 排他的な上限が唯一の利用可能な機能である場合、過去に包括的範囲クエリはどのように実行されましたか？
4

3 に答える 3

3

一般的な包括的なサブマップの実装を次に示します。ここでは、マップがソートされているため、tailmap の時間の複雑さが低くなると想定しています。したがって、トリックは、tail から開始して返されたキーを確認し、それらのキーに基づいて、通常のサブマップである tail を取得します。または次のキーを持つサブマップ:

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);
}
于 2010-05-18T14:01:42.497 に答える
0

おそらく、次のようなことができます。

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, boolean fromInclusive, K toKey, boolean toInclusive) メソッドがあるようです。おそらく、SortedMap の代わりにそれを使用できます。

于 2010-05-18T13:46:36.970 に答える