PHPで自分が何階層目に存在しているかを知りたい

Question

[
    ['id' => 1, 'parent' => null],
    ['id' => 2, 'parent' => 1],
    ['id' => 3, 'parent' => 2],
    ['id' => 4, 'parent' => null],
    ['id' => 5, 'parent' => 4],
    ['id' => 6, 'parent' => 5],
    ['id' => 7, 'parent' => 5],
    ['id' => 8, 'parent' => 7],
]

PHPでこのような階層構造あったとします。

[
    ['id' => 1, 'parent' => null, index => 0],
    ['id' => 2, 'parent' => 1, index => 1],
    ['id' => 3, 'parent' => 2, index => 2],
    ['id' => 4, 'parent' => null, index => 0],
    ['id' => 5, 'parent' => 4, index => 1],
    ['id' => 6, 'parent' => 5, index => 2],
    ['id' => 7, 'parent' => 5, index => 2],
    ['id' => 8, 'parent' => 7, index => 3],
]

といった形でデータ自身が何階層目に位置しているかを知りたいです。

階層構造を全パターン洗い出して全てループすることで取得自体は出来たのですが、階層構造が増えていくと計算量が膨大になりそうなので何か良い方法があれば教えて頂きたいです。

Comments

[m.ts10806]

現在提示されてる構造で何を与えたら何を返したいのでしょうか。
パターンケースをいくつか例示してください

[Hina_0917]

階層構造データがあった場合に、その各配列の要素に自身が何階層目に位置しているかを付与したいです。
渡すデータ → 初めのコードブロックの配列データ
取得したいデータ → 渡したデータの各要素に自身が何階層目に位置しているか

[m.ts10806]

質問は編集できますので本文に追記を。
パターンケースは具体的な名称でお願いします。
具体的なインプットに対して得たいアウトプットの値はなにか。
1を与えたら3を、とか、テストケースにもなるのでそれらがないと実装にも繋がらないと思います。

Answer 1

データが膨大ならSQLなどで対応するのが現実的です。
いわゆる入れ子集合モデルというアプローチになります

参考

$arr=[
    ['id' => 1, 'parent' => null],
    ['id' => 2, 'parent' => 1],
    ['id' => 3, 'parent' => 2],
    ['id' => 4, 'parent' => null],
    ['id' => 5, 'parent' => 4],
    ['id' => 6, 'parent' => 5],
    ['id' => 7, 'parent' => 5],
    ['id' => 8, 'parent' => 7],
];
$result=array_map(function($x,$y){
  return array_merge($x,["index"=>0]);
},$y=array_values(array_filter($arr,function($x){
  return is_null($x["parent"]);
})),array_keys($y));

$i=0;
while(true){
  $indexs=array_map(function($x){
    return $x["id"];
  },array_filter($result,function($x) use($i){
    return $x["index"]==$i;
  }));
  if(count($indexs)==0) break;
  $result=array_merge($result,array_map(function($x) use($i){
    return array_merge($x,["index"=>$i+1]);
  },array_filter($arr,function($x) use($indexs){
    return in_array($x["parent"],$indexs);
  })));
  $i++;
}
usort($result,function($x,$y){return $x["id"]-$y["id"];});
print_r($result);

Comments

[Hina_0917]

丁寧な回答ありがとうございます！
とても勉強になりました。

Answer 2

やっつけ仕事なので少し条件が変われば動かないと思いますが

<?php
$data = [
    ['id' => 1, 'parent' => null],
    ['id' => 2, 'parent' => 1],
    ['id' => 3, 'parent' => 2],
    ['id' => 4, 'parent' => null],
    ['id' => 5, 'parent' => 4],
    ['id' => 6, 'parent' => 5],
    ['id' => 7, 'parent' => 5],
    ['id' => 8, 'parent' => 7],
];

$ar = [];
foreach ($data as $a) {
    $ar[$a['id']] = ['parent'=>$a['parent']];
}

foreach ($ar as $k=>$v) {
    if ($v['parent'] == null) {
        $ar[$k]['index'] = 0;
    } else {
        if (isset($ar[$v['parent']]['index'])) {
            $ar[$k]['index'] = $ar[$v['parent']]['index'] + 1;
        }
    }
}

for ($i=0; $i<count($data); $i++) {
    $data[$i]['index'] = $ar[$data[$i]['id']]['index'];
}

var_dump($data);
?>

Comments

[Hina_0917]

回答ありがとうございました！
無事動作させることが出来ました。

[takasima20]

(･∀･)b