nestedsetbehavior

Could benefit from using of Postgresql's ltree data type where available: http://www.postgresql.org/docs/9.1/static/ltree.html

The Problem

I have noticed a bit of a problem with it if you use it for exports or similar tasks where you are traversing through the whole database getting data and pushing it out to a file.

The extension has an internal cache stored in a static variable. This can be disastrous since this means that the memory of the model you just used will be stored in memory and because of that is not released when you loop through to the next element.

I was traversing through about 100000 items and after adding a call to a model that uses the nested set behaviour my export script started running out of memory.

I am using a call like this in a loop:

$ancestor = $this->ancestors(1)->find();

If you look in the afterFind Method in the nested set behaviour it does this:

$owner=$this->getOwner();
self::$_cached[get_class($owner)][$this->_id=self::$_c++]=$owner;

This stores the object in a static array. Quite quickly this will fill the memory up. This problem is probably only ever going to show up in the rare event of you traversing through a large number of nodes and I can see that this is the wanted behaviour in most cases.

The Solution

Make sure to destruct the model manually after you have used it. Like so:

$ancestor->__destruct();

The nested set behaviour has a destructor that removes the object from the static cache.

unset(self::$_cached[get_class($this->getOwner())][$this->_id]);

Suggestion

Add possibility to turn caching off in the behaviour.

Something like:

public function behaviors()
    {
      return array(
            'NestedSetBehavior'=>array(
                'class'=>'application.components.behaviors.trees.NestedSetBehavior',
                'leftAttribute'=>'left',
                'rightAttribute'=>'right',
                'levelAttribute'=>'level',
                'hasManyRoots'=>true,
                'cache'=>false
        ));
    }

Hi there, I'd like to attach a user_id field to this table and have 1 tree per user. Do you think this plugin will work in this way?

Thanks for the great work, Marco.

hi, thanks for your great job is there a best solution to use it with CMenu?

when a top level root has too many children , if want to use the pagination . how to ? i noticed this method : public function descendants($depth=null, $self = false)

too many children means the tree may be too deep or too wide . both situation need consider how to apply pagination , any idea ?

Hi,I have just uploaded an extension for Nested Set Behavior Administration with jsTree plugin.This is the Link: Nested Set Behavior Administration GUI with jsTree

A very useful extension, thank you so much for sharing! Could you please help me get this clear — how exactly can I display the whole tree via CTreeView widget? What is the right way to get the whole tree, when three has many roots?

the usage example is very helpful , also we can check it out from svn , in the unit test directory one can find more usage!

how about developing an extension that bridge the nestedset model and the adjacency model , we can translate one model easily to another . there are some code pieces in the internet converting the nestedset to adjacency model . you need create both table and config the mapping for two table fields( because some table may be exist earlier and may have different field name ) ,often converting take place in midnight ,it will cost a lot of time .

I just implemented jqGrid Tree view using Nested Sets with multiple nodes. It took me sometime to work out the logic, so i thought i could share my code, if some other beginner like me needs to check.

Using Nested Sets in multiple roots mode requires the use of the 'adjacency' jqGrid tree Model. Atleast that is what i understand.

The view file details:

<?php
Yii::app()->clientScript->registerCoreScript('jquery.ui');
Yii::app()->clientScript->registerCssFile(Yii::app()->baseUrl . '/css/ui-lightness/jquery-ui-1.8.13.custom.css');
Yii::app()->clientScript->registerCssFile(Yii::app()->baseUrl . '/css/ui.jqgrid.css');
Yii::app()->clientScript->registerScriptFile(Yii::app()->baseUrl . '/js/jqGrid/i18n/grid.locale-en.js', CClientScript::POS_HEAD);
Yii::app()->clientScript->registerScriptFile(Yii::app()->baseUrl . '/js/jqGrid/jquery.jqGrid.min.js', CClientScript::POS_HEAD);
?>
<table id="list"></table> 
<div id="pager"></div> 
<?php
$script = '
    jQuery("#list").jqGrid(
    {
        treeGrid: true,
        treeGridModel: "adjacency",
        ExpandColumn: "name",
        rowNum: -1,
        url: "' . $this->createUrl("fetchTree") . '",
        datatype: "json",
        treedatatype: "json",
        treeIcons: {plus:"ui-icon-plus",minus:"ui-icon-minus",leaf:"ui-icon-cancel"},
        mtype: "POST",
        ExpandColClick: true,
        colNames:["id", "Group Name"],
        colModel :
            [ 
                {name:"id", index:"id", width:1, hidden: true, key: true},
                {name:"name", index:"name", width:300, sortable: false}
            ],
        height: "auto",
        caption: "View Groups"
    });
