Battling (My Own) Idiocy

a.k.a. do everything wrong the first time just to get it out of the way

Implementing a Nested Set (part one)

Posted by halestock on February 3, 2010

While representing data in a tree structure is normally straightforward, implementing it in a relational database is somewhat of a struggle. The standard way of representing hierarchical data in a relational database is using what’s called a nested set, which (luckily) Doctrine has a built-in behavior for.

While this makes things easier, I’ve found that Symfony doesn’t understand how to deal with this. At first I tried several plugins which are available for managing this behavior, but of the few I found most were either unmaintained or still a work in-progress. So, I decided to just dive in and see if I could get the behavior to work correctly with some basic formatting. In the following code I’ll put together a simple nested set called “category”. Although this example uses Symfony’s admin generator to generate the module, it should still be applicable if you choose to generate a normal module for it.

Adding the nested set behavior is just a matter of specifying “actAs” when defining your schema. For a full explanation on Doctrine’s Nested Set, read this.

# /config/doctrine/schema.yml

Category:
  actAs:
    NestedSet:
      hasManyRoots: true
      rootColumnName: root_id
  columns:
    name: string(255)

Although the only column being specified is name, by default Doctrine will create a primary key field called id, and the fields lft, rgt, level and (optionally) root_id, which are used for the nested set. For a full explanation of exactly how the nested set works, you can visit here.

I won’t go into the details of creating an entire project in Symfony, but for this example let’s assume I’ve created a project called hierarchy and have used the admin generator to create the backend module category. When you first view index page of category, you’ll notice that all the columns are displayed:

More importantly, however, when you create a new item, or edit or delete any of the existing ones, Symfony will treat it as it would any other record, which can cause very unexpected behavior. To preserve the structure when modifying a nested set, it’s necessary to first use the getNode() method on any existing records, or one of several methods provided by Doctrine when creating a new record.

In my case, the first step I took was to implement configure() in CategoryForm.class.php so I could remove the auto-generated fields and replace them with a dropdown to select the category’s parent. You can also set help messages and such, but that type of thing is of course optional.

class CategoryForm extends BaseCategoryForm
{
  public function configure()
  {
    // create a new widget to represent this category's "parent"
    $this->setWidget('parent', new sfWidgetFormDoctrineChoiceNestedSet(array(
      'model'     => 'Category',
      'add_empty' => true,
    )));

    // if the current category has a parent, make it the default choice
    if ($this->getObject()->getNode()->hasParent())
    {
      $this->setDefault('parent', $this->getObject()->getNode()->getParent()->getId());
    }

    // only allow the user to change the name of the category, and its parent
    $this->useFields(array(
      'name',
      'parent',
    ));
    // set labels of fields
    $this->widgetSchema->setLabels(array(
      'name'   => 'Category',
      'parent' => 'Parent category',
    ));
    // set a validator for parent which prevents a category being moved to one of its own descendants
    $this->setValidator('parent', new sfValidatorDoctrineChoiceNestedSet(array(
      'required' => false,
      'model'    => 'Category',
      'node'     => $this->getObject(),
    )));
    $this->getValidator('parent')->setMessage('node', 'A category cannot be made a descendent of itself.');
  }
}

You’ll notice that I used a new widget, sfWidgetFormDoctrine, and validator, sfValidatorDoctrineChoiceNestedSet. They are similar to the built-in sfWidgetFormDoctrineChoice and sfValidatorDoctrineChoice, modified to work with a nested set. Essentially, sfWidgetFormDoctrineChoiceNestedSet extends upon sfWidgetFormDoctrineChoice by always sorting it according to the nested set’s hierarchy, and formatting each item so you can see the hierarchy in the dropdown. sfValidatorDoctrineChoiceNestedSet adds an extra validation by making sure that the selected value of ‘parent’ is not a descendent of the current record. I will fully dissect these in my next post, but I wanted to finish up this post with the meat of this example, which is the actual saving of records.

When you want to override some part of the saving mechanism, the place to do it is usually in the forms doSave method. This method gets called after validation of the form, but before the form is actually saved. So, this is exactly where we need to override Symfony’s normal save call.

class CategoryForm extendsBaseCategoryForm
{
  ...

