current community

your communities

more stack exchange communities

Stack Exchange
tour help
careers 2.0
Take the 2-minute tour ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote 1 down vote favorite
1

I am returning a list of pages and their parent pages from a MySQL database and putting all results into an array as follows where every result is an array which includes the parent, name and id of the forum (the key of array pages is also the same as page id).

For the sake of the model and the applicaiton, there are some other parameters.

  • "root pages" have a parent of 0
  • there are no orphaned pages

so, the MySQL query will return this dataset.

pages=>
     [1] => array(id=>1, 
                  parent=>0, 
                  name=>Hello World)
     [2] => array(id=>1, 
                  parent=>1, 
                  name=>Child of Hello World)
     [3] => array(id=>1, 
                  parent=>0, 
                  name=>Brother of Hello World)
     [4] => array(id=>4, 
                  parent=>2, 
                  name=Grand-child of Hello World)
     [6] => array(id=>6, 
                  parent=>4, 
                  name=Great-grand-child of Hello World)

i would then like to transform the array into something that looks like this

pages=>
     [1] => id=>1, 
            name=>Hello World
            children=>

                [2] => id=>1
                       name=>Child of Hello World
                       children=>

                           [4] => 
                             id=>4
                             name=> Grand-child of Hello World)
                             children=>

                                 [6] => 
                                   id=>6
                                   name=> Great-grand-child of Hello World
                                   children= null

     [3] => array(id=>1, 
                  name=>Brother of Hello World
                  children=>null

So basically, i want to turn a linear array into a nested multidimensional array so that i can print my sitemap.

it needs to be a recursive solution. there are over 700 pages and up to 5 or 6 levels.

i only want to do 1 mysql query. not 700 so please dont give me a mysql based solution.

share|improve this question
2  
please use your favorite search engine and search for "mysql nested sets" –  knittl Aug 12 '11 at 21:14

2 Answers 2

up vote 4 down vote accepted 
<?php

$pages = array();
$pages[1] = array('id' => 1, 'parent' => 0, 'name' => 'Hello World');
$pages[2] = array('id' => 1, 'parent' => 1, 'name' => 'Child of Hello World');
$pages[3] = array('id' => 1, 'parent' => 0, 'name' => 'Brother of Hello World');
$pages[4] = array('id' => 4, 'parent' => 2, 'name' => 'Grand-child of Hello World');
$pages[6] = array('id' => 6, 'parent' => 4, 'name' => 'Great-grand-child of Hello World');

$children = array();
foreach($pages as $key => $page){
    $parent = (int)$page['parent'];
    if(!isset($children[$parent]))
        $children[$parent] = array();
    $children[$parent][$key] = array('id' => $page['id'], 'name' => $page['name']);
}

$new_pages = recursive_append_children($children[0], $children);

function recursive_append_children($arr, $children){
    foreach($arr as $key => $page)
        if(isset($children[$key]))
            $arr[$key]['children'] = recursive_append_children($children[$key], $children);
    return $arr;
}

print_r($new_pages);

?>

Outputs:

Array
(
    [1] => Array
        (
            [id] => 1
            [name] => Hello World
            [children] => Array
                (
                    [2] => Array
                        (
                            [id] => 1
                            [name] => Child of Hello World
                            [children] => Array
                                (
                                    [4] => Array
                                        (
                                            [id] => 4
                                            [name] => Grand-child of Hello World
                                            [children] => Array
                                                (
                                                    [6] => Array
                                                        (
                                                            [id] => 6
                                                            [name] => Great-grand-child of Hello World
                                                        )

                                                )

                                        )

                                )

                        )

                )

        )

    [3] => Array
        (
            [id] => 1
            [name] => Brother of Hello World
        )
)
share|improve this answer
    
This is O(N) time complexity, since both loops can be shown to look at each element in the array exactly one time. –  Paulpro Aug 12 '11 at 22:09
    
thank you for your response. just made a few minor tweaks to adjust it to the entire data array but great answer thanks. so $children[$parent][$key] = array('id' => $page['id'], 'name' => $page['name']); is now $children[$parent][$key] = $pages[$key]; –  j6mes Aug 12 '11 at 22:15
    
@Partydroid You're welcome. Only difference is that will keep the parent values in your resulting array, which it looks like you wanted to get rid of. You could always just unset($children[$parent][$key]['parent']); though too. –  Paulpro Aug 12 '11 at 22:19
up vote 5 down vote

Here is a quick recursive function that builds a tree. Note that it's not great (one reason is because it doesn't get rid of items that have been already added to the tree, so each time you recurse it goes thru the entire list) - but it should work enough to get you started.

function buildTree($itemList, $parentId) {
  // return an array of items with parent = $parentId
  $result = array();
  foreach ($itemList as $item) {
    if ($item['parent'] == $parentId) {
      $newItem = $item;
      $newItem['children'] = buildTree($itemList, $newItem['id']);
      $result[] = $newItem;
    }
  }

  if (count($result) > 0) return $result;
  return null;
}

$myTree = buildTree($myArray, 0);
share|improve this answer
    
thanks for helping. i didnt use this but gave me a good idea of how i would do it next time. –  j6mes Aug 12 '11 at 22:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.