Apache Zeta Components - high quality PHP components

• Tutorial
• API

eZ Components - Tree

Introduction

The Tree component enables you to create, manipulate and query tree structures. The component provides many operations on trees, as well as on the nodes in the trees. Because there are different algorithms for storing tree structures in a relational database—each with different properties—the component supports multiple back-ends. The Tree component itself comes with a memory (ezcTreeMemory) and XML (ezcTreeXml) back-end. The TreeDatabaseTiein component provides three back-ends that store the tree structure in a database table.

Aside from storing the hierarchical data itself, the component also enables you to associate data with the tree nodes. The data is stored through a data store. Depending on the back-ends, different data stores are available, as shown in the following table:

1

Available through the TreeDatabaseTiein component

2

Available through the TreePersistentObjectTiein component

Dependencies

From the table and comments above, it becomes apparent that there are a few optional dependencies. Through the TreeDatabaseTiein and TreePersistentObjectTiein components, additional functionality becomes available.

Class overview

ezcTreeMemory, ezcTreeXml

These two classes are available (without using the Tiein components) to store tree data in memory or in an XML file. There is a matching data store for each of those two classes (ezcTreeMemoryDataStore and ezcTreeXmlInternalDataStore).

ezcTreeDbMaterializedPath, ezcTreeDbNestedSet, ezcTreeDbParentChild

These three back-ends are made available through the TreeDatabaseTiein component. Each of them implements a different strategy for storing the relations between nodes. The nature of your application will determine the appropriate back-end. For more information, see the Back-ends section.

ezcTreeNode

This class represents one node of the tree. Objects of this class can be added to the tree. The object stores both the ID and data belonging to the node. Data is always fetched on demand, unless ezcTreeNodeListIterator is used with the pre-fetch option.

ezcTreeNodeListIterator

This class can be used to iterate over an ezcTreeNodeList, which is returned by many of the node fetching operations (see the ezcTree documentation for which operations are supported). It is advised to use this class to iterate through the nodes and not to simply use foreach() on a returned ezcTreeNodeList. This is because this class also supports pre-fetching associated data, which can drastically reduce the number of queries being run in case a database-based data store is used (such as ezcTreeDbExternalTableDataStore or ezcTreePersistentObjectDataStore).

Basic usage

To use a tree, you will need both a tree back-end (a class inherited from ezcTree), and a data store (implementation of the ezcTreeDataStore interface). The following example shows how to instantiate a new tree object using the ezcTreeXml back-end and the ezcTreeXmlInternalDataStore data store:

1. <?php
2. require_once 'tutorial_autoload.php';
4. $store = new ezcTreeXmlInternalDataStore();
5. $tree = new ezcTreeXml( 'files/example1.xml', $store );
7. $f = $tree->fetchNodeById( 'F' );
8. echo $f->data, "<br/>\n"; // echos Fluorine
9. ?>

Lines 4 and 5 define the data store and the tree. The parameters to ezcTree's constructor specify which file and data store to use. After opening the tree, lines 7 and 8 demonstrate how to fetch a node from the tree by using the node ID, and then access the data that belongs to the node. IDs can be either integer numbers or strings. There are a few restrictions when using strings as IDs; they must:

1. be a valid PHP array key

2. consist of XML NameChar characters only

Memory trees can never be instantiated, because there is no permanent storage available. They will always have to be created from scratch or created from another tree by using the ezcTree::copy() method.

Operations on trees

It is possible to run many operations on trees and nodes, other than fetching the nodes. The following example demonstrates two different types of operations on the tree or on nodes.

1. <?php
2. require_once 'tutorial_autoload.php';
4. $store = new ezcTreeXmlInternalDataStore();
5. $tree = new ezcTreeXml( 'files/example1.xml', $store );
7. if ( $tree->fetchNodeById( 'F' )
8.           ->isDescendantOf( $tree->fetchNodeById( 'NonMetals' ) ) )
9. {
10.     echo "Flourine is a non-metal.<br/>\n";
11. }
13. if ( $tree->isDescendantOf( 'O', 'NonMetals' ) )
14. {
15.     echo "Oxygen is a non-metal.<br/>\n";
16. }
18. $nonMetals = $tree->fetchSubtree( 'NonMetals' );
19. echo "We found {$nonMetals->size} non-metals: \n";
20. foreach ( $nonMetals->nodes as $node )
21. {
22.     echo "- {$node->id}: {$node->data} \n";
23. }
24. ?>

