Second Step for Java. Chapter 3 Section 2

ハノイの塔を分解

ハノイの塔のユースケース

いつもと同じようにユースケースから考えてみましょう。まずは単純にプレイヤーが塔を解くだけで、ソフトで解くことは後回しにしましょう。

今までの例と同様に、アクタはハノイの塔を解くプレイヤーになります。

ユースケースはどうなるでしょうか。まず、プレイヤーが行う行動を考えてみれば、そこからユースケースが導き出せます。プレイヤーが行うことは円盤を塔から塔へ移動させることだけです。とすれば、プレイヤーから見たユースケースは「円盤の移動」を行うユースケースだけになります。

しかし、これだけだと単に目的もなく円盤を移動させるだけのゲームになってしまいますね。そこで、ゲームの目的である「塔にさしてある円盤を異なる塔に動かす」を思い出してください。この目的が達成できたかどうかを調べることはアプリケーションにとって重要な機能の 1 つになると思いませんか。というわけで、これをユースケースにして見ましょう。

でも、このユースケースは直接プレイヤーとやり取りを行うわけではないことに気づかれたでしょうか。すべての円盤の移動が終わったかどうかは、円盤の移動が終わった後に判定できます。ようするに「円盤の移動」ユースケースから「終了チェック」が呼び出されるようになりと考えればいいのではないでしょうか。

同じように考えられることをもう１つユースケースにしてみました。それは、円盤の移動の制約条件に関することです。前節で説明したように、ハノイの塔の円盤の移動の方法には 2 つの規則があります。円盤を移動するときに、この規則が守られているかをチェックする必要があります。これをユースケースにしてみました。

このユースケースもプレイヤーと直接やり取りを行うことはありません。「円盤の移動」ユースケースから呼ばれるような形になります。

今までの説明をまとめたのが図 3-6 になります。上述したように「移動のチェック」ユースケースと「終了チェック」ユースケースはプレイヤーとは直接線で結ばれずに、「円盤の移動」ユースケースと結ばれます。これらのユースケースは「円盤の移動」ユースケースに含まれると考えることもできるので、「円盤の移動」ユースケースからは点線で線を引き、<<include>> という表示をしておきます。<<include>> 以外にも <<extends>> などのメタタグがユースケースでは使われます。

図 3-6 ハノイの塔のユースケース

クラスの抽出

今回は今までとちょっと違って、ユースケースからクラスを抽出し、それからシーケンスを考えていきます。

クラスの抽出は初心者にとって最難関の 1 つではないでしょうか。今までの章では、まずシーケンスを考えて、アプリケーションの動作を理解するようにしてきました。シーケンスの中に自然とクラスの概念的なものが入ってくると考えたからです。

しかし、まず機能的な面からクラスを抽出して、そのクラスのオブジェクト間のシーケンスを後から考えることも可能です。というか、ある程度複雑なアプリケーションだと、すべての場合のシーケンスをはじめから考えるのはとても難しいので、必然的にクラス抽出が先になります。その後、ある場面を想定して、その時のオブジェクト間のシーケンスを考えていく順序になると思います。

ただし、どちらの方法がいいとか悪いということはありません。アプリケーションを作る人が考えやすい方法で行えばいいのではないでしょうか。

というわけで、クラスを見つけていきましょう。やはり、登場人物をあげてみて、その登場人物でユースケースであげた機能がすべて満たされているかを調べてみましょう。

はじめに登場するのはプレイヤーに相当する Player クラスです。Player クラスはプレイヤーとのやり取りを行うためのクラスとしてみましょう。そうすると、Player クラスの持つ一番重要な機能は

プレイヤーからの入力処理

です。その他の機能は何があるでしょうか。たとえば、

入力された円盤が動けるかどうかのチェック

がありますが、これも Player クラスで実装してみましょう。入力されたときに円盤が動かせない場合は再入力を行ってもらうようにしようと思っているのですが、そのたびに Player クラスの入力のための関数をコールするのも面倒だと思うからです。

他に登場人物はいるでしょうか。プレイヤーに対して、ハノイの塔を用意したり、ゲームが完了したなどをチェックするためのゲームの管理人を登場させましょう。クラスの名前は Hanoi にしましょう。

Hanoi クラスが行うことはゲームの管理にかかわること、すなわち

ハノイの塔を用意する
ゲームの終了チェック
ハノイの塔の表示

