Translate a nested heirarchical array into another heirarchical array

Yes, that does sound like a pointless title. Let me explain the situation, we have a self referential model, Pages, which has child pages and a parent page. Because I'm using CakePHP for this project I have added the Tree Behaviour to the model also which is really handy, but you don't need that behaviour (mptt structure) in order for this to work.

Basically, if you have a self referential model and you use some method to get a big nested array of objects, their child objects and so forth - you can use this code to translate that array of objects into a simple associative array of only the keys you need.

Why would you want to do that?

Often times you need to translate some heirarchical data into a format for displaying in a browser. Adding ul and li tags - or, as I have had to do in the past, you need to display the data in a pdf. Both functions use a similar approach, loop through the data with a recursive function and output tags and data here and there. In fact the tree helper in CakePHP is very handy for exactly this.

On this occasion I had a different requirement though, and that was to output some custom xml so that the flash designer could code up a menu.

The xml should look something like:

<navigation>
<log_in />
<log_out>
 <menu id="1" title="ABOUT US">
 <menu id="2" title="INTRO" />
 <menu id="3" title="PRINCIPALS">
   <menu id="7" title="ONE" />
   <menu id="8" title="TWO" />
   <menu id="9" title="THREE" />
 </menu>
 <menu id="11" title="WHAT WE DO" />
</menu>
</log_out>
</navigation>

As you can see its pretty straight forward, but one subtle difference is that there are not nested ul tags like you would have if replicating this sort of structure using HTML nested list items. I strongly considered using the tree behaviour for this output, but it meant hacking around with the tree behaviour code.

Another approach would be to use the xml helper function serialize(). This useful function would take an array similar to:

$nav['navigation']['logOut']['menu'] =
array(array('id' => '1', 'title' => 'ABOUT US',
            'menu' => array(
                    array('id' => '2', 'title' => 'INTRO'),
                            array('id' => '3', 'title' => 'PRINCIPALS',
                                  'menu' => array(array('id' => '7', 'title' => 'ONE'),
                                                  array('id' => '8', 'title' => 'TWO'),
                                                  array('id' => '9', 'title' => 'THREE'))),
                            array('id' => '11', 'title' => 'WHAT WE DO'))));

and translate it perfectly into the xml, with menu tags and all. This struck me as a pretty neat solution, the only problem being getting the data into this format of array - which I was to find out is not a trivial task.

The Recursive Function:

Here is the function I wrote to accomplish this, its pretty neat in the end. I had to strip out some extra calls to the db, so it accepts a nested array of objects as an argument:

   /**
     * Takes an array of pages, puts them into nested array.
     */
    private function generateNav($pages = array()) {

        foreach ($pages as $page) {

            $pageId = $page['Page']['id'];

            //Recurse on children:
            if ($this->Page->childCount($pageId)) {
                $this->generateNav($page['children']);
            }

            $pageData = $page;
            $parentId = ($pageData['Page']['parent_id'] != NULL)?$pageData['Page']['parent_id']:'root';

            //If page has children, create a branch including the children and merge into parent branch
            //else add directly to parent branch
            if ($this->Page->childCount($pageId)) {
                $arrayPortion = array('id' => $pageData['Page']['id'], 'title' => $pageData['Content'][0]['nav'], 'menu' => array());

                $branch = array_merge($arrayPortion, $this->children[$pageId]);
                unset($this->children[$pageId]);
                $this->children[$parentId]['menu'][] = $branch;
            }
            else {
                $arrayPortion = array('id' => $pageData['Page']['id'], 'title' => $pageData['Content'][0]['nav']);
                $this->children[$parentId]['menu'][] = $arrayPortion;
            }

        }
    }

It works by adding children to an array, so all the children for a certain parent will be added to the children array. A parent with an id of 32 might have a child array such as:

[32] => Array
(
     [menu] => Array
     (
           [0] => Array
           (
                [id] => 44
                [title] => Intro
            )
     )
)

On the way back up the stack, if the page the function is currently looking at has children, then those children are retrieved from the array and merged with their parent array. So we are building the tree of data from the bottom up, as we go up the stack we group increasingly larger chunks of the tree together, until at the top where we finally put the last two parts together:

if ($this->Page->childCount($pageId)) {
                $arrayPortion = array('id' => $pageData['Page']['id'], 'title' => $pageData['Content'][0]['nav'], 'menu' => array());

                $branch = array_merge($arrayPortion, $this->children[$pageId]);
                unset($this->children[$pageId]);
                $this->children[$parentId]['menu'][] = $branch;
}

The array_merge() is the important bit there, so that the children are merged into the menu element sub array of the parent.

It makes my head hurt.

Yes, this was quite a challenge, it made me think pretty hard about how recursion works. It was more difficult for me than when I have had to code up some recursive function in the past because I was managing arrays of data. I couldn't just output the data and be done with it, I needed to keep the data arranged in a way that mapped to the original form.

But I've documented it now, so next time it shouldn't be so bad.

Retrospect
in retrospect I guess I should have hacked up the tree helper and been done with it. But in the end I'm happy with the neat array of data I'm passing back from the controller and the view is exceptionally light :-p Plus, it was a good challenge and I don't like leaving something like this undone.

Hope it helps someone else trying to achieve the same thing.