Lines 7 to 11 show how to tell whether a node is a descendant of another node. Most of the operations can also be done directly on the tree by using the node IDs. This is shown in lines 13 to 16. All operations are implemented on the tree level, so using the syntax in lines 13 to 16 will result in slightly higher performance. Lines 18 to 23 demonstrate another tree operation: fetching a sub-tree. All operations that can return more than one node do so as an ezcTreeNodeList.

Refer to the ezcTreeNode documentation for a full list of supported operations.

Iterating over a node list

When you iterate over a node list manually, such as in the previous examples, the associated data is fetched on demand - at the moment the ->data property of a node is requested. If you have a large node list to be returned, this can create many database queries if you are using a database-based back-end and data store. In such cases, you might want to fetch all data in one go - with one query. The ezcTreeNodeListIterator class enables you to do this:

1. <?php
2. require_once 'tutorial_autoload.php';
4. $store = new ezcTreeXmlInternalDataStore();
5. $tree = new ezcTreeXml( 'files/example1.xml', $store );
7. $noble = $tree->fetchChildren( 'NobleGasses' );
8. echo "We found {$noble->size} noble gasses: \n";
10. foreach ( new ezcTreeNodeListIterator( $tree, $noble, true ) as $nodeId => $nodeData )
11. {
12.     echo "- {$nodeId}: {$nodeData} \n";
13. }
14. ?>

In line 7 we use the ezcTree->fetchChildren() method to find all the direct children of the node with the ID "NobleGasses". Then in lines 10 to 13 we create a ezcTreeNodeListIterator over the returned ezcTreeNodeList $noble. The first parameter is the tree, the second one is the node list, and the third parameter specifies whether the data should be prefetched.

Creating and modifying a tree

If you want to create a new tree, instead of instantiating a tree you use the overloaded ezcTree::create() factory method. Once a tree and associated store are created you can proceed to fill the tree with nodes. The example below demonstrates this (and creates the XML file that is used in the other examples in this tutorial):

1. <?php
2. require_once 'tutorial_autoload.php';
4. $store = new ezcTreeXmlInternalDataStore();
5. $tree = ezcTreeXml::create( 'files/example1.xml', $store );
7. $rootNode = $tree->createNode( 'Elements', 'Elements' );
8. $tree->setRootNode( $rootNode );
10. $nonMetal = $tree->createNode( 'NonMetals', 'Non-Metals' );
11. $rootNode->addChild( $nonMetal );
12. $nobleGasses = $tree->createNode( 'NobleGasses', 'Noble Gasses' );
13. $rootNode->addChild( $nobleGasses );
15. $nonMetal->addChild( $tree->createNode( 'H',  'Hydrogen' ) );
16. $nonMetal->addChild( $tree->createNode( 'C',  'Carbon' ) );
17. $nonMetal->addChild( $tree->createNode( 'N',  'Nitrogen' ) );
18. $nonMetal->addChild( $tree->createNode( 'O',  'Oxygen' ) );
19. $nonMetal->addChild( $tree->createNode( 'P',  'Phosphorus' ) );
20. $nonMetal->addChild( $tree->createNode( 'S',  'Sulfur' ) );
21. $nonMetal->addChild( $tree->createNode( 'Se', 'Selenium' ) );
23. $nobleGasses->addChild( $tree->createNode( 'F',  'Fluorine' ) );
24. $nobleGasses->addChild( $tree->createNode( 'Cl', 'Chlorine' ) );
25. $nobleGasses->addChild( $tree->createNode( 'Br', 'Bromine' ) );
26. $nobleGasses->addChild( $tree->createNode( 'I',  'Iodine' ) );
27. ?>

In line 5 we create a new tree by using the ezcTreeXml::create() factory method. The name of the file is the first argument and the data store is the second argument. This will create a completely empty tree without nodes or even a root node. In lines 7 and 8 we then create a new node with the ezcTree->createNode() method, which accepts the node ID and node data value as arguments. The ezcTreeDbExternalTableDataStore data store also supports compound data values, as is listed in the documentation for ezcTreeDbExternalTableDataStore->__construct(). Lines 10 to 13 proceed to add two new nodes to the $rootNode and lines 15-26 add further nodes to the $nonMetal and $nobleGasses nodes.

Auto-generated IDs

The Tree component also supports auto-generated IDs for tree nodes. In order to let the component generate IDs for you, you need to set the Tree property "autoId" to "true". In the example below we create another tree structure, but let the Tree component generate the IDs automatically:

1. <?php
2. require_once 'tutorial_autoload.php';
4. $store = new ezcTreeXmlInternalDataStore();
5. $tree = ezcTreeXml::create( 'files/royals.xml', $store );
6. $tree->autoId = true;
8. $rootNode = $tree->createNode( null, 'Beatrix' );
9. $tree->setRootNode( $rootNode );
11. $willem = $tree->createNode( null, 'Willem-Alexander' );
12. $rootNode->addChild( $willem );
13. $friso = $tree->createNode( null, 'Friso' );
14. $rootNode->addChild( $friso );
16. echo $friso->id, "\n";
18. $willem->addChild( $tree->createNode( null, 'Catharina' ) );
19. $willem->addChild( $tree->createNode( null, 'Alexia' ) );
20. $willem->addChild( $tree->createNode( null, 'Ariane' ) );
22. $friso->addChild( $tree->createNode( null, 'Luana' ) );
23. $friso->addChild( $tree->createNode( null, 'Zaria' ) );
24. ?>

The main change compared to the previous example is the setting of autoId to true in line 6. When autoId is set, the ID argument to ezcTree::createNode() can be null. In that case an ID is automatically generated.

This property must be set immediately after instantiating the tree, unless an already existing tree is opened through the ezcTreeXml class. For database backends, there are a few extra requirements for the schema. The "id" field should be defined as an auto-increment integer field, or an integer field linked with a sequence.

Back-ends

Non-database back-ends

The Tree component comes with two generic back-ends - one that stores the tree structure in an XML file, and another one that only keeps a tree structure in memory. The XML back-end uses PHP's DOM functionality to parse the tree and thus the entire tree structure is loaded into memory when an ezcTreeXml object is instantiated.

The ezcTreeMemory back-end has to be created from scratch when it used. However, it is also possible to copy an ezcTreeXml-based tree to a memory-based one. The example below demonstrates this:

1. <?php
2. require_once 'tutorial_autoload.php';
4. $store = new ezcTreeXmlInternalDataStore();
5. $tree = new ezcTreeXml( 'files/example1.xml', $store );
7. $memTree = ezcTreeMemory::create( new ezcTreeMemoryDataStore() );
8. ezcTree::copy( $tree, $memTree );
10. echo $memTree->getChildCountRecursive( 'Elements' ), "\n";
11. ?>

Operations on trees based on ezcTreeMemory are of course faster than operations on trees based on ezcTreeDb or ezcTreeXml.

Database-based back-ends

By installing the TreeDatabaseTiein and TreePersistentObjectTiein components, a few more back-ends and data stores are available. There are three additional back-ends:

1. ezcTreeDbParentChild - Uses the ID of the parent to keep track of the structure only.

2. ezcTreeDbNestedSet - Uses left/right values in addition to the parent ID that the ezcTreeDbParentChild back-end uses to keep track of the tree structure.

3. ezcTreeDbMaterializedPath - Uses /1/2/4/6/19/24 style paths to store the tree structure.

Each of those three back-ends have different performance-related properties depending on which operation is run. The following table summarizes some of the properties of each algorithm:

Data stores

The database back-ends that the TreeDatabaseTiein component provides also support two different data stores. One of them, ezcTreeDbExternalTableDataStore, comes with the TreeDatabaseTiein component. Another one, ezcTreePersistentObjectDataStore, is provided through the TreePersistentObjectTiein component.

Database table

ezcTreeDbExternalTableDataStore can be used in two different modes. In the first you specify a database field that is matched against the node's ID, and another field that is used for the "data" property belonging to a node. The next example illustrates this:

