SitePoint Sponsor

User Tag List

Results 1 to 11 of 11
  1. #1
    SitePoint Member
    Join Date
    Sep 2003
    Location
    A House
    Posts
    12
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    Converting Nested Set Array into a Nested Array

    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.

    Code:
    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
            )
    )
    Code:
    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
                                    (
                                    )
    
                            )
    
                    )
    
            )
    
    )
    PHP Code:
    $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.
    Last edited by saberworks; Dec 18, 2003 at 14:25. Reason: code paste bug fix

  2. #2
    Non-Member coo_t2's Avatar
    Join Date
    Feb 2003
    Location
    Dog Street
    Posts
    1,819
    Mentioned
    1 Post(s)
    Tagged
    1 Thread(s)
    Quote Originally Posted by saberworks
    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

  3. #3
    SitePoint Member
    Join Date
    Sep 2003
    Location
    A House
    Posts
    12
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    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).

  4. #4
    Non-Member coo_t2's Avatar
    Join Date
    Feb 2003
    Location
    Dog Street
    Posts
    1,819
    Mentioned
    1 Post(s)
    Tagged
    1 Thread(s)
    Quote Originally Posted by 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).
    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

  5. #5
    SitePoint Member
    Join Date
    Sep 2003
    Location
    A House
    Posts
    12
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    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.

  6. #6
    SitePoint Member
    Join Date
    Sep 2003
    Location
    A House
    Posts
    12
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    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.

  7. #7
    SitePoint Member
    Join Date
    Sep 2003
    Location
    A House
    Posts
    12
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    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.

    PHP Code:
    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).

  8. #8
    SitePoint Member
    Join Date
    Sep 2003
    Location
    A House
    Posts
    12
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    Oops!

    There is a bug in the above code. This code should fix it.
    PHP Code:
        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($catstrue);
                }

                
    $next_id key($cats);

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

            return 
    $new;
        } 

  9. #9
    Non-Member coo_t2's Avatar
    Join Date
    Feb 2003
    Location
    Dog Street
    Posts
    1,819
    Mentioned
    1 Post(s)
    Tagged
    1 Thread(s)
    Quote Originally Posted by saberworks

    $new[$cat['id']]['children'] = $this->nest($cats, true);
    Did you really mean $this->nest ? Is this part of a class?

    --ed

  10. #10
    SitePoint Member
    Join Date
    Sep 2003
    Location
    A House
    Posts
    12
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    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.

  11. #11
    SitePoint Zealot prefab's Avatar
    Join Date
    Jan 2003
    Location
    Belgium
    Posts
    133
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    I'm using a slightly modified version of saberworks' code:

    PHP 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.


Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •