Simple Nested Sets in Doctrine 2

Unlike Doctrine 1 with it’s NestedSet behaviour, there is no nested set functionality in the core of Doctrine 2. There are a few extensions available that offer nested set support:

I tried all of these extensions, but none of them felt simple or lightweight enough for my application. What I wanted to do was have a Category entity which could have a tree of sub-categories, e.g:

Food
    Pizza
        Margherita
        La Reine
        Giardiniera
    Chocolate
        Dark
        Milk
        White

The simplest way I found of doing this without using any extensions was to make use of SPL‘s RecursiveIterator and RecursiveIteratorIterator classes. Here’s the final code, to output a drop-down menu like this one:

/** @var $em \Doctrine\ORM\EntityManager */
$root_categories = $em->getRepository('Entity\Category')->findBy(array('parent_category' => null));

$collection = new Doctrine\Common\Collections\ArrayCollection($root_categories);
$category_iterator = new Entity\RecursiveCategoryIterator($collection);
$recursive_iterator = new RecursiveIteratorIterator($category_iterator, RecursiveIteratorIterator::SELF_FIRST);

foreach ($recursive_iterator as $index => $child_category)
{
    echo '<option value="' . $child_category->getId() . '">' . str_repeat('&nbsp;&nbsp;', $recursive_iterator->getDepth()) . $child_category->getTitle() . '</option>';
}

Here’s how it’s done. Start out with an entity class that looks something like this:

namespace Entity;

/**
 * @Entity
 * @Table(name="category")
 */
class Category
{

    /**
     * @Id
     * @Column(type="integer", nullable=false)
     * @GeneratedValue(strategy="IDENTITY")
     */
    protected $id;

    /**
     * @Column(type="string", length=130, nullable=false)
     */
    protected $title;

    /**
     * @ManyToOne(targetEntity="Category", inversedBy="child_categories")
     * @JoinColumn(name="parent_category_id", referencedColumnName="id")
     */
    protected $parent_category;

    /**
     * @OneToMany(targetEntity="Category", mappedBy="parent_category")
     */
    protected $child_categories;

    public function __construct()
    {
        $this->child_categories = new \Doctrine\Common\Collections\ArrayCollection;
    }

    // Getters and setters ...

}

Next, the RecursiveCategoryIterator class. I have written this to interface with Doctrine’s Collection object, but it could easily be re-written to work with native PHP arrays (see this note in the PHP manual for an example of a RecursiveIterator class that uses native arrays).

namespace Entity;

use Doctrine\Common\Collections\Collection;

class RecursiveCategoryIterator implements \RecursiveIterator
{

    private $_data;

    public function __construct(Collection $data)
    {
        $this->_data = $data;
    }

    public function hasChildren()
    {
        return ( ! $this->_data->current()->getChildCategories()->isEmpty());
    }

    public function getChildren()
    {
        return new RecursiveCategoryIterator($this->_data->current()->getChildCategories());
    }

    public function current()
    {
        return $this->_data->current();
    }

    public function next()
    {
        $this->_data->next();
    }

    public function key()
    {
        return $this->_data->key();
    }

    public function valid()
    {
        return $this->_data->current() instanceof \Entity\Category;
    }

    public function rewind()
    {
        $this->_data->first();
    }

}

That’s everything! A very simple Nested Set behaviour in Doctrine 2 using only a simple RecursiveIterator class – no complicated extensions.

Edit: As Hans has pointed out, while this approach does allow us to model hierarchies, it is not truly a nested set model as it does not number each node to allow for tree traversal. This model is probably closer to an adjacency list.