1. <?php
2. require_once 'tutorial_autoload.php';
4. $dbh = ezcDbFactory::create( 'sqlite://:memory:' );
5. $dbh->exec( <<<ENDSQL
6.     CREATE TABLE nested_set (
7.         'id' varchar(255) NOT NULL,
8.         'parent_id' varchar(255),
9.         'lft' integer NOT NULL,
10.         'rgt' integer NOT NULL
11.     );
12.     CREATE UNIQUE INDEX 'nested_set_pri' on 'nested_set' ( 'id' );
13.     CREATE INDEX 'nested_set_left' on 'nested_set' ( 'lft' );
14.     CREATE INDEX 'nested_set_right' on 'nested_set' ( 'rgt' );
16.     CREATE TABLE data (
17.         'node_id' varchar(255) NOT NULL,
18.         'data_field' varchar(255) NOT NULL
19.     );
20.     CREATE UNIQUE INDEX 'data_pri' on 'data' ( 'node_id' );
21. ENDSQL
22. );
24. $store = new ezcTreeDbExternalTableDataStore( $dbh, 'data', 'node_id', 'data_field' );
25. $tree = new ezcTreeDbNestedSet( $dbh, 'nested_set', $store );
27. $tree->setRootNode( $rootNode = $tree->createNode( 'Elements', 'Elements' ) );
28. $rootNode->addChild( $nonMetal = $tree->createNode( 'NonMetals', 'Non-Metals' ) );
29. $rootNode->addChild( $nobleGasses = $tree->createNode( 'NobleGasses', 'Noble Gasses' ) );
30. $nonMetal->addChild( $tree->createNode( 'H',  'Hydrogen' ) );
32. echo $tree->fetchNodeById( 'H' )->data, "\n";
33. ?>

In this example, lines 4 to 22 set up the database and database tables. Refer to the specific database back-end's documentation for full information on what the different tables should look like. In this case, for the data store we only create two fields: node_id and data_field. We can see this back in line 24, where we instantiate the store object. We specify the database object, the name of the data table ('data'), the field that is matched against the node ID ('node_id') and which field to use for data ('data_field'). In lines 27 to 30 we then insert some sample nodes and line 32 demonstrates the retrieval of data.

In the second mode, we do not specify a field to fetch data from:

1. <?php
2. require_once 'tutorial_autoload.php';
4. // Setup the database tables
5. $dbh = ezcDbFactory::create( 'sqlite://:memory:' );
6. $dbh->exec( <<<ENDSQL
7.     CREATE TABLE nested_set (
8.         'id' varchar(255) NOT NULL,
9.         'parent_id' varchar(255),
10.         'lft' integer NOT NULL,
11.         'rgt' integer NOT NULL
12.     );
13.     CREATE UNIQUE INDEX 'nested_set_pri' on 'nested_set' ( 'id' );
14.     CREATE INDEX 'nested_set_left' on 'nested_set' ( 'lft' );
15.     CREATE INDEX 'nested_set_right' on 'nested_set' ( 'rgt' );
17.     CREATE TABLE data (
18.         'node_id' varchar(255) NOT NULL,
19.         'melting_temp_k' float,
20.         'boiling_temp_k' float
21.     );
22.     CREATE UNIQUE INDEX 'data_pri' on 'data' ( 'node_id' );
23. ENDSQL
24. );
26. // Setup the store and tree
27. $store = new ezcTreeDbExternalTableDataStore( $dbh, 'data', 'node_id' );
28. $tree = new ezcTreeDbNestedSet( $dbh, 'nested_set', $store );
30. // Insert data
31. $tree->setRootNode( $root = $tree->createNode( 'Metals', array() ) );
32. $root->addChild( $tree->createNode( 'Fe',  array( 'melting_temp_K' => 1811, 'boiling_temp_K' => 3134 ) ) );
34. // Fetch data
35. var_dump( $tree->fetchNodeById( 'Fe' )->data );
36. ?>

