php - Recursive function to create a folder tree from array -

so have following:

id           => id of folder name         => name of folder folder_id    => null if it's in root, have "id" of it's parent if it's inside folder 

i have of these listed out in array so: (this $folder_array in example)

array (     [1] => array (         [name] => folder1         [id] => 1         [folder_id] => null     )     [2] => array (         [name] => folder2         [id] => 2         [folder_id] => null     )     [3] => array (         [name] => folder3         [id] => 3         [folder_id] => 2     )     [4] => array (         [name] => folder4         [id] => 4         [folder_id] => 3     ) } 

i trying make array has folder tree of sorts, i'd like:

array (     [1] => array (         [name] => folder1         [id] => 1         [folder_id] => null     )     [2] => array (         [name] => folder2         [id] => 2         [folder_id] => null,         [children] => array (             [3] => array (                 [name] => folder3                 [id] => 3                 [folder_id] => 2,                 [children] => array (                     [4] => array (                         [name] => folder4                         [id] => 4                         [folder_id] => 3                     )                 )             )         )     ) } 

so far can first level of folders it's right children array, i'm having trouble getting multiple levels go in.

could me fix code can make effective folder tree. also, if has more effective ways of organizing, i'd open well.

this code far:

$folder_array = array(     "1" => array("name"=> "folder1","id" => "1","folder_id" => null),     "2" => array("name"=> "folder2","id" => "2","folder_id" => null),     "3" => array("name"=> "folder3","id" => "3","folder_id" => "2"),     "4" => array("name"=> "folder4","id" => "4","folder_id" => "3") );  //a new array store folder tree in $new_array = array();  //now search through each 1 has no folder_id foreach($folder_array $folder) {     //if folder id empty, means in root(home) folder     if(empty($folder['folder_id']))     {         $new_array[$folder['id']] = $folder_form_array[$folder['id']];          //now go through folder_array again , see if has folders inside 1         foreach($folder_array $folder2)         {             //..and on         }     } } 

this 'multi-way' tree 'data' stored @ nodes.

unless source array in order, such 'parent' nodes come before 'child' nodes, tree not build correctly if 1 pass used.

this version of code multiple passes when trying insert children.

to reduce amount of array scanning, separate list of nodes ($sourcekeys) kept, , inserted nodes deleted list.

as usual: working code @ eval.in - , - full source code @ pastebin.com

todo: test how expensive large trees (maybe update?)

the function tries insert 1 node...

/**  * insert:  find 'parent' node  *          if child not found insert 'node'  *  * @param array node passed reference new node inserted  * @param integer $parentid - root id - may null indicate 'root'  * @param integer $childid  * @param array   $folderinfo - 'node data' stored   * @return boolean  true if parentid found , child alive  *                   false if parent not found anywhere in tree  */ function insertnode(&$node, $parentid, $childid, $folderinfo) {      // root node     if (is_null($parentid)) {         $node[$childid] = $folderinfo;         $node[$childid]['children'] = array();         return true;     }      if (isset($node[$parentid])) { // node processed         if (!isset($node[$parentid]['children'][$childid])) {             $node[$parentid]['children'][$childid] = array_merge($folderinfo,                                            array('children' => array())); // add child node             return true;         }         return true; // end of processing     }      // check children of node...     foreach($node $idx => &$child) { // need reference         if (count($child['children']) >= 1) { // check children...             if (insertnode($child['children'], $parentid, $childid, $folderinfo)) {                 return true;             }         }     }     return false; // parentid not in tree } 

start process data...

// extract root nodes need first... $roots = array_filter($source, function($data) {                                   return is_null($data['folder_id']);                                });  // need list of child nodes haven't been added yet $sourcekeys = array_diff(array_keys($source), array_keys($roots)); 

initialize output tree , process root nodes...

$thetree = array();  // first need insert roots... worth doing separate pass... foreach($roots  $idx => $folderinfo) {     insertnode($thetree, $folderinfo['folder_id'], $folderinfo['id'], $folderinfo); } 

now process list of 'child nodes' need added...

// multiple passes down source trying insert nodes. // know have finished when nothing inserted during pass.  // efficiency, drive off sourcekeys array after removing // inserted entries...  {     $insertcount = 0;      foreach($sourcekeys $position => $idx) {          $folderinfo = $source[$idx];         $inserted = insertnode($thetree, $folderinfo['folder_id'], $folderinfo['id'], $folderinfo);         if ($inserted) {             $insertcount++;             unset($sourcekeys[$position]); // safe in 'foreach'         }     }  } while ($insertcount > 0); 

we done... reporting do...

// report nodes not inserted... may useful foreach($sourcekeys $idx) {         var_dump('not inserted:', $source[$idx]); }  // output tree echo '<pre>', 'children in same order input array.', '<br />';     print_r($thetree); echo '</pre>'; exit; 

test data - note: random order , 1 invalid node (666).

$source = array (    4 =>   array("name" => "folder4",   "id" => 4,   "folder_id" => 3),    11 =>  array("name" => "folder11",  "id" => 11,  "folder_id" => 3),    13 =>  array("name" => "folder13",  "id" => 13,  "folder_id" => 12),    31 =>  array("name" => "folder31",  "id" => 31,  "folder_id" => 99),    12 =>  array("name" => "folder12",  "id" => 12,  "folder_id" => 98),    42 =>  array("name" => "folder42",  "id" => 42,  "folder_id" => 32),    32 =>  array("name" => "folder32",  "id" => 32,  "folder_id" => 99),    666 => array("name" => "folder666", "id" => 666, "folder_id" => 9999),    99 =>   array("name" => "folder99root",   "id" => 99,   "folder_id" => null),    3 =>   array("name" => "folder3",   "id" => 3,   "folder_id" => 98),    33 =>  array("name" => "folder33",  "id" => 33,  "folder_id" => 99),    98 =>   array("name" => "folder98root",   "id" => 98,   "folder_id" => null), );