nestedsetbehavior Nested set behavior for AR models

  1. Documentation
  2. Installing and configuring
  3. Selecting from a tree
  4. Modifying a tree
  5. Modifying a tree
  6. Useful code
  7. Change Log
  8. 1.05
  9. 1.04
  10. 1.03
  11. 1.02
  12. 1.01
  13. 1.00
  14. 0.99b
  15. 0.99
  16. 0.95
  17. 0.90
  18. 0.85

Note: Latest release and documentation are available from extension github page.

This extension allows managing trees stored in database as nested sets. It's implemented as Active Record behavior.

Implemented by creocoder.

Resources

Documentation

Installing and configuring

First you need to configure model as follows:

public function behaviors()
{
    return array(
        'NestedSetBehavior'=>array(
            'class'=>'ext.yiiext.behaviors.trees.NestedSetBehavior',
            'leftAttribute'=>'lft',
            'rightAttribute'=>'rgt',
            'levelAttribute'=>'level',
    );
}

There is no need to validate fields specified in leftAttribute, rightAttribute, rootAttribute and levelAttribute options. Moreover, there could be problems if there are validation rules for these. Please check if there are no rules for fields mentioned in model's rules() method.

In case of storing a single tree per database, DB structure can be built with extensions/yiiext/behaviors/trees/schema.sql. If you're going to store multiple trees you'll need extensions/yiiext/behaviors/trees/schema_many_roots.sql.

By default leftAttribute, rightAttribute and levelAttribute values are matching filed names in default DB schemas so you can skip configuring these.

There are two ways this behavior can work: one tree per table and multiple trees per table. The mode is selected based on the value of hasManyRoots option that is false by default meaning single tree mode. In multiple trees mode you can set rootAttribute option to match existing filed in the table storing the tree.

Selecting from a tree

In the following we'll use an example model Category with the following in its DB:

- 1. Mobile phones
	- 2. iPhone
	- 3. Samsung
		- 4. X100
		- 5. C200
		- 6. Motorola
- 7. Cars
	- 8. Audi
	- 9. Ford
	- 10. Mercedes

In this example we have two trees. Tree roots are ones with ID=1 and ID=7.

Getting all roots

Using NestedSetBehavior::roots():

$roots=Category::model()->roots()->findAll();

Result:

Array of Active Record objects corresponding to Mobile phones and Cars nodes.

Getting all descendants of a node

Using NestedSetBehavior::descendants():

$category=Category::model()->findByPk(1);
$descendants=$category->descendants()->findAll();

Result:

Array of Active Record objects corresponding to iPhone, Samsung, X100, C200 and Motorola.

Getting all children of a node

Using NestedSetBehavior::children():

$category=Category::model()->findByPk(1);
$descendants=$category->children()->findAll();

Result:

Array of Active Record objects corresponding to iPhone, Samsung and Motorola.

Getting all ancestors of a node

Using NestedSetBehavior::ancestors():

$category=Category::model()->findByPk(5);
$descendants=$category->ancestors()->findAll();

Result:

Array of Active Record objects corresponding to Samsung and Mobile phones.

Getting parent of a node

Using NestedSetBehavior::getParent():

$category=Category::model()->findByPk(9);
$parent=$category->parent;

Result:

Array of Active Record objects corresponding to Cars.

Getting node siblings

Using NestedSetBehavior::getPrevSibling() or NestedSetBehavior::getNextSibling():

$category=Category::model()->findByPk(9);
$nextSibling=$category->nextSibling;

Result:

Array of Active Record objects corresponding to Mercedes.

Getting the whole tree

You can get the whole tree using standard AR methods like the following.

For single tree per table:

Category::model()->findAll(array('order'=>'lft'));

For multiple trees per table:

Category::model()->findAll(array('condition'=>'root_id=?','order'=>'lft'),array($root_id));

Modifying a tree

In this section we'll build a tree like the one used in the previous section.

Creating root nodes

You can create a root node using NestedSetBehavior::saveNode(). In a single tree per table mode you can create only one root node. If you'll attempt to create more there will be CException thrown.

$root=new Root;
$root->title='Mobile Phones';
$root->saveNode();
$root=new Root;
$root->title='Cars';
$root->saveNode();

Result:

- 1. Mobile Phones
- 2. Cars
Adding child nodes

There are multiple methods allowing you adding child nodes. To get more info about these refer to API. Let's use these to add nodes to the tree we have:

$category1=new Category;
$category1->title='Ford';
$category2=new Category;
$category2->title='Mercedes';
$category3=new Category;
$category3->title='Audi';
$root=Category::model()->findByPk(1);
$category1->appendTo($root);
$category2->insertAfter($category1);
$category3->insertBefore($category1);

Result:

- 1. Mobile phones
	- 3. Audi
	- 4. Ford
	- 5. Mercedes
- 2. Cars

Logically the tree above doesn't looks correct. We'll fix it later.

$category1=new Category;
$category1->title='Samsung';
$category2=new Category;
$category2->title='Motorola';
$category3=new Category;
$category3->title='iPhone';
$root=Category::model()->findByPk(2);
$category1->appendTo($root);
$category2->insertAfter($category1);
$category3->prependTo($root);

Result:

- 1. Mobile phones
	- 3. Audi
	- 4. Ford
	- 5. Mercedes
- 2. Cars
	- 6. iPhone
	- 7. Samsung
	- 8. Motorola
$category1=new Category;
$category1->title='X100';
$category2=new Category;
$category2->title='C200';
$node=Category::model()->findByPk(3);
$category1->appendTo($node);
$category2->prependTo($node);

Result:

- 1. Mobile phones
	- 3. Audi
		- 9. С200
		- 10. X100
	- 4. Ford
	- 5. Mercedes
- 2. Cars
	- 6. iPhone
	- 7. Samsung
	- 8. Motorola

Modifying a tree

In this section we'll finally make our tree logical.

Tree modification methods

There are several methods allowing you to modify a tree. To get more info about these refer to API.

Let's start:

// move phones to the proper place
$x100=Category::model()->findByPk(10);
$c200=Category::model()->findByPk(9);
$samsung=Category::model()->findByPk(7);
$x100->moveAsFirst($samsung);
$c200->moveBefore($x100);
// now move all Samsung phones branch
$mobile_phones=Category::model()->findByPk(1);
$samsung->moveAsFirst($mobile_phones);
// move the rest of phone models
$iphone=Category::model()->findByPk(6);
$iphone->moveAsFirst($mobile_phones);
$motorola=Category::model()->findByPk(8);
$motorola->moveAfter($samsung);
// move car models to appropriate place
$cars=Category::model()->findByPk(2);
$audi=Category::model()->findByPk(3);
$ford=Category::model()->findByPk(4);
$mercedes=Category::model()->findByPk(5);

foreach(array($audi,$ford,$mercedes) as $category)
    $category->moveAsLast($cars);

Result:

- 1. Mobile phones
	- 6. iPhone
	- 7. Samsung
		- 10. X100
		- 9. С200
	- 8. Motorola
- 2. Cars
	- 3. Audi
	- 4. Ford
	- 5. Mercedes
Moving a node making it a new root

There is a special moveAsRoot() method that allows moving a node and making it a new root. All descendants are moved as well in this case.

Example:

$node=Category::model()->findByPk(10);
$node->moveAsRoot();
Identifying node type

There are three methods to get node type: isRoot(), isLeaf(), isDescendantOf().

Example:

$root=Category::model()->findByPk(1);
CVarDumper::dump($root->isRoot()); //true;
CVarDumper::dump($root->isLeaf()); //false;
$node=Category::model()->findByPk(9);
CVarDumper::dump($node->isDescendantOf($root)); //true;
CVarDumper::dump($node->isRoot()); //false;
CVarDumper::dump($root->isLeaf()); //true;
$samsung=Category::model()->findByPk(7);
CVarDumper::dump($node->isDescendantOf($samsung)); //true;

Useful code

Non-recursive tree traversal
$level=0;

foreach($categories as $n=>$category)
{
	if($category->level==$level)
		echo CHtml::closeTag('li')."\n";
	else if($category->level>$level)
		echo CHtml::openTag('ul')."\n";
	else
	{
		echo CHtml::closeTag('li')."\n";

		for($i=$level-$model->level;$i;$i--)
		{
			echo CHtml::closeTag('ul')."\n";
			echo CHtml::closeTag('li')."\n";
		}
	}

	echo CHtml::openTag('li');
	echo CHtml::encode($category->title);
	$level=$category->level;
}

for($i=$level;$i;$i--)
{
	echo CHtml::closeTag('li')."\n";
	echo CHtml::closeTag('ul')."\n";
}

Change Log

1.05

  • External transaction support for NestedSetBehavior::delete() method (creocoder)

1.04

  • Fix for $depth parameter of NestedSetBehavior::ancestors() method (creocoder)

1.03

  • Class renamed to NestedSetBehavior (creocoder)
  • Rare bug with cache correction after NestedSetBehavior::addNode() fixed (creocoder)
  • Readmes non-recursive tree traversal algorithm fix (creocoder)

1.02

  • Added moveAsRoot() method (creocoder)
  • Updated readmes (Sam Dark)

1.01

  • Added not integer pk support (creocoder)
  • Remove final from class (creocoder)

1.00

  • Some behavior refactoring before release (creocoder)
  • Advanced doc added (creocoder)

0.99b

  • Allow to use multiply change tree operations (creocoder)
  • Method saveNode() now create root in "single root mode" (creocoder)
  • Unit tests refactored (creocoder)
  • Some behavior refactoring (creocoder)

0.99

  • Added note about removing fields from rules (Sam Dark)
  • Added Unit tests for single root mode (creocoder)
  • All attributes are now correctly quoted (creocoder)
  • Renamed fields: 'root'=>'rootAttribute', 'left'=>'leftAttribute', 'right'=>'rightAttribute', 'level'=>'levelAttribute' (creocoder)
  • Renamed method parent() => getParent() (creocoder)

0.95

  • Unit tests added (creocoder)
  • Incorrect usage of save() and delete() instead of behavior's saveNode() and deleteNode() is now detected (creocoder)

0.90

  • Moving a node to a different root is now supported (creocoder)

0.85

  • Initial public release (creocoder)
75 1
103 followers
2 776 downloads
Yii Version: 1.1
License: BSD-2-Clause
Category: Database
Developed by: creocoder
Created on: Jun 11, 2010
Last updated: 12 years ago

Related Extensions