2-5 Oracleの階層問い合わせを模倣(nocycle未対応)

Javaアルゴリズムパズル

create table treeT(ID primary key,OyaID) as
select  1, 0 from dual union
select  2, 1 from dual union
select  3, 2 from dual union
select  4, 3 from dual union
select  5, 1 from dual union
select  6, 5 from dual union
select  7, 6 from dual union
select  8, 7 from dual union
select  9, 7 from dual union
select 10, 8 from dual union
select 11, 8 from dual union
select 12, 8 from dual union
select 13,11 from dual

select ID,OyaID,Level,Connect_by_is_leaf,
sys_connect_by_path(to_char(ID),',') as path
  from treeT
Start With OyaID = 0
connect by prior ID = OyaID;

Oracleの階層問い合わせを、スタックを使った深さ優先探索で実装する。

ソース

public final class hire1 {
    //ノード
    class NodeDef {
        int ID;
        int OyaID;
        NodeDef(int pID,int pOyaID){
            ID = pID;
            OyaID = pOyaID;
        }
        int LV=1; //Level用
        int isLeaf=1; //isleaf用
        String Path; //sys_connect_by_path用

        void PrintOut(){
            System.out.println("ID=" + Integer.toString(ID)
                             + ",OyaID=" + Integer.toString(OyaID)
                             + ",Level=" + Integer.toString(LV)
                             + ",isLeaf=" + Integer.toString(isLeaf)
                             + ",path=" + Path);
        }
    };

    //スタック
    class StackClass {
        int stackP;
        NodeDef stackValue[];

        StackClass(){
            stackP = 0;
            stackValue = new NodeDef[200];
        }

        private void push(NodeDef pNodeDef){
            stackValue[stackP++] = pNodeDef;
            //System.out.println("pushValue is " + Integer.toString(pNodeDef.ID));
        }
        private NodeDef pop(){
            //System.out.println("popValue is " + Integer.toString(stackValue[stackP-1].ID));
            return stackValue[--stackP];
        }
        boolean isEmpty(){
            return stackP == 0;
        }
    }

    //対象データ
    NodeDef TargetData[] = new NodeDef[13];

    public static void main(String[] args) {
        hire1 mi = new hire1();
        mi.main();
    }

    void main() {
        TargetData[0] =  new NodeDef( 1, 0);
        TargetData[1] =  new NodeDef( 2, 1);
        TargetData[2] =  new NodeDef( 3, 2);
        TargetData[3] =  new NodeDef( 4, 3);
        TargetData[4] =  new NodeDef( 5, 1);
        TargetData[5] =  new NodeDef( 6, 5);
        TargetData[6] =  new NodeDef( 7, 6);
        TargetData[7] =  new NodeDef( 8, 7);
        TargetData[8] =  new NodeDef( 9, 7);
        TargetData[9] =  new NodeDef(10, 8);
        TargetData[10] = new NodeDef(11, 8);
        TargetData[11] = new NodeDef(12, 8);
        TargetData[12] = new NodeDef(13,11);

        int UPB = TargetData.length-1;

        StackClass st = new StackClass();

        //Start withの条件を満たす行を探す
        for (int i=0;i<=UPB;i++){

            //start with句を満たしたらpushして階層問い合わせ
            if (TargetData[i].OyaID == 0){
                TargetData[i].Path = Integer.toString(TargetData[i].ID);
                st.push(TargetData[i]);

                int LoopChk = 0;
                while (st.isEmpty() == false){
                    NodeDef priNode = st.pop();
                    for(int K=UPB;K>=0;K--){
                        if (priNode.ID == TargetData[K].OyaID){ //connect by句

                            TargetData[K].LV = priNode.LV+1;
                            TargetData[K].Path = priNode.Path + "-" + Integer.toString(TargetData[K].ID);

                            for (int L=0;L<=UPB;L++)
                                if (TargetData[L].ID == priNode.ID) //主キーでpriorデータを探索しIsLeafを0に
                                    TargetData[L].isLeaf = 0;

                            st.push(TargetData[K]);
                        }
                    }
                    priNode.PrintOut();
                }
                if (++LoopChk == 100){
                    System.out.println("There is a Loop."); break;
                }
            }

            //階層問い合わせ後の、初期化処理
            for (int J=0;J<=UPB;J++){
                TargetData[J].LV=1;
                TargetData[J].Path="";
                TargetData[J].isLeaf=1;
            }
        }
    }
}

実行結果

ID=1,OyaID=0,Level=1,isLeaf=0,path=1
ID=2,OyaID=1,Level=2,isLeaf=0,path=1-2
ID=3,OyaID=2,Level=3,isLeaf=0,path=1-2-3
ID=4,OyaID=3,Level=4,isLeaf=1,path=1-2-3-4
ID=5,OyaID=1,Level=2,isLeaf=0,path=1-5
ID=6,OyaID=5,Level=3,isLeaf=0,path=1-5-6
ID=7,OyaID=6,Level=4,isLeaf=0,path=1-5-6-7
ID=8,OyaID=7,Level=5,isLeaf=0,path=1-5-6-7-8
ID=10,OyaID=8,Level=6,isLeaf=1,path=1-5-6-7-8-10
ID=11,OyaID=8,Level=6,isLeaf=0,path=1-5-6-7-8-11
ID=13,OyaID=11,Level=7,isLeaf=1,path=1-5-6-7-8-11-13
ID=12,OyaID=8,Level=6,isLeaf=1,path=1-5-6-7-8-12
ID=9,OyaID=7,Level=5,isLeaf=1,path=1-5-6-7-9