パッケージ jp.ne.ytp.util.tree

複数のキーを持つ二分探索木アルゴリズムを実現するパッケージです。

参照:
説明

インタフェースの概要

OneLayerListener	MultiKeyTreeクラスの1階層分の走査を行なう際に、 イベント通知するためのメソッドを規定するインタフェースです。
TreeActionListener	MultiKeyTreeクラスからイベントを通知するためのメソッドを規定するインタフェースです。

クラスの概要

MultiKeyTree

複数のキーを持つことが可能な二分探索木のクラスです。

パッケージ jp.ne.ytp.util.tree の説明

複数のキーを持つ二分探索木アルゴリズムを実現するパッケージです。
中心となるのはMultiKeyTreeクラスです。このクラスを利用するには、 TreeActionListenerインタフェースを実装したクラスを準備する必要があります。 TreeActionListenerインタフェースを実装したクラスは、 木を作成する段階と木を走査する段階それぞれで、MultiKeyTreeクラスから適宜イベントを受け取ります。 これらのイベント内に適切な処理を実装することで、 ファイルソート・データマッチング・集計処理などを簡単に実現できます。 (このパッケージでは、ファイル出力や集計そのものの機能は持っていません。 これらは利用者側で実装する必要があります。)

次のコードは、集計に使用する場合の簡単な例です。 集計処理自体は、イベントを受け取った利用者側クラスで実装していることに注意してください。 キーはStringクラスを3つ使用しています。一般的なビジネスアプリケーションの場合は、 会社コード・部門コード・年月日のようになるでしょう。 ノードが管理するデータとしてはIntegerクラスを利用し、レコード番号を足し込むようにしています。 (実際のアプリケーションでは、ビジネスデータを持つ独自のクラスになると思います。) 木を走査する段階のイベント内で、画面出力処理を実装しています。

import java.util.*;
import jp.ne.ytp.util.tree.*;

public class MultiKeyTreeTester implements TreeActionListener {
    private static int LAYER = 3;
    private int num_ = 0;
    
    public static void main(String[] args) {
        MultiKeyTreeTester tester = new MultiKeyTreeTester();
        tester.test(args);
    }
    
    public void test(String[] args) {
        MultiKeyTree tree = new MultiKeyTree(LAYER);
        String[][] keys = {
             {"xx", "bbb", "111"}
            ,{"xx", "ccc", "222"}
            ,{"xx", "bbb", "222"}
            ,{"xx", "bbb", "333"}
            ,{"aaa", "eee", "555"}
            ,{"aaa", "bbb", "666"}
            ,{"aaa", "bbb", "777"}
        };
        
        // アクションリスナーの登録
        tree.addListener(this);
        
        // キーの登録
        for (int i = 0; i < keys.length; i++) {
            num_ = i + 1;
            tree.put(keys[i]);
        }
        
        // 木の走査
        tree.traverse();
    }
    
    /*** 以下はTreeActionListenerインタフェースの実装 ***/
    
    /*** 木作成時の処理 ***/
    public Object initializeRoot() {
        return new Integer(0);
    }
    
    public Object create(int iLayer) {
        // レコード番号をノードデータとする
        return new Integer(num_);
    }
    
    public Object match(int iLayer, Object nodeData) {
        // レコード番号をノードデータに加算する
        return new Integer(num_ + ((Integer)nodeData).intValue());
    }
    
    /*** 走査時の処理 ***/
    public void sort(Object[] keys, int iLayer, Object nodeData) {
        indent(iLayer);
        
        // キーと値の表示
        System.out.print("D:" + iLayer);
        for (int i = 0; i < keys.length; i++) {
            System.out.print(" " + keys[i]);
        }
        System.out.println(" (" + nodeData + ")");
    }
    
    public void makeHeader(Object key, int iLayer, Object nodeData) {
        indent(iLayer);
        
        // キーと値の表示
        System.out.println("H:" + iLayer + " " + key + " (" + nodeData + ")");
    }
    
    public void makeFooter(Object key, int iLayer, Object nodeData) {
        indent(iLayer);
        
        // キーと値の表示
        System.out.println("F:" + iLayer + " " + key + " (" + nodeData + ")");
    }
    
    private void indent(int iLayer) {
        // インデントの設定
        for (int i = 0; i < iLayer * 2; i++) {
            System.out.print(" ");
        }
    }
}

これを実行した結果は次の通りです。

H:0  (28)
  H:1 aaa (18)
    H:2 bbb (13)
      D:3 aaa bbb 666 (6)
      D:3 aaa bbb 777 (7)
    F:2 bbb (13)
    H:2 eee (5)
      D:3 aaa eee 555 (5)
    F:2 eee (5)
  F:1 aaa (18)
  H:1 xx (10)
    H:2 bbb (8)
      D:3 xx bbb 111 (1)
      D:3 xx bbb 222 (3)
      D:3 xx bbb 333 (4)
    F:2 bbb (8)
    H:2 ccc (2)
      D:3 xx ccc 222 (2)
    F:2 ccc (2)
  F:1 xx (10)
F:0  (28)

かっこの中はノードが管理するIntegerクラスの値です。 HやFで始まる行はヘッダとフッタを表していて、かっこの中は集計値となります。 木を走査する段階では集計は既に終わっているので、 ヘッダ出力のタイミングでも集計値を表示することが可能です。

また、上記コードの「走査時の処理」のみを次のように書き換えます。

    public void sort(Object[] keys, int iLayer, Object nodeData) {
        indent(iLayer);
        
        // キー出力
        System.out.print("<LAYER" + iLayer + " key=\"" + keys[keys.length - 1] + "\" value=\"");
        
        // 値出力
        System.out.print(nodeData);
        
        System.out.println("\"/>");
    }
    
    public void makeHeader(Object key, int iLayer, Object nodeData) {
        indent(iLayer);
        
        // 開始タグの出力
        System.out.println("<LAYER" + iLayer + " key=\"" + key + "\" value=\"" + nodeData + "\">");
    }
    
    public void makeFooter(Object key, int iLayer, Object nodeData) {
        indent(iLayer);
        
        // 終了タグの出力
        System.out.println("</LAYER" + iLayer + ">");
    }

その結果得られる出力は次のようになります。

<LAYER0 key="" value="28">
  <LAYER1 key="aaa" value="18">
    <LAYER2 key="bbb" value="13">
      <LAYER3 key="666" value="6"/>
      <LAYER3 key="777" value="7"/>
    </LAYER2>
    <LAYER2 key="eee" value="5">
      <LAYER3 key="555" value="5"/>
    </LAYER2>
  </LAYER1>
  <LAYER1 key="xx" value="10">
    <LAYER2 key="bbb" value="8">
      <LAYER3 key="111" value="1"/>
      <LAYER3 key="222" value="3"/>
      <LAYER3 key="333" value="4"/>
    </LAYER2>
    <LAYER2 key="ccc" value="2">
      <LAYER3 key="222" value="2"/>
    </LAYER2>
  </LAYER1>
</LAYER0>

このようにして、集計した結果をXMLファイルとして出力する処理も簡単に実装できます。