SitePoint Sponsor

User Tag List

Page 1 of 4 1234 LastLast
Results 1 to 25 of 83

Hybrid View

  1. #1
    Non-Member
    Join Date
    Jan 2004
    Location
    Planet Earth
    Posts
    1,764
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    Views on my Modified Preorder Tree Classes

    Hello, the most commonly used method to traverse a hierarchy uses recursion which is slow and tedious, so I thought I'd use the alternate method

    More complicated though a lot faster, and this far is what I have, and thought I'd post the script to get feedback on it, and in doing so, help others.

    What I'm pondering on is, would I be better off with a Service Layer to encapsulate the process that is within the Controller, since there are a couple of statements that are using direct reference to the database layer in the Controller ?

    I think this is breaking layering

    PHP Code:
    //-- start
        
        
    class MenuPageController extends Controller {
            function 
    MenuPageController() {
                
    Controller::Controller();
            } 
            
            function 
    Dispatch() {
                
    $root TreeGateway::LoadTreeFinder::FindByRoot() );
                
    $tree TreeGateway::LoadAllTreeFinder::FindAll$root['fld_lft'], $root['fld_rgt'] ) );
                
                
    $temp = array();
                
    $traversal = &new TraversalPreOrderTree;
                
                for( 
    $a 0;$a sizeof$tree );$a++ ) {
                    if( 
    sizeof$temp ) > (int) ) {
                        while( 
    $temp[sizeof$temp ) -1] < (int) $tree[$a]['fld_rgt'] ) {
                            
    array_pop$temp );
                        }
                    }
                    
    $temp[] = $tree[$a]['fld_rgt'];
                    
                    
    $traversal -> Add$tree[$a], sizeof$temp ) );
                }
                
                
    $view = &new Menu;
                
    $view -> Put$traversal -> Fetch() );
                
                return 
    $view;
            }
        }
        
        class 
    TraversalPreOrderTree {
            var 
    $archive;
            
            function 
    TraversalPreOrderTree() {    
                
    $this -> archive = array();
            }
            
            function 
    Fetch() {
                return 
    $this -> archive;
            }
            
            function 
    Add$node$level ) {
                
    $this -> archive[] = $this -> Load$node$level );
            }
            
            function 
    Load$node$level ) {
                
    $leaf = array();
                
                
    $leaf['id']     = (int) $node['fld_id'];
                
                
    $leaf['lev']     = (int) $level;
                
    $leaf['lft']     = (int) $node['fld_lft'];
                
    $leaf['rgt']     = (int) $node['fld_rgt'];
                
                
    $leaf['name']     = (string) $node['fld_name'];
                
    $leaf['desc']     = (string) $node['fld_description'];
                
                return 
    $leaf;
            }
        }
        
        class 
    TreeGateway {
            function 
    TreeGateway() {
            }
            
            function 
    Load$resultset ) {
                
    $iterator = &new QueryIterator$resultset );
                
                return 
    $iterator -> GetCurrent();            
            }
            
            function 
    LoadAll$resultset ) {
                
    $archive = array();
                
    $iterator = &new QueryIterator$resultset );
                
    #
                
    while( $iterator -> IsValid() ) {
                    
    $row $iterator -> GetCurrent();
                    
    $iterator -> GetNext();
                    
    #
                    
    $archive[] = $row;
                }
                return 
    $archive;
            }
            
            function 
    Sort() { }
            function 
    Move() { }
            
            function 
    Insert() { }
            function 
    Update() { }
            function 
    Delete() { }
        }
        
        class 
    TreeFinder {
            function 
    TreeFinder() {
            }
            
            function 
    FindByRoot() {
                
    $db singleton::getInstance();
                
    #
                
    $findByRoot "SELECT * FROM ".DBASE_HIERARCHY." WHERE 
                    fld_name = 'Root' ORDER BY fld_lft ASC"
    ;
                    
                return 
    $db -> Execute$findByRoot );
            }
            
            function 
    FindAll$lft$rgt ) {
                
    $db singleton::getInstance();
                
    #
                
    $findAll "SELECT * FROM ".DBASE_HIERARCHY." WHERE 
                    fld_lft BETWEEN '"
    .$lft."' AND '".$rgt."' ORDER BY fld_lft ASC";
                
                return 
    $db -> Execute$findAll );
            }
        }
        
        class 
    Menu {
            var 
    $hierarchy;
            var 
    $tag 'menu';
            var 
    $html;
            
            function 
    Menu() {
            }
            
            function 
    Put( &$model ) {
                
    $this -> hierarchy = &$model;
            }
            
            function 
    ToHtml() {
                return 
    $this -> html;
            }
            
            function 
    Implement() {
                
    $html '';
                
    $content = &new ViewHelper'menu-section.template.tpl' );
                
                
    $iterator = &new ArrayIterator$this -> hierarchy );
                
    $row $iterator -> GetCurrent();
                
    $iterator -> GetNext();
                
                
    #
                
    $content -> Paste'<tag.section />''<li>'.$row['name'].'</li><tag.section />' );
                
                
    $level $row['lev']; // initially zero
                
                
    while( $iterator -> IsValid() ) {
                    
    $row $iterator -> GetCurrent();
                    
    $iterator -> GetNext();
                    
    #
                    
    $newlevel $row['lev'];
                    
                    if( 
    $newlevel $level ) { 
                        
    $content -> Paste'<tag.section />''' );
                        
    $content -> Paste'<tag.lessthan />''<li>'.$row['name'].'</li><tag.section />'."\r\n" );
                    }
                    else if( 
    $newlevel == $level ) { 
                        
    $content -> Paste'<tag.section />''<li>'.$row['name'].'</li><tag.section />'."\r\n" );
                        
                    }
                    else {
                        
    $content -> Paste'<tag.lessthan />''' );
                        
    $content -> Paste'<tag.section />''<ul><li>'.$row['name'].'</li><tag.section /></ul><tag.lessthan />'."\r\n" );
                    }
                    
                    
    $level $newlevel;
                }
                
                
    $this -> html = (string) $content -> Finalise();
            }
        }
        
        
    /* change log
        ** 
    The View layer is a mess, though I'm not too concerned about this just now, which will be refactored later - I just want to sort out the Controller/Model layering first

    Thanks for your comments and help.

  2. #2
    SitePoint Wizard Dangermouse's Avatar
    Join Date
    Oct 2003
    Posts
    1,024
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Off Topic:

    Just our curiosity, what are the "#" on a seperate line for?

  3. #3
    Non-Member
    Join Date
    Jan 2004
    Location
    Planet Earth
    Posts
    1,764
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Readability, ie

    PHP Code:
    ...
    $iterator = &new ArrayIterator( ... );
    #
    ... 
    Lets you see right away that the iterator statement(s) are a seperate function from the rest of the function/method

    Though some folks just have whitespace, I use on occasion the hash as well

  4. #4
    SitePoint Wizard Dangermouse's Avatar
    Join Date
    Oct 2003
    Posts
    1,024
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Off Topic:

    is a whitespace kinda guy

  5. #5
    SitePoint Addict been's Avatar
    Join Date
    May 2002
    Location
    Gent, Belgium
    Posts
    284
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Off Topic:

    Widow Maker gets paid by K-line?
    Per
    Everything
    works on a PowerPoint slide

  6. #6
    Non-Member
    Join Date
    Jan 2004
    Location
    Planet Earth
    Posts
    1,764
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)


    Nope, I'm not paid by filesize based on every 1024 bytes

    Paid once the job is done, and it's not getting done by answering off topic postings either

    Does anyone have any genuine comments and help to give ?

  7. #7
    SitePoint Addict
    Join Date
    Mar 2003
    Location
    Germany
    Posts
    216
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Here's one that finds your post helpful already!

    Have very little time this week, so I must keep this short.

    You have prpobably seen this, but there's an article about storing hierarchical
    data in a db on this very site:

    http://www.sitepoint.com/article/hie...-data-database

    I was about to develop my own menu class, that's why I find your post interesting. I intended to use the other method (adjacency list), but only because I thought the db table might be easier to manage. As my menu has only 2 levels, I wouldn't need recursion either. My idea was to get all rows from the db pre-sorted and then just do some array mangling to get everything that I need out of it. My table has a level column as well and one column for the position of the element within the level. But I think your way is probably more flexible.

    How do you handle the table, especially the left and right values? Do you input them by hand? Or do you have some handy function for this? Manually I think it would be rather complicated?

    As I'm using WACT for my project, I can at least keep the HTML out of the class, since my idea was for the class to return an array that could be used as a data source for a list in the template. On the other hand, I would have to hard-code the css styles for the menu list elements in the class (I'm using special css classes for "navlink", "navsection" "activenavlink" and "activenavsection"). Couldn't think of a way around this yet.

    Another problem I had was the Home page link, that is the first link in my menu. Should this be the root level? But then all elements would be sub-items of Home, which I want to avoid. (I want Home to be a "Category" or "subsection" like the others, with no children). If I put it on the same level as the other categories, I have a problem with the breadcrumb trail instead... (I want the menu class to output breadcrumb trails as well). My idea was to put home on the same level and include antoher column that says what element is the "home" link. Don't know if this is ideal. How would you deal with that?

    Can your menu class show what page is currently active? This was also a concern of mine. My idea was to call the menu class with the name of the page (every Page controller knows what page it is for, so this would be no problem in my case). Page names may not be unique though so I intended to use the relative link instead (like "services/termsandconditions.php").

    Can't say much about your layering problem, I'm afraid... So, only more questions...

  8. #8
    eschew sesquipedalians silver trophy sweatje's Avatar
    Join Date
    Jun 2003
    Location
    Iowa, USA
    Posts
    3,749
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    On topic, but not much help:

    The last time I dealt extensivly with a db based heirarchical structure, I compleetly skipped all of the php code and used the Oracle CONNECT BY statement, which, though proprietary, makes extracting the data set much easier.

    As for rendering, at the time I was using Smarty, and make recursive calls to a template.

    Not much help for you on either the extraction or the redering front I'm afraid.
    Jason Sweat ZCE - jsweat_php@yahoo.com
    Book: PHP Patterns
    Good Stuff: SimpleTest PHPUnit FireFox ADOdb YUI
    Detestable (adjective): software that isn't testable.

  9. #9
    Non-Member
    Join Date
    Jan 2004
    Location
    Planet Earth
    Posts
    1,764
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Mkrz, thanks for sharing your thoughts

    1) I have a script I found prior to starting this which has some class methods to allow you to insert dynamically. Also it is possible to move parts of your hierarchy, and to update them.

    Although in saying this, some of the script uses the recursive methods, whereas my (current) script does not, and so I will need to take time to look over the script and see if I can factor in some functionality to allow dynamic INSERTs, UPDATEs, and DELETEs, as well as being able to (eventually) move and sort hierarchy nodes.

    2) I intend to not only develop a hierarchy menu with this scripts, though to allow for dynamic database driven drop down menus as well using CSS and Javascript ?

    Shouldn't be too difficult as I see it, since the bulk of the work for these menus are client side anyways.

    As for breadcrumb navigation, I will be looking at this as well, which isn't too difficult either, well a lot easier than a category based menu anyways as I'm lead to believe

    I've read the Site Point article, printed it off last week in fact, and I'm not in favour of recursion, it's my pet hate in programming

    SweatJs, thanks for your comments as well, have not used the ORACLE database, but it sounds interesting. I note from your MVC ind. strength article you put a lot of logic in the database, which makes more sense of course

    Okay, going to be looking to see which pattern is going to be benifit to me in regards to the database later, and hope to post back today

    Mkrz, I can post the script I found again, in this post or email it to you if you want ? let me know

  10. #10
    SitePoint Addict
    Join Date
    Mar 2003
    Location
    Germany
    Posts
    216
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Quote Originally Posted by Widow Maker
    Mkrz, thanks for sharing your thoughts

    Although in saying this, some of the script uses the recursive methods, whereas my (current) script does not, and so I will need to take time to look over the script and see if I can factor in some functionality to allow dynamic INSERTs, UPDATEs, and DELETEs, as well as being able to (eventually) move and sort hierarchy nodes.
    Personally I wouldn't mind to keep the two things separate in this case, if necessary. I also wouldn't mind if updating/inserting wouldn't be fast, since it only happens rarely, and only at the backend/admin section.
    The class that retrieves the menu should be really fast though (one of the few cases where I care, because you have to retrieve it on every page). The DB query could be heavily chached though, I guess?

    As for breadcrumb navigation, I will be looking at this as well, which isn't too difficult either, well a lot easier than a category based menu anyways as I'm lead to believe
    I also think this is the easier part. Just start somewhere in the hierarchy and go upwards.

    Mkrz, I can post the script I found again, in this post or email it to you if you want ? let me know
    Yes, please post it here, so that others can also have a look if they want. I remember the arcticle also mentioned functions for inserting elements, but as far as I remember, it was somewhat rudimentary. Will have to read it again. I think ultimately you should have some kind of wizard for this? Normally I use rapid dev tools like PhpMyEdit for the backend, but in this case it doesn't help much because you can't handle the tree logic with it properly and you would have to insert the "parent" or "left"/"right" values manually which is a bit painful in this case.

    And as for Oracle, I guess that very few of us are graced with access to it...

  11. #11
    eschew sesquipedalians silver trophy sweatje's Avatar
    Join Date
    Jun 2003
    Location
    Iowa, USA
    Posts
    3,749
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Off Topic:

    Quote Originally Posted by mkrz
    And as for Oracle, I guess that very few of us are graced with access to it...
    Blessed...Cursed...it is such a fine line

    You can download and install for a development machine for free...but admin is a nightmare, nothing like MySQL.

    Quote Originally Posted by Oracle License
    License Rights
    We grant you a nonexclusive, nontransferable limited license to use the programs only for the purpose of developing a single prototype of your application, and not for any other purpose. If you use the application you develop under this license for any internal data processing or for any commercial or production purposes, or you want to use the programs for any purpose other than as permitted under this agreement, you must contact us, or an Oracle reseller, to obtain the appropriate license. We may audit your use of the programs. Program documentation may accessed online at /docs.

  12. #12
    Non-Member
    Join Date
    Jan 2004
    Location
    Planet Earth
    Posts
    1,764
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    I have something like Oracle 8.1 though never unzipped it (yet)

    Wouldn't a setup file create the Root node within the hierarchy tree ? As for the script, I've pasted it below for all and sundry

    PHP Code:
    <?
    //****************************************************************************
    // phpDBTree 1.2
    //****************************************************************************
    //      Author: Maxim Poltarak  <maxx at e dash taller dot net>
    //         WWW: [url]http://dev.e-taller.net/dbtree/[/url]
    //    Category: Databases
    // Description: PHP class implementing a Nested Sets approach to storing
    //              tree-like structures in database tables. This technique was
    //              introduced by Joe Celko <http://www.celko.com/> and has some 
    //              advantages over a widely used method called Adjacency Matrix.
    //****************************************************************************
    // The lib is FREEWARE. That means you may use it anywhere you want, you may 
    // do anything with it. The Author mentioned above is NOT responsible for any 
    // consequences of using this library. 
    // If you don't agree with this, you are NOT ALLOWED to use the lib!
    //****************************************************************************
    // You're welcome to send me all improvings, feature requests, bug reports...
    //****************************************************************************
    // SAMPLE DB TABLE STRUCTURE:
    //
    // CREATE TABLE categories (
    //   cat_id        INT UNSIGNED NOT NULL AUTO_INCREMENT,
    //   cat_left    INT UNSIGNED NOT NULL,
    //   cat_right    INT UNSIGNED NOT NULL,
    //   cat_level    INT UNSIGNED NOT NULL,
    //   PRIMARY KEY(cat_id),
    //   KEY(cat_left, cat_right, cat_level)
    // );
    //
    // This is believed to be the optimal Nested Sets use case. Use `one-to-one`
    // relations on `cat_id` field between this `structure` table and 
    // another `data` table in your database.
    //
    //****************************************************************************
    // NOTE: Although you may use this library to retrieve data from the table,
    //         it is recommended to write your own queries for doing that.
    //         The main purpose of the library is to provide a simpler way to 
    //         create, update and delete records. Not to SELECT them.
    //****************************************************************************
    //
    // IMPORTANT! DO NOT create either UNIQUE or PRIMARY keys on the set of
    //            fields (`cat_left`, `cat_right` and `cat_level`)!
    //            Unique keys will destroy the Nested Sets structure!
    //
    //****************************************************************************
    // CHANGELOG:
    // 16-Apr-2003 -=- 1.1
    //            - Added moveAll() method
    //            - Added fourth parameter to the constructor
    //            - Renamed getElementInfo() to getNodeInfo() /keeping BC/
    //            - Added "Sample Table Structure" comment
    //            - Now it die()'s in case of any serious error, because if not you
    //              will lose the Nested Sets structure in your table
    // 19-Feb-2004 -=- 1.2
    //            - Fixed a bug in moveAll() method?
    //              Thanks to Maxim Matyukhin for the patch.
    //****************************************************************************
    // Note: For best viewing of the code Tab size 4 is recommended
    //****************************************************************************

    class CDBTree {
        var 
    $db;    // CDatabase class to plug to
        
    var $table;    // Table with Nested Sets implemented
        
    var $id;    // Name of the ID-auto_increment-field in the table.

        // These 3 variables are names of fields which are needed to implement 
        // Nested Sets. All 3 fields should exist in your table! 
        // However, you may want to change their names here to avoid name collisions.
        
    var $left 'cat_left';
        var 
    $right 'cat_right';
        var 
    $level 'cat_level';

        var 
    $qryParams '';
        var 
    $qryFields '';
        var 
    $qryTables '';
        var 
    $qryWhere '';
        var 
    $qryGroupBy '';
        var 
    $qryHaving '';
        var 
    $qryOrderBy '';
        var 
    $qryLimit '';
        var 
    $sqlNeedReset true;
        var 
    $sql;    // Last SQL query

    //************************************************************************
    // Constructor
    // $DB : CDatabase class instance to link to
    // $tableName : table in database where to implement nested sets
    // $itemId : name of the field which will uniquely identify every record
    // $fieldNames : optional configuration array to set field names. Example:
    //                 array(
    //                    'left' => 'cat_left', 
    //                    'right' => 'cat_right', 
    //                    'level' => 'cat_level'
    //                 )
        
    function CDBTree(&$DB$tableName$itemId$fieldNames=array()) {
            if((empty(
    $tableName)) || (empty($itemId))) die("phpDbTree error: ".$this->db->error());
            
    $this->db $DB;
            
    $this->table $tableName;
            
    $this->id $itemId;
            if(
    is_array($fieldNames) && sizeof($fieldNames)) 
                foreach(
    $fieldNames as $k => $v)
                    
    $this->$k $v;
        }

    //************************************************************************
    // Returns a Left and Right IDs and Level of an element or false on error
    // $ID : an ID of the element
        
    function getElementInfo($ID) { return $this->getNodeInfo($ID); }
        function 
    getNodeInfo($ID) {
            
    $this->sql 'SELECT '.$this->left.','.$this->right.','.$this->level.' FROM '.$this->table.' WHERE '.$this->id.'=\''.$ID.'\'';
            if((
    $query=$this->db->query($this->sql)) && ($this->db->num_rows($query) == 1) && ($Data $this->db->fetch_array($query)))
                return array((int)
    $Data[$this->left], (int)$Data[$this->right], (int)$Data[$this->level]); 
            else die(
    "phpDbTree error: ".$this->db->error());
        }

    //************************************************************************
    // Clears table and creates 'root' node
    // $data : optional argument with data for the root node
        
    function clear($data=array()) {
            
    // clearing table
            
    if((!$this->db->query('TRUNCATE '.$this->table)) && (!$this->db->query('DELETE FROM '.$this->table))) die("phpDbTree error: ".$this->db->error());

            
    // preparing data to be inserted
            
    if(sizeof($data)) {
                
    $fld_names implode(','array_keys($data)).',';
                if(
    sizeof($data)) $fld_values '\''.implode('\',\''array_values($data)).'\',';
            }
            
    $fld_names .= $this->left.','.$this->right.','.$this->level;
            
    $fld_values .= '1,2,0';

            
    // inserting new record
            
    $this->sql 'INSERT INTO '.$this->table.'('.$fld_names.') VALUES('.$fld_values.')';
            if(!(
    $this->db->query($this->sql))) die("phpDbTree error: ".$this->db->error());

            return 
    $this->db->insert_id();
        }

    //************************************************************************
    // Updates a record
    // $ID : element ID
    // $data : array with data to update: array(<field_name> => <fields_value>)
        
    function update($ID$data) {
            
    $sql_set '';
            foreach(
    $data as $k=>$v$sql_set .= ','.$k.'=\''.addslashes($v).'\'';
            return 
    $this->db->query('UPDATE '.$this->table.' SET '.substr($sql_set,1).' WHERE '.$this->id.'=\''.$ID.'\'');
        }

    //************************************************************************
    // Inserts a record into the table with nested sets
    // $ID : an ID of the parent element
    // $data : array with data to be inserted: array(<field_name> => <field_value>)
    // Returns : true on success, or false on error
        
    function insert($ID$data) {
            if(!(list(
    $leftId$rightId$level) = $this->getNodeInfo($ID))) die("phpDbTree error: ".$this->db->error());

            
    // preparing data to be inserted
            
    if(sizeof($data)) {
                
    $fld_names implode(','array_keys($data)).',';
                
    $fld_values '\''.implode('\',\''array_values($data)).'\',';
            }
            
    $fld_names .= $this->left.','.$this->right.','.$this->level;
            
    $fld_values .= ($rightId).','.($rightId+1).','.($level+1);

            
    // creating a place for the record being inserted
            
    if($ID) {
                
    $this->sql 'UPDATE IGNORE '.$this->table.' SET '
                    
    $this->left.'=IF('.$this->left.'>'.$rightId.','.$this->left.'+2,'.$this->left.'),'
                    
    $this->right.'=IF('.$this->right.'>='.$rightId.','.$this->right.'+2,'.$this->right.')'
                    
    'WHERE '.$this->right.'>='.$rightId;
                if(!(
    $this->db->query($this->sql))) die("phpDbTree error: ".$this->db->error());
            }

            
    // inserting new record
            
    $this->sql 'INSERT INTO '.$this->table.'('.$fld_names.') VALUES('.$fld_values.')';
            if(!(
    $this->db->query($this->sql))) die("phpDbTree error: ".$this->db->error());

            return 
    $this->db->insert_id();
        }

    //************************************************************************
    // Assigns a node with all its children to another parent
    // $ID : node ID
    // $newParentID : ID of new parent node
    // Returns : false on error
    //************************************************************************ 
    // Assigns a node with all its children to another parent 
    // $ID : node ID 
    // $newParentID : ID of new parent node 
    // Returns : false on error 
       
    function moveAll($ID$newParentId) { 
          if(!(list(
    $leftId$rightId$level) = $this->getNodeInfo($ID))) die("phpDbTree error: ".$this->db->error()); 
          if(!(list(
    $leftIdP$rightIdP$levelP) = $this->getNodeInfo($newParentId))) die("phpDbTree error: ".$this->db->error()); 
          if(
    $ID == $newParentId || $leftId == $leftIdP || ($leftIdP >= $leftId && $leftIdP <= $rightId)) return false

          
    // whether it is being moved upwards along the path
          
    if ($leftIdP $leftId && $rightIdP $rightId && $levelP $level ) { 
             
    $this->sql 'UPDATE '.$this->table.' SET ' 
                
    $this->level.'=IF('.$this->left.' BETWEEN '.$leftId.' AND '.$rightId.', '.$this->level.sprintf('%+d', -($level-1)+$levelP).', '.$this->level.'), ' 
                
    $this->right.'=IF('.$this->right.' BETWEEN '.($rightId+1).' AND '.($rightIdP-1).', '.$this->right.'-'.($rightId-$leftId+1).', ' 
                               
    .'IF('.$this->left.' BETWEEN '.($leftId).' AND '.($rightId).', '.$this->right.'+'.((($rightIdP-$rightId-$level+$levelP)/2)*$level $levelP 1).', '.$this->right.')),  ' 
                
    $this->left.'=IF('.$this->left.' BETWEEN '.($rightId+1).' AND '.($rightIdP-1).', '.$this->left.'-'.($rightId-$leftId+1).', ' 
                               
    .'IF('.$this->left.' BETWEEN '.$leftId.' AND '.($rightId).', '.$this->left.'+'.((($rightIdP-$rightId-$level+$levelP)/2)*$level $levelP 1).', '.$this->left')) ' 
                
    'WHERE '.$this->left.' BETWEEN '.($leftIdP+1).' AND '.($rightIdP-1
             ; 
          } elseif(
    $leftIdP $leftId) { 
             
    $this->sql 'UPDATE '.$this->table.' SET ' 
                
    $this->level.'=IF('.$this->left.' BETWEEN '.$leftId.' AND '.$rightId.', '.$this->level.sprintf('%+d', -($level-1)+$levelP).', '.$this->level.'), ' 
                
    $this->left.'=IF('.$this->left.' BETWEEN '.$rightIdP.' AND '.($leftId-1).', '.$this->left.'+'.($rightId-$leftId+1).', ' 
                   
    'IF('.$this->left.' BETWEEN '.$leftId.' AND '.$rightId.', '.$this->left.'-'.($leftId-$rightIdP).', '.$this->left.') ' 
                
    '), ' 
                
    $this->right.'=IF('.$this->right.' BETWEEN '.$rightIdP.' AND '.$leftId.', '.$this->right.'+'.($rightId-$leftId+1).', ' 
                   
    'IF('.$this->right.' BETWEEN '.$leftId.' AND '.$rightId.', '.$this->right.'-'.($leftId-$rightIdP).', '.$this->right.') ' 
                
    ') ' 
                
    'WHERE '.$this->left.' BETWEEN '.$leftIdP.' AND '.$rightId 
                
    // !!! added this line (Maxim Matyukhin) 
                
    .' OR '.$this->right.' BETWEEN '.$leftIdP.' AND '.$rightId 
             

          } else { 
             
    $this->sql 'UPDATE '.$this->table.' SET ' 
                
    $this->level.'=IF('.$this->left.' BETWEEN '.$leftId.' AND '.$rightId.', '.$this->level.sprintf('%+d', -($level-1)+$levelP).', '.$this->level.'), ' 
                
    $this->left.'=IF('.$this->left.' BETWEEN '.$rightId.' AND '.$rightIdP.', '.$this->left.'-'.($rightId-$leftId+1).', ' 
                   
    'IF('.$this->left.' BETWEEN '.$leftId.' AND '.$rightId.', '.$this->left.'+'.($rightIdP-1-$rightId).', '.$this->left.')' 
                
    '), ' 
                
    $this->right.'=IF('.$this->right.' BETWEEN '.($rightId+1).' AND '.($rightIdP-1).', '.$this->right.'-'.($rightId-$leftId+1).', ' 
                   
    'IF('.$this->right.' BETWEEN '.$leftId.' AND '.$rightId.', '.$this->right.'+'.($rightIdP-1-$rightId).', '.$this->right.') ' 
                
    ') ' 
                
    'WHERE '.$this->left.' BETWEEN '.$leftId.' AND '.$rightIdP 
                
    // !!! added this line (Maxim Matyukhin) 
                
    ' OR '.$this->right.' BETWEEN '.$leftId.' AND '.$rightIdP 
             

          } 
          return 
    $this->db->query($this->sql) or die("phpDbTree error: ".$this->db->error()); 
       } 

    //************************************************************************
    // Deletes a record wihtout deleting its children
    // $ID : an ID of the element to be deleted
    // Returns : true on success, or false on error
        
    function delete($ID) {
            if(!(list(
    $leftId$rightId$level) = $this->getNodeInfo($ID))) die("phpDbTree error: ".$this->db->error());

            
    // Deleting record
            
    $this->sql 'DELETE FROM '.$this->table.' WHERE '.$this->id.'=\''.$ID.'\'';
            if(!
    $this->db->query($this->sql)) die("phpDbTree error: ".$this->db->error());

            
    // Clearing blank spaces in a tree
            
    $this->sql 'UPDATE '.$this->table.' SET '
                
    $this->left.'=IF('.$this->left.' BETWEEN '.$leftId.' AND '.$rightId.','.$this->left.'-1,'.$this->left.'),'
                
    $this->right.'=IF('.$this->right.' BETWEEN '.$leftId.' AND '.$rightId.','.$this->right.'-1,'.$this->right.'),'
                
    $this->level.'=IF('.$this->left.' BETWEEN '.$leftId.' AND '.$rightId.','.$this->level.'-1,'.$this->level.'),'
                
    $this->left.'=IF('.$this->left.'>'.$rightId.','.$this->left.'-2,'.$this->left.'),'
                
    $this->right.'=IF('.$this->right.'>'.$rightId.','.$this->right.'-2,'.$this->right.') '
                
    'WHERE '.$this->right.'>'.$leftId
            
    ;
            if(!
    $this->db->query($this->sql)) die("phpDbTree error: ".$this->db->error());

            return 
    true;
        }

    //************************************************************************
    // Deletes a record with all its children
    // $ID : an ID of the element to be deleted
    // Returns : true on success, or false on error
        
    function deleteAll($ID) {
            if(!(list(
    $leftId$rightId$level) = $this->getNodeInfo($ID))) die("phpDbTree error: ".$this->db->error());

            
    // Deleteing record(s)
            
    $this->sql 'DELETE FROM '.$this->table.' WHERE '.$this->left.' BETWEEN '.$leftId.' AND '.$rightId;
            if(!
    $this->db->query($this->sql)) die("phpDbTree error: ".$this->db->error());

            
    // Clearing blank spaces in a tree
            
    $deltaId = ($rightId $leftId)+1;
            
    $this->sql 'UPDATE '.$this->table.' SET '
                
    $this->left.'=IF('.$this->left.'>'.$leftId.','.$this->left.'-'.$deltaId.','.$this->left.'),'
                
    $this->right.'=IF('.$this->right.'>'.$leftId.','.$this->right.'-'.$deltaId.','.$this->right.') '
                
    'WHERE '.$this->right.'>'.$rightId
            
    ;
            if(!
    $this->db->query($this->sql)) die("phpDbTree error: ".$this->db->error());

            return 
    true;
        }

    //************************************************************************
    // Enumerates children of an element 
    // $ID : an ID of an element which children to be enumerated
    // $start_level : relative level from which start to enumerate children
    // $end_level : the last relative level at which enumerate children
    //   1. If $end_level isn't given, only children of 
    //      $start_level levels are enumerated
    //   2. Level values should always be greater than zero.
    //      Level 1 means direct children of the element
    // Returns : a result id for using with other DB functions
        
    function enumChildrenAll($ID) { return $this->enumChildren($ID10); }
        function 
    enumChildren($ID$start_level=1$end_level=1) {
            if(
    $start_level 0) die("phpDbTree error: ".$this->db->error());

            
    // We could use sprintf() here, but it'd be too slow
            
    $whereSql1 ' AND '.$this->table.'.'.$this->level;
            
    $whereSql2 '_'.$this->table.'.'.$this->level.'+';

            if(!
    $end_level$whereSql $whereSql1.'>='.$whereSql2.(int)$start_level;
            else {
                
    $whereSql = ($end_level <= $start_level
                    ? 
    $whereSql1.'='.$whereSql2.(int)$start_level
                    
    ' AND '.$this->table.'.'.$this->level.' BETWEEN _'.$this->table.'.'.$this->level.'+'.(int)$start_level
                        
    .' AND _'.$this->table.'.'.$this->level.'+'.(int)$end_level;
            }

            
    $this->sql $this->sqlComposeSelect(array(
                
    ''// Params
                
    ''// Fields
                
    $this->table.' _'.$this->table.', '.$this->table// Tables
                
    '_'.$this->table.'.'.$this->id.'=\''.$ID.'\''
                    
    .' AND '.$this->table.'.'.$this->left.' BETWEEN _'.$this->table.'.'.$this->left.' AND _'.$this->table.'.'.$this->right
                    
    .$whereSql
            
    ));

            return 
    $this->db->query($this->sql);
        }

    //************************************************************************
    // Enumerates the PATH from an element to its top level parent
    // $ID : an ID of an element
    // $showRoot : whether to show root node in a path
    // Returns : a result id for using with other DB functions
        
    function enumPath($ID$showRoot=false) {
            
    $this->sql $this->sqlComposeSelect(array(
                
    ''// Params
                
    ''// Fields
                
    $this->table.' _'.$this->table.', '.$this->table// Tables
                
    '_'.$this->table.'.'.$this->id.'=\''.$ID.'\''
                    
    .' AND _'.$this->table.'.'.$this->left.' BETWEEN '.$this->table.'.'.$this->left.' AND '.$this->table.'.'.$this->right
                    
    .(($showRoot) ? '' ' AND '.$this->table.'.'.$this->level.'>0'), // Where
                
    ''// GroupBy
                
    ''// Having
                
    $this->table.'.'.$this->left // OrderBy
            
    ));

            return 
    $this->db->query($this->sql);
        }

    //************************************************************************
    // Returns query result to fetch data of the element's parent
    // $ID : an ID of an element which parent to be retrieved
    // $level : Relative level of parent
    // Returns : a result id for using with other DB functions
        
    function getParent($ID$level=1) {
            if(
    $level 1) die("phpDbTree error: ".$this->db->error());

            
    $this->sql $this->sqlComposeSelect(array(
                
    ''// Params
                
    ''// Fields
                
    $this->table.' _'.$this->table.', '.$this->table// Tables
                
    '_'.$this->table.'.'.$this->id.'=\''.$ID.'\''
                    
    .' AND _'.$this->table.'.'.$this->left.' BETWEEN '.$this->table.'.'.$this->left.' AND '.$this->table.'.'.$this->right
                    
    .' AND '.$this->table.'.'.$this->level.'=_'.$this->table.'.'.$this->level.'-'.(int)$level // Where
            
    ));

            return 
    $this->db->query($this->sql);
        }

    //************************************************************************
        
    function sqlReset() {
            
    $this->qryParams ''$this->qryFields ''$this->qryTables ''
            
    $this->qryWhere ''$this->qryGroupBy ''$this->qryHaving ''
            
    $this->qryOrderBy ''$this->qryLimit '';
            return 
    true;
        }

    //************************************************************************
        
    function sqlSetReset($resetMode) { $this->sqlNeedReset = ($resetMode) ? true false; }

    //************************************************************************
        
    function sqlParams($param='') { return (empty($param)) ? $this->qryParams $this->qryParams $param; }
        function 
    sqlFields($param='') { return (empty($param)) ? $this->qryFields $this->qryFields $param; }
        function 
    sqlSelect($param='') { return $this->sqlFields($param); }
        function 
    sqlTables($param='') { return (empty($param)) ? $this->qryTables $this->qryTables $param; }
        function 
    sqlFrom($param='') { return $this->sqlTables($param); }
        function 
    sqlWhere($param='') { return (empty($param)) ? $this->qryWhere $this->qryWhere $param; }
        function 
    sqlGroupBy($param='') { return (empty($param)) ? $this->qryGroupBy $this->qryGroupBy $param; }
        function 
    sqlHaving($param='') { return (empty($param)) ? $this->qryHaving $this->qryHaving $param; }
        function 
    sqlOrderBy($param='') { return (empty($param)) ? $this->qryOrderBy $this->qryOrderBy $param; }
        function 
    sqlLimit($param='') { return (empty($param)) ? $this->qryLimit $this->qryLimit $param; }

    //************************************************************************
        
    function sqlComposeSelect($arSql) {
            
    $joinTypes = array('join'=>1'cross'=>1'inner'=>1'straight'=>1'left'=>1'natural'=>1'right'=>1);

            
    $this->sql 'SELECT '.$arSql[0].' ';
            if(!empty(
    $this->qryParams)) $this->sql .= $this->sqlParams.' ';

            if(empty(
    $arSql[1]) && empty($this->qryFields)) $this->sql .= $this->table.'.'.$this->id;
            else {
                if(!empty(
    $arSql[1])) $this->sql .= $arSql[1];
                if(!empty(
    $this->qryFields)) $this->sql .= ((empty($arSql[1])) ? '' ',') . $this->qryFields;
            }
            
    $this->sql .= ' FROM ';
            
    $isJoin = ($tblAr=explode(' ',trim($this->qryTables))) && ($joinTypes[strtolower($tblAr[0])]);
            if(empty(
    $arSql[2]) && empty($this->qryTables)) $this->sql .= $this->table;
            else {
                if(!empty(
    $arSql[2])) $this->sql .= $arSql[2];
                if(!empty(
    $this->qryTables)) {
                    if(!empty(
    $arSql[2])) $this->sql .= (($isJoin)?' ':',');
                    elseif(
    $isJoin$this->sql .= $this->table.' ';
                    
    $this->sql .= $this->qryTables;
                }
            }
            if((!empty(
    $arSql[3])) || (!empty($this->qryWhere))) {
                
    $this->sql .= ' WHERE ' $arSql[3] . ' ';
                if(!empty(
    $this->qryWhere)) $this->sql .= (empty($arSql[3])) ? $this->qryWhere 'AND('.$this->qryWhere.')';
            }
            if((!empty(
    $arSql[4])) || (!empty($this->qryGroupBy))) {
                
    $this->sql .= ' GROUP BY ' $arSql[4] . ' ';
                if(!empty(
    $this->qryGroupBy)) $this->sql .= (empty($arSql[4])) ? $this->qryGroupBy ','.$this->qryGroupBy;
            }
            if((!empty(
    $arSql[5])) || (!empty($this->qryHaving))) {
                
    $this->sql .= ' HAVING ' $arSql[5] . ' ';
                if(!empty(
    $this->qryHaving)) $this->sql .= (empty($arSql[5])) ? $this->qryHaving 'AND('.$this->qryHaving.')';
            }
            if((!empty(
    $arSql[6])) || (!empty($this->qryOrderBy))) {
                
    $this->sql .= ' ORDER BY ' $arSql[6] . ' ';
                if(!empty(
    $this->qryOrderBy)) $this->sql .= (empty($arSql[6])) ? $this->qryOrderBy ','.$this->qryOrderBy;
            }
            if(!empty(
    $arSql[7])) $this->sql .= ' LIMIT '.$arSql[7];
            elseif(!empty(
    $this->qryLimit)) $this->sql .= ' LIMIT '.$this->qryLimit;

            if(
    $this->sqlNeedReset$this->sqlReset();

            return 
    $this->sql;
        }
    //************************************************************************
    }
    ?>
    Enjoy

  13. #13
    SitePoint Addict
    Join Date
    Mar 2003
    Location
    Germany
    Posts
    216
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Thanks! Quite a lot of stuff... Will need some more time to digest it. I guess it might save me an awful lot of time. Having read said article again, I think I will now switch to the tree traversal method, too. But in this case I will really have to write an admin page that lists all elements, and for each element there should be at least two options: 1) insert a new element beneath this element, and 2) delete this element. If this is automated, then I can do the rest (setting the properties of the items, like link href, link text etc) like usual w/ PhpMyEdit or the like.
    Not concerning the code you just posted, but the article, I still it will be faster if you always make just 1 query where you get ALL elements of the tree, store this in an array and then do all further manipulations in memory on this array? For instance, I always need the bread crumb trail AND the menu, and I don't see why I should 2 db queries for this.
    Btw, one other requirement in my setup is to be able to only expand the category that the currently active pages lives in.

    By the way, what about the root element? Should there now be a "dummy" root element? Because in my current site, there is no single "root". E.g.

    - home
    - contact
    - translations
    ......- services
    .......- F.A.Q.
    .......- pricing
    - legal
    .......- t & c
    .......- privacy

    etc.

    Also, there is still the problem of how to handle the home page in the breadcrumb trail. E.g. for "translations" I need a trail like

    Home -> Translations

    So I could always print out the "Home" element, but for the home page itself I obviously don't want

    Home -> Home

    I might insert some IF logic, but that's a bit cumbersome?

  14. #14
    Non-Member
    Join Date
    Jan 2004
    Location
    Planet Earth
    Posts
    1,764
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    You shouldn't need to check for duplicate leafs if you have a Root, ie Home ?

    I suppose to create the breadcrumb from this,

    Code:
    Home > About > Employment
    Then all you'd need is the LEFT and RIGHT integers which belong to 'Employment', found of course via a database query ?

    That is one query, then you'd need another one to find all the hierarchy nodes that fall BETWEEN the LEFT and the RIGHT of 'Employment'.

    That is two queries you need to make, and I cannot for the life of me, figure out how'd you do it with just the one query in it's self ?

    Maybe a sub SELECT could help, though my SQL knowledge doesn't at this time, stretch to that

    Once you've done your second query, you'd build an array via this part of the script I posted,

    PHP Code:
    ...
    for( 
    $a 0;$a sizeof$tree );$a++ ) { 
                    if( 
    sizeof$temp ) > (int) ) { 
                        while( 
    $temp[sizeof$temp ) -1] < (int) $tree[$a]['fld_rgt'] ) { 
                            
    array_pop$temp ); 
                        } 
                    } 
                    
    $temp[] = $tree[$a]['fld_rgt']; 
    ... 
    To construct your breadcrumb trail ?

  15. #15
    SitePoint Addict
    Join Date
    Mar 2003
    Location
    Germany
    Posts
    216
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Quote Originally Posted by Widow Maker
    You shouldn't need to check for duplicate leafs if you have a Root, ie Home ?
    For the breadcrumb, yes, that would be easy. But if I make "Home" the root node, this would instead clash with my wanting "home" to ba a category in the menu just like the others? That's my problem. Both scenarios (breadcrumb and menu) seem to be mutually exclusive with respect to this.

    That is two queries you need to make, and I cannot for the life of me, figure out how'd you do it with just the one query in it's self ?
    Well, you could get ALL elements and then do the traversal with loops over the array. This will not be sophisticated at all, but I think it will be fast, since it all happens in memory?! I guess 1 db query will take an order of magnitude longer than 20 stupid/brute force loops over an array? This should really be measured though, but I couldn't get XDebug working yet. Does anyone have practical experience with this?

    E.g. you get all elements from the DB. They will already be nicely ordered. You store this in an array with all necessary attributes (level, lft, rgt). If you need the path to a node, when you would normally now do a query like:

    SELECT title FROM tree WHERE lft < 4 AND rgt > 5 ORDER BY lft ASC

    (from the sitepoint article) you could just as well loop over the array and in every iteration do:

    PHP Code:
    // (OTTOMH)
    if ($array[i]['lft'] < 4) && ($array[i]['rgt'] > 5) {  
       
    $trail[] = $array[i]

    Haven't tested this, but it should be possible?

  16. #16
    SitePoint Evangelist
    Join Date
    May 2004
    Location
    New Jersey, USA
    Posts
    567
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    You'd have to split the returned data with some code, but it's basically:
    Code:
       SELECT * FROM table
       WHERE
     	table.left < $left AND table.right > $right
       OR
     	table.left > $left AND table.right < $right
    Above, you're locating "entirely containing" nodes, which are parents, and "entirely contained" nodes, which are children. And then in PHP you split them apart:
    PHP Code:
       foreach ($results as $r)
       {
          if (
    $r['left'] < $left)
          {
             ... 
    this is a parent ...
          } 
          else
          {
             ... 
    this is a child ...
          }
       } 
    =Austin

  17. #17
    SitePoint Zealot
    Join Date
    Aug 2003
    Location
    Sydney
    Posts
    187
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Heya Widow,

    I did write a basic class for this a while ago with the help of another coder, I didnt really put it into extensive use, so I dont know if it worked really well, but it did seem to do the job I was after.

    I just set it up so I had to pass the table name and the table id and of course whatever was about to be inserted. Because all the tables using this structure were built the same it was easy enough to do it this way.

  18. #18
    SitePoint Guru
    Join Date
    Dec 2003
    Location
    oz
    Posts
    819
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    I haven't read the whole thread, so appologies if I'm no help =P

    Just on a note to speed things up when reading tree data from a database. Have you thought of a singleton TreeMapper with a hashtable and then using just one query to get the whole tree when the singleton is initially retrieved? Load it up first time something like this, and set the map to a static member of the singleton.

    PHP Code:
        function getNodeMap()
        {
            
    $map = array();
            
    $result db.query("SELECT * from TreeTable");
            while (
    $row $result->next())
            {
                 if (!isset(
    $map[$row[parent]]))
                     
    $map[$row['parent']] = array();
     
                 if (
    row['side'] == 'left')
                     
    $map[$row[parent]]['left'] = createNode(row);
                 elseif (
    row['side'] == 'right')
                     
    $map[$row[parent]]['right'] = createNode(row);
            {
     
            return 
    $map;
        } 
    Then you could just traverse it easily as any traversal. And access would be insanely fast since you are accessing a hashtable - ie O(1). Plus since you do only one query in total, it would be pretty fast as far as the db is concerned.

    Again - appologies if this is no help. Just thougth of it and thought it may be of help to you.

  19. #19
    SitePoint Addict
    Join Date
    Apr 2004
    Location
    Melbourne
    Posts
    362
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    On the topic of preoder trees, what's the speed hit if you have a really big tree and want to delete / add something in to an earlier part of the tree? From how I understand it, all later records in the db have to be updated... doesn't this incur a big performance hit?

  20. #20
    Non-Member
    Join Date
    Jan 2004
    Location
    Planet Earth
    Posts
    1,764
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Yes, whilsts SELECTs are said to be a lot faster, UPDATEs are slower ?

    But as Mkrz has suggested, UPDATEs are mostly in regards to the administration side of a site, and I kind of agree with that, in regards to what I want to use the script for

    If you feel that a lot of UPDATEs for non administration tasks are going to be a performance hit, then maybe using recursion could compensate for this ?

  21. #21
    SitePoint Enthusiast maetl's Avatar
    Join Date
    Jan 2003
    Location
    Aotearoa
    Posts
    34
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    interesting discussion... don't know how directly relevant it is, but I was reading this the other day, and it looked quite interesting, basically the concept of storing the path to the node with the node itself:

    http://c2.com/cgi/wiki?TreeInSql

    this would be a real pain if there is a need for lots of reordering of the tree (updates), but it would be good for really large trees...

  22. #22
    Non-Member
    Join Date
    Jan 2004
    Location
    Planet Earth
    Posts
    1,764
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Thanks

    Will be trying to look over it this weekend if I can.

    PHP Code:
    ...
    function 
    getNodeMap()
        {
            
    $map = array();
            
    $result db.query("SELECT * from TreeTable");
            while (
    $row $result->next())
            {
                 if (!isset(
    $map[$row[parent]]))
                     
    $map[$row['parent']] = array();

                 if (
    row['side'] == 'left')
                     
    $map[$row[parent]]['left'] = createNode(row);
                 elseif (
    row['side'] == 'right')
                     
    $map[$row[parent]]['right'] = createNode(row);
            {

            return 
    $map;
        } 
    ... 
    This I can understand, though trying to (now) work out the best method within the function to map the nodes in their parent <> child relationship

    Just curious though, how would a class per node structure work out, has anyone tried that before ?

  23. #23
    Resident Java Hater
    Join Date
    Jul 2004
    Location
    Gerodieville Central, UK
    Posts
    446
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    You may wanna look at

    http://fungus.teststation.com/~jon/t...eeHandling.htm

    for trees, it's much better than Celko's system for larger trees.

    Celko's Set fall over when you have large trees. I did an experiement on my home PC (which is a AMD 2800, DDR400 1Gb RAM, 500Gb RAID 0 HDD, two 22" monitors, etc etc, so it's fairly zippy) with a tree setup like a balanced 20 level deep binary tree (1 million nodes), and in a worst case scenario it took 20 seconds to update, which is very slow considering that was after a few goes, so the DB table was toally cached in RAM. I would hate to think what it would be like on a machine slower than mine.

    In order to use Celko sets well one needs to have a gap policy. Ideally that gap policy would be setup so that the root node uses the full numeric domain (i.e the Left , right values would be 0, (2^64) -1 for a table that used UNSIGNED BIGINT as the oval datatypes. Each child node would have a left / right value that was proportal to the right-left value of the parent. Every now and then gap optimisation would need to take place if one ran out of left/right values (would only happen in very skewed trees).

    Just my two cents on DB's and trees. For a HTML menu, I guess it wouldn't have many nodes anyway.

    If you want some fun, look at Vadim Tropashko's techniques for tree handling. Be warned, there's no point implementing them on MySQL (unless you have version 5), you wanna use a DB with Stored Procs ideally

  24. #24
    Non-Member
    Join Date
    Jan 2004
    Location
    Planet Earth
    Posts
    1,764
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Thanks

    Tried the link just now, though the page isn't loading properly as I need to install an IE update

    Though the update ain't happening just now, Microsoft's servers must be busy huh

    I can see your point about the depth of a tree, though I cannot imagine in the life span of the script I develop, ever having a tree deeper than 6 levels, nor any number of nodes near the number you tested for.

    But I never know, do I ? So it'll be interesting to see what your link has to offer

  25. #25
    Resident Java Hater
    Join Date
    Jul 2004
    Location
    Gerodieville Central, UK
    Posts
    446
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Quote Originally Posted by Widow Maker
    Thanks

    Tried the link just now, though the page isn't loading properly as I need to install an IE update

    Though the update ain't happening just now, Microsoft's servers must be busy huh

    I can see your point about the depth of a tree, though I cannot imagine in the life span of the script I develop, ever having a tree deeper than 6 levels, nor any number of nodes near the number you tested for.

    But I never know, do I ? So it'll be interesting to see what your link has to offer

    Well, yeah the link is useful, though you might as well stick to Celko for now. I would use that tree system that link offers for more complex projects. I'm thinking about using it for for a tree / OO based controller myself (I started playing with some PHP5 code for this), which might get worked into the PHP 5 version of LIMB, if ever I get time to get rid of all this crap freelance work I have backlogged from a few months back.

    If only I could work 3 or 4 days a week, it would give me enough time to work on this :P


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
  •