などがあります。

さて、登場人物間の関係はどうなるでしょうか。Hanoi クラスは Player クラスに対して移動する円盤の問い合わせを行う必要があります。ということは Hanoi クラスは Player クラスを知っている必要があります。逆に Player クラスは Hanoi クラスを知っている必要があるでしょうか。Player クラスの機能には Hanoi クラスに問い合わせを行う必要などはないようです。したがって、Player クラスは Hanoi クラスのことを知る必要はないと思います。

これで、登場人物はすべて洗い出せたでしょうか。ここまでの概略のクラス図を図 3-7 に示しました。Hanoi クラスと Player クラスの関連は、Hanoi クラスが Player クラスのことを知っているだけなので、片方向の矢印となります。

図 3-7 ハノイの塔の概略クラス図

とりあえず、ここはこのぐらいにしておいて、後でまた必要なクラスなどがあれば追加しましょう。次は、これをもとにシーケンスを考えていきましょう。

処理の流れを考えていこう

おおざっぱな処理の流れをまず考えていきましょう。ゲームを開始するには、ハノイの塔を準備しなくてはいけないですね。これが一番はじめに行うことになるでしょう。次にはこの塔を表示する必要があります。ここまでが、初期設定と呼ばれるところだと思います。

実際のゲームではループを用いて何度も次のような流れをくり返します。

プレイヤーからの入力を促す
プレイヤーの入力
入力された指示で円盤が動けるかどうかをチェック
動ける場合は円盤を動かす
塔の表示
終了チェック

これをオブジェクト間のメッセージとしてシーケンス図をあらわしていきましょう。

図 3-8 ハノイの塔のおおざっぱなシーケンス

今まで使ってない記号が図 3-8 ではつかわれています。左上の角が折られているような四角ですが、これはコメントを表します。シーケンス図で分かりにくいところなどがあればこの記号を使用してコメントを入れておきましょう。

図 3-9 コメントの記号

ハノイの塔をどうやって表すか

クラスの詳細を決める前に 1 つ重要なことを決めておきたいと思います。それはハノイの塔をソフトウェア的にどのように表せばいいかということです。実世界での現象をソフトウェアでどのように表現するかは、アプリケーションを作る上でとても重要になります。この The Second Step for Java で取りあげているゲームでもそれは同様です。たとえば、将棋やチェスをどう表現するか、またアナグラムなどのパズルはどのように表現するかは、その後のパズルなどの解法のアルゴリズムなどに深くかかわってきます。ハノイの塔もそれは同様です。

いろいろな方法で塔を表すことができると思いますが、１つの例として次のような方法を用いて表してみました。

ハノイの塔を構成するのは 3 つの塔と、複数の大きさの異なる円盤です。塔にさした円盤を取りだすときは、一番上の円盤しか取りだすことはできません。塔の中程や一番下を直接取りだすことはできずに、一番上から順順に取り出すことしかできません。一番上の円盤は一番最後にさしたものですから、最後にさしたものを最初に取りだすことができるわけです。

図 3-10 ハノイの塔の性質

このような性質を First In, Last Out といいます。最初に入れたものは一番最後に取りだされるというわけです。その他に似たような性質として First In, Fist Out というものもあります。最初に入れたものが、最初に取りだされるものです。

この 2 つの性質をソフトウェア的にあらわしたものをスタックとキューといいます。今回のハノイの塔はこのスタックを用いて表すことができそうです。Java にはスタックを表すために java.util.Stack というクラスが用意されているので、これを使用しましょう。Stack クラスは java.util.Vector クラスの派生クラスで、最後の要素だけにアクセスできるようにした特殊な Vector と考えることができます。また、Vector クラスは Collection API に含まれるので、Stack も Collection API の一員です。図 3-11 にスタックを示してみました。図 3-10 のハノイの塔と動作が同じであることがお分かりでしょうか。

図 3-11 スタック

スタックに要素を入れることをよく「積む」といいます。英語でいえば push です。取りだす方は特に決まったいい方はないようですが、英語では pop といいます。もう一つ、peek と呼ばれる処理があります。pop はスタックに積まれた要素を取りだしますが、peek はスタックから取り出すのですが、スタックに積まれている要素はそのまま残ります。図 3-12 はこの 3 つの処理を図で表したものです。

Stack クラスでも、push, pop, peek の 3 つの関数が使用できます。

