ジェネリクスの続きです。今回は型パラメータについてもう少し詳しく説明します。
Java の型パラメータは任意のデータ型を表しますが、プログラムによってはデータ型に制約をかけたい場合があります。Java は型パラメータの指定で制約を設定することができます。
<T extends Foo> 型 T は型 Foo か、そのサブクラス
これを「型境界」といいます。Foo はクラスでもインターフェースでもかまいません。これにより、型 T は Foo を継承したサブクラスに制限されます。複数の制約をかけたい場合は型 (インターフェース) を & でつないでください。
他のプログラミング言語、たとえば Scala ではこれを「上限境界」といいます。Scala の場合、上限境界のほかに下限境界もありますが、Java には上限境界しかありません。ご注意くださいませ。
簡単な例を示しましょう。
jshell> class Foo {}
| 次を作成しました: クラス Foo
jshell> class Bar extends Foo {}
| 次を作成しました: クラス Bar
jshell> class Baz extends Bar {}
| 次を作成しました: クラス Baz
jshell> class Oops<T extends Bar> {}
| 次を作成しました: クラス Oops
jshell> var a = new Oops<Foo>()
| エラー:
| 型引数Fooは型変数Tの境界内にありません
| var a = new Oops<Foo>();
| ^-^
jshell> var b = new Oops<Bar>()
b ==> Oops@69d0a921
jshell> var c = new Oops<Baz>()
c ==> Oops@446cdf90
継承関係が Foo - Bar - Baz というクラスを作ります。クラス Oops はジェネリクスクラスで、型パラメータに T extends Bar を指定しているので、指定できる型は Bar または Bar のサブクラスである Baz になります。new Oops<Foo>() とするとエラーになりますが、new Oops<Bar>() と new Oops<Baz>() はインスタンスを生成することができます。
ジェネリクス型には直接的な継承関係はありませんが、型パラメータに渡すクラスの継承関係を使って、ジェネリクス型でも継承関係 (スーパークラスとサブクラスの関係) を考えることができます。たとえば、ジェネリクス型 Foo<T> を考えてみましょう。
リスト : クラス Foo の定義
class Foo<T> {
private T value;
Foo(T x) { value = x; }
T getValue() { return value; }
void setValue(T x) { value = x; }
}
型パラメータと同じ継承関係を持たせることを「共変 (covariant)」といいます。共変が許されると、次のようなプログラムが可能になります。
リスト : 共変
Foo<Object> a = new Foo<String>("hello");
String は Object のサブクラスなのでアップキャストが可能です。ジェネリクス型でもアップキャストができると便利な場合があります。
型パラメータと逆の継承関係を持たせることを「反変 (contravariant)」といいます。反変が許されると、次のようなプログラムが可能になります。
リスト : 反変 Foo<String> a = new Foo<Object>(new Object());
反変は直感に反するところがあって、ちょっと難しいかもしれません。メソッドの引数の型や返り値の型で反変を指定すると、メソッドの使い勝手がよくなる場合があります。
共変ではなく反変ではないことを「非変 (nonvariant)」とか「不変」と呼びます。これはジェネリクス型に継承関係を持たせない方法です。
Java の場合、ジェネリクス型は非変ですが配列は共変です。共変の場合、次のようなプログラムを書くことが可能です。
jshell> Integer [] a = new Integer [] {1, 2, 3, 4}
a ==> Integer[4] { 1, 2, 3, 4 }
jshell> Object [] b = a
b ==> Integer[4] { 1, 2, 3, 4 }
jshell> b[0] = 10
$9 ==> 10
jshell> for (Object x: b) System.out.println(x)
10
2
3
4
Integer の配列 a を作成します。変数 b を Object の配列に宣言すると、変数 b に a の配列を代入することができます。配列の値を Integer 以外の値に書き換えなければ、このプログラムでも正常に動作します。
ところが、配列 b は Object で宣言しているので、そこに文字列を代入することができます。次の例を見てください。
jshell> b[0] = "hello, world" | 例外java.lang.ArrayStoreException: java.lang.String | at (#11:1)
このように、b[0] に文字列をセットすると例外が送出されます。これをプログラムすると次のようになります。
リスト : Java の配列は共変 (実行時エラー)
public class sample120 {
public static void main(String[] args){
Integer [] a = new Integer [] {1, 2, 3, 4};
Object [] b = a;
b[0] = "hello, world";
for (Object x: b) System.out.println(x);
}
}
実際、コンパイルしてもエラーにはならないのですが、実行すると例外が送出されます。
$ javac sample120.java
$ java sample120
Exception in thread "main" java.lang.ArrayStoreException: java.lang.String
at sample120.main(sample120.java:5)
Java のジェネリクス型は非変に設定されているので、このような危険なプログラムを書くことはできません。
リスト : ジェネリクス型は非変
class Foo { }
class Bar extends Foo { }
class Baz extends Bar { }
class Oops<T> { }
public class sample121 {
public static void main(String[] args) {
var a = new Oops<Foo>();
a = new Oops<Bar>();
System.out.println(a);
}
}
$ javac sample121.java
sample123.java:9: エラー: 不適合な型: Oops<Bar>をOops<Foo>に変換できません:
a = new Oops<Bar>();
^
エラー1個
もちろん、配列に書き込みを行わなければ、共変でも問題は発生しません。一般に、immutable なデータ構造は共変に、mutable なデータ構造は非変に設定したほうがよいとされています。
Java の場合、? という型指定を使うと、共変と反変を指定することができます。? を「ワイルドカード」といいます。? は任意の型を表します。たとえば、Foo<?> で宣言された変数には、Foo<Integer> でも Foo<Double> でも Foo のインスタンスであれば何でもセットすることができます。簡単な例を示しましょう。
リスト : ワイルドカード (sample122.java)
class Foo<T> {
private T x;
Foo(T a) { x = a; }
T getX() { return x; }
void setX(T a) { x = a; }
}
public class sample122 {
public static void main(String[] args) {
Foo<?> a = new Foo<Integer>(123);
int n = (Integer)a.getX(); // 型が不定なのでキャストが必要
System.out.println(n);
a = new Foo<Double>(1.2345);
double m = (Double)a.getX();
System.out.println(m);
a = new Foo<String>("hello!");
System.out.println(a.getX());
// a.setX("oops!"); コンパイルエラー
// 型が不定なので特定の型を書き込むことはできない
// System.out.println(a.getX());
}
}
$ javac sample122.java $ java sample122 123 1.2345 hello!
変数 a の型をワイルドカードを使って Foo<?> と宣言すると、Foo のインスタンスであれば何でも a に代入することができます。ただし、データ型の情報が失われるため、メソッド getX() で取り出した値の型は Object として扱われることになり、ダウンキャストが必要になります。同様に、型が特定できないため、setX() で特定のデータを書き込むことはできません。コンパイルエラーになります。
Java の場合、ワイルドカードにも制約をかけることができます。
1 を「上限境界ワイルドカード」といい、共変に相当します。2 を「下限境界ワイルドカード」といい、反変に相当します。簡単な例を示しましょう。
リスト : 共変と反変の指定 (sample123.java)
class Foo { }
class Bar extends Foo { }
class Baz extends Bar { }
class Oops<T> {
private T value;
Oops(T x) { value = x; }
T getValue() { return value; }
void setValue(T x) { value = x; }
}
public class sample123 {
public static void main(String[] args) {
// Oops<? extends Bar> a = new Oops<Foo>(new Foo()); コンパイルエラー
Oops<? extends Bar> b = new Oops<Baz>(new Baz());
Bar obj1 = b.getValue(); // OK キャスト不要 (アップキャスト)
System.out.println(obj1);
// b.setValue(new Bar()); コンパイルエラー
Oops<? super Bar> c = new Oops<Foo>(new Foo());
// Oops<? super Bar> d = new Oops<Baz>(new Baz()); コンパイルエラー
c.setValue(new Bar()); // 書き込みは OK
// c.setValue(new Foo()); Bar 以外はコンパイルエラー
Bar obj2 = (Bar)c.getValue(); // キャストが必要になる
System.out.println(obj2);
}
}
$ javac sample123.java $ java sample123 Baz@4d7e1886 Bar@3cd1a2f1
変数 a, b は Oops<? extends Bar> と宣言しているので共変です。Oops<Baz> のインスタンスは代入できますが、Oops<Foo> のインスタンスは代入できません。b.getValue() の返り値は Bar 型の変数にキャストせずに代入することができます。共変の場合、値を書き換えることはできません。b.setValue(new Bar()) を呼び出すとコンパイルエラーになります。
変数 c, d は Oops<? super Bar> と宣言しているので反変です。Oops<Foo> のインスタンスは代入できますが、Oops<Baz> のインスタンスは代入できません。反変の場合、制約で宣言したデータ型は代入することができます。したがって、c.setValue() は正常に動作します。ただし、Bar 以外のデータ型を渡すとコンパイルエラーになります。c.getValue() の返り値はデータ型が Bar と特定できないので、Object として扱われます。このため、ダウンキャストが必要になり、データ型に対して安全なプログラムにはなりません。
さて、これだけでは共変と反変がなんの役に立つのかよくわかりませんね。そこで、簡単な使用例を示しましょう。前回作成した連結リスト SinglyLinkedList<E> にメソッド pushAll(() と popAll() を追加します。ここで、メソッドの仕様を次のように定義すると使い勝手が悪くなります。
pushAll() はコレクション c のすべての要素を連結リストの先頭に追加します。popAll() は連結リストの先頭から要素を取り出して、それをコレクション c に追加します。ここで、上記のように引数の型を Collection<E> とすると、要素が同じデータ型のコレクションしか引数に渡すことができません。このような場合、共変と反変が役に立ちます。
pushAll() の場合、コレクションの要素が連結リストの要素のサブクラスであれば、連結リストに代入することができるはずです。これは引数の型を共変に設定すれば実現できます。popAll() の場合、コレクションの要素が連結リストの要素のスーパークラスであれば、連結リストの要素をコレクションに代入することができるはずです。これは引数の型を反変に設定すれば実現できます。したがって、メソッドの仕様は次のようになります。
これをプログラムすると次のようになります。
リスト : pushAll() と popAll()
// コレクションの要素をリストに追加
void pushAll(Collection<? extends E> c) {
for (E x: c) {
head.setLink(new Cell(x, head.getLink()));
}
}
// リストの要素を取り出してコレクションに追加
void popAll(Collection<? super E> c) {
for (E x: this) {
c.add(x);
}
clear();
}
pushAll() の引数は Collection<? extends E> と宣言されているので、要素は E または E のサブクラスであることが保証されています。for 文で要素を変数 x に取り出すとき、キャストせずにそのまま行うことができます。同様に、popAll() の引数は Collection<? super E> と宣言されているので、要素は E または E のスーパークラスであることが保証されています。メソッド add() で要素を追加するとき、アップキャストになるので安全に行うことができます。
それでは実際に試してみましょう。
リスト : 簡単なテスト
class Foo {}
class Bar extends Foo {}
class Baz extends Bar {}
public class slist3 {
public static void main(String[] args) {
var xs = new ArrayList<Baz>() {
{
add(new Baz());
add(new Baz());
add(new Baz());
}
};
System.out.println(xs);
var ys = new SinglyLinkedList<Bar>();
ys.pushAll(xs);
System.out.println(ys);
var zs = new ArrayList<Foo>();
ys.popAll(zs);
System.out.println(ys);
System.out.println(zs);
}
}
$ javac slist3.java $ java slist3 [Baz@4d7e1886, Baz@3cd1a2f1, Baz@2f0e140b] (Baz@2f0e140b Baz@3cd1a2f1 Baz@4d7e1886) () [Baz@2f0e140b, Baz@3cd1a2f1, Baz@4d7e1886]
変数 xs には Baz のインスタンスを格納した ArrayList をセットし、変数 ys には Bar を格納する連結リストをセットします。Baz は Bar のサブクラスなので、ys.pushAll(xs) はコンパイル可能で正常に動作します。次に、Foo のインスタンスを格納する ArrayList を変数 zs にセットします。Foo は Bar のスーパークラスなので、ys.popAll(zs) はコンパイル可能で正常に動作します。
このように、共変と反変を設定すると、メソッドの使い勝手を改善することができます。
List<E> を継承しているコレクションクラスでは、Collections クラスのメソッド binarySearch() で二分探索、sort() でソートすることができます。このとき、型 E は Comparable<E> を継承する必要があります。Comparable<E> は Comparable のジェネリクス版です。宣言されているメソッドは compareTo() だけです。
int compareTo(E o);
Comparable と違って引数の型が E になります。compareTo() は自分自身のオブジェクト (this) と引数 o を比較し、o が大きい場合は負の整数、等しい場合は 0、小さい場合は正の整数を返します。
Collections.sort() は次のように定義されています。
static <E extends Comparable<? super E>> void sort(List<E> list)
ここで型 E の制約に注意してください。制約は Comparable<E> で十分なように思えます。実際、compareTo() を実装したクラスであれば、問題なくコンパイルすることができます。ところが、継承を考えるとうまくいかない場合があるのです。次のリストを見てください。
リスト : Comparable<E> の使用 (sample124.java)
import java.util.ArrayList;
import java.util.Collections;
class Foo implements Comparable<Foo> {
private int x;
Foo(int n) { x = n; }
int getX() { return x; }
void setX(int n) { x = n; }
public int compareTo(Foo o) {
int r = x - o.x;
if(r < 0) return -1;
else if (r == 0) return 0;
return 1;
}
public String toString() {
return "Foo(" + x + ")";
}
}
class Bar extends Foo {
Bar(int n) { super(n); }
@Override
public String toString() {
return "Bar(" + getX() + ")";
}
}
クラス Foo で Comparable<E> を継承する場合は型 E に Foo を指定します。それから、メソッド compareTo() を実装します。クラス Baz は Foo を継承しているので、Comparable<Foo> も継承します。ここで、Bar のインスタンスをソートすることを考えてみましょう。
sort() の型 E の制約を Comparable<E> として Bar をソートする場合、インターフェース Comparable<Bar> が必要になります。ところが、Bar に実装されているのは Comparable<Foo> しかありません。この場合はコンパイルエラーになります。
制約を Comparable<? super E> とした場合、Bar のスーパークラス Foo も許されので Comparable<Foo> が制約になります。この場合、コンパイルは通って正常に実行することができます。
それでは実際に試してみましょう。
リスト : 簡単な実行例
public class sample124 {
public static void main(String[] args) {
var xs = new ArrayList<Foo>() {
{
add(new Foo(3));
add(new Foo(1));
add(new Foo(2));
}
};
System.out.println(xs);
Collections.sort(xs);
System.out.println(xs);
var ys = new ArrayList<Bar>() {
{
add(new Bar(2));
add(new Bar(3));
add(new Bar(1));
}
};
System.out.println(ys);
Collections.sort(ys);
System.out.println(ys);
}
}
$ javac sample124.java $ java sample124 [Foo(3), Foo(1), Foo(2)] [Foo(1), Foo(2), Foo(3)] [Bar(2), Bar(3), Bar(1)] [Bar(1), Bar(2), Bar(3)]
このように、Foo のサブクラス Bar のインスタンスでもソートすることができます。
最後に簡単な例題として、「連想リスト (association list : a-list)」を作ってみましょう。連想リストは Lisp / Scheme でよく用いられるデータ構造で、Java では Pair を要素とするコレクションで簡単に実装することができます。次の図を見てください。
┌────┬────┬────┬──→ データ
│ │ │ │
連想リスト => [("a", 1), ("b", 2), ("c", 3), ("d", 4)]
│ │ │ │
└────┴────┴────┴──→ キー
図 : 連想リストの構造
上図の場合、文字列 "a", "b", "c", "d" がキーで、整数 1, 2, 3, 4 がデータとなります。一般に、キーとその値を格納するコレクションを「マップ (map)」と呼びます。Java のライブラリには、インターフェース Map<K, V> が用意されています。K がキーで、V が値を表す型パラメータです。具体的には、クラス HashMap<K, V> や TreeMap<K, V> を使います。HashMap はアルゴリズムにハッシュ法、TreeMap は二分木 (平衡木) が用いられています。
連想リストは線形探索になるので、要素数が多くなると実行時間は遅くなります。HashMap や TreeMap のほうが高速に処理できるので、Java で連想リストを使う機会はほとんどないと思いますが、Java のお勉強ということで、あえて連想リストのプログラムを作ってみましょう。
プログラムは簡単です。次のリストを見てください。
リスト : 連想リスト
class AssocList<K, V> {
private SinglyLinkedList<Pair<K, V>> contents;
public AssocList() {
contents = new SinglyLinkedList<Pair<K, V>>();
}
// key の探索
private Pair<K, V> assoc(K key) {
for (Pair<K, V> p: contents) {
if (key.equals(p.getFst()) && p.getSnd() != null) return p;
}
return null;
}
// key があるか
public boolean hasKey(K key) {
return assoc(key) != null;
}
// 追加
public void add(K key, V value) {
Pair<K, V> p = assoc(key);
if (p == null)
contents.insert(0, new Pair<K,V>(key, value));
else
p.setSnd(value);
}
// 取得
public V get(K key) {
Pair<K, V> p = assoc(key);
return p != null ? p.getSnd() : null;
}
// 削除 (null に書き換えるだけ)
public V remove(K key) {
Pair<K, V> p = assoc(key);
if (p != null) {
V v = p.getSnd();
p.setSnd(null);
return v;
}
return null;
}
// 空にする
public void clear() { contents.clear(); }
}
クラス AccocList のフィールド変数 contents にコレクションクラスをセットします。今回は SinglyLinedList を使いましたが、他のコレクションクラスを使っても簡単に実装することができます。キーを探索するため、作業用のメソッド assoc() を定義します。名前は Lisp / Scheme から拝借しました。String 以外の参照型データの場合、演算子 == による等値の判定はオブジェクトのアドレスが用いられます。オブジェクトに格納されている値を比較したい場合はメソッド equals() を使ってください。
assoc() を定義すると、あとのメソッドは簡単です。ただし、注意点が一つあって、今回は remove() でデータを削除するとき、連結リストから削除するのではなく、値を null に書き換えることで対応しています。このため、キーの有無を判定するメソッド hasKey() では、assoc() でキーを見つけたあと、値が null でないことを確認しています。あとは簡単なので、詳細はプログラムリストをお読みください。
それでは実際に実行してみましょう。
リスト : 連想リストのテスト
static void testAlist() {
var alist = new AssocList<String, Integer>();
alist.add("foo", 10);
alist.add("bar", 20);
alist.add("baz", 30);
alist.add("oops", 40);
System.out.println(alist.get("foo"));
System.out.println(alist.get("bar"));
System.out.println(alist.get("baz"));
System.out.println(alist.get("oops"));
alist.add("bar", 200);
System.out.println(alist.get("bar"));
System.out.println(alist.hasKey("FOO"));
System.out.println(alist.hasKey("baz"));
System.out.println(alist.remove("baz"));
System.out.println(alist.hasKey("baz"));
System.out.println(alist.get("baz"));
}
10 20 30 40 200 false true 30 false null
正常に動作していますね。
//
// slist3.java : 片方向連結リスト (ジェネリクス版)
//
// Copyright (C) 2016-2021 Makoto Hiroi
//
import java.util.Iterator;
import java.util.ArrayList;
import java.util.List;
import java.util.Collection;
// 例外クラス
class ListIndexOutOfBoundsException extends IndexOutOfBoundsException {
public ListIndexOutOfBoundsException() { }
public ListIndexOutOfBoundsException(String msg) { super(msg); }
}
// 連結リスト
class SinglyLinkedList<E> implements Iterable<E> {
// セル
private class Cell {
// フィールド変数
private E value;
private Cell link;
// コンストラクタ
Cell(E item, Cell xs) {
value = item;
link = xs;
}
// アクセスメソッド
E getValue() { return value; }
Cell getLink() { return link; }
void setValue(E item) { value = item; }
void setLink(Cell xs) { link = xs; }
}
// フィールド変数
private Cell head;
private int size;
// コンストラクタ
SinglyLinkedList() {
head = new Cell(null, null); // ヘッダーセル
size = 0;
}
// n 番目のセルを求める
private Cell nth(int n) {
int i = -1;
Cell xs = head;
while (xs != null) {
if (n == i) return xs;
i++;
xs = xs.getLink();
}
throw new ListIndexOutOfBoundsException("SinglyLinkedList");
}
// 参照
public E get(int n) {
return nth(n).getValue();
}
// 挿入
public void insert(int n, E item) {
Cell xs = nth(n - 1);
Cell ys = new Cell(item, xs.getLink());
xs.setLink(ys);
size++;
}
// 削除
public E remove(int n) {
Cell xs = nth(n - 1);
Cell ys = xs.getLink();
if (ys == null) {
throw new ListIndexOutOfBoundsException("SinglyLinkedList");
}
xs.setLink(ys.getLink());
size--;
return ys.getValue();
}
// 書き換え
public E set(int n, E item) {
Cell xs = nth(n);
E old = xs.getValue();
xs.setValue(item);
return old;
}
// 空にする
public void clear() {
head.setLink(null);
size = 0;
}
// 個数を求める
public int size() { return size; }
// 空リストか
public boolean isEmpty() { return size == 0; }
// List 型に変換する
public List<E> toList(){
List<E> a = new ArrayList<>();
Cell xs = head.getLink();
for (int i = 0; i < size; i++) {
a.add(xs.getValue());
xs = xs.getLink();
}
return a;
}
// 文字列に変換
public String toString(){
String buff = "(";
Cell xs = head.getLink();
while (xs != null) {
buff += xs.getValue().toString();
xs = xs.getLink();
if (xs != null) buff += " ";
}
buff += ")";
return buff;
}
// イテレータ
public Iterator<E> iterator() {
// 無名クラス
return new Iterator<E>() {
Cell xs = head.getLink();
public boolean hasNext() { return xs != null; }
public E next() {
E item = xs.getValue();
xs = xs.getLink();
return item;
}
public void remove() {
throw new UnsupportedOperationException();
}
};
}
// コレクションの要素をリストに追加
void pushAll(Collection<? extends E> c) {
for (E x: c) {
head.setLink(new Cell(x, head.getLink()));
}
}
// リストの要素を取り出してコレクションに追加
void popAll(Collection<? super E> c) {
for (E x: this) {
c.add(x);
}
clear();
}
}
class Pair<T, U> {
private T fst;
private U snd;
// コンストラクタ
Pair(T x, U y) {
fst = x;
snd = y;
}
// メソッド
T getFst() { return fst; }
U getSnd() { return snd; }
void setFst(T x) { fst = x; }
void setSnd(U y) { snd = y; }
// 文字列に変換
public String toString() {
return "(" + fst.toString() + ", " + snd.toString() + ")";
}
}
// 連想リスト
class AssocList<K, V> {
private SinglyLinkedList<Pair<K, V>> contents;
public AssocList() {
contents = new SinglyLinkedList<Pair<K, V>>();
}
// key の探索
private Pair<K, V> assoc(K key) {
for (Pair<K, V> p: contents) {
if (key.equals(p.getFst()) && p.getSnd() != null) return p;
}
return null;
}
// key があるか
public boolean hasKey(K key) {
return assoc(key) != null;
}
// 追加
public void add(K key, V value) {
Pair<K, V> p = assoc(key);
if (p == null)
contents.insert(0, new Pair<K,V>(key, value));
else
p.setSnd(value);
}
// 取得
public V get(K key) {
Pair<K, V> p = assoc(key);
return p != null ? p.getSnd() : null;
}
// 削除 (null に書き換えるだけ)
public V remove(K key) {
Pair<K, V> p = assoc(key);
if (p != null) {
V v = p.getSnd();
p.setSnd(null);
return v;
}
return null;
}
// 空にする
public void clear() { contents.clear(); }
}
class Foo { }
class Bar extends Foo { }
class Baz extends Bar { }
// 簡単なテスト
public class slist3 {
// 連想リストのテスト
static void testAlist() {
var alist = new AssocList<String, Integer>();
alist.add("foo", 10);
alist.add("bar", 20);
alist.add("baz", 30);
alist.add("oops", 40);
System.out.println(alist.get("foo"));
System.out.println(alist.get("bar"));
System.out.println(alist.get("baz"));
System.out.println(alist.get("oops"));
alist.add("bar", 200);
System.out.println(alist.get("bar"));
System.out.println(alist.hasKey("FOO"));
System.out.println(alist.hasKey("baz"));
System.out.println(alist.remove("baz"));
System.out.println(alist.hasKey("baz"));
System.out.println(alist.get("baz"));
}
public static void main(String[] args) {
var xs = new ArrayList<Baz>() {
{
add(new Baz());
add(new Baz());
add(new Baz());
}
};
System.out.println(xs);
var ys = new SinglyLinkedList<Bar>();
ys.pushAll(xs);
System.out.println(ys);
var zs = new ArrayList<Foo>();
ys.popAll(zs);
System.out.println(ys);
System.out.println(zs);
testAlist();
}
}