Manage trees, the simple way

Sep 30, 2011 − Have to manage a tree structure for, let's say a menu? Still want to be able to understand the tree hierarchy just by looking the flat entries? Don't want to use nested sets or closure table because it's too complicated and error prone? Then stay tuned, it may interest you.

Have to manage a tree structure for, let's say a menu? Still want to be able to understand the tree hierarchy just by looking the flat entries?
Don't want to use nested sets or closure table because it's too complicated and error prone?

Introducing materialized-paths for php.

This php 5.4+ library consists of only one trait that provides a set of useful methods to handle tree manipulation.

It's database agnostic in the sense it's not tied to any ORM or persistence backend. Plain old php objects, baby!

API

Its main API consists in tree traversing and node positioning.

The NodeInterface is self explanatory
but we'll focus on its main methods:

• NodeInterface::buildTree:

  is responsible for creating an object hierarchy, a tree of NodeInterface objects from a flat resultSet

• NodeInterface::setChildOf:

  is responsible for the nodes manipulation. it will automate:

  • cascading modifications to the parent and children in the tree
  • recursively update the node's path representation

• NodeInterface::getParent:

  Returns -guess what ?- the next ancestor.

• NodeInterface::getNodeChildren:

  Returns -guess what ?- the direct children, a DoctrineCommonCollectionsCollection object.
  Useless dependency, you may say. And you may be right.

How to use it

Put simply, the workflow consists of:

1. Get a flat collection of objects that implement NodeInterface.
2. Build a tree from this collection.
3. Use this tree.

In this example, we'll work with a MenuItem class, using Doctrine ORM to get the collection of objects.

Step One, get the flat result

Define a class that implements NodeInterface. Let's assume it is managed by Doctrine.

<?php

namespace Entity;


use KnpComponentTreeMaterializedPathNode;
use KnpComponentTreeMaterializedPathNodeInterface;

use DoctrineCommonCollectionsArrayCollection;
use DoctrineORMMapping as ORM;


/**
* @ORMEntity
* @ORMTable(name="menu")
* @ORMEntity(repositoryClass="EntityMenuItemRepository")
*/
class MenuItem implements NodeInterface
{
    const PATH_SEPARATOR = '/';

    // traits baby!
    // if your php version doesn't support traits, copy paste the methods of KnpComponentTreeMaterializedPathNode
    use Node {

    }

    /**
     * @ORMId
     * @ORMColumn(type="integer")
     * @ORMGeneratedValue(strategy="AUTO")
     */
    protected $id;

    /**
     * @ORMColumn(type="string", length=255)
     */
    protected $name;

    /**
     * @param Collection the children in the tree
     */
    private $children;

    /**
     * @param NodeInterface the parent in the tree
     */
    private $parent;

    /**
     * @ORMColumn(type="string", length=255, nullable=true)
     */
    private $path;

    /**
     * @ORMColumn(type="integer", nullable=true)
     */
    private $sort;

    public function __construct()
    {
        $this->children = new ArrayCollection;
    }

    public function __toString()
    {
        return (string) $this->name;
    }

    /**
     * @return string
     */
    public function getId()
    {
        return $this->id;
    }
}

Optional Step, fill the flat

Something makes me say it could be useful.
Find a way to fill in some data.

My psql prompt outputs me something like that:

 id | locale_id |   name    |    path    | sort |
----+-----------+-----------+------------+------+
  1 | fr        | fr        | /fr        |      |
  2 |           | villes    | /fr/2      |      |
  4 |           | subNantes | /fr/2/3/4  |      |
  7 | en        | en        | /en        |      |
  8 |           | villes    | /en/8      |      |
  9 |           | Nantes    | /en/8/9    |      |
 10 |           | subNantes | /en/8/9/10 |      |
 11 |           | Lorient   | /en/8/11   |      |
 12 |           | Rouen     | /en/8/12   |      |
  6 |           | Rouen     | /fr/2/6    |    1 |
  3 |           | Nantes    | /fr/2/3    |    0 |
  5 |           | Lorient   | /fr/2/5    |    2 |

Step Two, build the tree

This essential step transforms a flat resultSet into a nice (yellow lemon?) tree.

<?php

$repository = $entityManager->getRepository('EntityMenuItem');
$menu = $repository->find($id);

// get some data
$qb = $this->createQueryBuilder('m')
    ->andWhere('m.path LIKE :path')
    ->andWhere('m.id != :id')
    ->addOrderBy('m.path', 'ASC')
    ->addOrderBy('m.sort', 'ASC')
    ->setParameter('path', $menu->getPath().'%')
    ->setParameter('id', $menu->getId())
;
// here is the data
$results = $qb->getQuery()->execute();

$menu->buildTree(new ArrayObject($results));

// ...

Voila! The menu object is now correctly hydrated, it has a parent, and a children collection.

Step Three, use the tree

<?php

//...

$parent = $repository->find($parentId);

// set the $menu node as a child of the $parent node
$menu->setChildOf($parent);

$em->persist($menu);
$em->flush();

//traverse the tree
$child = $menu->getChildren()->get(0)->getChildren()->get(1);
$child = $menu->getChildren()[0]->getChildren()[1]; // 5.4 baby

$root = $child->getRoot();
$childParent = $child->getParent();

$childParent->isChildOf($root);
$childParent->isParentOf($root);

// ...

If you want more examples or don't like Doctrine (nobody's perfect), you can check the tests, that uses the tree without being tied to a database.