a) push	b) pop	c) peek

図 3-12 スタックの操作

ハノイの塔に戻りましょう。1 つの塔をスタックで表せることは分かりましたが、塔にさす円盤をどのようにあらわしましょうか。円盤に求められる性質を考えていけば、おのずと答えが見つかると思います。塔に円盤をさすときに問題になるのは、さす円盤の大きさが塔にささっている円盤より小さいということです。とすると、問題なのは円盤の大きさになります。スタックであらわされる塔には、円盤の大きさを入れることにしましょう。円盤の大きさは int 型であらわせますが、Collection API では int 型のようなプリミティブ型を格納することはできないので、かわりに java.lang.Integer クラスを使用します。円盤の大きさは 1 から始まる整数で、1 の次に大きいものは 2、その次はそれに 1 を足していけばいいでしょう。こうすれば、円盤の枚数と最大の円盤の大きさが同じになります。

塔は 3 つあるので、Stack オブジェクトを要素とする List オブジェクトであらわしましょう。図 3-13 に例を示してみました。a) で示したハノイの塔を、ソフトウェア的にあらわしたものが b) になります。

図 3-13 ハノイの塔の表現

クラスの詳細

さて、ハノイの塔のあらわし方も決まったので、クラスの詳細を決めていきましょう。

まず、Player クラスから行きましょう。図 3-8 のシーケンス図から考えると、Player オブジェクトが Hanoi オブジェクトからコールされる関数は「次の手を提示する」という関数だけのようです。Player オブジェクトが自分自身にコールする関数は「円盤が移動できるかチェック」です。前者は public な関数、後者は private な関数になります。

次の手を提示する関数名は nextStep にしましょう。円盤が移動できるかどうかのチェックは isMovable にしてみました。isXXXX という関数名は XXXX であるかどうかとか、XXXX ができるかどうかなどを調べるときによく使われる名前です。この関数の戻り値は一般的に boolean になります。

isMovable 関数では移動できるかのチェックにハノイの塔の現在の状態が必要になります。塔の状態は Hanoi オブジェクトが持っているので、これを引数として渡しもらう必要があります。ということは nextStep 関数の引数は塔の状態になり、それを isMovable 関数をコールするときに渡すようにすればいいですね。塔の状態は上述したように List オブジェクトに 3 つの Stack オブジェクトが入ったものです。

nextStep 関数の戻り値はどの円盤をどこに動かすかという情報です。動かせる円盤は塔の一番上の円盤だけなので、塔の番号さえ示せれば円盤が特定できます。移動先も塔の番号で示すことができます。でも、ちょっと待ってください。戻り値として、移動させる円盤の塔の番号と移動先の塔の番号という 2 つの値を帰さなくてはいけなくなってしまいました。でも、Java では戻り値の個数は 1 つです。

さぁ、困ってしまいました。どうしましょうか。

次に示す 2 種類の方法が考えられます。

関数から値を戻すための引数を使う方法
戻り値となる複数の情報を持ったクラスを作成し、これを戻り値とする方法

1 の方法は Java では引数で渡すオブジェクトが値渡しでなく参照であることを利用したものです。たとえば、次のようなプログラムを実行してみましょう。

public class ClassA {
 
    public int value;
  
    public void setValue(int v){
        value = v;
    }

 
    public int getValue(){
        return value;
    }
}
 
public class ClassB {
    private void foo1(int x){
        x = 15;
    }
 
    private void foo2(ClassA a){
        a.setValue(15);
    }
 
 
    public ClassB(){
        int x = 10;
        System.out.println("Before Executing foo1, X = " + x);
 
        foo1(x);
        System.out.println("After Executing foo1, X = " + x);
 
        ClassA a = new ClassA();
        a.setValue(10);
        System.out.println("Before Executing foo2, A = " + a.getValue());
 
        foo2(a);
        System.out.println("After Executing foo2, A = " + a.getValue());
    }

    public static void main(String args[]){
        new ClassB();
    }
}

実行結果はこうなりました。

C:\temp>java ClassB
Before Executing foo1, X = 10
After Executing foo1, X = 10
Before Executing foo2, A = 10
After Executing foo2, A = 15

C:\temp>

int などのプリミティブ型では引数で渡した変数を関数内で更新しても、呼び出し元には反映されません。これに反して、オブジェクトを変数として渡した場合は、関数内でオブジェクトを更新すると、呼び出し元にもその変更が反映されていることがわかります。

