Yii 1.1: nestedset

Nested Set implementation using the ActiveRecord paradigm.
16 followers

This extension is an implentation of a Nested Set using the ActiveRecord method. At the moment, this extension only has an implementation using the "modified pre-order tree traversal algorithm" that can be found at this website. More information can also be found at the MySQL website about hierarchical storage.

The extension is implemented as a behavior so you can simply attach it to your own models.

This release may not be ready for production environments and (as every beta release) may need excessive testing. Please let me know if you find a bug or if you want to contribute.

Resources

Documentation

Requirements

  • Yii 1.0 or above

Installation

  • Extract the release file under protected/extensions

Usage

Step 1:

Before you start using it, you must set up a table in your database that can store hierarchical information. Using the "modified pre-order tree traversal algorithm" requires that table has some extra fields that allow us to store the structure of the tree. These columns are: ['id','lft','rgt','level']. Make sure that before you start modifying your tree, you you have one "root node" in your database. The node MUST have depth/level 0, and when it's the only node in the table, it has lft & right values of respectively 0 and 1.

I added a sql file as an example to the extension:

CREATE TABLE IF NOT EXISTS `tree` (
  `id` int(11) NOT NULL auto_increment,
  `lft` int(11) NOT NULL,
  `rgt` int(11) NOT NULL,
  `level` int(11) NOT NULL,
  `name` varchar(255) NOT NULL default '',
  PRIMARY KEY  (`id`),
  KEY `lft` (`lft`),
  KEY `rgt` (`rgt`),
  KEY `level` (`level`),
  KEY `name` (`name`)
) 
 
-- When using MySQL: add this:
-- ENGINE=InnoDB  DEFAULT CHARSET=latin1 AUTO_INCREMENT=1 ;
 
INSERT INTO `tree` (`id`, `lft`, `rgt`, `level`, `name`) VALUES
(1, 0, 1, 0, 'Root');

Step 2:

Now, we need to make sure the extension is loaded by Yii by adding it to your config file:

return array(
    //...
    'import'=>array(
        //...
        'application.extensions.nestedset.*'
    ),
    //...
);

Step 3:

Your third task is to create a model that extends the CActiveTreeRecord class. This is pretty straightforward and works almost the same as the default CActiveRecord class. The only thing thati s different that you add the TreeBehavior to your model:

<?php
 
class Tree extends CActiveRecord
{
    public static function model($className=__CLASS__)
    {
        return parent::model($className);
    }
 
    public function behaviors(){
        return array(
            'TreeBehavior' => array(
                'class' => 'application.extensions.nestedset.TreeBehavior'
            )
        );
    }
}
 
?>

When you use different column-names for your id/left/right/level columns, you can override the default names by setting the behavior parameters in your model:

public function behaviors(){
    return array(
        'TreeBehavior' => array(
            'class' => 'application.extensions.nestedset.TreeBehavior',
            '_idCol' => 'id',
            '_leftCol' => 'left',
            '_rightCol' => 'right',
            '_levelCol' => 'level',
        )
    );
}

Step 4:

When you have created your model, you are ready to use it in your controllers. See the example controller file for more tree manipulations.

$root = Tree::model()->findByPK(1);
 
$newNode = new Tree();
$newNode->name = "First Node";
$root->appendChild($newNode); //You do not have to use the "save" function here.
 
$newNode2 = new Tree();
$newNode2->name = "Second Node";
$root->appendChild($newNode2); //You do not have to use the "save" function here.
 
$newNode3 = new Tree();
$newNode3->name = "GrandChild Node";
$newNode->appendChild($newNode3); //You do not have to use the "save" function here.
 
// The structure looks like this:
//  * Root
//  -- * First Node
//  -- -- * GrandChild Node
//  -- * Second Node
 
// Let's do some modifications:
$newNode2->moveLeft();
 
// The structure now looks like this:
//  * Root
//  -- * Second Node
//  -- * First Node
//  -- -- * GrandChild Node
 
$newNode3->moveUp();
 
// And finally, the structure now looks like this:
//  * Root
//  -- * Second Node
//  -- * First Node
//  -- * GrandChild Node

Change Log

April 24, 2009

  • Initial beta release.

April 27, 2009

  • Changed implementation so it works like a behavior
  • Dynamically updates all open objects with the behavior attached so that you don't have to reload every object after manipulating your tree
  • Column names now configurable in the behavior settings array
  • Several minor bugfixes
  • Added more detailed example/test suite.

Januari 03, 2010 (v.0.4 - Quick maintenance release)

  • Fixed several bugs:
    • Moving subtrees sometimes created corrupted database.
    • Fixed bug in hasChildNodes function that delivered incorrect results
  • Now consistently throws exceptions when operating on an unsaved node.
  • In getNestedTree, you can opt to return the root node or not using the $returnrootnode parameter
  • Fixes "root" detection in moveUp()
  • getChildNodes() now returns a sorted list
  • Added debug traces to all methods

Total 20 comments

#3092 report it
schmunk at 2011/03/15 01:23pm
Does not work with 1.1.x

Looks promising, but found no way to get it working with 1.1.6, even with the fixes provided below.

#2603 report it
drumaddict at 2011/01/22 05:54pm
How can someone store more than one trees?

Is it possible to maintain two or more different trees/structures using the same table?-I don't think so.For example I am thinking of a CMS where the end user can add more than one nested menus (with hierarchical structure).The model also seems to be bound to the table,so one whould need different table and model for every menu,or what?

#370 report it
luc at 2010/06/23 09:45am
how to update the tree completely ?

Hi, ok, extension works well (after a few fixes see #965 and #999) with the jstree extension. I ask myself on how to update completely a nested set after having manipulating it with the jstree ???

(I've asked the same question on the jstree extension).

#652 report it
银河王子 at 2010/03/29 01:38am
what's wrong

I encountered a problem . TreeBehavior does not have a method named "getIsNewRecord".How to solve it ?

#656 report it
jerry2801 at 2010/03/27 12:10pm
advise

first, this is great extension~!

i have tree data use id/parent_id,

if behavior can add function like: rebuildFromAdjacency($parentKey='parent_id')

#679 report it
Nique at 2010/03/20 08:02pm
Broken

This extension seems to be really broken. Nothing works.. :(

Please update.

#759 report it
donnut at 2010/03/03 10:05am
bug in getSiblings()

The test if the calling node is equal to any child of its parent never fails. Thus, the calling node is included in the returned array.

current code:

foreach ($children as $child) {
    if ($this != $child) {
        $res[] = $child;
    }
}

suggested code:

foreach ($children as $child) {
   if($this->getIDValue() != $child->getIDValue()) {
       $res[] = $child;
   }
}

Also, I suggest to initialize $res:

 $res = array();

and the following line is not necessary:

 $pk = $this->Owner->primaryKey();
#981 report it
thyseus at 2010/01/15 07:55am
Right, and also do this in Line 366

cr0t is right, and you also need to fix line 366 of TreeBehavior.php the same way:

if($this->getOwner()->getIsNewRecord())

then everything should be working fine....

#1015 report it
Sergey Kuznetsov at 2010/01/09 02:22pm
BugReport fix

You can change the TreeBehavior.php file (line 319) like this:

if($this->getOwner()->getIsNewRecord())

instead of old:

if($this->getIsNewRecord())

and all be working for 1.1 version ... But I can't test this code on the older versions of Yii Framework. Somebody, please, test this fix.

#1021 report it
thyseus at 2010/01/07 03:37pm
Bug Report

I try to append a Child to the root.

500: TreeBehavior has no method called"getIsNewRecord".

I use yii-1.1-dev snapshot from today.

#1026 report it
Remko Nolten at 2010/01/06 06:31pm
addChild Error

Which version of Yii do you use?

#1027 report it
jwerner at 2010/01/06 06:19pm
addChild Error

While testing the supplied example, I get this error:

TreeBehavior does not have a method named "getIsNewRecord".

Trace:

#0 [internal function]: CComponent->__call('getIsNewRecord', Array)
#1 .../protected/extensions/nestedset/TreeBehavior.php(366): TreeBehavior->getIsNewRecord()
#2 [internal function]: TreeBehavior->appendChild(Object(Tree))
#3 .../yii-1.0.11.r1579/framework/base/CComponent.php(215): call_user_func_array(Array, Array)
#4 .../yii-1.0.11.r1579/framework/db/ar/CActiveRecord.php(519): CComponent->__call('appendChild', Array)
#5 [internal function]: CActiveRecord->__call('appendChild', Array)
#6 .../protected/controllers/SiteController.php(20): Tree->appendChild(Object(Tree))
#1073 report it
thyseus at 2009/12/17 09:44pm
Also important:

Add the following to appendChild($node) - so sub-childs of the node keep the structure:

if($node->hasChildNodes() && $node->level != 0) $childs = $node->getChildNodes();

and after transaction->commit:

if($childs != array()) {
          foreach($childs as $child) {
            $child->moveBelow($node);
          }
        }

(email me or use forum or icq 38541423 for a working example)

#1081 report it
thyseus at 2009/12/15 05:10am
small Addition...

please add the line

$criteria->order = $this->_lftCol." ASC";

to line 326 in TreeBehavior.php so Child Nodes get sorted when using getChildNodes() in your next release...

Nice work ! I am using this module in an productive Document Management System. Thank you so far!

#1089 report it
thyseus at 2009/12/11 09:37am
getNextSibling() and getPrevSibling() broken in 1.1beta?

Hi,

is it possible that the methods getNextSibling() and getPrevSibling() are broken in 1.1beta?

00237: throw new CException(Yii::t('yii','{class} does not have a method named "{name}".', 00238: array('{class}'=>get_class($this), '{name}'=>$name))); 00239: } 00240: 00241: /** 00242: * Returns the named behavior object. 00243: * The name 'asa' stands for 'as a'. 00244: * @param string the behavior name 00245: * @return IBehavior the behavior object, or null if the behavior does not exist 00246: * @since 1.0.2 00247: */ 00248: public function asa($behavior) 00249: {

thanx !

#1111 report it
jerry2801 at 2009/12/07 03:59am
add parent_id field, and afford reBuildTree() api~

AS TITLE~

thanks for your nice job~

#1169 report it
ch0un0ky at 2009/11/18 07:15pm
Very big mistake in function moveNode()

Hello, you have realy big mistake in this function, when someone call moveAfter() and that move must be up, it will write bad values to db. Please repair it in next releace.

online: 760 in after if

$move = $movenode->getLeftValue() - $sibling->getRightValue() + 1;

to

$move = $movenode->getLeftValue() - $sibling->getRightValue() - 1;

#1182 report it
ch0un0ky at 2009/11/11 06:28pm
Little mistake in hasChildNodes

Realy nice extension. Thanks for that.

And you have mistake in this function.

  • @return boolean True when the node has childe nodes, false when the node is a leaf.

public function hasChildNodes() { return $this->getLeftValue() == ($this->getRightValue() - 1); }

it has to be

return $this->getLeftValue() != ($this->getRightValue() - 1);

#1303 report it
mech7 at 2009/09/23 05:36pm
level..

One more thing if you add level to getTree..

public function getTree($returnrootnode = true, $level = false)

You can set the depth of the tree which is usefull if you use it for a menu, so you can only get main menu items.. or menu with max depth of 2 etc..

This then needs be set in getNestedTree also..

and in getNestedTree.. getTree was called to have the root node always.

$rawtree = $this->getTree(false);

Instead..

$rawtree = $this->getTree($returnrootnode);

(Which is set as parameter)

And as last suggestion.. instead of the printNestedTree inside the controller, its easy to put it in a widget...

I can now call the menu I want like:

<?php $this->widget('application.components.RenderMenu',array('root_id' => 1, 'depth' => 1));?>

Atleast these where the modifications I made.. your code really helped me alot so big thanks :D

#1313 report it
mech7 at 2009/09/18 04:56pm
Good ^^

It's pretty nice extensions thanks... just one more thing to add..

In move up there is:

if($parent->name == "Root" || $parent->id <= 1)

It would be nice if change it too..

if($parent->id <= $this->_rootId)

And then add a variable for _rootId with default 1..

This way you are not stuck on having "name" in the table (I didn't need it) And it is possible to have more then one hierachie by setting a scope in the model.

Leave a comment

Please to leave your comment.

Create extension
  • Yii Version: 1.1
  • License: New BSD License
  • Developed by: Remko Nolten
  • Category: Database
  • Votes: +25 / -3
  • Downloaded: 2,953 times
  • Created on: Apr 24, 2009
  • Last updated: Jan 3, 2010