DerEuroMark

Some of you might alread have worked with the TreeBehavior to generate nested categories or something like that. In most cases we just want to have two or three levels...

Some of you might alread have worked with the TreeBehavior to generate nested categories or something like that. In most cases we just want to have two or three levels and some hierarchic structure using parent_id. But trees can do way more than that. At least if you also use lft and rght (which the behavior uses internally to order the tree) and MPTT (Modified Preorder Tree Traversal).

Unfortunately, a helper for tree-structered output is not a pat of the cake core. Luckily some skilled developer(s) created a very nicely working version for 1.x which I upgraded and enhanced for 2.x. It works flawlessly with any model that uses the TreeBehavior.

What for?

Navigation, Category Tree in Shop Systems, Threaded Boards with Posts or Comments, … The list where you can use models that behave like trees is endless. In my case we needed a complex category tree including “active path” feature and breadcrumbs. Also some additional magic to keep the tree in a visible “length” (to only show the revelant branches and only to a specific level).

Setup

The behavior can just be attached to the model itself using $actsAs – as always. For the helper we include it in our controller as $helpers = array('Tools.Tree');.

Your table should have “parent_id”, “lft”, “rght” fields. If you use UUIDs, make sure that “parent_id” is UUID (char36) just as your primary key. “lft”/”rght” must be integers, though. Otherwise your tree will always be invalid as those fields have nothing to do with the ids itself, but the order inside the tree.

From the documentation: “The parent field must be able to have a NULL value! It might seem to work, if you just give the top elements a parent value of zero, but reordering the tree (and possible other operations) will fail”.

Usage

TreeBehavior

I don’t want to go into the details regarding the core Tree behavior, as it is already very well explained in the documentation.

Just remember: Do not touch the lft/right fields. They should not be in your forms or be modified from you in any way. The behavior internally sets the right values here. You just need to tell it what parent_id you want to put it under.

If you already saved some records in your tree there are usually three ways of getting the data in a way that you can output it properly:

1. find(all) in combination with 'order' => array('lft' => 'ASC') and maybe scope/conditions
2. find(threaded) and 'conditions' => array('id' => $id, ...) and 'order' => array('lft' => 'ASC')
3. children($id) if you have multiple trees in your table, for example – or if you want to retrieve only a part of the tree

The last two methods will already nest your data using parent_id/children as key. The first one you can nest yourself if needed using Hash::nest() as shown below.

Note that you must set the order yourself for both find() calls. Only children() will automatically use the correct order.

Short reference of useful behavior methods:

• getPath: return current path to this id
• children: get all children to an id
• removeFromTree (with true/false to remove children or moving them up)
• moveUp
• moveDown
• verify: check that the tree is valid
• recover: if not valid, try to repair the tree (with mode return/delete)

You can put two up/down icons in your index table or threaded tree list pointing to two actions up/down which then invoke the behavior’s methods. This way you can easily sort your tree using those methods from the backend. You can also use some more sophisticated ajax dynamic tree reordering using jquery plugins etc. Then you would probably use reorder() as this method can reorder multiple items at once.

The current path is needed to build a breadcrumbs list. See the chapter for breadcrumbs below for details.

Another useful method (even though it shouldn’t be in the behavior but the view scope) is generateTreeList(). We can use it to populate our select boxes. A baked edit/add form for your categories should look like this:

...
echo $this->Form->input('parent_id');
...

Just pass down $parents in your action:

$spacer = '--';
$parents = $this->Category->generateTreeList($conditions, $keyPath, $valuePath, $spacer);
$this->set(compact('parents'));

TreeHelper

Way more interesting is how we can actually output the tree in a way that allows us to style it – especially the currently active path. Also how to fully customize each tree level.

The most simple use case – using the key/value (id and name usually) of the threaded array:

// in your view/element ctp 
echo $this->Tree->generate($categories, array('id' => 'my-tree'));

I will simply output a nested ul/li tree with the displayField (name) text.

We could also use helper callbacks (here a custom MyTreeOutputHelper::format() method) to adjust the nodes:

echo $this->Tree->generate($categories, array('id' => 'my-tree', 'callback' => ($this->MyTreeOutput, 'format')));

This method then can look like:

public function format($data) {
    if (empty($data['data']['Category']['visible'])) {
        return; // do not display
    }
    // append (active) for active path elements
    return $data['data']['Category']['name'] . ($data['activePathElement'] ? ' (active)' : '');
}

A more verbose example of the tree helper capabilities using elements:

$categories = Hash::nest($categories); // optional, if you used find(all) instead of find(threaded) or children()
 
$treeOptions = array('id' => 'main-navigation', 'model' => 'Category', 'element' => 'node', 'autoPath' => array($currentCategory['Category']['lft'], $currentCategory['Category']['rght']));
 
