SitePoint Sponsor

User Tag List

Results 1 to 16 of 16
  1. #1
    SitePoint Enthusiast
    Join Date
    Jul 2005
    Location
    Palo Alto, CA
    Posts
    76
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    function display_tree() : add nlevel

    I really enjoyed the http://www.sitepoint.com/article/hie...ata-database/2 article and was reading through the related comments thread ( http://www.sitepoint.com/forums/show...0&page=3&pp=25 ) I thought it was a great idea for what I am using this script for to add a node level.

    While trying to add some nodelevel functionality thus allowing easier tracking of where you are in the tree - I ran across some trouble.
    Quote Originally Posted by mysite
    0 Earth
    - 1 North America
    - - 2 United States
    - - - 3 Michigan
    - - - 3 California
    - - 2 Canada
    - - - 3 Ontario
    - 1 Europe
    - - 2 Spain
    - - - 2 France
    Notice that the France line has 3 dashes, instead of 2. It's parent is Europe though not Spain. Why are three dashes being displayed?
    PHP Code:
    //
    // display_tree
    function display_tree($root) {
        global 
    $geo_table;
       
    // retrieve the left and right value of the $root node
    echo mysql_error ();
        
    $sql "SELECT lft, rgt FROM $geo_table  WHERE title='$root';";
        
    $result mysql_query($sql);
        
    $row mysql_fetch_array($result);

       
    // start with an empty $right stack
       
    $right = array();

       
    // now, retrieve all descendants of the $root node

       
    $result mysql_query('SELECT title, lft, rgt, nlevel 
                             FROM '
    .$geo_table.
                             
    ' WHERE lft BETWEEN '.$row['lft'].' AND 
                             '
    .$row['rgt'].' ORDER BY lft ASC;');


        
    // display each row
       
    while ($row mysql_fetch_array($result)) {
           
    // only check stack if there is one
           
    if (count($right)>0) {
               
    // check if we should remove a node from the stack
               
    while ($right[count($right)-1]<$row['rgt']) {
                   
    array_pop($right);
               }
           }

           
    // display indented node titleeny    
           
    echo str_repeat('- ',count($right)) . $row['nlevel'] ." " $row['title']."
           <BR \>"
    ;

           
    // add this node to the stack
           
    $right[] = $row['rgt'];
       }


  2. #2
    SitePoint Guru enygmadae's Avatar
    Join Date
    Sep 2002
    Location
    Dallas, Tx.
    Posts
    795
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    I know it sounds silly, but have you checked the data to ensure that it's right?
    PHP News, Views and Community: http://www.phpdeveloper.org

  3. #3
    SitePoint Enthusiast
    Join Date
    Jul 2005
    Location
    Palo Alto, CA
    Posts
    76
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    yes yes.

    [mysql]
    -- Database: `travter_test`
    --

    -- --------------------------------------------------------

    --
    -- Table structure for table `cont_geography`
    --

    CREATE TABLE `cont_geography` (
    `id` int(8) NOT NULL auto_increment,
    `title` varchar(255) default NULL,
    `parent` varchar(255) default NULL,
    `lft` int(16) default NULL,
    `rgt` int(16) default NULL,
    `nlevel` int(3) default NULL,
    PRIMARY KEY (`id`)
    ) TYPE=MyISAM AUTO_INCREMENT=11 ;

    --
    -- Dumping data for table `cont_geography`
    --

    INSERT INTO `cont_geography` VALUES (1, 'Earth', NULL, 1, 20, 0);
    INSERT INTO `cont_geography` VALUES (2, 'North America', 'Earth', 2, 13, 1);
    INSERT INTO `cont_geography` VALUES (3, 'United States', 'North America', 3, 8, 2);
    INSERT INTO `cont_geography` VALUES (4, 'Michigan', 'United States', 4, 5, 3);
    INSERT INTO `cont_geography` VALUES (5, 'California', 'United States', 6, 7, 3);
    INSERT INTO `cont_geography` VALUES (6, 'Canada', 'North America', 9, 12, 2);
    INSERT INTO `cont_geography` VALUES (7, 'Ontario', 'Canada', 10, 11, 3);
    INSERT INTO `cont_geography` VALUES (8, 'Europe', 'Earth', 14, 19, 1);
    INSERT INTO `cont_geography` VALUES (9, 'Spain', 'Europe', 15, 18, 2);
    INSERT INTO `cont_geography` VALUES (10, 'France', 'Europe', 16, 17, 2);
    [/mysql]

  4. #4
    SitePoint Guru enygmadae's Avatar
    Join Date
    Sep 2002
    Location
    Dallas, Tx.
    Posts
    795
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    one thing you might try - you have two different result sets coming back into $row.
    Try changing one of them to something else...
    PHP News, Views and Community: http://www.phpdeveloper.org

  5. #5
    SitePoint Enthusiast
    Join Date
    Jul 2005
    Location
    Palo Alto, CA
    Posts
    76
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    I thought I would see what happened if I added another country to Europe.

    [mysql]
    UPDATE `cont_geography` SET `id` = 1, `title` = 'Earth', `parent` = NULL, `lft` = 1, `rgt` = 22, `nlevel` = 0 WHERE `id` = 1;
    UPDATE `cont_geography` SET `id` = 8, `title` = 'Europe', `parent` = 'Earth', `lft` = 14, `rgt` = 21, `nlevel` = 1 WHERE `id` = 8;
    UPDATE `cont_geography` SET `id` = 9, `title` = 'Spain', `parent` = 'Europe', `lft` = 15, `rgt` = 20, `nlevel` = 2 WHERE `id` = 9;
    UPDATE `cont_geography` SET `id` = 10, `title` = 'France', `parent` = 'Europe', `lft` = 16, `rgt` = 19, `nlevel` = 2 WHERE `id` = 10;
    INSERT INTO `cont_geography` SET `id` = 11, `title` = 'Germany', `parent` = 'Europe', `lft` = 17, `rgt` = 18, `nlevel` = 2 WHERE `id` = 11;
    [/mysql]

    and I got this result!
    Quote Originally Posted by mysite
    0 Earth
    - 1 North America
    - - 2 United States
    - - - 3 Michigan
    - - - 3 California
    - - 2 Canada
    - - - 3 Ontario
    - 1 Europe
    - - 2 Spain
    - - - 2 France
    - - - - 2 Germany
    something is definently wrong with the number of values in $right.

  6. #6
    SitePoint Member
    Join Date
    Jul 2005
    Posts
    13
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    I realized I hadn't clearly defined what a child with no descendants should look like

    Rebuild your tree. Take a look at Europe and its descendants:

    INSERT INTO `cont_geography` VALUES (9, 'Spain', 'Europe', 15, 18, 2);
    INSERT INTO `cont_geography` VALUES (10, 'France', 'Europe', 16, 17, 2);

    These show that France is, in fact, descended from Spain. Rebuild your tree, and all should be OK. Or, if you are inserting the data manually, try this:

    INSERT INTO 'cont_geography' VALUES (9, 'Spain', 'Europe', 15, 16, 2);
    INSERT INTO 'cont_geography' VALUES (10, 'France', 'Europe', 17, 18, 2);
    INSERT INTO 'cont_geography' VALUES (11, 'Germany', 'Europe', 19, 22, 2);
    INSERT INTO 'cont_geography' VALUES (12, 'Berlin', 'Germany', 20, 21, 2);

    Note that, if there are no descendants for a given node, the left and right values are consecutive. If, however, there are one (or more) descendants, the numbering increases sequentially DOWN THE LEFT, then UP THE RIGHT. So, by this token, the above changes should increase Europe's RIGHT value to 23 (only an increase of two digits, or one node - Berlin). By incrementing SpainLeft, FranceLeft,FranceRight, SpainRight in your code, you've asked that France be descended from Spain.

    If I have thoroughly confused you, don't hesitate to throw something at me.
    Last edited by bigClown; Jul 27, 2005 at 13:25. Reason: Clarification

  7. #7
    SitePoint Enthusiast
    Join Date
    Jul 2005
    Location
    Palo Alto, CA
    Posts
    76
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Code:
    0 Earth
    - 1 North America
    - - 2 United States
    - - - 3 Michigan
    - - - 3 California
    - - 2 Canada
    - - - 3 Ontario
    - 1 Europe
    - - 2 Spain
    - - 2 France
    - - 2 Germany
    Of course bigClown, you were absolutely right. Now that I have gone through this error I understand how the database structure and the script its self works much more clearly.

    If an item has no descendents it's right = (left +1) .

    I am sure this is not the last problem I will have while personalizing these functions, I am also (unless someone beats me to it) going to make a delete_node() function.

    Thanks again for your help bigClown!

  8. #8
    SitePoint Member
    Join Date
    Jul 2005
    Posts
    13
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    Cool A quick and dirty delete_node routine.

    Well, here's a routine, based loosely on the theories expounded in the article for the add_node routine. Pretty much what you need to do is remove the node and all its descendants, then decrement all remaining nodes. They should all be decremented by the difference between the selected node's right and left values, plus one.

    Code:
      function delete_node($title) {
        // This will delete a node AND ALL DESCENDANT NODES! If this isn't what you want,
        //  consider moving all sub-nodes out first. Alternatively, I can rewrite this to
        //  remove only the node, and change the nlevel of all child nodes to point to the
        //  deleted node's parent. However, this strikes me as slightly counter-intuitive.
        //
        // Logically, I think that the process will be similar to that of adding a node, only
        //  in reverse. First, we'll need to get the left and right value of the node to be
        //  removed. When we have this, we'll run a delete to remove any node whose left and
        //  right fall between these values (inclusive, to remove the node itself). Then, we
        //  need to decrement all left and right node values by the difference between the
        //  deleted node's right and left values, plus one.
    
        global $geo_table;    
        
        // First, get the right/left from the selected node.
        $result = mysql_query('SELECT rgt, lft from '.$geo_table.' WHERE title="'.$title.'";');
        $row = mysql_fetch_array($result);
        $leftVal = $row['lft'];
        $rightVal = $row['rgt'];
        $decrementBy = $rightVal - $leftVal + 1;
        
        // Now, we have the range of nodes to be deleted.
        $result = mysql_query('DELETE FROM '.$geo_table.' WHERE lft BETWEEN '.$leftVal.' AND '.$rightVal.';');
        
        // If this is right, we should decrement all remaining nodes with a left and/or right
        //  greater than the deleted node's right value by our $decrementBy value. I think.
        $result2 = mysql_QUERY('UPDATE '.$geo_table.' SET rgt=rgt-'.$decrementBy.' WHERE rgt>'.$rightVal.';');
        $result3 = mysql_QUERY('UPDATE '.$geo_table.' SET lft=lft-'.$decrementBy.' WHERE lft>'.$rightVal.';');
        
        // And that should do it.
      }

  9. #9
    SitePoint Enthusiast
    Join Date
    Jul 2005
    Location
    Palo Alto, CA
    Posts
    76
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    haha, thanks so much bigClown. I had that on my todo list for monday. :-D

    you should post delete_node with your other two comments on the related article.
    of course, $geo_table = tree in the article.

    Thanks again, I am not so pro that I would have been able to figure it out in so few lines. ctually, I am pretty amature. Thanks again- I am learning a great deal.

  10. #10
    SitePoint Member
    Join Date
    Jul 2005
    Posts
    13
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    Red face Pro? ME?! I'm a CLOWN, man!!

    Heh! I'm a full-time entertainer, left the programming field four years ago, now, and found that I missed it. So, I've been getting back into it, bit by bit. This just struck me as something I could see, as a practical project.

    My next planned todo is to be able to move a node within its current location. For example, say you're using this for a website's navigation menu. You may want to be able to move a given page within its current submenu location either up or down. I am actually looking at integrating AJAX into this, as well. Not sure why, just seems a good fit.

  11. #11
    SitePoint Enthusiast
    Join Date
    Jul 2005
    Location
    Palo Alto, CA
    Posts
    76
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Haha, you have a great webby - I can see where that move_node section could be useful for your menu. I find it commendable that someone so intelligent spends their life making people happy rather than trying to uproot Gate$.

    about delete_node() though. with a database structure as I have running for me right now, id,title,parent,lft,right,nlevel - personally I could simply

    PHP Code:
    $result mysql_query('DELETE FROM '.$geo_table.' WHERE id = '.$id); 
    instead of the whole
    PHP Code:
    WHERE lft BETWEEN '.$leftVal.' AND '.$rightVal.' 
    business, right?

    The reason I ask is because I want to make sure that I am not missing some advantage in the "business".

  12. #12
    SitePoint Member
    Join Date
    Jul 2005
    Posts
    13
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    That would be fine, with two minor (and related) problems: First, it doesn't dispose of any descendant nodes. Second, it doesn't change any of those non-disposed subnodes to point to a current node. I mean, say you delete Canada from your example. Ontario still exists, pointing at a non-existent Canada record, which leaves it hanging, even on a rebuild. In fact, it would probably barf on a rebuild.

    What you'd need to do is to address any descendants first, then do your delete the way you have it. I agree that IDs are the way to go - point the child nodes to the parent's ID rather than the parent's name. I inadvertently added a second Canada/Ontario set earlier, and that's a pain - I had no means of removing just that later one, based on what we'd been doing.

    If you're after a non-destructive delete (delete this node, but not its children), delete by ID is the way to go. Just make sure to move the child nodes to a properly connected parent first.

  13. #13
    SitePoint Enthusiast
    Join Date
    Jul 2005
    Location
    Palo Alto, CA
    Posts
    76
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    aha, so I was missing something in the "business" end :-D
    Your way definently works how it needs to and is consistent with the idealogy behind the other functions.

    As for parentID instead of parentTitle. I agree that that would be easier, could just delete all who have the parentID. But, the "complicated" approach we are currently pursuing has more thought behind it, which of course makes it better

  14. #14
    SitePoint Member
    Join Date
    Jul 2005
    Posts
    13
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Nope, you couldn't just delete all those who have the parentID - that'd be the same as deleting all who have 'Canada' as their parent title. You'd still need to use the left and right value, because you can have sub-sub-nodes. For example, suppose you have 'Berlin' under 'Germany' under 'Europe' under 'Earth'. Delete any with a parent of 'Europe', and 'Berlin' is still there, because its GRANDparent is 'Europe'.

    Does this make any sense?

  15. #15
    SitePoint Enthusiast
    Join Date
    Jul 2005
    Location
    Palo Alto, CA
    Posts
    76
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    of course, and your right that your way is the way to do it.
    I was thinking to short sited, as we kids are prone to do.

  16. #16
    SitePoint Member
    Join Date
    Jul 2005
    Posts
    13
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Ouch! Kids?! I'm just used to moofing the things up! BTW, another advantage of this approach (modified traversal vs. recursive) is that any node can be determined to be a descendant of another, simply by checking if its values are between the left and right of the possible ancestor. By this, orphans are fairly easily remedied!


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
  •