Converting Nested Set Array into a Nested Array

[saberworks]

I've been going through this tutorial on nested sets: http://www.sitepoint.com/article/1105/2

And I'm having a problem. Their method for "getting the tree" is nice, but they use this stack method for printing multiples spaces in front of nested items. Instead of just printing, I need the whole tree to be in a nested array I can pass around to various functions (specifically in this case, I'm going to use the nested array to generate a javascript tree browser with expanding and collapsing nodes - but that's not important).

So, the flat array is listed below, and below that is the array I want. If anyone could be of help, that would be greatly appreciated. I'm having trouble wrapping my head around it!

Also, as I was writing this post, I realized I could recursively look through the array for children, but that would require a foreach loop going through the entire array looking for children for *each* node... not very efficient. So I programmed it, and tried to modify the array as I found children to delete the childen (so they wouldn't ever get looped through more than once).

I'm thinking, there has to be a better way. It's certainly twisting my brain all up! So anyway, first we have the original array, then the array I want, then the code I used to get the array that I want, but hoping I can figure a more elegant way to get it.

Array
(
    [0] => Array
        (
            [cat_id] => 1
            [parent_id] => 
            [cat_name] => null test
            [cat_description] => null null null null null
            [lft] => 1
            [rgt] => 8
        )

    [1] => Array
        (
            [cat_id] => 5
            [parent_id] => 1
            [cat_name] => sub cat #1
            [cat_description] => sub cat #1
            [lft] => 2
            [rgt] => 5
        )

    [2] => Array
        (
            [cat_id] => 7
            [parent_id] => 5
            [cat_name] => sub sub cat #1
            [cat_description] => sub sub cat #1
            [lft] => 3
            [rgt] => 4
        )

    [3] => Array
        (
            [cat_id] => 6
            [parent_id] => 1
            [cat_name] => sub cat #2
            [cat_description] => sub cat #2
            [lft] => 6
            [rgt] => 7
        )

    [4] => Array
        (
            [cat_id] => 10
            [parent_id] => 
            [cat_name] => parent Cat
            [cat_description] => parent Cat
            [lft] => 9
            [rgt] => 12
        )

    [5] => Array
        (
            [cat_id] => 11
            [parent_id] => 10
            [cat_name] => kid of parent Cat
            [cat_description] => kid of parent Cat
            [lft] => 10
            [rgt] => 11
        )
)

Array
(
    [0] => Array
        (
            [cat_id] => 1
            [parent_id] => 
            [cat_name] => null test
            [cat_description] => null null null null null
            [children] => Array
                (
                    [0] => Array
                        (
                            [cat_id] => 5
                            [parent_id] => 1
                            [cat_name] => sub cat #1
                            [cat_description] => sub cat #1
                            [children] => Array
                                (
                                    [0] => Array
                                        (
                                            [cat_id] => 7
                                            [parent_id] => 5
                                            [cat_name] => sub sub cat #1
                                            [cat_description] => sub sub cat #1
                                            [children] => Array
                                                (
                                                )

                                        )

                                )

                        )

                    [1] => Array
                        (
                            [cat_id] => 6
                            [parent_id] => 1
                            [cat_name] => sub cat #2
                            [cat_description] => sub cat #2
                            [children] => Array
                                (
                                )

                        )

                )

        )

    [1] => Array
        (
            [cat_id] => 10
            [parent_id] => 
            [cat_name] => parent Cat
            [cat_description] => parent Cat
            [children] => Array
                (
                    [0] => Array
                        (
                            [cat_id] => 11
                            [parent_id] => 10
                            [cat_name] => kid of parent Cat
                            [cat_description] => kid of parent Cat
                            [children] => Array
                                (
                                )

                        )

                )

        )

)

$nested_cats = nest_cats($cats);

function nest_cats($cats) {
    $levels = array();
    $i = 0;

    foreach($cats as $cat) {
        if($cat['parent_id'] == null) {
            unset($cat['lft']);
            unset($cat['rgt']);
            $levels[$i] = $cat;
            $levels[$i]['children'] = get_children($cat['cat_id'], $cats);
            $i++;
        }
    }

    return $levels;
}

function get_children($id, $cats) {
    $return = array();
    $i = 0;

    foreach($cats as $cat_id => $cat) {
        if($cat['parent_id'] == $id) {
            unset($cat['lft']);
            unset($cat['rgt']);
            $return[$i] = $cat;
            unset($cats[$cat_id]);
            $return[$i]['children'] = get_children($cat['cat_id'], $cats);
            $i++;
        }
    }

    return $return;
} 

Thanks in advance for any help.

[coo_t2]

I've been going through this tutorial on nested sets: http://www.sitepoint.com/article/1105/2

[snip]

Have you looked into using any libraries out there that deal with nested sets?
I've been using [and a partridge in a] Pear/Tree. It probably does most of what you need done for you.

http://pear.php.net/package/Tree
http://opensource.visionp.biz/index.php?id=85

--ed

[saberworks]

Thanks for the reply, but even when they use the nested set method, it appears that for their "getChildren()" method, they are doing one query per level of the tree, which completely defeats the purpose of using a nested set (you can get the whole tree in one query).

[coo_t2]

Thanks for the reply, but even when they use the nested set method, it appears that for their "getChildren()" method, they are doing one query per level of the tree, which completely defeats the purpose of using a nested set (you can get the whole tree in one query).

Oh really? To be honest I haven't really looked much at the code that makes that package work.


There's other packages that you can use too.

Here's another Pear one:
http://oss.webcluster.at/

Here's another link:
http://www.inses.ru/link/?www.inses....reebrowser.zip

Don't remember if that one uses the nested sets method or not.

Both were posted in this thread:
http://sitepointforums.com/showthread.php?t=139942

--ed

[saberworks]

Thanks again. I had previously downloaded the treebrowser.zip one. It is capable of creating the first array I posted (the flat one), but it does not do nesting as in the second array.

I just downloaded the PEAR Nested_Set one, and it's got the same thing (in that it returns a "flat" representation of the tree). Its ouptut mechanisms (used for generating javascript trees, similar to what I'm doing) uses an approach similar to the one I've come up with above. Instead of unsetting the array items they've already hit, however, they "mark" them as hit and skip over them. I think it still results in a lot of unneeded looping (it still loops on the full array each recursive time, it just does an initial comparison at the beginning to determine whether the node has previously been examined, and if so, "continues").

Probably it's the most elegant solution I can come up with for now. I think it's fairly speedy, so I'll stick with it for now. It seems like I'm using this parent_id thing which I shouldn't have to use (since I'm doing a nested set anyway!), I'll go through and see if I can rewrite it by examining the lft and rgt values. Maybe that will help.

[saberworks]

Actually, I think I figured a way to do it. I will code it and post it tonight, going to see the new lord of the rings movie now Thanks again for your comments.

[saberworks]

Okay, I figured a really good way to do it. It only iterates one key of the main array once. Here is the code, in case anyone is interested.

function nest(&$cats) {
    $new = array();

    while(list($i, $cat) = each($cats)) {
        $new[$cat['id']] = $cat;

        if($cat['rgt'] - $cat['lft'] != 1) {
            $new[$cat['id']]['children'] = nest($cats);
        }
        else {
            return $new;
        }
    }

    return $new;
} 

This will take the first array I posted way above and turn it into the second (nested) one. (Actually, I changed 'cat_name' to be 'title' and cat_id to be 'id' in case you're actually going to try it out).

[saberworks]

There is a bug in the above code. This code should fix it.

    function nest(&$cats) {
        $new = array();

        while(list($id, $cat) = each($cats)) {
            $new[$cat['id']] = $cat;

            if($cat['rgt'] - $cat['lft'] != 1) {
                $new[$cat['id']]['children'] = $this->nest($cats, true);
            }

            $next_id = key($cats);

            if($next_id && $cats[$next_id]['parent_id'] != $cat['parent_id']) {
                return $new;
            }
        }

        return $new;
    } 

[coo_t2]

$new[$cat['id']]['children'] = $this->nest($cats, true);

Did you really mean $this->nest ? Is this part of a class?

--ed

[saberworks]

Oops, yeah, I moved it into part of a class. But you can just remove the $this-> part and it should work. Sorry about the confusion.

[prefab]

I'm using a slightly modified version of saberworks' code:

function nestedArray(&$result, $prefix = '', $path = '', $level = -1) {
    $new = array();
    if(is_array($result)) {            
        while(list($n, $sub) = each($result)) {
            $subId = $prefix.$sub['id']; 
            $new[$subId] = $sub; 
            $new[$subId]['_tree_path'] = $path.'/'.$sub['name'];
            $new[$subId]['_tree_level'] = $level + 1;
                                
            if($sub['right'] - $sub['left'] != 1) {
                // recurse ($result is manipulated by reference!)
                $new[$subId]['subnodes'] = nestedArray($result, $prefix,
                    $new[$subId]['_tree_path'], $new[$subId]['_tree_level']);                                
            }                
            
            $next_id = key($result);
            if($next_id && $result[$next_id]['parentId'] != $sub['parentId']) { 
                return $new; 
            } 
        }
    }
    return $new; 
} 

Everything works well if I retrieve all childnodes of a certain node. But once I limit the childnode level,
to fetch only direct child nodes for example, things go wrong. Nodes are getting nested, while they
shouldn't be nested (still the same parentId).

The code above is so quick and compact, that it's hard to figure out where things go wrong.
I suspect the $result[$next_id]['parentId'] != $sub['parentId'] part, but I can't seem to find
a solution myself. PM me if you need actual usage code.

Thanks.