Iteratorパターン

「デザインパターン入門」の例について

Iteratorパターンについて、下記の本（以下「デザインパターン入門」と記す）

Java言語で学ぶデザインパターン入門

結城浩著

ソフトバンクパブリッシング株式会社

で取り上げられている例は、Iteratorパターンを使うケースではないように思う。

「デザインパターン入門」では、本の集合を表すBookShelfクラスを作っている。このクラスは、下記のメソッドを持つ。

int getLength ( ): 本の冊数を返す。
Book getBookAt ( int index ): index番目の本を返す。

これらのメソッドがあれば、次のように利用することができる。

BookShelf book_shelf;

～～～～～～～～～～～

int length = book_shelf.getLength();
for (int i = 0 ; i < length ; i++) {
        Book book = book_shelf.getBookAt(i);
                :
}

しかし、「デザインパターン入門」では、わざわざIteratorパターンを使って、次のように利用することを推奨している。

BookShelf book_shelf;

～～～～～～～～～～～

Iterator it = book_shelf.iterator();
while (it.hasNext()) {
        Book book = it.next();
                :
}

「デザインパターン入門」では、forループでなく、Iteratorパターンを使うことで、次のようなメリットがあるとしている。

BookShelfクラスの実装には依存しない。

BookShelfクラスの実装を、現状の配列ではなく、Vectorを使うようにしても、BookShelfクラスを利用する側は変更しなくて済む。

これは、正しくないように思う。

BookShelfクラスを利用する側は、下記の２つのメソッドから成る、BookShelfクラスのインターフェースを見ている。forループを使う場合でも、BookShelfクラスの実装を意識して利用している訳ではない。

int getLength ( ): 本の冊数を返す。
Book getBookAt ( int index ): index番目の本を返す。

仮に、BookShelfクラスの実装を、Vectorを使うように書き換えても、上記の２つのメソッドが同じように機能するのであれば、forループであっても、呼び出し側は変更する必要は無い。

BookShelfクラスに、上記の２つのメソッドを持たせていた、ということは、元々、BookShelfクラスを利用する時に、forループを使っても良い、と宣言していたようなものである。これらのメソッドを用意した時点で、BookShelfクラスは、Iteratorパターンを適用すべきケースではなくなっていると思う。

Iteratorパターンを使わない集合のクラス

前述のBookShelfクラスもそうだが、Iteratorパターンを使わない集合のクラスでは、個数を返すsizeメソッドと、指定した位置の要素を返すgetAtメソッドという、２つのメソッドを用意するのがふつうだ。これらのメソッドは、暗黙の了解として、以下のような条件を満たすことが望ましい。

size: 実行時間はほぼゼロとすべき。
getAt: 任意の要素に対して、一定時間でアクセスできるようにすべき。

例えば、集合の要素にアクセスする側では、次のようなコードになる。

FooSet set;

～～～～～～～～～～～～～～

for (int i = 0 ; i < set.size() ; i++) {
        Foo foo = set.getAt(i);
                :
}

この時、sizeメソッドは要素の個数分だけ繰り返し実行されるため、この実行に時間がかかってしまうと、かなり遅くなる。これを避けるために、呼び出し側では次のように書くこともある。

int size = set.size();
for (int i = 0 ; i < size ; i++) {
        Foo foo = set.getAt(i);
                :
}

また、getAtメソッドは、何番目の要素であっても、一定の時間で取得できるようにしないと、二重ループになってしまう。特に、MFCを使っている時に、下記のように集合クラスを実装してしまうことがある。

class FooSet {
private:
        CObList m_list;

public:
        Foo* getAt ( int index ) {
                POSITION position = m_list.GetHeadPosition();
                int i = 0;
                while (position) {
                        Foo* foo = (Foo*)m_list.GetNext(position);
                        if (i == index)
                                return foo;
                        i++;
                }
        }
};

getAtメソッドは、確かに指定された位置の要素を返すのだが、全ての要素にアクセスする処理が二重ループになるため、事実上、使いものにならない。

集合のクラスでは、これらの点に注意して、実装する必要がある。

逆に、個数を返すsizeメソッドと、指定した位置の要素を返すgetAtメソッドが、集合クラスに定義できるのであれば、呼び出し側ではforループを使えば良い。わざわざIteratorパターンを使う必要は無い。

Iteratorパターンを使うべきケース

getAtメソッドの実装が簡単でなく、かつ、要素にランダムアクセスする必要が無い場合