この性質を利用したのが、1 の方法です。

2 の方法は複数の情報をまとめるだけのクラスを作ってしまおうというものです。この点では C 言語などで使われる構造体の使い方が似ています。

さて、どちらの方法が適しているでしょうか。実をいうと正解はありません。アプリケーションを作成するときのさまざまな条件を検討して決めるしかありません。たとえば、Microsoft の COM+ では 1 の方法を使います。

1 の方法の欠点は、引数の渡し方が参照渡しであるかどうかはプログラミング言語に依存しており、使用できない場合もあるということです。

今回は 2 の手法を使用することにします。すなわち、円盤の移動元と移動先をもつクラスを作成します。名前は円盤の移動に関する情報ということで PileMovementInfo クラスにしました。

PileMovementInfo クラスは、属性として移動元の source、移動先の destination を持ちます。この 2 つの属性はコンストラクタで指定できるようにします。メンバ関数はこの 2 つの属性の getter 関数だけです。

さて、Player クラスに戻って、属性を考えていきましょう。属性は特になくてもいいと思うのですが、入力を行うための Reader は nextStep 関数が呼ばれるたびに生成するのは無駄なので、属性にしておきましょう。

これをまとめると Player クラスは次のようになります。

Player クラス	ハノイの塔を解くプレイヤーとの仲介を行うクラス。 Hanoi オブジェクトから手の問い合わせに答える。その際に、円盤の移動のチェックを行う。
属性	private BufferedReader reader	入力を行う Reader
メンバ関数	public PileMovementInfo nextStep(java.util.List towers)	次に移動する円盤とその移動先を提示する関数戻り値は円盤の移動元と移動先を持つ PileMovementInfo オブジェクト
メンバ関数	private boolean isMovavle(java.util.List towers, int source, int destination)	円盤が移動できるかどうかを調べる関数 source が円盤の移動元、destination が移動先を示す移動できる場合は戻り値が true、できない場合は false

ついでに PileMovementInfo クラスは次のようになります。

PileMovementInfo クラス	円盤の移動元の塔と移動先の塔を保持するクラス
属性	private int source	移動元の塔の番号
属性	private int destination	移動先の塔の番号
メンバ関数	public int getSource()	移動元の塔の番号を返す関数
メンバ関数	public int getDestination()	移動先の塔の番号を返す関数

次は Hanoi クラスです。図 3-8 のシーケンス図では初期設定の部分で、「ハノイの塔の生成」と「ハノイの塔の表示」の 2 つの関数がコールされています。ゲームのループに入ってからは「円盤の移動」、「ハノイの塔の表示」、「終了チェック」の 3 種類の関数が呼ばれています。「ハノイの塔の表示」は共通になるので 4 つの private な関数があります。

public な関数はゲームの管理を行う関数があります。これは Mastermind などの例と同じですね。

これら 5 つの関数名を決めていきます。「ハノイの塔の生成」は makeTowers、「ハノイの塔の表示」は printTowers にしました。「円盤の移動」は movePile、「終了チェック」は checkCompletion です。

ゲームの管理は startGame にしました。ゲームの管理を行うということで maintainGame などでもいいのですが、この関数をコールする立場からするとゲームの管理というよりは、この関数をコールすることでゲームが開始されると考えるほうがわかりやすいかなぁと思ったからです。

関数名に動詞 + 目的語が多いのは関数が何らかの動作を示しているからです。なんどもいうようですが、なるべくその動作が分かるような名前を選ぶことは重要です。

makeTowers 関数の戻り値は List オブジェクトの塔の状態ですが、塔を決めるためには何が必要でしょうか。円盤の枚数は必要ですね。あとは、最初に円盤がさしてある塔を指定することでしょうか。

この 2 つの情報を makeTowers 関数の引数にするのと、Hanoi クラスの属性としてしまうことのどちらがいいでしょうか。これも状況に応じて変わるので、どちらか一方がいいということはないと思います。これらの情報がクラスの他の部分でもよく使われるのであれば属性に、使われないのであれば引数にすることが多いです。

円盤の枚数と初期状態の円盤の位置は他の関数などでも使われそうです。したがって、この 2 つの情報は属性にして、makeTowers 関数は引数なしとしましょう。

