先週はナビゲーション可能なマップであるNavigableMapインタフェースを紹介しました。今週はそのセット版であるjava.util.NavigableSetインタフェースです。
NavigableMapインタフェースではキーのナビゲーションが可能でした。一方のNavigableSetインタフェースでは保持している要素のナビゲーションが可能です。ナビゲーションするためには要素がソートされている必要があります。NavigableSetインタフェースもNavigableMapインタフェースと同様にSortedSetインタフェースの派生インタフェースとなっています。
NavigableSetインタフェースの使い方はNavigableMapインタフェースが理解できていれば、簡単です。表1にNavigableSetインタフェースのナビゲーションメソッドを示しました。
| メソッド名 | 説明 |
|---|---|
| lower(e) | 指定された要素よりも小さい要素を返します |
| floor(e) | 指定された要素と等しいか小さい要素を返します |
| ceiling(e) | 指定された要素と等しいか大きい要素を返します |
| higher(e) | 指定された要素よりも大きい要素を返します |
これらのナビゲーションメソッドは相当する要素がない場合はnullを返します。
また、セットの一部を取得するためのメソッドはSortedSetインタフェースのheadSetメソッド、tailSetメソッド、subSetメソッドがオーバロードされています。これもNavigableMapインタフェースと同様です。
サンプルのソース NavigableSetSample.java
表1に示したようなメソッドを使うために、まずセットを用意します。NavigableSetインタフェースの実装クラスとしてはjava.util.TreeSetクラス、java.util.concurrent.ConcurrentSkipListSetクラスがあります。ここではTreeSetクラスを使用しました。
NavigableSet<String> set = new TreeSet<String>();
set.add("Echo");
set.add("Mike");
set.add("Alpha");
set.add("Sierra");
set.add("Kilo");
set.add("India");
set.add("Quebec");
set.add("Charlie");
set.add("Golf");
set.add("Oscar");
まずナビゲーションメソッド群です。
// 要素がセットに含まれている場合
System.out.println("lower Golf: " + set.lower("Golf"));
System.out.println("floor Golf: " + set.floor("Golf"));
// 要素がセットに含まれていない場合
System.out.println("lower Foxtrot: " + set.lower("Foxtrot"));
System.out.println("floor Foxtrot: " + set.floor("Foxtrot"));
// 要素がセットに含まれている場合
System.out.println("cieling India: " + set.ceiling("India"));
System.out.println("heigher India: " + set.higher("India"));
// 要素がセットに含まれていない場合
System.out.println("cieling Juliet: " + set.ceiling("Juliet"));
System.out.println("heigher Juliet: " + set.higher("Juliet"));
これに対応する出力結果を次に示します。
lower Golf: Echo floor Golf: Golf lower Foxtrot: Echo floor Foxtrot: Echo cieling India: India heigher India: Kilo cieling Juliet: Kilo heigher Juliet: Kilo
次にセットの部分セットを取得するメソッド群を試してみましょう。
System.out.println("headSet: Echoを含まない");
System.out.println(set.headSet("Echo", false));
System.out.println("headSet: Echoを含む");
System.out.println(set.headSet("Echo", true));
System.out.println("tailSet: Oscarを含まない");
System.out.println(set.tailSet("Oscar", false));
System.out.println("tailSet: Oscarを含む");
System.out.println(set.tailSet("Oscar", true));
System.out.println("subSet: Kilo, Oscarを含まない");
System.out.println(set.subSet("Kilo", false, "Oscar", false));
System.out.println("subSet: Kilo, Oscarを含む");
System.out.println(set.subSet("Kilo", true, "Oscar", true));
出力結果を以下に示します。
headSet: Echoを含まない [Alpha, Charlie] headSet: Echoを含む [Alpha, Charlie, Echo] tailSet: Oscarを含まない [Quebec, Sierra] tailSet: Oscarを含む [Oscar, Quebec, Sierra] subSet: Kilo, Oscarを含まない [Mike] subSet: Kilo, Oscarを含む [Kilo, Mike, Oscar]
NavigableMapインタフェースを理解していれば、このような出力結果が得られることは容易に想像がつきます。
二分探索
ここではちょっと趣向を変えて、簡単な数当てゲームを作ってみました。
サンプルのソース Numbers.java
このサンプルを実行すると10個の整数を表示します。この中に当たりが1つ含まれます。それを当てるというゲームです。以下に実際のゲームの様子を示しました。
C:\>java Numbers 1回目 候補: 16 20 27 31 36 54 70 89 96 99 数字を入力してください> 36 36 小さいです 2回目 候補: 54 70 89 96 99 数字を入力してください> 89 89 正解です!
候補となる数字はソートされており、回答を行うと当たりの数字と比較したヒントが出ます。次の回答時には前回のヒントに応じて候補が絞られていきます。
候補とヒントをまとめてNavigableMapオブジェクトに保持させています。ヒントはHint列挙型で表しています。
enum Hint {
BIG {
public String toString(){
return "大きいです";
}
},
SMALL {
public String toString(){
return "小さいです";
}
},
CORRECT {
public String toString(){
return "正解です!";
}
}
};
toStringメソッドをオーバーライドして、日本語でヒントが出力できるようにしました。NavigableMapオブジェクトには候補となる数字をキー、このHint列挙型をバリューにしています。
回答とそれに対して候補数字を絞り込む部分を次に示します。
private void startGame(NavigableMap<Integer, Hint> map) {
Console console = System.console();
for (int i = 0; i < NUMBER_OF_GAME; i++) {
console.printf("%n%d回目 候補:", i + 1);
for (Integer number: map.keySet()) {
console.printf("%3d", number);
}
String input = console.readLine("%n数字を入力してください> ");
int inputNumber = Integer.parseInt(input);
Hint hint = map.get(inputNumber);
if (hint == null) {
console.printf("%s は候補にありません%n", input);
continue;
} else {
console.printf("%s %s%n", input, hint);
}
if (hint == Hint.BIG) {
map = map.headMap(inputNumber, false);
} else if (hint == Hint.SMALL) {
map = map.tailMap(inputNumber, false);
} else {
return;
}
}
console.printf("%n残念でした%n");
}
ここでは、標準入出力からの入出力にjava.io.Concoleクラスを使用しています。Consoleクラスに関しては第37回 コンソールからパスワードを入力するにはをご覧ください。
回答に対するヒントがhint変数です。この値がBIGの場合、正解は回答よりも小さい値なので、赤字で示したように回答よりも前の部分だけをmapに代入しています。逆にSMALLの場合は、正解は回答よりも大きいので、回答よりも後ろの部分をmapに代入します。
これで、候補の絞込みができるわけです。
