ТАК,

Проблема

Предположим, у нас есть плоский массив со следующей структурой:

$array = [
  ['level'=>1, 'name' => 'Root #1'],
  ['level'=>1, 'name' => 'Root #2'],
  ['level'=>2, 'name' => 'subroot 2-1'],
  ['level'=>3, 'name' => '__subroot 2-1/1'],
  ['level'=>2, 'name' => 'subroot 2-2'],
  ['level'=>1, 'name' => 'Root #3']
];

Проблема в том, чтобы преобразовать этот массив, чтобы он стал деревом. Подчиненность определяется только порядком элементов иlevel поле. Давайте определимсяchildren как имя измерения для хранения дочерних узлов. Для массива выше это будет:

  array (
    array (
      'level' => 1,
      'name' => 'Root #1',
    ),
    array (
      'level' => 1,
      'name' => 'Root #2',
      'children' => 
      array (
        array (
          'level' => 2,
          'name' => 'subroot 2-1',
          'children' => 
          array (
            array (
              'level' => 3,
              'name' => '__subroot 2-1/1',
            ),
          ),
        ),
        array (
          'level' => 2,
          'name' => 'subroot 2-2',
        ),
      ),
    ),
    array (
      'level' => 1,
      'name' => 'Root #3',
    ),
  )

Еще немного уточнений, если не очевидно, кто является родителем для кого: следующий код может легко визуализировать идею:

function visualize($array)
{
   foreach($array as $item)
   {
      echo(str_repeat('-', $item['level']).'['.$item['name'].']'.PHP_EOL);
   }
}
visualize($array);

-для массива выше это:

-[Root #1]
-[Root #2]
--[subroot 2-1]
---[__subroot 2-1/1]
--[subroot 2-2]
-[Root #3]

конкретика

Существуют некоторые ограничения как для желаемого решения, так и для входного массива:

Входной массиввсегда в силе: это означает, что его структура всегда может быть преобразована в древовидную структуру. Нет таких странных вещей, как отрицательные / нечисловые уровни, нет недопустимой структуры уровней и т. Д.Входной массив может быть огромным, и в настоящее время максимальный уровень не ограниченРешениедолжен решить вопрос сОдин цикл, поэтому мы не можем разделить массив на куски, применить рекурсию или каким-либо образом перейти в массив. Простоforeach (или другой цикл - это не имеет значения), только один раз, каждый элемент один за другим должен обрабатываться.

Мой подход

В настоящее время у меня есть решение со стеком. Я работаю со ссылками и поддерживаю текущий элемент стека, на который будет производиться запись на текущем шаге. Это:

function getTree(&$array)
{
   $level = 0;
   $tree  = [];
   $stack = [&$tree];
   foreach($array as $item)
   {
      if($item['level']>$level) //expand stack for new items
      {
         //if there are child elements, add last to stack:
         $top = key($stack);
         if(count($stack[$top]))
         {
            end($stack[$top]);
            $stack[] = &$stack[$top][key($stack[$top])];
         }
         //add ['children'] dim to top stack element
         end($stack);
         $top = key($stack);
         $stack[$top]['children'] = [];
         $stack[] = &$stack[$top]['children'];
      }
      while($item['level']<$level--) //pop till certain level
      {
         //two times: one for last pointer, one for ['children'] dim
         array_pop($stack);
         array_pop($stack);
      }
      //add item to stack top:
      end($stack);
      $stack[key($stack)][] = $item;
      $level = $item['level'];
   }
   return $tree;
}

-Так как это достаточно долго, я создалобразец использования и вывода.

Вопрос

Как видите, мое решение довольно длинное и основано на ссылках и обработке внутреннего указателя массива (такие вещи, какend()), таквопрос в том:

Может быть, есть другие - более короткие и ясные способы решения этой проблемы? Это выглядит как стандартный вопрос, но я не нашел соответствующего решения (есть одно подобноевопрос - но там точно есть ОПparent_id подчинения пока у меня нет)