преобразование плоского массива дерева с петлей единовременного

Question

SO,

Проблема

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

$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] 

Особенности

Есть некоторые ограничения как для требуемого массива раствора и ввода:

• Входной массив всегда уважительной: это означает, что его структура всегда может быть переработан в древовидной структуре. Нет таких странных вещей, как отрицательные/нечисловые уровни, недействительная структура уровней, e t.c.
• Входной массив может быть огромным, и в настоящее время, максимальный уровень не ограничен
• Решение должны решить вопрос с одного цикла, поэтому мы не можем разделить массив куски, применить рекурсию или скачок в массиве как-то. Просто просто 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; 
} 

-since это достаточно долго, я создал sample использование & выхода.

Вопрос

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

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

Answer 1

Хорошая вещь о вашей проблеме заключается в том, что ваш вход всегда отформатирован правильно, поэтому ваша фактическая проблема сужается до поиска детей для каждого узла, если они существуют, или для поиска родителя для каждого узла, если он есть. Последнее здесь более подходит, потому что мы знаем, что узел имеет родительский элемент, если его уровень больше одного, и это ближайший узел над ним в исходном плоском массиве с уровнем, равным уровню текущего узла минус один. В соответствии с этим мы можем просто следить за несколькими узлами, которые нас интересуют. Чтобы быть точнее, когда мы находим два узла с одинаковым уровнем, узел, который был найден ранее, не может иметь больше детей.

Реализация этого будет выглядеть следующим образом:

function buildTree(array &$nodes) { 
    $activeNodes = []; 

    foreach ($nodes as $index => &$node) { 
     //remove if you don't want empty ['children'] dim for nodes without childs 
     $node['children'] = []; 
     $level = $node['level']; 
     $activeNodes[$level] = &$node; 

     if ($level > 1) { 
      $activeNodes[$level - 1]['children'][] = &$node; 
      unset($nodes[$index]); 
     } 
    } 
} 

Demo

Answer 2

об осуществлении с помощью рекурсии:

function buildTreeHelper(&$array, $currentLevel = 1) 
{ 
    $result = array(); 
    $lastIndex = 0; 
    while($pair = each($array)) { 
     list(, $row) = $pair; 
     $level = $row['level']; 
     if ($level > $currentLevel) { 
      $result[$lastIndex]['children'] = buildTreeHelper($array, $level); 
     } else if ($level == $currentLevel) { 
      $result[++$lastIndex] = $row; 
     } else { 
      prev($array); // shift back 
      break; 
     } 
    } 
    return $result; 
} 

function buildTree($array) 
{ 
    reset($array); 
    return buildTreeHelper($array); 
} 

$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'] 
]; 

print_r(buildTree($array));