Iteratorパターンを使うべきなのは、getAtメソッドの実装が簡単でなく、かつ、要素にランダムアクセスする必要が無いようなケースである。

「デザインパターン入門」に合わせて、本の例を示そう。数十万冊の本を持つ図書館データベースを考える。ここで、ユーザがある条件で本を検索したとしよう。例えば、著者が「鈴木太郎」の本、といった具合である。検索結果は、どのように返すべきであろうか？

検索された本のインスタンスをすべて生成してから、その集合を一度に返す、という仕様でも良いのであれば、Iteratorパターンを使う必要はない。しかし、この仕様には、次のような問題がある。

すべての結果が揃うまで、結果が返されない。最悪の場合、数十万冊の本の照合がすべて完了するまで、数時間かかる可能性もある。
検索された本の冊数が多い場合、返される結果が巨大になる。最悪の場合、メモリ上に収まらない可能性もある。

このようなケースでは、Iteratorパターンを使うべきである。検索結果として、本の集合ではなく、Iteratorを返すのだ。

こうすれば、検索ボタンを押した直後に、ユーザに結果を返すこともできる。ユーザが検索された本を１つずつチェックしている間に、バックグラウンドで次々と本の検索を進めておけば良いのである。

また、図書館データベースがリモートにある場合は、データ転送量を最小限に抑えられる、という効果もある。検索で数千冊の本がヒットしたとしても、ユーザが３冊目で目的の本を見つけてしまえば、転送される本の情報は３冊分だけで済む。

この他にも、Iteratorパターンを使うべきケースはたくさんある。例えば、下記のようなケースである。

テキストファイルの内容を、先頭から１行ずつ取得する場合。
Ｃ言語のソースコードを構文解析して、トークンを１つずつ返す場合。

部分集合を作る場合

部分集合を作る場合も、Iteratorパターンを使うことがある。

「デザインパターン入門」では、本の集合を表すBookShelfクラスを作った。ここで、すべての本の中から、例えば著者が「鈴木太郎」の本だけを選び出したとしよう。これを、どのように持てば良いだろうか。

著者が「鈴木太郎」の本だけを持つBookShelfインスタンスを作っても良いが、そうではなく、検索された本だけにアクセスできるようなIteratorインスタンスを作る、という方法を採用することもある。

集合を表すクラスが、単なるデータの集合ではなく、データ管理に関わる機能を持っている場合は、Iteratorパターンを使った方が良い。

例えば、BookShelfクラスに、次のようなメソッドがあるとしよう。

Save: マスターファイルに、本の情報を書き込む。

この場合、著者が「鈴木太郎」の本だけを選び出した結果もBookShelfインスタンスとして作ってしまうと、著者が「鈴木太郎」の本だけをマスターファイルに書き込む、というようなことができてしまう。

検索した結果に対しては、本の情報を参照することしかさせない、という意図を示すために、検索結果はBookShelfクラスではなく、Iteratorとして返すようにするのである。

Iterator実装上の問題

Iteratorを実装する上では、集合に対する要素の追加／削除との兼ね合いが問題となる。

C++で考えると、例えば、著者が「鈴木太郎」の本だけを選び出した結果を持つIteratorは、具体的には何を持てば良いか。良く見かけるのは、次の２つである。

マスターであるBookShelfクラスの中での、Bookインスタンスの位置（何番目の要素か）を持つ。
マスターであるBookShelfクラスが持っているBookインスタンスへのポインタを持つ。

インスタンスの位置を持つ方法では、検索を実行した後で、本の追加／削除が行われ、本の位置が変わってしまうと、問題が起きる。そもそも、本の位置が不変でなければならない、というのは、かなり大きな制約だし、実装依存でもあるので、この方法はあまり推奨されない。

ポインタを持つ方法でも、検索を実行した後で、本の削除をすると、問題が起きる。IteratorからBookインスタンスへのポインタを参照しようとした時に、実体が削除されてしまっている可能性があるからだ。

検索した時に、Bookインスタンスをコピーし、Iterator自身もBookインスタンスを持つようにすれば、この問題を回避できる。しかし、メモリを無駄に消費する結果となる。データサイズ等によって、不可能な場合も多い。

Javaの場合はgarbage collectorの仕組みがあるので、問題が無い。C++でも同様に、Bookクラスに参照カウンタを設け、garbage collectionを行う、という方法も考えられる。

PIXYシステム2での、Iteratorパターンの使用例

天体画像自動検査システム「PIXYシステム2」

CatalogDBAccessor

net.aerith.misao.database.CatalogDBAccessor