Did you find this post useful?

  • Albert R. Carnier Guedes

    I like very much this solution, but there are a problem : when i define a defined parent category as a daughter of a daughter of the same category, the iterator does not work. There are a solution to solve using the same class ?

  • ???? ????????

    I’m write my DocumentType entity like in this example

    * @ORMEntity

    * @ORMTable(name=”document_types”)

    * @property int $parent

    * @property string $title

    * @property int $id

    *

    */

    class DocumentType {

    /**

    * @ORMId

    * @ORMColumn(type=”integer”, nullable=false)

    * @ORMGeneratedValue(strategy=”IDENTITY”)

    */

    protected $id;

    /**

    * @ORMColumn(type=”string”, length=255, nullable=false)

    */

    protected $title;

    /**

    * @ORMManyToOne(targetEntity=”DocumentType”, inversedBy=”child_types”)

    * @ORMJoinColumn(name=”parent”, referencedColumnName=”id”)

    */

    protected $parent;

    /**

    * @ORMOneToMany(targetEntity=”DocumentType”, mappedBy=”parent”)

    */

    protected $child_types;

    public function __construct()

    {

    $this->child_types = new DoctrineCommonCollectionsArrayCollection;

    }

    }

    It’s work when i’m get records from db. But when i’m need to add, i’m have this error

    Found entity of type on association SEDEntityDocumentType#parent, but expecting SEDEntityDocumentType

    Why?

    • ???? ????????

      Sorry, i’m realize, that i’m need object DocumentType in parent field, not just string or int. It’s work.

  • naitmeir

    the output before the foreach prints object(RecursiveIteratorIterator)#417 (0) and doesn’t gets into the loop. And of course the table has some sample data entered. Someone knows why?

  • Carlos

    Thanks for that good solution. For a select box, this works fine.

    I try to store the results in an multidimensional array. Is there any possibility of getting the parent_id like: $child_category->getParent_id()? My idea:

    foreach ($recursive_iterator as $index => $child_category)
    {
    $categoryTreeArray[$recursive_iterator->getDepth()][$child_category->getParent_id()]=$child_category->getTitle();
    }

    • wildlyinaccurate

      Well each category has $parent_category and $child_categories associations, so you should be able to do something like $category->getParent()->getId() (assuming you have a getter method called getParent).

  • Wilmer

    I throws this error: Fatal error: Call to a member function hasField() on a non-object

  • Julien

    Same here ! I just wanted a simple nest… I meant “adjacent” lists !
    I’ll start with that !
    Thanks a lot !

  • meilon

    I like what I see and I like to implement this in my symfony2 application. could you give me a hint on how to implement this? I just started using symfony2 and I am not that good with it right now.

  • Coder

    Nice work.
    Does this generate a query per item or will it pull all the subcategories back in one hit. i.e. 3 queries for Dark, Milk, White or one one returning them all?

    • http://wildlyinaccurate.com/ Joseph

      I think it would depend on how the associations are set up. Doctrine probably doesn’t know whether an item has children without doing a query, so I would guess that you get at least one query per item.

      Obviously this approach isn’t great performance-wise. For large collections you’ll probably want to use a proper nested set extension.

  • Hans

    Actually this is not nested sets but adjacent lists! nested set and adjacent lists are two ways to store a hierarchy as a list. Maybe you’re confusing nested set and hierarchy, aren’t you?

    • http://wildlyinaccurate.com/ Joseph

      You’re right, this is not a nested set model. This is just a very simple way of iterating over adjacent lists, which is what many people use nested sets for anyway. I hope it goes without saying that you cannot have a true nested set model without ordering the nodes for tree traversal.

  • http://www.flameboy.fr Joris

    Thanks for this tutorial! I just have two questions:

    - Does the sub-categories (for example “Margherita”) can have sub-categories, which can also have a sub-categories (etc.), or is it adviced to use a depth of three nodes max?

    - Did you try to implement this model with Symfony2 forms? Is it possible?

    • http://wildlyinaccurate.com/ Joseph

      The categories can have as many levels of sub-category as you like – I don’t think RecursiveIteratorIterator has a maximum depth.

      I’m not really familiar with Symfony2 forms. What kind of implementation do you want?

      • http://www.flameboy.fr Joris

        Thanks for your reply!

        I was just curious about it because Symfony2 forms are really particular so I wonder if it is possible to implement your simple nested sets with this:
        http://symfony.com/doc/current/book/forms.html

  • Paul Fonkeng

    Hi,
    I’ll like to use the sluggable and timestampable features of Doctrine Extension. Can you help me with some info on how to get them work together, especially with annotations?

    Thanks and have a great day.
    Paul

  • http://blog.bartekszewczyk.com Bartek

    Thanks for helping with CI and doctrine!

  • Murat

    gladly following you…
    Thank you very much for this writing