';
 
Yii::app()->clientScript->registerScript('jqGrid',$script);
?>

The actionFetchTree method:

public function actionFetchTree()
    {
        $ADDWHERE = '';
        if (isset ($_REQUEST["nodeid"]))
            $node = (integer)$_REQUEST["nodeid"];
        else
            $node = 0;
        // detect if here we post the data from allready loaded tree
        // we can make here other checks
        if( $node >0) 
        {
            //in jqGrid the level starts from 0, but in nested sets with multiple roots the level starts from 1
            $n_lvl = (integer)$_REQUEST["n_level"] + 1;         
            $parent = Yii::app()->db
                    ->createCommand("Select id, root, lft, rgt from tbl_tree WHERE id = $node")
                    ->queryRow();
            $ADDWHERE = " root = " . $parent["root"] . " AND level = " . ($n_lvl+1) . " AND lft > " . $parent["lft"] . " AND rgt < " . $parent["rgt"];
        } 
        else 
        { 
            // initial grid
            $n_lvl =0;
            $ADDWHERE = " level = 1 ";
        }        
        $SQL1 = "SELECT id, root, name, level-1 as lvl, lft, rgt, is_ledger from tbl_tree WHERE $ADDWHERE order by root, lft";
 
        header("Content-type: text/html;charset=utf-8");
        $response->page = 1;
        $response->total = 1;
        $cmd = Yii::app()->db->createCommand($SQL1);
        $result = $cmd->queryAll();
        $i=0;
        foreach ($result as $row)
        {
            if ($row['is_ledger'] == true) $leaf = 'true';else $leaf='false';
            if ($row['lvl'] == 0) $root = NULL; else $root = $parent['id'];
            $l = (integer)$row['lvl'];
            if( $n_lvl ==  $l)
            {
                $response->rows[$i]['cell']=array
                    (
                        $row['id'],
                        $row['name'],
                        $n_lvl,
                        $root,
                        $leaf,
                        'false'
                    );
                $i++;
            }
        }
        echo json_encode($response);
    }

The explanation is given in the jqGrid wiki site where the usage of Adjacency Model is described. The only point to remember here is that while sending the children nodes we need to send the immediate parent id, and not the root id for that tree. So, in the beginning of the code, we try to obtain the root details through a queryRow() call

This is really a great extension.

Please notice that while performing the moveNode action, the checking is being done to find out if a txn has already been set (i.e., if there was a beginTransaction() issued by some controller). And only if it has not been set, the extension tries to set one by itself.

But while deleting a Node, the same is not being done. I feel that this checking could have been done in the delete method also. In my implementation, i have enabled this checking and it is working fine, as of now.

Beautiful work!

One note, this is technically not a nested set, but an adjacency list - this type of tree implementation is optimized for fast reading, but writes are more expensive than a nested set. It also had the advantage (over a nested set) of maintaining sibling order.

Personally I prefer adjacency lists - and this is an awesome implementation, queries neatly packaged as scopes, operations fully wrapped in transactions, fully unit tested, etc. - very, very nice work!

Thanks!

First of all, great extension.

Now I need to extend its functionality in order to keep several trees in the same table. Not one tree with several roots, but several trees within the same table. I would need this "profile_id" filter to paint one tree or another.