printTowers 関数の引数は塔の状態を表す List オブジェクトです。最大枚数が分からないと、どの程度の大きさで表示すればいいか分からないのですが、属性にしたのですぐ使うことができます。printTowers 関数で行う処理は関数の中だけで閉じているので、戻り値は必要ないと思います。

movePile 関数は移動する円盤の移動元と移動先の塔が引数となります。もちろん、塔の状態を表すオブジェクトも必要ですね。この関数も戻り値は特に必要はないです。

checkCompletion 関数は塔の状態を表すオブジェクトと、移動の目的の塔の番号が必要です。最終的に移動する塔の番号は他の関数では使用されないようなので、これは属性にせずに引数にしましょう。checkCompletion 関数の戻り値は「終了したかどうか」を示す boolean 型にしました。

最後に残った startGame 関数ですが、ゲームをスタートさせるだけなので引数も戻り値もなしにしましょう。

次に、属性を考えていきましょう。

まず、定数として塔の本数、はじめに円盤がさしてある塔の番号、目的の塔の番号を定数にしておきます。塔の本数は常に 3 本なので定数でかまいませんが、残りの 2 つの塔番号はプログラム中で変更できるように static でない変数にしてもいいかもしれません。

定数以外の属性として、最大の円盤の大きさが必要なことは上述しました。それ以外に考えられる属性にはなにがあるでしょうか。2 つの属性候補が考えられませんか。１つは Player オブジェクト、他方はハノイの塔を表現した List オブジェクトです。ただし、これらのオブジェクトを実際に使用するのは startGame 関数の中だけになります。List オブジェクトは printTowers 関数などで使われますが、引数と渡すので、属性にしておく必要はないことになります。

ゲームをするのにプレイヤーがいないことはないので、Player オブジェクトは属性にしておきましょう。このようにクラス間が強い結びつきをしている場合、その関係を集約といいます。たとえば、クラス A とクラス B があり、A が B を持っているような関係です。

このとき、A と B のライフサイクルが同じになるような特別な集約をコンポジッションといいます。ライフサイクルとはオブジェクトが生成されてから消滅するときまでです。たとえば、クラス A が生成されるときに同時にクラス B が生成され、クラス A が消滅するときも同時にクラス B も消滅するような関係です。それこそ、親分が子分に向かって「おまえのいのち、俺があずかった」というようなオブジェクトの関係というわけです。

クラス図で集約は図 3-14 のようにクラス間を結ぶ線の根元に塗りつぶされた菱形を描きます。

図 3-14 集約とコンポジッション

List オブジェクトはローカル変数にとりあえずしておきましょう。不都合があれば、再び属性にするかどうかを考えてみます。このようにはじめの設計で 100% 仕様が決まってしまうことはありません。分析 - 設計 - 実装 - 検証というアプリケーション作成の流れは 1 度だけではなく、何度もくり返し行うというのが最近のはやりです。

Hanoi クラスについてまとめてみたのが次の表です。

Hanoi クラス	ハノイの塔を行うクラス。 Player オブジェクトに手の問い合わせ、円盤の移動、表示、終了チェックを行う。
属性	private final static int NUMBER_OF_TOWERS	塔の本数
	private final static int START	初期状態で円盤が置かれている塔の番号
	private final static int END	最終的に円盤を移動させる塔番号
	private int size	円盤の最大の大きさ
	private Player player	ハノイの塔を遊ぶプレイヤー
メンバ関数	public void startGame()	ゲームを開始する関数
	private List makeTowers()	ハノイの塔を表現する List オブジェクトを生成する生成にはは false
	private void printTowers(java.util.List towers)	ハノイの塔の表示を行う引数は塔を表現する List オブジェクト
	private void movePile(List towers, int srouce, int destination)	円盤の移動を行う関数 towers はハノイの塔、source が移動元の塔番号、destination が移動先塔番号
	private boolean checkCompletion(List towers, int goal){	終了チェックを行う関数 towers はハノイの塔、goal は最終的に移動する塔番号

3 種類のクラスをクラス図で示したものが図 3-15 です。Hanoi クラスと Player クラスの関連は図 3-7 と異なり、ライフサイクルが同じにするためコンポジッションにしました。また、Hanoi クラスと Player クラスの橋渡し的な PileMovementInfo が加わっています。PileMovementInfo クラスはその他のクラスからの依存関係にあります。

図 3-15 ハノイの塔のクラス図

(Dec. 2001)