赤経赤緯と範囲を指定して、範囲内に存在する天体データをデータベースから検索した時に返されるIteratorである。

CatalogDBAccessorクラスは、次のように利用する。

CatalogDBManager manager;

～～～～～～～～～～～～～

// 検索範囲
Coor coor = new Coor(0.0, 0.0);
double radius = 1.0;

// 検索
CatalogDBAccessor accessor = manager.getAccessor(coor, radius);

// 検索結果の表示など
CatalogStar star = accessor.getFirstElement();
while (star != null) {
                :
        star = accessor.getNextElement();
}

PIXYシステム2のデータベースアクセスでは、多くのIteratorクラスが使用されている。

CatalogDBAccessor: 同定用カタログデータベースの中から検索した天体データを、順次取得するためのIterator。
CelestialDivisionMapAccessor: 天空をメッシュ状に分割し、そのうち、有効になっている部分の、データベース内の場所（フォルダ階層）を、順次取得するためのIterator。
CelestialDivisionMapDBAccessor: 天空をメッシュ状に分割し、そのうち、有効になっている部分の、データベースに記録されているXML要素を、順次取得するためのIterator。
InformationDBAccessor: 画像情報データベースの中から検索した画像情報データを、順次取得するためのIterator。
XmlDBAccessor: データベース内のある場所に存在する要素を、順次取得するためのIterator。
XmlDBFileAccessor: ディスク上に構築されたデータベース内のある場所（フォルダ）に存在するXMLファイルに含まれている要素を、順次取得するためのIterator。
XmlDBMemoryAccessor: メモリ上に構築されたデータベース内のある場所に存在する要素を、順次取得するためのIterator。

これらのIteratorクラスの関係は、次のようになっている。

Iteratorクラスの関係

図に示すように、データベースのパッケージには、いくつかのマネージャクラスがある。

PIXYシステム2は、「画像情報データベース」「同定用カタログデータベース」「光度データベース」という、３つのデータベースを持つ。それぞれに対応するマネージャのクラスが、InformationDBManager, CatalogDBManager, MagnitudeDBManager である。

３つのデータベースの中身は、共通の形式を採用している。その共通の形式に基づいたアクセスを司るのが、PrimitiveManagerクラスである。上記の３つのマネージャは、内部でこのクラスを使用している。但し、このクラスは抽象クラスである。

データベースは、ディスク上に構築することも、メモリ上に構築することもできるようになっている。ディスク上に構築したデータベースを扱うのがPrimitiveFileManagerクラス、メモリ上に構築したデータベースを扱うのがPrimitiveMemoryManagerクラスである。どちらも、PrimitiveManagerクラスのサブクラスである。

CatalogReader

net.aerith.misao.catalog.io.CatalogReader

天体カタログを読み込み、天体データを順に１つずつ取得するためのIteratorである。

PIXYシステム2でサポートしている天体カタログには、さまざまな形態のものがある。小さいものでは、わずか数行のテキストファイルのものもあるし、大きいものでは、数ギガバイトものデータが、複数のファイルに分割されて記録されているものもある。

いかなる種類の天体カタログであっても、統一した形で読み込めるように設けたのが、抽象クラスのCatalogReaderである。

CatalogReaderクラスは、下記のようなインターフェースを持つ。

void open ( ): 天体カタログを開く。この場合、すべての天体データを取得することになる。
void open ( Coor coor, double fov ): 赤経赤緯と範囲を指定して、天体カタログを開く。この場合、カタログに記録されている天体のうち、範囲内のものだけを取得することになる。
CatalogStar readNext(): 天体データを１つ取得する。このメソッドを繰り返し呼び出す。

このインターフェースに合致するものであれば、いかなるものであっても、天体カタログとして、PIXYシステム2は読み込むことができる。例えば、メモリ上にVectorで持っているいくつかの天体データの集合や、どこかのWWWページなど、ファイルとして保存されていなくても良い。

天体カタログが複数のファイルに分割されていれば、天体データを１つずつ読んでいく途中で、ファイルを切り換える必要がある。また、天体カタログの中には、天体データがうまく整列されており、指定した範囲外のデータの部分はスキップすることで、効率良く必要なデータだけを取得できるようになっているものもある。その場合は、うまくCatalogReaderのサブクラスを実装するのが望ましい。だが、こういったことは、CatalogReaderを利用する側ではまったく関知しない。実際のカタログの形式に関わらず、Openして、readNextを繰り返し呼び、Closeするだけである。