I have a table "profile_component" with fields "id", "left", "right" and "level" to manage the nested set behavior. But it also has a field "profile_id", so that the records with profile_id=0 represent one tree, the records with profile_id=1 represent a second tree, and so on.

Does anybody know how should I extend the component so that I can get one tree or another by setting this "profile_id" attribute?

I´m using also JsTree to render the tree and EJNestedTreeActions to deal with the tree actions.

Thanks in advance

in a project there may have many models , which have the tree struct . and if this extension can apply to multiple ar or can only to one specific ar . if attach to many different ar , does it need to modify the category table schema , may be add some field like : cate_type varchar(20) .. or i misunderstand the usage , i will modify the ar's table add the table field come from the category .
the tree struct can added to a exist table(which in first version may be plain ) ,let's say : menu(id,text,url). some time later , we need the menu to support tree struct , there are two choices : 1.add some another fields to the menu table ,like pid, level etc..; 2.- use another table such as node to maintain the relation :node(id ,type, id_type,type_pid,type_level)
the choice 2 may need do a lots things when perform the crud operations. for query may use the left join or inner join . and create , update , delete become even complex . so if i use this extension in my project , i have to modify the existing ar's table.

How track event change node, moved, created, updated, deleted? Event onAfterSave not work! I need delete cache if changed structur of tree. And it is I have to do in model.

Thanks :) !

Hi,

If you need to find the position of a node into its parent branch, you can use something like that in your model:

public function getPosition() {
   return ($this->lft - ($this->parent->lft+1))/2;
}

then simply get the value by using $model->position

Very cool extension by the way ;)

Regards

Hi,

I am trying to implement this extension with a single root, but I can't find an example for saving nodes with it.

Could somebody please post a save snippet for this case?

Best regards,

Can you add something like this :

[code]public function descendants($depth=null, $orderByLft=true)[/code]

order by lft is not always needed.

It would be nice if we could save the parent_id of the node along with lft/rgt/level. If you save the parent_id then the query to find the direct descendants (not to mention the parent) becomes trivial. It won't affect your other queries, but 2 of the most common (for me, anyway) - direct children and getting the parent - should see big speed increases on large tables. Or am I missing something? :)

Пасип, мужики, буду пользовать =)

If you will use it also need to add childs var in model class.

I put this function in overloaded class

class ENestedSetBehavior2 extends ENestedSetBehavior {
 
    /**
     * Tree must be sorted by left key
     * @param array $tree
     */
    public function hierarchical($tree = array()) {
        if(empty($tree))
            return false;
 
        $tmp = array();
        $parents = array();
        foreach($tree as $k=>$node){
            if($node->level == 1) {
                $tmp[$k] = $node;
                $parents[$node->level] = & $tmp[$k]->childs;
            } else {
                for($i = 1; $i < $node->level; $i++)
                    $parent = & $parents[$i];
 
                $parent[$k] = $node;    
                $parents[$node->level] = & $parent[$k]->childs;
            }
        }
        return $tmp;
    }
 
    /**
     * Named scope
     * @param int depth
     * @param boolean $self - return self node
     * @return CActiveRecord the owner.
     */
    public function descendants($depth=null, $self = false) {
...

Code example, in controller

$root = Category::model()->roots()->findByPk($id);
$branch = $root->descendants(null, true)->findAll();
 
$tree = Category::model()->tree->hierarchical($branch);
$this->render('tree', array(
    'model' => $root,
    'view' => $view,
    'tree' => $tree,
));

and views tree.php

<?php $this->renderPartial('_hierarchical', array('tree'=>$tree));?>

and _hierarchical.php

<?php if(!empty($tree)): ?>
<ul>
<?php
foreach($tree as $node):
?>
    <li>
        <?php echo CHtml::link($node->title, array('viewNode', 'id'=>$node->id)); ?>
        <?php if(!empty($node->childs))
                $this->renderPartial('_hierarchical', array('tree'=>$node->childs));
        ?>
    </li>
<?php 
endforeach;
?>
</ul>
<?php endif; ?>

this code will show somth like this