Differences when compared with the previous example include the data table definition in lines 17 to 21. Instead of defining a specific data field to use, there are now multiple fields ('melting_temp_k' and 'boiling_temp_k'). The instantiation of the data store in line 27 now misses the fourth argument as well. The data that is specified when creating a node now consists of an array describing all the fields in the database table, except for the 'node_id' as that one is implicit. When fetching the data the whole table record is returned, minus the 'node_id' field.

Persistent Object

The ezcTreePersistentObjectDataStore brings multiple data fields even further and extends the Tree to use persistent objects as data for the tree nodes.

1. <?php
2. require_once 'tutorial_autoload.php';
4. // Setup the database tables
5. $dbh = ezcDbFactory::create( 'sqlite://:memory:' );
6. $dbh->exec( <<<ENDSQL
7.     CREATE TABLE nested_set (
8.         'id' varchar(255) NOT NULL,
9.         'parent_id' varchar(255),
10.         'lft' integer NOT NULL,
11.         'rgt' integer NOT NULL
12.     );
13.     CREATE UNIQUE INDEX 'nested_set_pri' on 'nested_set' ( 'id' );
14.     CREATE INDEX 'nested_set_left' on 'nested_set' ( 'lft' );
15.     CREATE INDEX 'nested_set_right' on 'nested_set' ( 'rgt' );
17.     CREATE TABLE data (
18.         'node_id' varchar(255) NOT NULL,
19.         'melting_temp_k' float,
20.         'boiling_temp_k' float
21.     );
22.     CREATE UNIQUE INDEX 'data_pri' on 'data' ( 'node_id' );
23. ENDSQL
24. );
26. // Create the example Persistent Object definition files and stub classes
27. $dbSchema = ezcDbSchema::createFromDb( $dbh );
28. $writer1 = new ezcDbSchemaPersistentWriter( true );
29. $writer2 = new ezcDbSchemaPersistentClassWriter( true );
30. $writer1->saveToFile( 'files/po_defs', $dbSchema );
31. $writer2->saveToFile( 'files/classes', $dbSchema );
32. require 'files/classes/data.php';
34. // Setup the store and tree
35. $session = new ezcPersistentSession( $dbh, new ezcPersistentCodeManager( "files/po_defs" ) );
36. $store = new ezcTreePersistentObjectDataStore( $session, 'data', 'node_id' );
37. $tree = new ezcTreeDbNestedSet( $dbh, 'nested_set', $store );
39. // Insert data
40. $metal = new data();
41. $tree->setRootNode( $root = $tree->createNode( 'Metals', $metal ) );
42. $iron = new data();
43. $iron->setState( array( 'melting_temp_k' => 1811, 'boiling_temp_k' => 3134 ) );
44. $root->addChild( $tree->createNode( 'Fe', $iron ) );
46. // Fetch data
47. $fe = $tree->fetchNodeById( 'Fe' )->data;
48. var_dump( $fe );
49. ?>

The database tables are set up just like the previous example in lines 5 to 24. Lines 26 to 32 then continue to use the DatabaseSchema component to write persistent definition files and class stubs. The store is set up in lines 35 and 36. ezcTreePersistentObjectDataStore uses ezcPersistentSession as the first argument and then the object's class and object's ID property as second and third arguments. Unlike the previous example, you should specify the class and property names of the persistent objects that you are storing - not the table name and ID field. Lines 39 to 48 then show how data is inserted into the tree, and how it is retrieved. You will most likely have to tune the classes that are generated for you in a real life situation, as the generated classes (line 29 and 31) only have private properties and the getState() and setState() methods that persistent objects are required to have. Refer to the PersistentObject documentation for more information.

Visualization

Sometimes it is useful to visualize a tree structure. The Tree component has some functionality for this in the form of different visualizers. There are currently three possibilities.

Text-based visualization

The ezcTreeVisitorPlainText class implements a visitor pattern to render a tree for the console. Both latin1 and utf-8 are supported as character sets, and the utf-8 version looks much better. The following example shows how to generated a text-based representation of the tree from the first example in this tutorial:

