SitePoint Sponsor

User Tag List

Page 1 of 2 12 LastLast
Results 1 to 25 of 43
  1. #1
    Non-Member
    Join Date
    Jan 2003
    Posts
    5,748
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    Talking Adjacency List Script via Patterns (PHP5 Only)

    Umm...

    Been keeping this in the dark for a while, but thought I'd post it to these forums for all to use. The script will generate a Composite structure for you based on a database query, leaving yourself to generate the HTML.

    I'll leave that as an exercise, though to give you some help, a Visitor is involved

    First, the SQL dump

    Code:
    -- 
    -- Table structure for table `catologue`
    -- 
    
    CREATE TABLE `catologue` (
      `id` int(6) unsigned NOT NULL auto_increment,
      `name` varchar(32) NOT NULL default '',
      `parent` int(6) NOT NULL default '0',
      PRIMARY KEY  (`id`)
    ) ENGINE=InnoDB DEFAULT CHARSET=latin1 AUTO_INCREMENT=15 ;
    
    -- 
    -- Dumping data for table `catologue`
    -- 
    
    INSERT INTO `catologue` (`id`, `name`, `parent`) VALUES (1, 'Catologue', 0);
    INSERT INTO `catologue` (`id`, `name`, `parent`) VALUES (2, 'Entertainment', 12);
    INSERT INTO `catologue` (`id`, `name`, `parent`) VALUES (3, 'Video', 2);
    INSERT INTO `catologue` (`id`, `name`, `parent`) VALUES (4, 'DVD', 2);
    INSERT INTO `catologue` (`id`, `name`, `parent`) VALUES (5, 'Gaming', 2);
    INSERT INTO `catologue` (`id`, `name`, `parent`) VALUES (6, 'Furnishings', 12);
    INSERT INTO `catologue` (`id`, `name`, `parent`) VALUES (7, 'Bathroom', 6);
    INSERT INTO `catologue` (`id`, `name`, `parent`) VALUES (8, 'Kitchen', 6);
    INSERT INTO `catologue` (`id`, `name`, `parent`) VALUES (9, 'Lounge', 6);
    INSERT INTO `catologue` (`id`, `name`, `parent`) VALUES (10, 'Bedroom', 6);
    INSERT INTO `catologue` (`id`, `name`, `parent`) VALUES (11, 'Garden', 6);
    INSERT INTO `catologue` (`id`, `name`, `parent`) VALUES (12, 'Home', 1);
    INSERT INTO `catologue` (`id`, `name`, `parent`) VALUES (13, 'Action & Adventure', 4);
    INSERT INTO `catologue` (`id`, `name`, `parent`) VALUES (14, 'Family', 4);
    And the ouput, via this

    PHP Code:
    $list Gateway::loadFinder::findByParentId1/* edited */ ) );
        
        
    $adapter = new DbAdapter$list[0] );
        
    $walker = new DbWalker$list );
        
    $walker -> walk$adapter );
        
        echo( 
    '<pre>' ); print_r$adapter -> getItems() ); echo( '</pre>' );
        
        exit; 
    Now, the script you need,

    PHP Code:
    // use your own database connection classes
    //
    class ApplicationFaultException extends Exception {}
        class 
    IllegalParameterException extends Exception {}
        
        class 
    Gateway {
            public function 
    __construct() {}
            
            static public function 
    load$resultset false ) {
                
    $items = array();
                if( 
    $resultset ) {
                    while( 
    $resultset -> fetch() ) {
                        
    $row $resultset -> getall();
                        
    $items[] = $row;
                    }
                }
                return 
    $items;
            }
        }
        
        class 
    Finder {
            public function 
    __construct() {}
            
            static public function 
    findByParentId$id ) {
                try {
                    
    $db DbFactory::getConnection();
                    
    $stmt $db -> createStatement'select * from catologue where parent = ?' );
                    
    $stmt -> setInteger1, (int) $id );
                    
    $rslt $stmt -> execute();
                } catch( 
    SqlException $e ) {
                    die( 
    $e -> getMessage() );
                }
                if( 
    $rslt -> isSuccess() ) {
                    return 
    $rslt;
                }
                return 
    false;
            }
        }
        
        class 
    DbWalker {
            private 
    $items;
            
            public function 
    __construct$items ) {
                
    $this -> items $items;
            }
            
            public function 
    walk$adapter ) {
                foreach( 
    $this -> items as $item ) {
                    
    $adapter -> push$item );
                    
    $walker = new DbWalkerGateway::loadFinder::findByParentId$item['id'] ) ) );
                    
    $walker -> walk$adapter );
                }
            }
        }
        
        class 
    DbAdapter {
            private 
    $items;
            
            public function 
    __construct$item ) {
                
    $this -> items = new Composite$item );
            }
            
            public function 
    getItems() {
                return 
    $this -> items;
            }
            
            public function 
    push$item ) {
                
    $c = new Composite$item );
                if( 
    $tmp $this -> traverse$this -> getItems(), $item ) ) {
                    
    $tmp -> attach$c );
                }
            }    
            
            public function 
    traverse$composite$item ) {
                if( 
    $composite -> getId() == (int) $item['parent'] ) {
                    return 
    $composite;
                } else {
                    if( 
    $composite -> hasChildren() ) {
                        
    $children $composite -> getChildren();
                        foreach( 
    $children as $child ) {
                            
    $c = new Composite$item );
                            if( 
    $tmp $this -> traverse$child$item ) ) {
                                
    $tmp -> attach$c );
                            }
                        }
                    }
                }
            }
        }
        
        abstract class 
    Component {
            public 
    $id;
            public 
    $name;
            public 
    $parent;
            public 
    $children = array();
            
            public function 
    __construct$item ) {
                
    $this -> id $item['id'];
                
    $this -> name $item['name'];
                
    $this -> parent $item['parent'];
            }
            
            public function 
    getId() {
                return 
    $this -> id;
            }
            
            public function 
    getName() {
                return 
    $this -> name;
            }
            
            public function 
    getParent() {
                return 
    $this -> parent;
            }
            
            public function 
    hasChildren() {
                return 
    count$this -> children );
            }
            
            public function 
    getChildren() {
                return 
    $this -> children;
            }
            
            public function 
    attach$composite ) {
                
    $this -> children[] = $composite;
            }
        }
        
        class 
    Composite extends Component {
            public function 
    __construct$item ) {
                
    parent::__construct$item );
            }
        } 
    Any questions, comments, etc are most welcome. I know there are issues with the Adjacency List approach, but for a lot of purposes and for convienence, the approach does work.
    Last edited by Dr Livingston; Feb 1, 2006 at 15:27.

  2. #2
    SitePoint Wizard
    Join Date
    May 2003
    Location
    Berlin, Germany
    Posts
    1,829
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    PHP Code:
        $adapter = new DbAdapter$list[0] );
        
    $walker = new DbWalker$list );
        
    $walker -> walk$adapter ); 
    This makes no sense to me. What are $list and $list[0] ? Why would the Adapter need $list[0] ?

  3. #3
    Non-Member
    Join Date
    Jan 2003
    Posts
    5,748
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    The class *Adapter, what it does is to generate the Composite structure, it's self based on what a *Walker recurses over yes?

    So, this part generates the ROOT Composite alone,

    PHP Code:
    $adapter = new DbAdapter$list[0] ); 
    As in,

    PHP Code:
    class DbAdapter {
            private 
    $items;
            
            public function 
    __construct$item ) {
                
    $this -> items = new Composite$item );
            } 
    ... 
    You then need something to recurse over the data structure, this is where the *Walker class comes in... Do you remember the previous classes I had posted to recurse and generate a Composite structure from an XML file?

    This does the exact same thing, even the Interface is the same The *Walker pushes the data (a given node) to the *Adapter class, which then constructs the Composite, and it's structure you see, this is why we have this part,

    PHP Code:
    ...
    $walker -> walk$adapter ); 
    Does this answer your questions?

  4. #4
    Non-Member
    Join Date
    Jan 2003
    Posts
    5,748
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    The $list[0] is the ROOT taken from the database, whereas the $list is all the nodes pulled from the database initially, which is always the ROOT anyways.

    For example, $list[0] is

    Code:
    array {
    [id] => 1,
    [name] => NameGoesHere
    [parent] => 0 }
    Whereas, $list is this

    Code:
    array {
    [0] => array {
    [id] => 1,
    [name] => NameGoesHere,
    [parent] => 0 } }
    There is a slight difference, and I pass $list[0] to the *Adapter, as I don't see how the constructor should have to alter the array prior to creating the (ROOT) Composite

    EDIT:

    This makes no sense to me.
    I think what you can't understand, is that both are referred to in the scripts yes? In the sense that they are of the same node level, in which case this is for shear convienence, but don't worry about it.

    As the *Adapter takes care of not making duplicates of the same node you see... You could query the database again** for the node(s) to be sent to the *Walker class I suppose but why have a second query to setup the process I ask, as there is no need to

    ** Ie

    PHP Code:
    $listForWalkerClass Gateway::loadFinder::findByParentId$list[0]['parent'] ) );
    ...
    $walker = new DbWalker$listForWalkerClass ); // should actually be AdjacencyListWalker
    ... 
    Anyways, have you taken it for a test run?
    Last edited by Dr Livingston; May 8, 2005 at 11:30.

  5. #5
    SitePoint Wizard REMIYA's Avatar
    Join Date
    May 2005
    Posts
    1,351
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    An excelent approach Dr Livingston. It was exactly what I needed several months ago, when trying to implement a PHP driven flat file database.

    I wish I had seen it then, instead of reinventing the wheel

  6. #6
    Mlle. Ledoyen silver trophy seanf's Avatar
    Join Date
    Jan 2001
    Location
    UK
    Posts
    7,168
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Quote Originally Posted by Dr Livingston
    First, the SQL dump
    Off Topic:

    Off-topic, but putting a number in parenthesis after int is only used for ZEROFILL. If you want to change the size of integer you will store in the column and the amount of space that will be used by that column you need to use a different integer column type, i.e. TINYINT, SMALLINT, MEDIUMINT or BIGINT

    Sean
    Harry Potter

    -- You lived inside my world so softly
    -- Protected only by the kindness of your nature

  7. #7
    Non-Member
    Join Date
    Jan 2003
    Posts
    5,748
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    I wish I had seen it then, instead of reinventing the wheel
    I agree with you, implementing a lean, and re-usable approach to using the Adjacency List method until now could be messy. Not anymore, thus the reason I've now (finally) posted this solution, so no longer will you or others need to reinvent the wheel

    Also, note you can use one Walker with another Adapter, such as an XmlWalker with the DbAdapter independently without the need to alter the script(s) in question

    Sean,

    The SQL was mocked just to give members something to test with, and nothing more but thanks for the tip.

  8. #8
    SitePoint Wizard Ren's Avatar
    Join Date
    Aug 2003
    Location
    UK
    Posts
    1,060
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    I think I would have gone the RecursiveIterator route.

    PHP Code:
    class DbWalkerIterator extends OuterIterator implements RecursiveIterator
    {
        private 
    $children;

        function 
    hasChildren()
        {
            
    $current parent::current();
            
    $this->children Gateway::load(Finder::findByParentId($current['id']));
            return 
    $this->children instanceof ArrayObject && $this->children->count() > 0;
        }

        function 
    getChildren() { return new DbWalkerIterator($this->children); }

    (OuterIterator is just a proxy of Iterator)

    PHP Code:
    class DbWalker extends RecursiveIteratorIterator
    {
        function 
    __construct($thing)
        {
            
    parent::__construct(new DbWalkerIterator($thing), RIT_SELF_FIRST);
        }

    DbWalker just becomes a RecursiveIteratorIterator..

    PHP Code:
    class DbAdaptor extends OuterIterator
    {
        function 
    current()
        {
            return new 
    Composite(parent::current());
        }

    And Adaptor is another iterator, overriding current() todo the adapting.

    And linked up something like...

    PHP Code:
    $list Gateway::load(Finder::findByParentId(1));

        
    $walker = new DbWalker($list);
        
    $adaptor = new DbAdaptor($walker);

        foreach(
    $adaptor as $child)
             echo 
    str_repeat(' '$walker->getDepth() * 4), $child->getName(), "\n"

  9. #9
    Non-Member
    Join Date
    Jan 2003
    Posts
    5,748
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Not bad Ren

    Never used PHP5s standard library as I have my reasons (see Using Composites thread) but if this example of yours works, then it could be an alternative to what I use.

    What I think could make the destinction is that if someone can follow the standard library and it's iterators, they'll find your approach easier to work with, than my approach?

    Now, who is going to attempt to do the Nested Set version of this huh? Someone...

  10. #10
    SitePoint Wizard Ren's Avatar
    Join Date
    Aug 2003
    Location
    UK
    Posts
    1,060
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Attached the full source, (uses PDO_SQLITE to bootstrap it)

    What I think could make the destinction is that if someone can follow the standard library and it's iterators, they'll find your approach easier to work with, than my approach?
    Possibly. I just prefer using iterators rather than building arrays.
    Now, who is going to attempt to do the Nested Set version of this huh? Someone...
    I have a stab later.
    The latest homebrew project uses nested sets to store tables of contents extracted from XML (DocBook, DBLite, TexinfoML etc).

    Screenshot
    Attached Files Attached Files

  11. #11
    SitePoint Guru
    Join Date
    Dec 2003
    Location
    oz
    Posts
    819
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Quote Originally Posted by REMIYA
    I wish I had seen it then, instead of reinventing the wheel
    Re-inventing the wheel is the PHP way.

  12. #12
    SitePoint Wizard REMIYA's Avatar
    Join Date
    May 2005
    Posts
    1,351
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Sorry, but reinventing the wheel is not any language way. Expecially the Open Sourced PHP.

    That is why people are targeting to OOP. Because they want reusable objects. To do their work fast and error prone.

  13. #13
    Non-Member
    Join Date
    Jan 2003
    Posts
    5,748
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Okay, the original renderer that I had scripted didn't render the unordered lists as compliant W3C standards, so if you attempt to style or manipulate the generated output via CSS and Javascript, you'll have some problems.

    I later fixed this with another iteration, and have now today, modified the renderer (posted) to comply with web standards, so you can now use CSS and Javascript

    I had forgot about this so my appologies folks, here is the update, leave yourselfs to tidy it up.

    PHP Code:
    class Renderer {
            public function 
    __construct() {}
            
            public function 
    finalise$composite ) { 
                
    $html $this -> render$composite );
                
                echo( 
    '<ul>'.$html.'</ul>' );
            }
            
            public function 
    render$composite ) {
                
    $fragment '';$x '';
                foreach( 
    $composite -> getChildren() as $child ) { $x '<ul>';
                    
    $tmp $this -> render$child );
                    
    $fragment .= $tmp;
                } 
                
    $y "\n<li>".$composite -> getName().$x.$fragment."\n"; if( $x != '' ) { $y .= '</ul></li>'; } else { $y .= '</li>'; }
                
                return 
    $y;
            }
        } 
    I've spent the last 20 minutes or so testing this with various data so I don't see any problems, but if there are, let me know,

    Thanks.

  14. #14
    SitePoint Enthusiast
    Join Date
    Sep 2004
    Location
    Malmö, Sweden
    Posts
    53
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    Rewritten for PHP 4

    Maybe some more of you guys still use PHP4 so I rewrote Livingstones' great example in order for it to work on PHP4 (verified on PHP4.4.0).

    PHP Code:
    <?php
    error_reporting
    (E_ALL);
    /**
    CREATE TABLE `catologue` (
      `id` int(6) unsigned NOT NULL auto_increment,
      `name` varchar(32) NOT NULL default '',
      `parent` int(6) NOT NULL default '0',
      PRIMARY KEY  (`id`)
    ) ENGINE=InnoDB DEFAULT CHARSET=latin1 AUTO_INCREMENT=15 ;

    -- 
    -- Dumping data for table `catologue`
    -- 

    INSERT INTO `catologue` (`id`, `name`, `parent`) VALUES (1, 'Catologue', 0);
    INSERT INTO `catologue` (`id`, `name`, `parent`) VALUES (2, 'Entertainment', 12);
    INSERT INTO `catologue` (`id`, `name`, `parent`) VALUES (3, 'Video', 2);
    INSERT INTO `catologue` (`id`, `name`, `parent`) VALUES (4, 'DVD', 2);
    INSERT INTO `catologue` (`id`, `name`, `parent`) VALUES (5, 'Gaming', 2);
    INSERT INTO `catologue` (`id`, `name`, `parent`) VALUES (6, 'Furnishings', 12);
    INSERT INTO `catologue` (`id`, `name`, `parent`) VALUES (7, 'Bathroom', 6);
    INSERT INTO `catologue` (`id`, `name`, `parent`) VALUES (8, 'Kitchen', 6);
    INSERT INTO `catologue` (`id`, `name`, `parent`) VALUES (9, 'Lounge', 6);
    INSERT INTO `catologue` (`id`, `name`, `parent`) VALUES (10, 'Bedroom', 6);
    INSERT INTO `catologue` (`id`, `name`, `parent`) VALUES (11, 'Garden', 6);
    INSERT INTO `catologue` (`id`, `name`, `parent`) VALUES (12, 'Home', 1);
    INSERT INTO `catologue` (`id`, `name`, `parent`) VALUES (13, 'Action & Adventure', 4);
    INSERT INTO `catologue` (`id`, `name`, `parent`) VALUES (14, 'Family', 4);
    */
    class Component {
        var 
    $id;
        var 
    $name;
        var 
    $parent;
        var 
    $children = array();
        
        function 
    Component$item ) {
            
    $this -> id $item['id'];
            
    $this -> name $item['name'];
            
    $this -> parent $item['parent'];
        }
        
        function 
    getId() {
            return 
    $this -> id;
        }
        
        function 
    getName() {
            return 
    $this -> name;
        }
        
        function 
    getParent() {
            return 
    $this -> parent;
        }
        
        function 
    hasChildren() {
            return 
    count$this->children );
        }
        
        function &
    getChildren() {
            return 
    $this->children;
        }
        
        function 
    attach(  $composite ) {
            
    $this->children[] = $composite;
        }
    }
        


    class 
    Composite extends Component {
        function 
    Composite$item ) {
            
    parent::Component$item );
        }


    class 
    Renderer {
        
        function 
    finalise$composite 
        {
            
    $html $this -> render$composite );
            
            echo( 
    '<ul>'.$html.'</ul>' );
        }
        
        function 
    render$composite ) {
            
    $fragment '';$x '';
            
            foreach( 
    $composite -> getChildren() as $child )
            { 
                
    $x '<ul>';
                
    $tmp $this -> render$child );
                
    $fragment .= $tmp;
            }
            
            
    $y "\n<li>".$composite -> getName().$x.$fragment."\n"
            
            if( 
    $x != '' 
            { 
                
    $y .= '</ul></li>'
            } 
            else 
            { 
                
    $y .= '</li>'
            }
            
            return 
    $y;
        }
    }
        
    class 
    DbAdapter {
            var 
    $items;
            
            function 
    DbAdapter$item ) {
                
    $this -> items = new Composite$item );
            }
            
            function &
    getItems() {
                return  
    $this -> items;
            }
            
            function 
    push$item ) {
                
    $c = new Composite$item );  
                
    $items = & $this -> getItems(); 
                if( 
    $tmp = & $this -> traverse$items $item ) ) {                
                    
    $tmp -> attach$c );
                }
            }    
            
            function &
    traverse( &$composite$item ) {

                if( 
    $composite -> getId() == (int) $item['parent'] ) {
                    return 
    $composite;
                } else {
                    if( 
    $composite -> hasChildren() ) {
                        
                        
    $children = & $composite -> getChildren();
                        
                        foreach( 
    $children as $key => $child ) {
                            
    $child = & $children[$key];
                            
                            
    $c = new Composite$item );
                            
                            if( 
    $tmp = & $this -> traverse$child$item ) ) {
                                
    $tmp -> attach$c );
                            }
                            unset(
    $child);
                        }
                    }
                }
                
    $var null;
                return 
    $var;
            }
        }  
        
    class 
    Gateway {
        
        function 
    load$resultset false ) {
            
    $items $resultset;
            return 
    $items;
        }
    }
        
    class 
    Finder {        
        function 
    findByParentId$id 
        {
                
    /**
                * Replace with your own DB-driver that executes sql and returns array
                *      array(3) {
                                id     => string(2) 12
                                name   => string(4) Home
                                parent => string(1) 1
                        }
                */
                
    $db Library::instance("DB");
                return 
    $db -> getArray'select * from catologue where parent = '.$id );
        }
    }
        
    class 
    DbWalker {
        var 
    $items;
        
        function 
    DbWalker$items ) {
            
    $this -> items $items
        }
        
        function 
    walk( &$adapter ) {
            
            foreach( 
    $this -> items as $item ) {            
                
    $adapter -> push$item );
                
    $walker = new DbWalkerGateway::loadFinder::findByParentId$item['id'] ) ) );
                
    $walker -> walk$adapter );
            }
        }
        
    }    
        
        
        
        
    $list Gateway::loadFinder::findByParentId) );

    $adapter = &new DbAdapter$list[0] );
    $walker = &new DbWalker$list );
    $walker -> walk$adapter );
        
    $items $adapter -> getItems();
    $renderer = new Renderer();
    $renderer -> finalise$items );  
    ?>
    Jan Bolmeson, M.Sc. Engineering Physics, ZCE
    Join my network @ LinkedIn.com

  15. #15
    SitePoint Guru
    Join Date
    May 2003
    Location
    virginia
    Posts
    988
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Nice!

  16. #16
    SitePoint Wizard dreamscape's Avatar
    Join Date
    Aug 2005
    Posts
    1,080
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Quote Originally Posted by Dr Livingston
    The SQL was mocked just to give members something to test with, and nothing more but thanks for the tip.
    No actually I believe it is an actual MySQL dump (from phpMyAdmin if I;m not mistaken), which means that is actually what you entered and it isn't mocked in any way

    Don't feel bad, I thought int(x) meant an integer with max length of x bytes or x length for a long time as well. You'd be surprised how many people don't know you cannot set a length on integer fields like that

  17. #17
    Non-Member
    Join Date
    Jan 2003
    Posts
    5,748
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Yes, it was a dump, but when I said mocked, I meant the data it's self was mocked, and not the database schema - the data was purely for testing

  18. #18
    SitePoint Enthusiast
    Join Date
    Sep 2004
    Location
    Malmö, Sweden
    Posts
    53
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    Use of Registry Pattern for

    In order to optmize the script provided in the thread one can also use a Static Registry Pattern as the finder class. I.e. instead of making a sql-query on each lookup we search in a predefined static array. (of course this has to be set in advance, but that is not really a problem since in most cases the total collection of objects is known)

    The following script doesn't work directly in the above script, it only needs a small modification (most names).
    PHP Code:
    /**
    * Finder Base class
    *
    * This is a class based to 100% on the RegistryStatic design pattern found
    * in chapter 5 in James Sweats book PHP Design Patterns.
    *
    * In this application we always know inbeforehand which obejcts might be used,
    * so in order to optimize the application and hence minimize the number of
    * queries to the database we use this unorthodox approach where instead of
    * searching an database we search a collection of objects. Since we will
    * be searching on the parent_id the store is created as a array where the
    * parent-ids are the keys.
    *
    * The other way to implement this class is to use sqls to fetch an row on
    * every find-request.
    *
    * @package Framework
    */
    class AdjacencyList_Finder
    {
        
    /**
        * Function to get the store
        * @access private
        * @return array of objects
        */
        
    function &_getFinder()
        {
            static 
    $_store = array();
            return 
    $_store;
        }

        
    /**
        * Function that checks if the parent_id does exist in the current selection
        * @param    integer     $parent_id      Id of the parental object
        * @access public
        * @return boolean
        */
        
    function isValidParent$parent_id )
        {
            
    $store = & AdjacencyList_Finder::_getFinder();
            return 
    array_key_exists$parent_id $store );
        }

        
    /**
        * The classical Registry::get Function
        * @param    integer     $parent_id      Id of the parental object
        * @access   public
        * @return   mixed
        */
        
    function &findByParentId$parent_id )
        {
            
    $store = & AdjacencyList_Finder::_getFinder();

            if ( 
    is_array$store ) && count$store ) > )
            {
                
    $result = array();
                foreach( 
    $store AS $key => $obj )
                {
                    if ( 
    $obj->getParent() == $parent_id )
                    {
                        
    $result[] = array('name'=> $obj->getName(),
                                          
    'id' => $obj->getId(),
                                          
    'parent_id' => $obj->getParent()
                                          );
                    }
                }
                return 
    $result;
            }
        }

        function &
    getById($id)
        {
            
    $store = & AdjacencyList_Finder::_getFinder();
            if ( 
    array_key_exists$id $store ) )
            {
                return array(
    'name'=> $store[$id]->getName(),
                             
    'id' => $store[$id]->getId(),
                             
    'parent_id' => $store[$id]->getParent()
                             );
            }
        }

        
    /**
        * Function that creates entries into the register
        * @param    integer     $id      Id of the object
        * @param    object      $obj     The object
        * @access   public
        * @return   boolean
        */
        
    function set($id$obj)
        {
            
    $store =& AdjacencyList_Finder::_getFinder();
            
    $store[$id] = $obj;
        }


    Example of setting the array:
    PHP Code:

            
    foreach( $collectionOfObjects AS $id => $obj )
            {
                
    $obj = & $c[$id];//PHP4 Fix since foreach makes a copy of objects
                
    AdjacencyList_Finder::set$obj->getId() , $obj );
            } 
    Send a me a message if you don't get it working... =o)

    //jan
    Jan Bolmeson, M.Sc. Engineering Physics, ZCE
    Join my network @ LinkedIn.com

  19. #19
    SitePoint Enthusiast
    Join Date
    Apr 2005
    Posts
    39
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Hi,

    I have been going through this article.

    I still think it's a little complicated (FOR ME), but have to admit that I am learning while I try to understand.

    I have some basic OO knowledge.

    I have tried to use the PHP4 rewritten version submitted by Madwax, but find my self in a never ending loop using my own db driver in class Finder, function findByParentId.

    PHP Code:
        $db = new DatabaseConnection;
        
    $rs $db->executeQuery'select * from catologue where parent = '.$id ); 

            return array(
    'id' => $db->getResult($rs,0,'id'), 'name' => $db->getResult($rs,0,'name'), 'parent' => $db->getResult($rs,0,'parent')); 
    Is there something wrong with my array? I looks different, but this is the only type of array I know.

    Can someone please advise me where I go wrong?

    Thanks a lot,

    Giorgio

  20. #20
    SitePoint Enthusiast
    Join Date
    Sep 2004
    Location
    Malmö, Sweden
    Posts
    53
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    can you please post your complete code and database dump and I'll take a quick look at it?
    Jan Bolmeson, M.Sc. Engineering Physics, ZCE
    Join my network @ LinkedIn.com

  21. #21
    Non-Member
    Join Date
    Jan 2003
    Posts
    5,748
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Umm...

    It's been this long since I developed that script that I've forgotten all about it now; I'm now using designs and scripts that have advanced past this script I had posted...

    Time for posting an update I think, might get around to it sometime I suppose. As to your problem, you would need to post more script; What scaffolding do you have for example?

  22. #22
    SitePoint Enthusiast
    Join Date
    Apr 2005
    Posts
    39
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    PHP Code:
    <?php 

    include "classes_database.php";

    error_reporting(E_ALL); 
    /** 
    CREATE TABLE `catologue` ( 
      `id` int(6) unsigned NOT NULL auto_increment, 
      `name` varchar(32) NOT NULL default '', 
      `parent` int(6) NOT NULL default '0', 
      PRIMARY KEY  (`id`) 
    ) ENGINE=InnoDB DEFAULT CHARSET=latin1 AUTO_INCREMENT=15 ; 

    -- 
    -- Dumping data for table `catologue` 
    -- 

    INSERT INTO `catologue` (`id`, `name`, `parent`) VALUES (1, 'Catologue', 0); 
    INSERT INTO `catologue` (`id`, `name`, `parent`) VALUES (2, 'Entertainment', 12); 
    INSERT INTO `catologue` (`id`, `name`, `parent`) VALUES (3, 'Video', 2); 
    INSERT INTO `catologue` (`id`, `name`, `parent`) VALUES (4, 'DVD', 2); 
    INSERT INTO `catologue` (`id`, `name`, `parent`) VALUES (5, 'Gaming', 2); 
    INSERT INTO `catologue` (`id`, `name`, `parent`) VALUES (6, 'Furnishings', 12); 
    INSERT INTO `catologue` (`id`, `name`, `parent`) VALUES (7, 'Bathroom', 6); 
    INSERT INTO `catologue` (`id`, `name`, `parent`) VALUES (8, 'Kitchen', 6); 
    INSERT INTO `catologue` (`id`, `name`, `parent`) VALUES (9, 'Lounge', 6); 
    INSERT INTO `catologue` (`id`, `name`, `parent`) VALUES (10, 'Bedroom', 6); 
    INSERT INTO `catologue` (`id`, `name`, `parent`) VALUES (11, 'Garden', 6); 
    INSERT INTO `catologue` (`id`, `name`, `parent`) VALUES (12, 'Home', 1); 
    INSERT INTO `catologue` (`id`, `name`, `parent`) VALUES (13, 'Action & Adventure', 4); 
    INSERT INTO `catologue` (`id`, `name`, `parent`) VALUES (14, 'Family', 4); 
    */ 
    class Component 
        var 
    $id
        var 
    $name
        var 
    $parent
        var 
    $children = array(); 
         
        function 
    Component$item ) { 
            
    $this -> id $item['id']; 
            
    $this -> name $item['name']; 
            
    $this -> parent $item['parent']; 
        } 
         
        function 
    getId() { 
            return 
    $this -> id
        } 
         
        function 
    getName() { 
            return 
    $this -> name
        } 
         
        function 
    getParent() { 
            return 
    $this -> parent
        } 
         
        function 
    hasChildren() { 
            return 
    count$this->children ); 
        } 
         
        function &
    getChildren() { 
            return 
    $this->children
        } 
         
        function 
    attach(  $composite ) { 
            
    $this->children[] = $composite
        } 

         


    class 
    Composite extends Component 
        function 
    Composite$item ) { 
            
    parent::Component$item ); 
        } 


    class 
    Renderer 
         
        function 
    finalise$composite 
        { 
            
    $html $this -> render$composite ); 
             
            echo( 
    '<ul>'.$html.'</ul>' ); 
        } 
         
        function 
    render$composite ) { 
            
    $fragment '';$x ''
             
            foreach( 
    $composite -> getChildren() as $child 
            { 
                
    $x '<ul>'
                
    $tmp $this -> render$child ); 
                
    $fragment .= $tmp
            } 
             
            
    $y "\n<li>".$composite -> getName().$x.$fragment."\n"
             
            if( 
    $x != '' 
            { 
                
    $y .= '</ul></li>'
            } 
            else 
            { 
                
    $y .= '</li>'
            } 
             
            return 
    $y
        } 

         
    class 
    DbAdapter 
            var 
    $items
             
            function 
    DbAdapter$item ) { 
                
    $this -> items = new Composite$item ); 
            } 
             
            function &
    getItems() { 
                return  
    $this -> items
            } 
             
            function 
    push$item ) { 
                
    $c = new Composite$item );   
                
    $items = & $this -> getItems(); 
                if( 
    $tmp = & $this -> traverse$items $item ) ) {                 
                    
    $tmp -> attach$c ); 
                } 
            }     
             
            function &
    traverse( &$composite$item ) { 

                if( 
    $composite -> getId() == (int) $item['parent'] ) { 
                    return 
    $composite
                } else { 
                    if( 
    $composite -> hasChildren() ) { 
                         
                        
    $children = & $composite -> getChildren(); 
                         
                        foreach( 
    $children as $key => $child ) { 
                            
    $child = & $children[$key]; 
                             
                            
    $c = new Composite$item ); 
                             
                            if( 
    $tmp = & $this -> traverse$child$item ) ) { 
                                
    $tmp -> attach$c ); 
                            } 
                            unset(
    $child); 
                        } 
                    } 
                } 
                
    $var null
                return 
    $var
            } 
        }   
         
    class 
    Gateway 
         
        function 
    load$resultset false ) { 
            
    $items $resultset
            return 
    $items
        } 

         
    class 
    Finder {         
        function 
    findByParentId$id 
        { 
                
    /** 
                * Replace with your own DB-driver that executes sql and returns array 
                *      array(3) { 
                                id     => string(2) 12 
                                name   => string(4) Home 
                                parent => string(1) 1 
                        } 
                */ 
        
    $db = new DatabaseConnection;
        
    $rs $db->executeQuery'select * from catologue where parent = '.$id ); 

            return array(
    'id' => $db->getResult($rs,0,'id'), 'name' => $db->getResult($rs,0,'name'), 'parent' => $db->getResult($rs,0,'parent'));
        } 

         
    class 
    DbWalker 
        var 
    $items
         
        function 
    DbWalker$items ) { 
            
    $this -> items $items
        } 
         
        function 
    walk( &$adapter ) { 
             
            foreach( 
    $this -> items as $item ) {             
                
    $adapter -> push$item ); 
                
    $walker = new DbWalkerGateway::loadFinder::findByParentId$item['id'] ) ) ); 
                
    $walker -> walk$adapter ); 
            } 
        } 
         
    }     
         
         
         
         
    $list Gateway::loadFinder::findByParentId) ); 

    $adapter = &new DbAdapter$list[0] ); 


    $walker = &new DbWalker$list ); 
    $walker -> walk$adapter ); 
         
    $items $adapter -> getItems(); 
    $renderer = new Renderer(); 
    $renderer -> finalise$items );   
    ?>

  23. #23
    SitePoint Enthusiast
    Join Date
    Apr 2005
    Posts
    39
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    Summary what I am trying to create

    OK, I came to this post last week after I tried to get some answers for an OO Menu.

    I want to create a menu that collapses/expands on a click, but also the page has to refresh. I want to be able to join contentpages and modules to each menu item.

    I want to call a page with a $_GET['menu_id'] and expand only that part of the tree.

    If the full tree would be this:

    1
    1.1
    1.1.1
    1.2
    2
    2.1
    2.2

    and I call the page with $menu_id = 1.1.1,
    I would like to see this:

    1.
    1.1
    1.1.1
    1.2
    2

    I also would like to keep my database as simple as possible, so table tree would have an id, parent_id, and item_description. This is just like your script.

    It should be easy, but I have been breaking my head over it for the past two weeks.

    Hope you guys can get me on the right track.

    Giorgio

    My previous post was: http://www.sitepoint.com/forums/showthread.php?t=339413

  24. #24
    Non-Member
    Join Date
    Jan 2003
    Posts
    5,748
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Hello,

    Not had the time to look at your script and specific problem at the moment, but here is some script I arrived at, after a refactor; There is now no need to recursively query the database, you just pull out the data from the data as is, and generate the Composite structure with a simple loop

    PHP Code:
    interface IConnection {} // empty
        
    interface IComposite {
            public function 
    getId();
            public function 
    hasChildren();
            public function 
    getChildren();
            public function 
    attachIComposite $composite );
        }
        
        include_once( 
    'path/to/database/classes' );
        
        
    $db DbFactory::getConnection$configs );
        
    // increase performance with a traverse of an array structure; not database structure
        
    $stmt $db -> createStatement'select * from categories order by id' );
        
    $rs $stmt -> execute();
        
        
    $items = array();
        if( 
    $rs -> isSuccess() ) {
            
    // for each record found
            
    while( $rs -> fetch() ) {
                
    // per row
                
    $items[$rs -> getField'id' )] = $rs -> getAll();
            }
        }
        
        class 
    Adapter {
            private 
    $composite;
            
            public function 
    __construct$item ) {
                
    $this -> composite = new Composite$item );
            }
            
            public function 
    getRoot() {
                return 
    $this -> composite;
            }
            
            public function 
    push$item ) {
                
    $c = new Composite$item );
                if( 
    $tmp $this -> traverse$this -> getRoot(), $item ) ) {
                    
    $tmp -> attach$c );
                }
            }
            
            public function 
    traverseIComposite $composite$item ) {
                if( 
    $composite -> getId() == $item['parent'] ) {
                    return 
    $composite;
                } else {
                    if( 
    $composite -> hasChildren() ) {
                        
    $children $composite -> getChildren();
                        foreach( 
    $children as $child ) {
                            
    $c = new Composite$item );
                            if( 
    $tmp $this -> traverse$child$item ) ) {
                                
    $tmp -> attach$c );
                            }
                        }
                    }
                }            
            }
        }
        
        class 
    Composite implements IComposite {
            private 
    $id;
            private 
    $name;
            private 
    $parent;
            private 
    $children = array();
            
            public function 
    __construct$item ) {
                
    $this -> id $item['id'];
                
    $this -> name $item['name'];
                
    $this -> parent $item['parent'];
            }
            
            public function 
    hasChildren() {
                return 
    count$this -> children );
            }
            
            public function 
    getChildren() {
                return 
    $this -> children;
            }
            
            public function 
    getId() {
                return 
    $this -> id;
            }
            
            public function 
    getName() {
                return 
    $this -> name;
            }
            
            public function 
    attachIComposite $composite ) {
                
    $this -> children[$composite -> getId()] = $composite;
            }
        }
        
        
    $adapter = new Adapter$items[1] );
        foreach( 
    $items as $item ) {
            
    $adapter -> push$item );
        }
        
        echo( 
    '<pre>' ); print_r$adapter -> getRoot() ); echo( '</pre>' ); 
    Here is the database table structure I used for this example,

    Code:
    -- phpMyAdmin SQL Dump
    -- version 2.7.0-pl1
    -- http://www.phpmyadmin.net
    -- 
    -- Host: localhost
    -- Generation Time: Jan 30, 2006 at 06:36 PM
    -- Server version: 5.0.17
    -- PHP Version: 5.1.1
    -- 
    -- Database: `tmpdb`
    -- 
    
    -- --------------------------------------------------------
    
    -- 
    -- Table structure for table `categories`
    -- 
    
    DROP TABLE IF EXISTS `categories`;
    CREATE TABLE IF NOT EXISTS `categories` (
      `id` int(3) NOT NULL auto_increment,
      `name` varchar(64) NOT NULL,
      `parent` int(3) NOT NULL,
      PRIMARY KEY  (`id`)
    ) ENGINE=InnoDB DEFAULT CHARSET=latin1 AUTO_INCREMENT=15 ;
    
    -- 
    -- Dumping data for table `categories`
    -- 
    
    INSERT INTO `categories` VALUES (1, 'Home', 0);
    INSERT INTO `categories` VALUES (2, 'Calendar', 1);
    INSERT INTO `categories` VALUES (3, 'Contacts', 1);
    INSERT INTO `categories` VALUES (4, 'Communications', 1);
    INSERT INTO `categories` VALUES (5, 'FAQs', 4);
    INSERT INTO `categories` VALUES (6, 'Feedback', 4);
    INSERT INTO `categories` VALUES (7, 'Announcements', 4);
    INSERT INTO `categories` VALUES (8, 'Private Messages', 4);
    INSERT INTO `categories` VALUES (9, 'New Message', 8);
    INSERT INTO `categories` VALUES (10, 'Administration', 1);
    INSERT INTO `categories` VALUES (11, 'Accounts', 10);
    INSERT INTO `categories` VALUES (12, 'New Account', 11);
    INSERT INTO `categories` VALUES (13, 'Search', 1);
    INSERT INTO `categories` VALUES (14, 'Help', 1);
    You can now use the previously posted renderer with this script with a few modifications to accept an object, instead of an array?

    This script is a lot more flexible an easier to use and understand, and gives an increased boost in performance, as you do not need to perform a query for every node there is... Who needs the Modfied Pre-order Traversal Tree approach huh?

  25. #25
    SitePoint Enthusiast
    Join Date
    Apr 2005
    Posts
    39
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    To make it work with my own database class I have changed the following:
    PHP Code:
        include_once( 'path/to/database/classes' ); 
         
        
    $db DbFactory::getConnection$configs ); 
        
    // increase performance with a traverse of an array structure; not database structure 
        
    $stmt $db -> createStatement'select * from categories order by id' ); 
        
    $rs $stmt -> execute(); 
         
        
    $items = array(); 
        if( 
    $rs -> isSuccess() ) { 
            
    // for each record found 
            
    while( $rs -> fetch() ) { 
                
    // per row 
                
    $items[$rs -> getField'id' )] = $rs -> getAll(); 
            } 
        } 
    To:
    PHP Code:
        include_once('classes_database.php'); 

        
    $db = new DatabaseConnection;
        
    $rs $db->executeQuery('select * from categories order by id') ;
         
        
    $items = array(); 
        if(
    $db->getNumRows($rs) ) { 
            
    // for each record found 
            
    while($row $db->getFetchedArray($rs)) { 
                
    // per row 
                
    $items[$db->getresult($rs0'id')] = $db->getResult($rs0'name');
            } 
        } 
    Now I get the following error:
    Fatal error: Maximum execution time of 30 seconds exceeded in d:\__CMS DEV Giorgio\tree.php on line 28

    Seems a never ending loop, but haven't done debugging yet. Is that DBFacatory a class you developed? Is the way I have changed the code OK?

    I think it goes wrong before the actual loop in class Adapter (getRoot).

    Does this script actually work with PHP4 and maybe you can gimme some explenation on "interface", since I never heard of it before.

    Lots of questions again..... But will hang your picture on the wall for answers

    Thx,

    Giorgio


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
  •