QA@IT

一覧からの階層情報付JSONの作成 (PHP)

8252 PV

PHP + jQuery Eeasyui(http://www.jeasyui.com/ )を使用してファイル、ディレクトリ(フォルダ)の関係をツリー表示するWebツールを作成しています。
ディレクトリ(フォルダ)の関係はデータベースのテーブルに登録している
・ファイル、ディレクトリ名
・階層レベル(階層の深さ)
・ほか付随する情報
から配列($sql_aray)を生成し、childArray関数を経て連想配列($json_Array)を作成、JSONに変換してjQuery EeasyuiのTreeに表示するように考えています。

実際のファイル、ディレクトリ構造からデータベースへ登録する情報は「ファイル、ディレクトリ一覧を作成する」というような再帰関数を使用した方法で解決しましたが、その逆で詰まっています。

ざっくりとしたコードですが、いま考えているものです。
{"text":"8","level":"5"} と {"text":"9","level":"2"} の階層レベルが2つ以上離れているときにどう処理すればいいのか?
そもそもこういった課題の解法として定番のアルゴリズムがあるのか?

アドバイスいただければ助かります。

/******** ここからコード *********/

<?php
$cntno = 0;
$sql_aray = [   {"text":"1","level":"1"},
      {"text":"2","level":"2"},
      {"text":"3","level":"2"},
      {"text":"4","level":"3"},
      {"text":"5","level":"4"},
      {"text":"6","level":"5"},
      {"text":"7","level":"4"},
      {"text":"8","level":"5"},
      {"text":"9","level":"2"},
      {"text":"10","level":"3"}];   //実際はDBから取得する
$json_Array = array();
$json_Array = childArray($sql_aray);

echo json_encode($json_Array);

/*
表示する結果:[{"text":"1","level":"1","children":[{"text":"2","mLevel":"2"},{"text":"3","mLevel":"2","children":[{"text":"4","mLevel":"3","children":[{"text":"5","mLevel":"4","children":[{"text":"6","mLevel":"5"}]},{"text":"7","mLevel":"4","children":[{"text":"8","mLevel":"5"}]},{"text":"9","mLevel":"2","children":[{"text":"10","mLevel":"3"}]}]}]}]}]
希望する結果:[{'text':'1','level':'1','children':[{'text':'2','mLevel':'2'},{'text':'3','mLevel':'2','children':[{'text':'4','mLevel':'3','children':[{'text':'5','mLevel':'4','children':[{'text':'6','mLevel':'5'}]},{'text':'7','mLevel':'4','children':[{'text':'8','mLevel':'5'}]}]}]},{'text':'9','mLevel':'2','children':[{'text':'10','mLevel':'3'}]}]}]
*/


function childArray($sql_aray){
   global $cntno;

   $mstrAry = Array();

   if($cntno > count($sql_aray)){
      return $mstrAry;
   }

   for ($k = $cntno ; $k < count($sql_aray)  ; $k++){

      if($cntno > count($sql_aray) - 1){break;}

      $rows = $sql_aray[$cntno];
      $level = $rows['level'];
      $text = $rows['text'];

      if($cntno == count($sql_aray) - 1){
         $nextLevel = 0;
      }else{
         $nextLevel = $sql_aray[$cntno + 1]['level'];
      }

      $cntno++;
      if($nextLevel > $level){
         $childAray = array("text" => $text, "level" => $level, "children" => childArray($sql_aray));

         if($mstrAry == []){
            $mstrAry = array($childAray);
         }else{
            $mstrAry = array_merge($mstrAry, array($childAray));
         }



      }elseif ($nextLevel == $level){
         $childAray = array("text" => $text, "level" => $level);

         if($mstrAry == []){
            $mstrAry = array($childAray);
         }else{
            $mstrAry = array_merge($mstrAry, array($childAray));
         }


      }elseif ($nextLevel < $level){

         $childAray = array("text" => $text, "level" => $level);

         if($mstrAry == []){
            $mstrAry = array($childAray);
         }else{
            $mstrAry = array_merge($mstrAry, array($childAray));
         }
         break;
      }
   }
   return $mstrAry;
}
?>

回答

もう少し {"text":"9","level":"2"} などで出てくる text (ファイル名・ディレクトリ名?)、 level , mlevel(階層?) などの説明が欲しかったですね。

「逆」というのはつまり、このファイル名/ディレクトリ名と深さの配列からツリーを再構築したいということですよね。

[ {"text":"1","level":"1"},
{"text":"2","level":"2"},
〜 略 〜
{"text":"9","level":"2"},
{"text":"10","level":"3"}];

各要素は名前と深さしか持っていませんが、よくあるデータの持ち方としては、
これに加えて親の情報と、ディレクトリかファイルかの情報を持たせたほうが処理はしやすくなると思います。

これらがない場合は、データ構造を取得処理(この配列の元データを作った処理)に依存し、さらに確定できない情報もあると思います。

現在取得するときに再帰で(おそらく並列処理せずに)取っているとのことですが、
例えばディレクトリ一覧の取得処理が

  1. 渡したディレクトリのすべてのディレクトリ・ファイルについて処理する
  2. ディレクトリからファイルか判断
    1. ディレクトリであれば出力し、すぐに自身を再帰的に呼び出す。
    2. ファイルであれば出力する。

ここから構造を推測するとします。

この再帰処理には
「順に見ていってディレクトリはすぐ再帰して子供を取りに行く」という特性があるので、
levelが大きくなったら(サブディレクトリの情報に移ったら)、その前のアイテムが親ディレクトリです。(親「ディレクトリ」なのでこの前のアイテムはディレクトリと確定できます。)

また、ディレクトリの情報も残しているので、levelが増加するときは常に1ずつとなります。

[ {"text":"1","level":"1"},    // 次の行でlevelが増えているので "text":"1" はディレクトリ
    {"text":"2","level":"2"},
    {"text":"3","level":"2"},  // 次の行でlevelが増えているので "text":"3" はディレクトリ
    {"text":"4","level":"3"},  // "text":"4" はディレクトリ
    {"text":"5","level":"4"},  // "text":"5" はディレクトリ
    {"text":"6","level":"5"},

逆にlevelが減った場合は下の階層を探索し尽くして親ディレクトリに戻り、そのlevelの続きのアイテムだと意味します。

    {"text":"2","level":"2"},
    {"text":"3","level":"2"},
    {"text":"4","level":"3"},
    {"text":"5","level":"4"},
    {"text":"6","level":"5"},  
    {"text":"7","level":"4"},  // level 4 の続き ( "text":"5" の兄弟 )
    {"text":"8","level":"5"},
    {"text":"9","level":"2"},  // level 2 の続き ( "text":"3" の兄弟 )
    {"text":"10","level":"3"}];

というような処理をjavascriptで書くと以下のようになります。
(phpで書く時間がなかったのですいません)
type という属性も勝手に追加しています。

子要素が出てきたら再帰処理で子要素の配列を作成します。

<!DOCTYPE html>
<html><head lang="ja"></head>
<body>
<textarea name="result" id="result" cols="40" rows="10"></textarea>
<script>
var items = [ {"text":"1","level":"1"},
{"text":"2","level":"2"},
{"text":"3","level":"2"},
{"text":"4","level":"3"},
{"text":"5","level":"4"},
{"text":"6","level":"5"},
{"text":"7","level":"4"},
{"text":"8","level":"5"},
{"text":"9","level":"2"},
{"text":"10","level":"3"}];

var result = [];


/**
 * 
 * @param result 見つかったアイテムを追加していく配列。処理後にここに結果が格納されている。
 * @param items 元情報となる配列
 * @param index itemsの検索開始インデックス(再帰処理で途中から探索するために必要)
 * @param currentLevel 探索対象のlevel
 * @returns {*} 最後に探索されたindex。再帰から戻ったときにこのindexから続きを行う
 */
 function rebuildTree(result, items, index, currentLevel){

    var i = index; // 受け取ったインデックスからループする

    while(i< items.length){
        if(currentLevel != items[i].level * 1 ) {

            if( currentLevel > items[i].level * 1 ){
                // 下の階層の探索が終わって元の階層に戻っているところ
                return i;
            }

            if( items[i].level * 1 == currentLevel + 1 ) {

                // 下の階層のデータが出てきたので 再帰で下のディレクトリの情報を再構築
                var children = [];
                i = rebuildTree(children, items, i, items[i].level * 1)
                result[result.length - 1].children = children;

                // 子がいたので、ディレクトリに確定する
                result[result.length - 1].type = "directory"
            }

        }else{
            result.push({ text: items[i].text, level: items[i].level, type: "dir or file", children: [] });
            currentLevel = items[i].level * 1;
            i++;
        }

    }
    return i;
}

rebuildTree(result, items, 0, 1);

document.getElementById("result").value = JSON.stringify(result);
console.log(JSON.stringify(result));
</script>
</body></html>

ただし、この処理は、空のディレクトリとファイルの区別はつきません。
再帰処理の構成が私の想定と違う場合も処理を修正しないといけません。

親ディレクトリ情報は追加した方が良いと思います。
(この場合は再構築の方法は違うやり方も出てくると思います。)

編集 履歴 (0)

flied_onionさん、ありがとうございます。

説明不足の点、すみませんでした。
ここまでシンプルなコードになるとは思いませんでした。
PHPでは以下のように再現しました。

<?php
    $items = array(
        array('text' => "1", "level" => "1"), 
        array('text' => "2", "level" => "2"), 
        array('text' => "3", "level" => "2"), 
        array('text' => "4", "level" => "3"), 
        array('text' => "5", "level" => "4"), 
        array('text' => "6", "level" => "5"), 
        array('text' => "7", "level" => "4"), 
        array('text' => "8", "level" => "5"), 
        array('text' => "9", "level" => "2"), 
        array('text' => "10", "level" => "3")
        );

$index = 0;
$result = array();
$result = rebuildTree($result, $items, 1);
echo json_encode($result);

function rebuildTree($result, $items, $level)
{
    global $index;

    while($index < count($items))
    {
        if($level != $items[$index]['level'] && $index > 0)
        {
            if($level > $items[$index]['level']){
            return $result;
        }

        if($items[$index]['level'] == $level + 1)
        {
            $children = Array();
            $children = rebuildTree($children, $items, $items[$index]['level']);

            if(count($children) > 0)
            {
                $result[count($result) - 1] += array('children' => $children);
            }
        }
        }else{
            array_push($result, array('text'=> $items[$index]['text'], 'level'=> $items[$index]['level']));
            $level = $items[$index]['level'];
            $index++;
        }
    }
    return $result;
}
?>
編集 履歴 (1)
ウォッチ

この質問への回答やコメントをメールでお知らせします。