1. <?php
2. require_once 'tutorial_autoload.php';
4. $store = new ezcTreeXmlInternalDataStore();
5. $tree = new ezcTreeXml( 'files/example1.xml', $store );
7. $visitor = new ezcTreeVisitorPlainText( ezcTreeVisitorPlainText::SYMBOL_UTF8 );
8. $tree->accept( $visitor );
9. echo (string) $visitor; // print the plot
10. ?>

The output is:

XHTML-based visualization

The ezcTreeVisitorXHTML class implements another visitor that renders the trees as nested XHTML lists. In the following example we render the same tree again with the default options for this visitor:

1. <?php
2. require_once 'tutorial_autoload.php';
4. $store = new ezcTreeXmlInternalDataStore();
5. $tree = new ezcTreeXml( 'files/example1.xml', $store );
7. $visitor = new ezcTreeVisitorXHTML();
8. $tree->accept( $visitor );
9. echo (string) $visitor;
10. ?>

This outputs the following XHTML:

The ezcTreeVisitorXHTML visitor allows some options that can be set through the constructor. Options include whether links should be added (addLinks), whether the root node should be shown (displayRootNode) and others. The options are documented with the ezcTreeVisitorXHTMLOptions class.

GraphViz-based visualization

In case you are not on the console, it is also possible to render the tree as a GraphViz .dot file that can then be used to generate an image, such as a PNG image. The next example shows the use of the ezcTreeVisitorGraphViz class:

1. <?php
2. require_once 'tutorial_autoload.php';
4. $store = new ezcTreeXmlInternalDataStore();
5. $tree = new ezcTreeXml( 'files/example1.xml', $store );
7. $visitor = new ezcTreeVisitorGraphViz;
8. $tree->accept( $visitor );
9. file_put_contents( 'files/graphviz.dot', (string) $visitor );
10. ?>

The generated .dot file can be converted to an image by running the following command:

The result of this is as follows (scaled):

YUI based visualization

Aside from console and graphical output, there is also a visualizer that renders the tree in a YUI compatible XHTML output. This can be used to automatically populate a YUI style menu. The code is pretty much the same, except for the addition of the xmlId argument to the constructor of ezcTreeVisitorYUI.

1. <?php
2. require_once 'tutorial_autoload.php';
4. $store = new ezcTreeXmlInternalDataStore();
5. $tree = new ezcTreeXml( 'files/example1.xml', $store );
7. $visitor = new ezcTreeVisitorYUI( 'menu' );
8. $tree->accept( $visitor );
9. echo (string) $visitor;
10. ?>

However, in order to actually render the menu, you need to have some specific JavaScript in the head element of your HTML code. First of all, you need to include the YUI code:

Then, you need the following code to turn the generated menu into a YUI menu (the {literal} opening and closing tag is required if you use the Template component):

The full (but minimal) code looks then like:

1. <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
2. <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
3. <head>
4.     <link rel="stylesheet" type="text/css" href="http://yui.yahooapis.com/2.3.1/build/menu/assets/skins/sam/menu.css"/>
6.     <script type="text/javascript" src="http://yui.yahooapis.com/2.3.1/build/yahoo-dom-event/yahoo-dom-event.js"></script>
7.     <script type="text/javascript" src="http://yui.yahooapis.com/2.3.1/build/container/container_core-min.js"></script>
8.     <script type="text/javascript" src="http://yui.yahooapis.com/2.3.1/build/menu/menu-min.js"></script>
9.     <script type="text/javascript">
10.     YAHOO.util.Event.onContentReady('menu', function () {
11.         var oMenu = new YAHOO.widget.MenuBar("menu", { autosubmenudisplay: true, showdelay: 200 });
13.         oMenu.render();
14.     });
15.     </script>
16. </head>
17. <body  class="yui-skin-sam">
18. <?php
19. require_once 'tutorial_autoload.php';
21. $store = new ezcTreeXmlInternalDataStore();
22. $tree = new ezcTreeXml( 'files/example1.xml', $store );
24. $visitor = new ezcTreeVisitorYUI( 'menu' );
25. $tree->accept( $visitor );
26. echo (string) $visitor;
27. ?>
28. </body>
29. </html>

The result of this is as follows (scaled):

The ezcTreeVisitorYUI visitor allows some options that can be set through the constructor. The options are documented with the ezcTreeVisitorYUIOptions class.