  /**
   * Updates and saves the current object. Overrides the parent method
   * by treating the record as a node in the nested set and updating
   * the tree accordingly.
   *
   * @param Doctrine_Connection $con An optional connection parameter
   */
  public function doSave($con = null)
  {
    // save the record itself
    parent::doSave($con);
    // if a parent has been specified, add/move this node to be the child of that node
    if ($this->getValue('parent'))
    {
      $parent = Doctrine::getTable('Category')->findOneById($this->getValue('parent'));
      if ($this->isNew())
      {
        $this->getObject()->getNode()->insertAsLastChildOf($parent);
      }
      else
      {
        $this->getObject()->getNode()->moveAsLastChildOf($parent);
      }
    }
    // if no parent was selected, add/move this node to be a new root in the tree
    else
    {
      $categoryTree = Doctrine::getTable('Category')->getTree();
      if ($this->isNew())
      {
        $categoryTree->createRoot($this->getObject());
      }
      else
      {
        $this->getObject()->getNode()->makeRoot($this->getObject()->getId());
      }
    }
  }
}

After I show the implementation of the custom widget/validator, we should be able to add and edit records correctly. What still remains is deleting existing records correctly, as that is not handled from within the framework of the CategoryForm. Additionally, I will show how to make some minor formatting changes to the index page, so that the hierarchy is shown in a much more presentable and understandable way.

About these ads

