Hector Virgen has released a brilliant Zend_Db_Table extension enabling simple use of the Modified Pre-order Tree Traversal pattern.

If you've never come across MPTT and are curious as to what it is and why, there is an excellent article on sitepoint explaining the whys & what fors.

MPTT is used on this site for the site map, menus at the top and the breadcrumb navigation, due to the simplicity of retrieving parents and children, it is ideal for this purpose.

Hectors class simplifies the use of the pattern quite considerably, it is capable of building the traversal across the whole table just by a parent reference and provides simple methods to fetch a tree, to fetch all the ancestors of a row as well as all of the decendants of a row.

Hectors original post is on his blog go there to grab the source

Usage Examples

To use the modified preorder tree traversal algorithm in your table, you will initially have to do just a little bit of work but once it is set up everything should be automated for you.

Firstly, you will need to alter the table in your database and add columns to store the "left" and "right" values. (Remember that 'left' and 'right' are reserved words in SQL - so use something else or your queries will fail!)

Next, you will need to create your table class by extending Virgen_Db_Table, and declare the traversal properties. 

<?php 
class MyTree extends Virgen_Db_Table
{
    protected $_name = 'tree_example';
    protected $_traversal = array(
        'left'          => 'THE NAME OF YOUR LEFT COL HERE',
        'right'         => 'THE NAME OF YOUR RIGHT COL HERE',
        'column'        => 'THE NAME OF YOUR PRIMARY KEY COL HERE',
        'refColumn'     => 'THE NAME OF YOUR PARENT ID COL HERE'
    );
}

Now when you insert a new record into your table, all of the left and right columns will be updated as necessary to reflect the new preorder tree.

If you have existing data in your table or want to rebuild the entire tree, Hector has provided a rebuildTreeTraversal() method. 

<?php
$mytree = new MyTree();
$mytree->rebuildTreeTraversal();

Fetching Descendents of a Given Node

Once your tree is built, you can fetch all descendents of a node with fetchAllDescendents(). The first argument is the node to fetch the descendents of. The node can be either an instance of Zend_Db_Table_Row_Abstract or the string/numeric value of the columns id (based on $_traversal['column']). You can optionally pass in a select object to use as the second argument, which will be used when selecting the descendents (this is where to do any joins or where clauses). 

 
<?php
// Fetch all of the children for row with the ID of 1 
$node = $mytree->find(1)->current();
$descendents = $mytree->fetchAllDescendents($node);
// Identical to:
$descendents = $mytree->fetchAllDescendents(1);

 
// With optional select object
$select = $mytree->select()->where('published = ?', 1)->limit(5);
$descendends = $mytree->fetchAllDescendents($node, $select);

Fetching Ancestors of a Given Node

You can also fetch the ancestors just as easily with fetchAllAncestors(). All ancestors from the immediate parent up to the root of the tree will be returned. 

 
<?php
 
$ancestors = $mytree->fetchAllAncestors($node);

Fetching Nodes as a Tree

You can fetch nodes as a tree by calling $table->fetchTree(). Its functionality is similar to fetchDescendents, except that it returns a modified rowset in that each row contains a tree_depth value. 

 
<?php
 
$tree = $mytree->fetchTree();
 
foreach ($tree as $node) {
    echo str_repeat(' ', $node->tree_depth * 4) . $node->id . PHP_EOL;
}

Restructuring the resultset for template iteration

This site uses PHPTAL as its template engine, as there is no simple way (it is possible, but is vastly over-complicated) to programatically iterate through the resultset in its returned form, so a simple loop to place all the children of parent rows into an associative array was needed!

For this to work you need to alter your tree fetch statement to the following 

 
<?php
 
$tree = $mytree->fetchTree()->toArray();

and then loop through your tree like this 

 
<?php

$menu = array(); 
$ref = array();

      foreach( $tree as $d ) {
        $d['Children'] = array();
        if( isset( $ref[ $d['Parent_ID'] ] )) {
            $ref[ $d['Parent_ID'] ]['Children'][ $d['Row_ID'] ] = $d;
            $ref[ $d['Row_ID'] ] =& $ref[ $d['Parent_ID'] ]['Children'][ $d['Row_ID'] ];
        } else {
                $menu[ $d['Row_ID'] ] = $d;
            $ref[ $d['Row_ID'] ] =& $menu[ $d['Row_ID'] ];
        }
     }

You are then left with a structured multidimensional array ($menu).

To produce a set of nested uniform lists recursively in TAL to display your tree, you'll need something like this 

<ul metal:define-macro="output_list" tal:condition="menu">
    <li tal:repeat="list_item menu">
       ${list_item/Row_Name}
        <tal:block tal:define="tree list_item/Children" metal:use-macro="output_list" />
    </li>
</ul>
<tal:block metal:use-macro="output_list" />

A big thanks to Hector for his work on this

tqsfmu69b5