How to turn this PHP array structure into multi-dimensional tree?

Question

I have a 2-dimensional PHP array which I need to turn in to a tree. The 'path' value in each inner-array is the enumerated path to the current node. (I got this idea from Bill Karwin's book on SQL Antipatterns).

So, the array that I am starting with looks something like this:

array(
[1] => array('name' => 'Animals', 'path' => '1/'),
[2] => array('name' => 'Birds', 'path' => '1/3/'),
[3] => array('name' => 'Cockatoos', 'path' => '1/3/5/'),
[4] => array('name' => 'Fish', 'path' => '1/2/'),
[5] => array('name' => 'Kookaburras', 'path' => '1/3/4/')
)

As you may have gathered, the index of the outer array is meaningless. I have simply ordered the inner arrays alphabetically on 'name' and PHP has assigned numeric indexes on the outer array.

As far as the 'path' value goes, the very last segement of each path is a pseudo-id for the node, i.e. Animals is node 1, Birds is node 3. You can see that the full path describes the route to the given node, e.g. 'Cockatoos' is parented by 'Birds', which is parented by 'Animals'.

I want to keep the alphabetic order of the nodes, but group them by their parent. In other words, I want an array that looks something like this (in its natural order):

[1]         => 'Animals'
[1][3]      => 'Birds'
[1][3][5]   => 'Cockatoos'
[1][3][4]   => 'Kookaburras'
[1][2]      => 'Fish'

I plan to iterate over this recursively to print a visual representation of the tree.

In trying to transform from one type of array to another my approaches have used recursion, variable variables and regular expressions, but I keep running into road blocks.

Also, is there an SPL data structure or iterator that I should be thinking about?

Thanks alot!

EDIT: Sorry, should have mentioned that the depth of the tree is variable. The example above has three levels, but in reality there will be many more.

Kim

Answer 1

This will work, no matter the depth of the tree, possible due to the use of the Eval() function (which stands for evaluate). But the sorting on alphabet is not working properly yet. Because the indexes of the parent arrays stay the same it gets mixed up. BUt atleast you can build a tree already :)

<?php
$a = array(
        array('name' => 'Animals', 'path' => '1/'), 
        array('name' => 'Birds', 'path' => '1/3/'), 
        array('name' => 'Eagles', 'path' => '1/3/3/'),
        array('name' => 'Cockatoos', 'path' => '1/3/5/'), 
        array('name' => 'Fish', 'path' => '1/2/'), 
        array('name' => 'Kookaburras', 'path' => '1/3/4/')
    );
Iterate($a);
$tree = Iterate($a);

var_dump($tree);

OneLevelDeeper($tree);
var_dump($tree);

function Iterate($ChildArray)
{
    $TreeArray;
    foreach($ChildArray as $Key => $Value)
    {
        //echo $Key.': '.$Value['name']."\r\n";
        $exp = explode('/', $Value['path']);
        $path;
        foreach($exp as $int)
        {
            if($int != "")
            {
                $path[] = $int;
            }
        }

        //Using Eval() function of PHP
        $BuildSourceToEvaluate = '$TreeArray';
        for($i=0; $i<(count($path)-1); $i++)
        {
            $BuildSourceToEvaluate .= '[$path['.$i.']]';
        }
        $BuildSourceToEvaluate .= '[] = $Value[\'name\'];';
        echo $BuildSourceToEvaluate."\r\n";
        Eval($BuildSourceToEvaluate);
        //print_r($path);
        /*
        switch(count($path))
        {
            case 0:
            break;
            case 1:
                $TreeArray[] = $Value['name']; 
                //$TreeArray[$path[0]] = $Value['name']; //Use this for unique paths and keeping hold of the last ID in the tree path
                //$TreeArray[$path[0]][] = $Value['name']; //Use this for non-unique tree paths
            break;
            case 2:
                $TreeArray[$path[0]][] = $Value['name']; 
                //$TreeArray[$path[0]][$path[1]] = $Value['name']; //Use this for unique paths and keeping hold of the last ID in the tree path
                //$TreeArray[$path[0]][$path[1]][] = $Value['name']; //Use this for non-unique tree paths
            break;
            case 3:
                $TreeArray[$path[0]][$path[1]][] = $Value['name'];
                //$TreeArray[$path[0]][$path[1]][$path[2]] = $Value['name']; //Use this for unique paths and keeping hold of the last ID in the tree path
                //$TreeArray[$path[0]][$path[1]][$path[2]][] = $Value['name']; //Use this for non-unique tree paths
            break;
        }
        */
        unset($path);
    }
    return $TreeArray;
}


function OneLevelDeeper(&$a)
{
    sort($a);
    foreach($a as $Key => $Value)
    {
        if(is_array($Value))
        {
            sort($a[$Key]);
            OneLevelDeeper($a[$Key]);
        }
    }
}

?>