Category tree with nested sets and Extbase (2)

This article describes an implementation of trees using nested sets. The goal of the implementation was providing a generic category tree for TYPO3 being compatible Extbase.


The difficulties of implementing a tree using nested sets is the fact that we have two requirements mixed into the same application. Our first requirement is a tree that can be handled like any tree: Nodes should be inserted, removed, moved... Our second requirement is being compatible with relational database technology and hence storing the tree as nested sets in a relation without demanding joins and recursive queries.

A first implementation of the tree which I came up with half a year ago did not manage to separate those concerns. There had been too much functionality in a tree class that did not belong there. So what I present here is a draft of a second version that seems to work quite well so far. Feel free to give me some feedback if you think, things could be improved.

Persistence layer

Extbase ships with its own ORM. The programmer uses repositories to store data to database and retrieve data from it. Although Extbase can handle 1:M and N:M relations directly, there is no way of handling recursive object relations as we have it within our tree with any other way than foreign keys. As we wanted to avoid recursive calls to the database we soon recognized that using default repositories is not the way to go.

So here is our current persistence layer: A node repository can handle selects, updates, deletes and insertions of nodes into node table. Nothing more.

We have two classes for handling the tree as a whole: A tree builder that can build up a tree from node objects and a nested set tree storage that does a traversal on the tree, marks our nodes with nested sets numbering and uses node repository again to store the nodes into the database. Take a look at the class diagram below to get an impression of how this works:

Class diagram for persistence layer.

So what is the API for using nested sets tree persistence:

$treeBuilder = new Tx_PtExtbase_Tree_TreeBuilder($nodeRepository);
$tree = $treeBuilder->buildTreeForNamespace('tree_namespace');

// some operations on tree

$nestedSetTreeStorage = new Tx_PtExtbase_Tree_NestedSetTreeStorage($nodeRepository);

So this should be quite simple - hm? We can move on to our tree API.

Tree API

As I mentioned above, handling the tree should not worry the programmer just because it is a nested sets implementation of a tree.

Here is what we can do with a tree using its API:

// Add a new node
$newNode = new Tx_PtExtbase_Tree_Node($nodeLabel);
$tree->insertNode($newNode, $parentNode);

// Add a node before another node
$newNode = new Tx_PtExtbase_Tree_Node($nodeLabel);
$tree->insertNode($newNode, $nodeToInsertBefore);
$tree->moveNodeBeforeNode($newNode, $nodeToInsertBefore);

// Add a node after another node
$newNode = new Tx_PtExtbase_Tree_Node($nodeLabel);
$tree->insertNode($newNode, $nodeToInsertAfter);
$tree->moveNodeAfterNode($newNode, $nodeToInsertAfter);

// Remove a node

// Move a node within tree
$tree->moveNode($nodeToBeMoved, $targetNode);

// Move a node before another node
$tree->moveNodeBeforeNode($nodeToBeMoved, $targetNode);

// Move a node after another node
$tree->moveNodeAfterNode($nodeToBeMoved, $targetNode);

Tree traversal algorithms

As you might well know, there are two standard algorithms for tree traversal: Depth-First Traversal and Breadth-First Traversal. Depth-first descends all the way from the root  to a leaf before it climbs the tree again, after each leaf has been visited. Breadth-first visits all children of a node before it descends and visits the next level of a tree.

For nested sets numbering of our tree, we need depth-first. But there is a bunch of other applications where traversing a tree is necessary. So we implemented a generic traversal class called TreeWalker implementing kind of a strategy pattern. The concrete strategy (what should be done when a node is visited for the first / last time) can be put into the algorithm and so we can have several TreeWalker classes, each one implementing another operation on the tree.

At the moment, there is a TreeWalker for nested sets numbering, one for exporting the tree into an array and one for exporting the tree into JSON. Here is the class diagram for TreeWalker functionality:

Here are some examples of API calls for tree traversal:

// Exporting tree to JSON
$jsonTreeWriter = Tx_PtExtbase_Tree_JsonTreeWriter::getInstance();
$treeAsJson = $jsonTreeWriter->writeTree($tree));

// Exporting tree as a PHP array
// This will put the tree into the following array-format:
  array (
  'uid' => int 4
  'label' => string 'root'
  'children' => 
    array (
      0 => array (
          'uid' => int 2
          'label' => string 'first child'
          'children' => array (
              0 => array (
                  'uid' => int 1
                  'label' => string 'first child of first child'
                  'children' => array()
      1 => array (
          'uid' => int 3
          'label' => string 'second child'
          'children' => array ()
$arrayTreeWriter = Tx_PtExtbase_Tree_ArrayTreeWriter::getInstance();
$treeAsArray = $arrayTreeWriter->writeTree($tree);

// Set up your own TreeWalker with your own visitors
$yourOwnVisitor = new YourOwnTreeWalkerVisitor();
$yourOwnTreeWalker = new Tx_PtExtbase_Tree_TreeWalker(array($yourOwnVisitor));

Conclusions and outlook

After getting persistence and API done, we will go one with GUI work. Our goal is to provide a TCA widget (based on Extbase and Fluid) so that you can have a new TCA type (category) and will be provided with a nice user interface in the backend.

There should also be an Ajax controller that handles all basic tree manipulation like insert, move, delete and edit.

We will also think about a practical way to let every possible object be connected to a node and hence give you the basical stuff you need for implementing arbitrary hierachical object structures based on trees.

Last but not least, there will be a tree-filter for pt_extlist and generic, category-based image collections in yag.

The usage of our generic widget will be covered in a third article on this topic (perhaps on Daniel's Blog?).

Inhalt © Michael Knoll 2009-2017  •  Powered by TYPO3  •  TypoScript Blogging by Fabrizio Branca  •  TYPO3 Photo Gallery Management by yag  •  Impressum