再帰的なデータ構造を表現する（デザインパターン活用）：JavaTips 〜Javaプログラミング編

» 2004年12月14日 10時00分 公開
[小田原大，＠IT]

再帰的なデータ構造

　OSのファイルシステムは、ファイルはフォルダに収められ、そのフォルダはさらにほかのファイルとともに上位のフォルダに、そのフォルダはさらに上位のフォルダに……、という具合に入れ子構造になって構成されています。このように、ある要素がそれと同等の要素を含むデータ構造を「再帰的なデータ構造」と呼びます。

ファイルシステムの表現

　このような再帰的なデータ構造をプログラム上で表現してみます（図1）。ファイルとフォルダをそれぞれFile、Folderというクラスで表します。ファイルとフォルダそれぞれにgetValueというメソッドを用意することにします。FileのgetValueは自身のファイル容量を返し、Folderについてはそのフォルダが持つすべてのファイル容量の合計を返すとします（リスト1〜リスト3）。

図1　実装する対象のファイルシステム 図1　実装する対象のファイルシステム
リスト1　File.java
package package net.mogra.wings.javatips;

public class File{
  private String name_;
  private int value_;
  public File(String name, int value){
    name_ = name;
    value_ = value;
  }
  public String getName(){
        return name_;
  }
  public int getValue(){
    return value_;
  }
}


リスト2　Folder.java
package net.mogra.wings.javatips;

import java.util.ArrayList;
import java.util.Iterator;

public class Folder{
  protected ArrayList files_ = new ArrayList();
  protected ArrayList folders_ = new ArrayList();
  public int getValue(){
    int value = 0;
    for(Iterator i = files_.iterator(); i.hasNext();) {
      value += ((File)i.next()).getValue();
    }
    for(Iterator i = folders_.iterator(); i.hasNext();) {
      value += ((Folder)i.next()).getValue();
    }
    return value;
  }
  public void add(File o){
    files_.add(o);
  }
  public void add(Folder o){
    folders_.add(o);
  }
}


リスト3　Client.java
package net.mogra.wings.javatips;

public class Client{
  public static void main(String[] args){
    // エントリの生成
    File file1 = new File("file1",100);
    File file2 = new File("file2",200);
    File file3 = new File("file3",50);
    File file4 = new File("file4",500);
    Folder f1 = new Folder();
    Folder f2 = new Folder();
    Folder f3 = new Folder();
    Folder f4 = new Folder();

    f1.add(f2); f1.add(f4);
    f2.add(file1); f2.add(f3);
    f3.add(file2); f3.add(file3);
    f4.add(file4);

    System.out.println("f1の値は "+f1.getValue());
 }
}


　上記のリストを実行すると、以下のような結果が得られます。

実行結果
Cf1の値は 850


　ここで紹介したプログラムは、FolderのgetValueを呼び出すと、Folderの子要素についてgetValueが再帰的に呼び出されるという、なかなかうまい仕組みを持っているように見えます。しかし、データ構造の要素が「ファイルであるかフォルダであるかを区別する」必要が生じ、そのためにファイル格納用、フォルダ格納用それぞれにArrayListをわざわざ用意しています。

　この、決してスマートとはいえないコードは、拡張しようとしたときに問題点が明らかになります。例えば、Folderを拡張した新しいFolder2というクラスを作成することを考えてみましょう。Folder2はFolderと同等に扱うことができないため、Folderが持つArrayListはFile用、Folder用、Folder2用と3つ必要になります。addメソッドも新しく加えなければなりません。つまり、既存のコードに修正を加える必要があるということです。Folder2も、当然これら3つのArrayListを持たなければなりません。

問題点の解消

　FileとFolderは、ここではgetValueというメソッドを持つ点以外は全く異なるクラスとして扱っていたため、インスタンスの区別は必然でした。しかし、この手間を省くうまい方法があります。FileとFolderが共通して継承するスーパークラスEntryを抽象クラスとして作成するのです（リスト4〜リスト6）。

リスト4　Entry.java
package net.mogra.wings.javatips;

public abstract class Entry {
  protected String name_;
  public abstract int getValue();
  public void add(Entry e){
    throw new RuntimeException();
  }
  public void remove(Entry e){
    throw new RuntimeException();
  }
  public Entry getChild(int i){
    throw new RuntimeException();
  }
}


リスト5　File.java
package net.mogra.wings.javatips;

public class File extends Entry{
  private int value_;
  public File(String name, int value){
    name_ = name;
    value_ = value;
  }
  public String getName(){
    return name_;
  }
  public int getValue(){
    return value_;
  }
}


リスト6　Folder.java
package net.mogra.wings.javatips;

import java.util.ArrayList;
import java.util.Iterator;

public class Folder extends Entry{
  protected ArrayList children_ = new ArrayList();
  public int getValue(){
    int value = 0;
    for(Iterator i = children_.iterator(); i.hasNext();){
      Entry e = (Entry)i.next();
      value += e.getValue();
    }
   return value;
  }
  public void add(Entry e){
    children_.add(e);
  }
  public Entry getChild(int i){
    return (Entry)children_.get(i);
  }
}


　FileとFolderをEntryクラスのサブクラスと見なすことにより、どちらもEntryクラスのオブジェクトとして統一的に扱うことができるようになります。つまりインスタンスの区別が不要になるのです。上の例で見たようにFolder2というクラスを追加することになっても、Folder2もまたEntryのオブジェクトと見なせるため、既存のコードの修正は必要ありません。

GoFのCompositeパターン

　配下に子要素を含まない単純要素（ここではFile）と何かしらの要素を配下に含む複合要素（ここではFolder）という異なるクラスを、抽象クラスによって同等のものと見なし、統一的に扱い、再帰的なデータ構造を表現するこの手法は、GoF（Gang of Four）のデザインパターンによりCompositeパターンとしてまとめられています。

　パターンの構造をクラス図で表すと、図2のようになります。

図2　Composite パターンの構造 図2　Composite パターンの構造

　Component：抽象クラス、Leaf：単純要素を表すクラス、Composite：複合要素を表すクラス、Client：Composite内のオブジェクトを操作するクラス。この4つのクラスがCompositeパターンの基本となります。ComponentクラスがLeafクラスとCompositeクラスの共通のインターフェイスを宣言することで、ClientはLeafとCompositeのオブジェクトを区別することなく扱うことができます。

Profile

WINGSプロジェクト

小田原大


Copyright © ITmedia, Inc. All Rights Reserved.

＠IT

@ITについて

RSSについて

アイティメディアIDについて

メールマガジン登録

＠ITのメールマガジンは、 もちろん、すべて無料です。ぜひメールマガジンをご購読ください。