echo $this->Tree->generate($categories, $treeOptions);

And the /Elements/node.ctp, for example:

$category = $data['Category'];
if (!$category['active']) { // You can do anything here depending on the record content
    return;
}
echo $this->Html->link($category['name'], array('action' => 'find', 'category_id' => $category['id']));

Using autoPath we can make the tree leverage the lft/rght MPTT and automatically mark the current path as active. Styling it via css is then a piece of cake.

To enhance it further, you can use frontend js via jquery plugins (accordion or multi-level menu) or the quite powerful superfish script. If you want to divide your tree in a main top and a sub side navigation you can achieve that using the maxDepth option and only return and output specific levels of the tree per menu.

Tip: Take a look at the test cases for the helper for further details on the above options and its usage as well as the expected output for those.

Short reference for the more important settings:

• ‘model’ => name of the model (key) to look for in the data array. defaults to the first model for the current controller. If set to false 2d arrays will be allowed/expected.
• ‘alias’ => the array key to output for a simple ul (not used if element or callback is specified)
• ‘type’ => type of output defaults to ul
• ‘itemType => type of item output default to li
• ‘id’ => id for top level ‘type’
• ‘class’ => class for top level ‘type’
• ‘element’ => path to an element to render to get node contents.
• ‘callback’ => callback to use to get node contents. e.g. array(&$anObject, ‘methodName’) or ‘floatingMethod’
• ‘autoPath’ => array($left, $right [$classToAdd = 'active']) if set any item in the path will have the class $classToAdd added. MPTT only.
• ‘maxDepth’ => used to control the depth upto which to generate tree
• ‘splitCount’ => the number of “parallel” types. defaults to null (disabled) set the splitCount, and optionally set the splitDepth to get parallel lists

And internally (on top of the above settings) in callbacks and elements the following information passed in as array (callback) or variables (element) is available:

• ‘data’ => the data array itself
• ‘depth’
• ‘hasChildren’
• ‘numberOfDirectChildren’
• ‘numberOfTotalChildren’
• ‘firstChild’
• ‘lastChild’
• ‘hasVisibleChildren’
• ‘activePathElement’

Performance

Don’t forget to add some indexes on your tables to speed up the “reading” process. This is most likely the bottle neck of larger trees. Therefore you should add indexes for parent_id, lft and rght:

ALTER TABLE  `categories` ADD INDEX  `lft` (  `lft` );
ALTER TABLE  `categories` ADD INDEX  `rght` (  `rght` );
ALTER TABLE  `categories` ADD INDEX  `parent_id` (  `parent_id` );

Breadcrumbs

We can use the behavior’s method for this as mentioned above:

// controller
$treePath = $this->Model->getPath($currentCategoryId);
$this->set(compact('treePath'));

Now we just have to display the list and style it:

$total = count($treePath);
echo '<ul id="category-breadcrumbs" class="breadcrumbs">';
echo '<li>';
echo $this->Html->link('ALL', array('action'=>'find', 'category_id' => ''));
echo '</li>';
foreach ($treePath as $key => $treeCategory) {
    if (!$treeCategory['Category']['active']) {
        continue;
    }
    echo '<li>';
    if ($total === $key + 1) {
        echo h($treeCategory['Category']['name']);
    } else {
        echo $this->Html->link($treeCategory['Category']['name'], array('action'=>'find', 'category_id' => $treeCategory['Category']['id']));
    }
    echo '</li>';
}
echo '</ul>';
}

You will notice that the last element will not be a link anymore but a normal <li> tag. This way we can style it as the current (active) node in a different way to the other path elements.

Tip: You could also use the existing helper method addCrumb() as well as getCrumbList() of the HtmlHelper and output your breadcrumbs this way. If you don’t need any special treatment of your nodes, that is.

More experimental stuff

For very large trees like in category navigation structures with >> 100 category nodes it probably makes sense to only display the current level, and all direct siblings in the “active path”. It can also be a factor for search engines to only link the “relevant” cross-links here. I experimented with the hideUnrelated option and a custom callback or element to manually hide the elements marked as 'hide' => true.

Tip: It does need a nested structure (so make sure you use the right methods from above) and the threePath passed in as option. See the test case for details.

The following keys are then also available in callbacks/elements:

• show => if it has to be shown as part of the active path
• parent_show => if it is a child of an active path element and should also be visible
• hide => if it should be hidden (tops the other two settings)

Yet undecided

I have been thinking about removing the find(all) support in favor of supporting always nested array input. This would probably make the code way shorter and easier to read and maintain. As outlined above using Hash::nest() you can always form your array this way prior to passing it into the helper. So the overhead here could be removed.

Feel free to submit any ideas, criticism or PRs (pull requests). I just recently started to seriously work with tree structured data.