title: Transform flat array to tree with one-time loop
body: <p>SO,</p>
  
  <p><strong>The problem</strong></p>
  
  <p>Suppose we have flat array with following structure:</p>
  
  <pre><code>$array = [
    ['level'=&gt;1, 'name' =&gt; 'Root #1'],
    ['level'=&gt;1, 'name' =&gt; 'Root #2'],
    ['level'=&gt;2, 'name' =&gt; 'subroot 2-1'],
    ['level'=&gt;3, 'name' =&gt; '__subroot 2-1/1'],
    ['level'=&gt;2, 'name' =&gt; 'subroot 2-2'],
    ['level'=&gt;1, 'name' =&gt; 'Root #3']
  ];
  </code></pre>
  
  <p>The issue is - transform that array so it will became a tree. Subordination is determined only with elements order and <code>level</code> field. Let's define <code>children</code> as a name of dimension for storing child nodes. For array above that will be:</p>
  
  <pre>
    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',
      ),
    )
  </pre>
  
  <p>A little more clarifications, if it's not obvious who is parent for who: following code could easily visualize idea:</p>
  
  <pre><code>function visualize($array)
  {
     foreach($array as $item)
     {
        echo(str_repeat('-', $item['level']).'['.$item['name'].']'.PHP_EOL);
     }
  }
  visualize($array);
  </code></pre>
  
  <p>-for array above it's:</p>
  
  <pre>
  -[Root #1]
  -[Root #2]
  --[subroot 2-1]
  ---[__subroot 2-1/1]
  --[subroot 2-2]
  -[Root #3]
  </pre>
  
  <p><strong>Specifics</strong></p>
  
  <p>There are some restrictions both for desired solution and input array:</p>
  
  <ul>
  <li>Input array is <em>always valid</em>: that means it's structure can always be refactored to tree structure. No such weird things as negative/non-numeric levels, no invalid levels structure, e t.c.</li>
  <li>Input array can be huge and, currently, maximum level is not restricted</li>
  <li>Solution <strong>must</strong> resolve a matter with <strong>single</strong> loop, so we can not split array to chunks, apply recursion or jump within array somehow. Just simple <code>foreach</code> (or another loop - it does not matter), only once, each element one-by-one should be handled.</li>
  </ul>
  
  <p><strong>My approach</strong></p>
  
  <p>Currently, I have solution with stack. I'm working with references and maintaining current element of stack to which writing will be done at current step. That is:</p>
  
  <pre><code>function getTree(&amp;$array)
  {
     $level = 0;
     $tree  = [];
     $stack = [&amp;$tree];
     foreach($array as $item)
     {
        if($item['level']&gt;$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[] = &amp;$stack[$top][key($stack[$top])];
           }
           //add ['children'] dim to top stack element
           end($stack);
           $top = key($stack);
           $stack[$top]['children'] = [];
           $stack[] = &amp;$stack[$top]['children'];
        }
        while($item['level']&lt;$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;
  }
  </code></pre>
  
  <p>-since it's long enough, I've created a <a href="http://3v4l.org/ofhSD" rel="nofollow noreferrer">sample</a> of usage &amp; output.</p>
  
  <p><strong>The question</strong></p>
  
  <p>As you can see, my solution is quite long and it relies on references &amp; array internal pointer handling (such things as <code>end()</code>), so <strong>the question is</strong>:</p>
  
  <p>May be there are other - shorter and clearer ways to resolve this issue? It looks like some standard question, but I've not found any corresponding solution (there is one similar <a href="https://stackoverflow.com/questions/8840319/build-a-tree-from-a-flat-array-in-php">question</a> - but there OP has exact <code>parent_id</code> subordination while I have not)</p>