23 Responses to “Implementing a Nested Set (part one)”

  1. despai said

    Nice article!!

  2. paulodani said

    Great article !

    I think that there are a error in CategoryForm (lines 35 and 39).

    line 35:
    $categoryTree->createRoot($this->getObject());

    line 39:
    $this->getObject()->getNode()->createRoot($this->getObject()->getId())

    • halestock said

      Thanks, fixed the labeling of categoryTree.

      As for the createRoot vs. makeRoot methods, makeRoot is used here because it moves the existing record as opposed to creating a new one (which is why it is used only if it isn’t a new record).

  3. paulodani said

    Thanks for the createRoot vs. makeRoot details, great help.

  4. Paulo said

    Really nice article!

    I think that the following test would improve the code.

    if ($this->isNew()) {
    $this->getObject()->getNode()->insertAsLastChildOf($parent);
    }
    else
    {
    if($this->getObject()->getNode()->getParent()->getId() != $this->getValue(‘parent’)) // test to see if the parent has changed
    $this->getObject()->getNode()->moveAsLastChildOf($parent);
    }

    This way only when the parent is changed it moves the object to the end of the line ;-) .

  5. Florian said

    Hi,

    I was so happy to see the code of

    sfValidatorDoctrineChoiceNestedSet
    and
    sfWidgetFormDoctrineChoiceNestedSet …

    Can you please post them, I think it’s one of the most important thing in your tuto !

    Thanks in advance.
    Florian.

  6. jp_morvan said

    Hi,
    Thank you for the plugin sfDoctrineNestedSetPlugin.

    I’ve a little problem with the widget sfWidgetFormDoctrineChoiceNestedSet.
    I don’t use root_id as root id but id_parent. So, in line 28, you have :
    $query->addOrderBy(‘root_id asc’)
    Has NestedSet’s template a method that can return the value of rootColumnName defined in schema.yml and than you can replace in line 28 ?

    • halestock said

      If you’re using parent_id to refer to the direct parent of a particular node instead of the root node, I’m not sure of how you would specify it as an ORDER BY clause (at least in an efficient way). However, you could instead retrieve the records (without sorting) as an array, sort it manually in PHP, and then cast it to a Doctrine_Collection like so:

      $result = $query->execute(array(), Doctrine::HYDRATE_ARRAY);
      // sort array here
      $collection = new Doctrine_Collection(“tableName”); // tableName => the name of your nested set table
      $collection->fromArray($objects);
      $objects = $collection;

      This may not be the best solution, but it should give you a starting point. The nice thing is that there’s a lot of flexibility when it comes to this, so there’s several ways you can go about it. (Another option is to specify your own table method to retrieve the choices and then pass it using the table_method option when you create the form)

      Hope this helps!

    • shane said

      or change that if statement to something more like this

      if (null === $this->getOption('table_method'))
      {
      $table = Doctrine_Core::getTable($this->getOption('model'));
      $query = null === $this->getOption('query') ? $table->createQuery() : $this->getOption('query');
      // force manual sorting according to root_id then by lft
      $query->addOrderBy( $table->getTree()->getAttribute('rootColumnName') .' asc')
      ->addOrderBy('lft asc');
      $objects = $query->execute();
      }

      • Jp_morvan said

        Hi,

        Thank you both of you for your reply.

        I’ll try the solution of Shane when I’ll have some time :p

      • shane said

        Another slight modification :D


        if (null === $this->getOption('table_method'))
        {
        $table = Doctrine_Core::getTable($this->getOption('model'));
        $query = null === $this->getOption('query') ? $table->createQuery() : $this->getOption('query');
        // force manual sorting according to root_id then by lft
        // check if multiple roots is set, if it is find out what the root column is.
        if( $table->getTree()->getAttribute('rootColumnName') !== null )
        $query->addOrderBy( $table->getTree()->getAttribute('rootColumnName') .' asc' );
        $query->addOrderBy('lft asc');
        $objects = $query->execute();
        }

  7. zazabe said

    Hi,

    Thanks for your widgets !

    just one think, what is the best way to delete items in admin ?
    I just override the delete action but I don’t think it’s the best way… maybe you have a better solution.

    One other point, I don’t know if it’s a bug of doctrine nestedset (I don’t think) or I do something wrong but my tree is corrupted after adding some item if I define my nestedset with hasManyRoots to false… (it’s not a problem to set it to true, I just want to know if I’m the only one to have this problem)

    Thanks again :)

    • maxdamage said

      Yeap… lost almost 24h on this “hasManyRoots: false”. Now works like a charm! (sf 1.4)
      It would be best to make this note in the article. Anyway, thanks! :)

  8. david said

    Take a look this plugin: sfDoctrineNestedSetEasyManagerPlugin
    getChildren() hits database in a loop, but you can contribute:

    http://github.com/binarty/sfDoctrineNestedSetEasyManagerPlugin

  9. Thanks for the article.

    Was very helpful

  10. I wrote a french article for use nested set with symfony here: http://www.blog.manit4c.com/2011/07/18/utiliser-le-nestedset-arbre-par-representation-intervallaire-avec-doctrine-et-symfony/
    Your’s help me for write it.

  11. Gustavo said

    Hi, I have a problem when moving nodes between trees (diferentes roots) ….

    example

    1
    1.1
    1.1.1
    1.1.2
    1.2
    1.3
    2

    If I move 1.1 to 2, is not problem, but when I move 1.1 again to 1 :

    Call to a member function getId() on a non-object in /var/www/…/lib/form/doctrine/CategoryForm.class.php on line 34

    line 34: $this->setDefault(‘parent’, $this->getObject()->getNode()->getParent()->getId());

    If I go to de list view, I can see that the tree is now corrupt. And if i see the table in DB I confirm that, the right and left values of 1 are wrong. I think that the problem is when the tree destiny is not empty the system don´t regenerate the values correctly.

    do you have any idea?

  12. Aleksei said

    Hello!
    I have to unset NestedSet’s variables, in order to fix moving between levels.

    class CategoryForm extends BaseCategoryForm
    {
    public function configure()
    {

    // ….

    unset(
    $this['root_id'], $this['lft'], $this['rgt'], $this['level']
    );
    }
    }

  13. [...] http://halestock.wordpress.com/2010/02/03/symfony-implementing-a-nested-set-part-one/ [...]

  14. Hardik said

    Hello halestock,

    i have one issue with your plugin, when deleting parent node it doesn’t remove all of its child.
    say for example if i remove Category 2 , it should also remove all of its child ( Category 2-A, Category 2-B, Category 2-C ).

    do you Have any solution to this ??

    Thank you,
    Hardik

  15. [...] Other: http://halestock.wordpress.com/2010/02/03/symfony-implementing-a-nested-set-part-one/ [...]

  16. Joe said

    Your code is awesome. It helps me to create an amazing tree in Symfony 1.4…. Thanks a lot and keep rocking with PHP….

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
Follow

Get every new post delivered to your Inbox.

%d bloggers like this: