SitePoint Sponsor

User Tag List

Results 1 to 12 of 12
  1. #1
    SitePoint Addict
    Join Date
    Nov 2005
    Posts
    241
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    Question preorder tree traversal alphebetical

    I'm using the method described at http://www.sitepoint.com/article/hie...ata-database/2 to store categories in my database. The only problem I am having is modifying the display_tree function to order the categories alphabetically and maintain the correct display. I have tried storing the data in various multidimensional arrays, then sorting the arrays with no avail.

    Does anyone know the solution?

    Any help appreciated. Thanks.

  2. #2
    SitePoint Addict
    Join Date
    Nov 2005
    Posts
    241
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Anyone?

  3. #3
    Worship the Krome kromey's Avatar
    Join Date
    Sep 2006
    Location
    Fairbanks, AK
    Posts
    1,621
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    You need a completely different approach to retrieving your tree by having MySQL compute the depth for you. This requires a single self join:
    Code:
    SELECT COUNT( parent.category ) -1 AS depth,
    	  node.category, node.lft
    	  FROM categories AS node, categories AS parent
    	  WHERE node.lft BETWEEN parent.lft AND parent.rgt
    	  GROUP BY node.category
    	  ORDER BY node.lft
    This will return a list of your categories in their proper nested order, with each level of nesting in ascending alphabetical order. I can't take credit for this query, but neither can I remember where I found it. Google for "hierarchical data in database" (and similar queries) and you'll find all kinds of useful resources that all came in great handy when I built my own system that needed to store hierarchical data.
    PHP questions? RTFM
    MySQL questions? RTFM

  4. #4
    SitePoint Addict
    Join Date
    Nov 2005
    Posts
    241
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Thanks a lot!

  5. #5
    SitePoint Addict
    Join Date
    Nov 2005
    Posts
    241
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Ok. I finally implemented this query into the PHP script and I am getting the same exact tree as I was before (no alphabetical order). Any ideas? Is there something I need to add? When you do "order by node.lft", I don't think the group by even makes any difference and without the "order by lft", the tree is completely messed up.

    By the way, the query is used as an example on http://dev.mysql.com/tech-resources/...ical-data.html
    Last edited by penguinator; Aug 27, 2007 at 15:15.

  6. #6
    Worship the Krome kromey's Avatar
    Join Date
    Sep 2006
    Location
    Fairbanks, AK
    Posts
    1,621
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    The GROUP BY clause will order them in alphabetical, ascending order. It works like a charm in my application - at each level in the hierarchy, the categories should be in ascending alphabetical order, and of course the levels themselves are in ascending order.

    Is that what you're looking for, or did you merely want a purely alphabetical order of all your categories? Or an alphabetical listing of only a single category?

    Please show us the output you are currently getting and what you want to see.
    PHP questions? RTFM
    MySQL questions? RTFM

  7. #7
    SitePoint Addict
    Join Date
    Nov 2005
    Posts
    241
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Here is a screenshot of the output.. http://img337.imageshack.us/img337/6065/screenuf6.jpg

    ... and the php function which is generating that output...
    PHP Code:
    function displayTree($root,$call='categories') {
        global 
    $settings;

        
    $query 'SELECT node.*, (COUNT(parent.name) - 1) AS depth
        FROM '
    .$settings['categories_table'].' AS node,
        '
    .$settings['categories_table'].' AS parent
        WHERE node.lft BETWEEN parent.lft AND parent.rgt
        GROUP BY node.name
        ORDER BY node.lft'
    ;

        
    $result mysql_query($query) or die(mysql_error());

        
    // display each row
        
    $output 'root<br />';
        for (
    $i=0;$row mysql_fetch_array($result);$i++) {

            
    // display indented node title
            
    if($row['id'] != '1'){
                if(
    $call == 'categories'){
                    
    $catname urlencode(urlencode($row['name']));
                    
    $output .= str_repeat('&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;',$row['depth']).'|__ '.$row['name']." <a href=\"javascript:delete_category('{$row['id']}','{$catname}')\">[X]</a> <a href=\"edit.php?catid={$row['id']}&ref=cats\">[Edit]</a> <a href=\"{$_SERVER['PHP_SELF']}?newsubparent={$row['id']}\">[+]</a> <a href=\"{$_SERVER['PHP_SELF']}?move={$row['id']}\">[Move]</a><br />\n";
                } elseif(
    $call == 'newlink'){
                    
    $output .= str_repeat('&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;',$row['depth']).'|__ '.$row['name']." <a href=\"{$_SERVER['PHP_SELF']}?cat={$row['id']}\">[+]</a><br />\n";
                }
            }

        }
        return 
    $output;


  8. #8
    SitePoint Addict
    Join Date
    Nov 2005
    Posts
    241
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Here is pure mysql output.


  9. #9
    Worship the Krome kromey's Avatar
    Join Date
    Sep 2006
    Location
    Fairbanks, AK
    Posts
    1,621
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Oops, you're exactly right, this query does not sort alphabetically, my bad!

    I remember now how my app displays everything properly nested and in alphabetical order - that's how I insert them! It would be trivial to add an ORDER BY depth, node.name or even simply ORDER BY node.name, but you would completely lose your hierarchical structure if you do that.

    The way I maintain an alphabetical order is when I insert a new entry, instead of merely tacking it onto the end like is recommended in the SitePoint article you found, I find the first entry among its siblings (i.e. the first-generation children of the new node's parent) that would come after the new node in alphabetical order, then shift that and every node after it to make room for the new node. It's only very marginally more complex than inserting at the end.

    I'd show you the queries that do this, but unfortunately I don't have those scripts here at the moment, only an older version that does not do this sorting. Essentially, though, it's fairly simple:

    1) Pull out a list of the new node's immediate children (i.e. the nodes that are only 1 level below the parent). That query would look something like this:
    Code:
    SELECT node.name, node.id, (COUNT(parent.id) - 1) AS depth
    FROM pages AS node,
    	pages AS parent,
    	pages AS sub_parent
    WHERE node.lft BETWEEN parent.lft AND parent.rgt
    	AND parent.lft BETWEEN sub_parent.lft AND sub_parent.rgt
    	AND sub_parent.id = '$parent_id'
    GROUP BY node.id
    HAVING depth = 1
    ORDER BY node.name
    2) Find the first node that would come immediately after the new node in an alphabetical listing. That could be as simple as modifying the above query as so (untested, pulling this one from memory):
    Code:
    HAVING depth = 1 AND node.name > '$new_node_name'
    LIMIT 1
    3) Now that we have the id of the first node that needs to move, we run the proper updates to insert our new node:
    Code:
    START TRANSACTION;
    SELECT @old_lft:=lft FROM pages WHERE id='$target_node_id' FOR UPDATE;
    UPDATE pages SET lft=lft+2 WHERE lft>=@old_lft;
    UPDATE pages SET rgt=rgt+2 WHERE rgt>=@old_lft;
    UPDATE pages SET lft=@old_lft, rgt=@old_lft+1 WHERE id='$new_node_id';
    COMMIT;
    NOTE: You can see from here that I'm using the InnoDB engine and transactions. If you are also using InnoDB (which I recommend for this purpose solely to guarantee ACID-ity of these operations), then you would actually want to start your transaction before the first query above. Also, you can probably gather from the last UPDATE that I insert my new nodes into the database at an invalid position (I give them default lft and rgt values of 0 if I recall correctly, where my root's lft is 1) and then afterward assign the proper lft and rgt values. I'm also using MySQL's user-defined variables here to do all the work in the database without needing to pull in and process result sets in PHP; not really sure if I'm gaining anything, but at least to me it's more readable this way.

    If you do all that from the get-go, you should end up with alphabetically-sorted, properly-nested hierarchical data when you run the first query I gave you way up in my first post here.
    PHP questions? RTFM
    MySQL questions? RTFM

  10. #10
    SitePoint Addict
    Join Date
    Nov 2005
    Posts
    241
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    The way my application currently works is there is a 'parent' column which contains the ID of the parent category. When a new category is added, the lft and rgt columns are updated.

    I'm going to look at what you suggested and see if I can get that to work. Thanks again.

  11. #11
    SitePoint Addict
    Join Date
    Nov 2005
    Posts
    241
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    I feel like a complete idiot now! With the following function, I just added an order by to the select query.

    PHP Code:
    function rebuildTree($parent$left) {
        global 
    $settings;
        
    // the right value of this node is the left value + 1
        
    $right $left+1;

        
    // get all children of this node
        
    $result mysql_query('SELECT id FROM '.$settings['categories_table'].
        
    ' WHERE parent="'.$parent.'" ORDER BY `name`;');
        while (
    $row mysql_fetch_array($result)) {
            
    // recursive execution of this function for each
            // child of this node
            // $right is the current right value, which is
            // incremented by the rebuild_tree function
            
    $right rebuildTree($row['id'], $right);
        }

        
    // we've got the left value, and now that we've processed
        // the children of this node we also know the right value
        
    mysql_query('UPDATE '.$settings['categories_table'].' SET lft='.$left.', rgt='.
        
    $right.' WHERE id="'.$parent.'";');

        
    // return the right value of this node + 1
        
    return $right+1;

    Why I didn't think of this is a mystery to me... I appreciate all of your help. I now have an organized tree.

  12. #12
    SitePoint Enthusiast
    Join Date
    Aug 2007
    Posts
    56
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Are you linking items or what nots to your categories too?

    I'm trying to figure that part out but no one seems to know. :\


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
  •