Java SE 6 コレクション・フレームワークのメソッド (2) : Set, SortedSet, NavigableSet

今回は Set, SortedSet, NavigableSet の3つ（一覧）。　

メソッドは独断と偏見で幾つかにカテゴリー分けしてます：

要素の取得：iterator() や getter メソッドなど
要素の追加：add() や addAll() など
要素の削除：remove() や clear() など
要素の削除&取得：poll() など

メソッドの役割が分かりにくそうな場合のみ別途説明を。　その他注意点

拡張対象のインターフェースに定義されているメソッドには @Override アノテーションを付与してます。　ただし、インターフェースのメソッドに @Override を付与すると実際にはコンパイルエラーになります。
配列に関するメソッド toArray(..) はここでは無視してます。

Set インターフェース

Set は要素に重複を許さない Collection です。　Set は Collection から受け継いだメソッドしかなく、Set に新に定義されているメソッドはありません。

package java.util;
public interface Set<E> extends Collection<E>{
    @Override int size();
    @Override boolean isEmpty();
    @Override boolean contains(Object o);
    @Override boolean containsAll(Collection<?> c);

    // ********** 要素の取得 **********
    @Override Iterator<E> iterator();

    // ********** 要素の追加 **********
    @Override boolean add(E e);
    @Override boolean addAll(Collection<? extends E> c);

    // ********** 要素の削除 **********
    @Override boolean remove(Object o);
    @Override boolean removeAll(Collection<?> c);
    @Override boolean retainAll(Collection<?> c);
    @Override void clear();
}

SortedSet インターフェース

SortedSet は順序付けされた Set です。　任意の2つの（E 型の）要素に対して順序を評価する*1必要がありますが、これには2つの方法があります：

要素が Comparable インターフェースを実装しているなら、その順序を用いる（自然順序*2）。
SortedSet を実装したクラスをインスタンス化する際に、要素の型 (E) に対する Comparator オブジェクト(Comparator) を指定する。

SortedSet 内では、要素は小さい順 (ascending order) に並んでいます（first() メソッドは最も小さい要素を返します）。

package java.util;
public interface SortedSet<E> extends Set<E>{
    @Override int size();
    @Override boolean isEmpty();
    @Override boolean contains(Object o);
    @Override boolean containsAll(Collection<?> c);
    Comparator<? super E> comparator();

    // ********** 要素の取得 **********
    @Override Iterator<E> iterator();
    E first();
    E last();
    SortedSet<E> headSet(E toElement);
    SortedSet<E> subSet(E fromElement, E toElement);
    SortedSet<E> tailSet(E fromElement);

    // ********** 要素の追加 **********
    @Override boolean add(E e);
    @Override boolean addAll(Collection<? extends E> c);

    // ********** 要素の削除 **********
    @Override boolean remove(Object o);
    @Override boolean removeAll(Collection<?> c);
    @Override boolean retainAll(Collection<?> c);
    @Override void clear();
}

SortedSet に新に定義されているメソッドを簡単に解説。

comparator() の返り値は、自然順序を利用しているなら null、別途 Comparator を設定している場合はその Comparator オブジェクトです。
iterator() メソッドで返される Iterator は要素を小さい順に返します。

first(), last() メソッドを数学っぽく書くと次のようになります(s instanceof SortedSet)：

s.first() = min { x ∈ s }
s.last() = max { x ∈ s }

headSet(), subSet(), tailSet() も同様にすると

s.headSet(toE) = { x ∈ s | x < toE }
s.subSet(fromE, toE) = { x ∈ s | fromE ≦ x < toE }*3
s.tailSet(fromE) = { x ∈ s | fromE ≦ x }

fromE としているところはその要素も含み、toE となっているところはその要素は含みません。　また、これらの返り値の SortedSet はいわゆる「backed」で、一方への変更が他方へ反映されます。　使用の際はご注意を。

文章で説明するのは面倒なので、簡単なサンプルを。

SortedSet<Integer> intSet = new TreeSet<Integer>();
intSet.add(1);
intSet.add(2);
intSet.add(3);
intSet.add(4);
intSet.add(5);
        
System.out.println("first() : "+intSet.first());
System.out.println("last() : "+intSet.last());
System.out.println("headSet(3) : "+intSet.headSet(3));
System.out.println("subSet(2, 4) : "+intSet.subSet(2, 4));
System.out.println("tailSet(3) : "+intSet.tailSet(3));

これを実行すると

first() : 1
last() : 5
headSet(3) : [1, 2]
subSet(2, 4) : [2, 3]
tailSet(3) : [3, 4, 5]

となります。

NavigableSet インターフェース

NavigableSet は SortedSet に有用なメソッドを付け加えたものです。　Java SE 6 以降では SortedSet よりも NavigableSet を使いましょう*4。

package java.util;
public interface NavigableSet<E> extends SortedSet<E>{
    @Override int size();
    @Override boolean isEmpty();
    @Override boolean contains(Object o);
    @Override boolean containsAll(Collection<?> c);
    @Override Comparator<? super E> comparator();

    // ********** 要素の取得 **********
    @Override Iterator<E> iterator();
    Iterator<E> descendingIterator();

    @Override E first();
    E lower(E e);
    E floor(E e);
    E ceiling(E e);
    E higher(E e);
    @Override E last();

    @Override SortedSet<E> headSet(E toElement);
    @Override SortedSet<E> subSet(E fromElement, E toElement);
    @Override SortedSet<E> tailSet(E fromElement);

    NavigableSet<E> descendingSet();
    NavigableSet<E> headSet(E toElement, boolean inclusive);
    NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive);
    NavigableSet<E> tailSet(E fromElement, boolean inclusive);

    // ********** 要素の追加 **********
    @Override boolean add(E e);
    @Override boolean addAll(Collection<? extends E> c);

    // ********** 要素の削除 **********
    @Override boolean remove(Object o);
    @Override boolean removeAll(Collection<?> c);
    @Override boolean retainAll(Collection<?> c);
    @Override void clear();

    // ********** 要素の削除&取得 **********
    E pollFirst();
    E pollLast();
}

NavigableSet に新に定義されているメソッドを簡単に解説。

descendingXxxx() メソッド

descending とは大きい順のことです。　NavigableSet は小さい順に並んでいるので、descendingXxxx() は逆順のものを返すメソッドです。

descendingIterator() : 大きい順に要素を列挙する Iterator を返します。
descendingSet() : 大きい順に並んだ NavigableSet を返します。　この返り値の NavigableSet は「backed」です。　また、comparator() の返り値はもとの NavigableSet の順序の逆順を表す順序 (Comparator) です。

lower(), floor(), ceiling(), higher() メソッド

数学っぽく書くと次のようになります(s instanceof NavigableSet)：

s.lower(e) = max { x ∈ s | x < e }
s.floor(e) = max { x ∈ s | x ≦ e }
s.ceiling(e) = min { x ∈ s | x ≧ e }
s.higher(e) = min { x ∈ s | x > e }

floor(), ceiling() は引数の要素と同じ要素が返される可能性があります。　lower(), heigher() は引数と同じ要素は返されません。

返り値の具体的な値を見てみましょう。　まず、NavigableSet のインスタンス a, b をそれぞれ以下のように定義します（Java の定義ではありませんが、意味は分かると思います）：

a = {1, 2, 3, 4, 5}
b = {1, 2, 4, 5}

この a, b に対して各メソッドを呼び出した結果は以下のようになります：

メソッド呼び出し	a に対して呼び出した返り値	b に対して呼び出した返り値
lower(3)	2	2
floor(3)	3	2
ceiling(3)	3	4
higher(3)	4	4

headSet(), subSet(), tailSet() メソッド

NavigableSet で新に定義されている headSet(), subSet(), tailSet() メソッドは境界要素を含むかどうかを boolean 値で指定できるようになっています。　全ての場合を書くとかえって分かりにくいかも知れませんが、以下参照：

headSet(..)
- s.headSet(e, true) = { x ∈ s | x ≦ e }
- s.headSet(e, false) = { x ∈ s | x < e }
subSet(..)
- s.subSet(e1, true, e2, true) = { x ∈ s | e1 ≦ x ≦ e2 }
- s.subSet(e1, true, e2, false) = { x ∈ s | e1 ≦ x < e2 }
- s.subSet(e1, false, e2, true) = { x ∈ s | e1 < x ≦ e2 }
- s.subSet(e1, false, e2, false) = { x ∈ s | e1 < x < e2 }
tailSet(..)
- s.tailSet(e, true) = { x ∈ s | x ≧ e }
- s.tailSet(e, false) = { x ∈ s | x > e }

これらの返り値の NavigableSet も「backed」です。

pollFirst(), pollLast() メソッド

それぞれ first(), last() で返される要素を NavigableSet から削除し、メソッドの返り値として返します。

*1:数学的には、任意の2つの要素に対して順序を決定することができる順序を全順序 (total order) といい、全順序を設定された集合を全順序集合 (total ordered set) といいます。　SortedSet は全順序集合です。　ちなみに、数学で単に順序というと、任意の2つの要素を持ってきたときに大小関係が定まらない場合があってもよいことになっています。

*2:natural ordering。　要素が実装している Comparable インターフェースを順序評価に使用しているような順序。

*3:もし e1 と e2 が同じなら、空集合が返されます。

*4:Java SE 6 には SortedSet を実装していて NavigableSet を実装していない具象クラスがないので、あえて SortedSet を使用する必要はないでしょう。

倭マン's BLOG

くだらない日々の日記書いてます。　たまにプログラミング関連の記事書いてます。　書いてます。