Working with a tree structure - Jet\Data_Tree

Working with data organized in a tree structure is quite common in our field. However, what are such categories of e-shop, sections of intranet, sections of portal and many other things - all these are data organized in a tree. That is, having a root and then nodes (branches) under which the child nodes fall and so on. This imaginary tree needs to be traversed to find parents, descendants, node paths, or to display/dump the tree. These are frequent operations, and so Jet has a tool for this that is not only used by the platform itself, but is also well used in the application space - I use it a lot myself.

Tree Data - General

In order for data (and it doesn't matter whether it is an associated array or an object instance - both are supported) to be arranged in a tree structure, it must satisfy a few simple rules:

  • Each item (future node) must have its own unique identifier
    It doesn't matter whether it is a number or a string. What is important is uniqueness. There must not be two nodes (branches) with the same identifier.
  • Each entry must have a parent branch identifier - the parent node
    The data should be consistent. That is, if a node has a parent node identifier of, say, 432, then a node with that identifier must exist. Otherwise, a data inconsistency is identified and an exception is thrown.

    This situation can be handled by switching the tree to adoption mode, or ignoring orphans - see below. However, this should not be the standard procedure, it is normal to take care of data consistency.
  • Each item should have a text name (human-readable)
    This will be called the node label and can be worked with, for example, at the UI level.
  • Data should be sorted
    It is definitely necessary to sort the data in advance according to their priority (which can be determined by anything - for example, alphabetical order, or some index) as they will be sorted in individual branches. And for speed, it's also a good idea to sort the data by the parent identifier (this is not necessary, but certainly advisable). So the ideal data will be sorted: 1. by the parent identifier, 2. within that by the priority you specify.
  • Each node can have any additional data
    Whether it is objects or associated fields, a node can (and should) carry additional data and information with it. In practice, however, it is not recommended to have a lot of such metadata for nodes. Suppose you have an e-shop with thousands of categories, and each category has a lot of information, including long text descriptions. I don't recommend putting such data in a tree. It means a lot of memory consumption, large data transfers and so on. However, you can have the necessary meta-information in the tree - that's what the tree is for.

Creating a tree from an array

Creating a tree from an array is the most typical operation in practice. It often involves processing raw data retrieved from a database, cache, or other storage. So let's show how to do it. From the previous section, you know what the data must satisfy.

Now we'll show how to do this in practice, using an example from the "guts" of Jet, namely building MVC pages into a tree structure. Information about one page - the future node of the tree structure - has the following keys:

  • id
  • parent_id
  • name
The list of such associated fields is loaded (which we won't deal with in the example, but the data is declared for the example) and we can produce a tree: $tree_data[] = [
    'id' => 'page-1',
    'parent_id' => MVC::HOMEPAGE_ID,
    'name' => 'Page 1'
];

$tree_data[] = [
    'id' => 'page-1-1',
    'parent_id' => 'page-1',
    'name' => 'Page 1-1'
];

$tree_data[] = [
    'id' => 'page-1-2',
    'parent_id' => 'page-1',
    'name' => 'Page 1-2'
];
$tree_data[] = [
    'id' => 'page-2',
    'parent_id' => MVC::HOMEPAGE_ID,
    'name' => 'Page 2'
];

uasort( $tree_data, function( array $a, array $b ) {
    return strcmp( $a['name'], $b['name'] );
} );
    
$tree = new Data_Tree();
        
$root = $tree->getRootNode();
$root->setId( MVC::HOMEPAGE_ID );
$root->setLabel( 'Homepage' );
        
$tree->setData( $tree_data );

Please note that the root node parameters are set. The root node always exists automatically. Its identifier is an empty value by default. Thus, any node that does not have a parent identifier automatically falls under the root node. However, in this case the root node identifier is set. The label of the root node is also set.

The setData method arranges the data into a tree structure and it is possible to work with the tree - which we will show later. If the data is inconsistent, a Jet\Data_Tree_Exception is thrown.

As mentioned, the tree data must have an identifier (the 'id' field key), a parent identifier (the 'parent_id' field key), and a label (the 'name' field key). However, the names of the array keys are not fixed. These are just the default values. You can use the constructor parameters and the appropriate methods (see below) to change the names of these keys according to your needs.

Creating a tree from a list of objects

Sometimes it may be more convenient and necessary to create a tree from a list of objects. By list we mean either a simple array containing objects, or some iterator returning objects on traversal. The principle is identical at the core to working with arrays. There are, of course, a few differences:

  • Instead of the setData method, it is necessary to use the setDataSource method, which is passed a list of objects and the Data_Tree class automatically switches to the object usage mode instead of the associated array.
  • Objekty musí mít příslušné metody - gettery pro předání potřebných informací:
    • getId - returns the node identifier
    • getParentId - returns the identifier of the parent node
    • getName - returns the node label
    Methods must exist, but their name is not mandatory. The names of the required object methods can be changed using the appropriate methods (see below). Of course, this must be done before using the setDataSource method.

Inconsistent tree

As already mentioned, the tree data should be consistent, otherwise an exception is thrown when the tree is initialized. However, the world is not perfect ... It may happen that we simply need to work with inconsistent data (for example, when a node has "disappeared" from the middle of the tree, but its children still exist). The situation is solvable.

Before initializing the tree, it is necessary to switch it to adoption mode:

$tree = new Data_Tree();
$tree->setAdoptOrphans( true );

Nodes without a parent are classified under the root node in this mode. They will therefore appear in the trees at least provisionally.

The other option is to simply ignore orphans and not include them in the tree at all:

$tree = new Data_Tree();
$tree->setIgnoreOrphans( true );

What to use is up to you and your specific situation. Jet alone cannot determine which solution is correct, so it forces the choice on you.

Use of the tree

The node of the tree

The tree is made up of individual nodes - as we have already said. And it is with the nodes that we will continue to work. So let's take a look at what exactly a node is. A tree node is an instance of the class Jet\Data_Tree_Node. It carries all the necessary information about the node, and such an object is also returned by the tree when working with it - when traversing the tree, searching, and so on.

It has been said that a node is an object of class Jet\Data_Tree_Node. However, this is only partially true. Using the appropriate method of the Data_Tree class (see below), you can force the use of your own class for a tree node (before populating it with data, of course). That is, you can make your own node. The only condition is that it must inherit from the Jet\Data_Tree_Node class.

Getting a node

This is a very basic operation. Based on the unique identifier, it is easy to get the instantiation of a node wherever it is in the tree structure:

$node = $tree->getNode( 'page-1-2' );

Attention! It may happen that the node does not exist. In this case, the value returned is null and it is necessary to take this eventuality into account.

Parents, descendants and journeys

Once we have a node, we can work with it. For example, to get its parents, or conversely, its children:

$parent = $node->getParent();
foreach($node->getChildren() as $child) {
    //... ... ..
}

Or it is possible to get trips. For example, you know that a node exists, but you need to know the path to it. So you need a list of the identifiers of all its parent nodes:

$parent_ids = $tree->getPath( 'page-1-2' );

Simply walking through a tree

You can very easily go through the tree as if it were a simple list. That is, go through all nodes sequentially from the root to the last node, with the browsing fully reflecting the tree layout. There is no need to use any recursive functions to do this, but a simple loop will do:

foreach( $tree as $node ) {
    echo 'Node ID: '.$node->getId().PHP_EOL;
    echo 'Parent node ID: '.$node->getParentId().PHP_EOL;
    echo 'Label: '.$node->getLabel().PHP_EOL;
    echo 'Depth: '.$node->getDepth().PHP_EOL;
}

... and so on

Now you already know the principle how to work with Jet\Data_Tree. Next, please take a look at the list of methods of the Jet\Data_Tree class and also the list of methods of the Jet\Data_Tree_Node class. There you will get more information and a complete overview of the Data_Tree options.

Method Overview

Method Meaning of
public __construct(
string $id_key='id',
string $parent_id_key='parent_id'
)		 The constructor allows you to set the most basic parameters directly, namely the name of the key of the array representing the identifier and the name of the key of the array representing the parent identifier.
public getNodesClassName(
) : string		 Returns the name of the class that will represent the tree node.
public setNodesClassName(
string $nodes_class_name
) : void		 Sets the name of the class that will represent the tree node.

It must be set before the tree is filled with data.

The class must inherit from Jet\Data_Tree_Node.
public getAdoptOrphans(
) : bool		 Indicates whether orphan adoption mode is enabled.

It must be set before the tree is populated with data.

Default state is: off
public setAdoptOrphans(
bool $adopt_orphans
) : void		 Turns on/off the orphan adoption mode.
public getIgnoreOrphans(
) : bool		 Indicates whether orphan ignoring mode is enabled.

It must be set before the tree is filled with data.

Default state is: off
public setIgnoreOrphans(
bool $ignore_orphans
) : void		 Enables/disables orphan ignoring mode.

It must be set before the tree is filled with data.
public getIdKey(
) : string		 Returns the key name of the array representing the node identifier.

Default value is: 'id'
public setIdKey(
string $id_key
) : void		 Sets the key name of the array representing the node identifier.

It must be set before the tree is populated with data.
public getParentIdKey(
) : string		 Returns the key name of the array representing the parent node identifier.

Default value is: 'parent_id'
public setParentIdKey(
string $parent_id_key
) : void		 Sets the key name of the array representing the parent node identifier.

It must be set before the tree is populated with data.
public getLabelKey(
) : string		 Returns the name of the key of the array representing the node's label.

Default value is: 'name'
public setLabelKey(
string $label_key
) : void		 Sets the key name of the array representing the node label.

It must be set before the tree is populated with data.
public getIdGetterMethodName(
) : string		 Returns the name of the method returning the node identifier in the object handling mode.

Default value: 'getId'
public setIdGetterMethodName(
string $id_getter_method_name
) : void		 Sets the name of the method that returns the node identifier in the object handling mode.

It must be set before the tree is filled with data.
public getParentIdGetterMethodName(
) : string		 Vthe name of the method that returns the identifier of the parent node in the object handling mode.

Default value: 'getParentId'
public setParentIdGetterMethodName(
string $parent_id_getter_method_name
) : void		 Sets the name of the method that returns the identifier of the parent node in the object handling mode.

It must be set before the tree is filled with data.
public getLabelGetterMethodName(
) : string		 Returns the name of the method returning the node label in the object handling mode.

Default value: 'getName'
public setLabelGetterMethodName(
string $label_getter_method_name
) : void		 Sets the name of the method returning the node label in the object handling mode.

It must be set before the tree is filled with data.
public setData(
array $data
) : void		 Populates and initializes the tree with the data being made up of associated arrays.
public setDataSource(
Iterator|array $data
) : void		 Populates and initializes the tree with the fact that the data is made up of objects and thus automatically switches on the mode of working with objects.
public getRootNode(
) : Data_Tree_Node|null		 Returns a root node that can be further configured.
public setRootNode(
Data_Tree_Node $node
) : void		 Imposes the root node from the outside.

It must be set before the tree is filled with data.
public appendNode(
array|object $item_data
) : Data_Tree_Node|null		 Adds a knot. The node being added is in the form of raw data. That is, an associated array or object (in object mode).

Returns an instance of the created node.

Used after the tree is filled with data.
public getNode(
string $node_id
) : Data_Tree_Node|null		 Returns an instance of the node represented by the given identifier, regardless of the node's location in the storm structure. Returns null if the node does not exist.
public getNodes(
) : Data_Tree_Node[]		 Returns instances of all nodes in the tree.
public getNodesIds(
) : array		 Returns the identifiers of all nodes in the tree.
public getNodeExists(
string $node_id
) : bool		 Indicates whether a node with the given identifier exists in the tree.
public getPath(
string $target_node_id
) : array|bool		 Searches for a path to a given node and returns it as an array of all parent node identifiers, including the search node, ordered chronologically from the root to the search node.
public toJSON(
) : string		 Exports the tree to JSON format.
public jsonSerialize(
) : array		 Allows you to pass a tree instance to the json_encode function.
public toArray(
) : array		 The storm is exported to the field, however, with respect to the plunge and tree arrangement. Thus, it is not a simple backward export of nodes to an array, but the resulting array represents a tree structure.
public getChildrenKey(
) : string		 For the purpose of exports (toJSON, toJSON and toArray)

Returns what key represents the children of the node in the exported data.

Default value: 'children'
public setChildrenKey(
string $children_key
) : void		 Pro účel exportů (toJSON, toJSON a toArray)

Nastavuje jaký klíč reprezentuje potomky uzlu v exportovaných datech.
public getDepthKey(
) : string		 For the purpose of exports (toJSON, toJSON and toArray)

Returns what key represents the depth of the node in the exported data.

Default value: 'depth'
public setDepthKey(
string $depth_key
) : void		 For the purpose of exports (toJSON, toJSON and toArray)

Sets which key represents the node depth in the exported data.
public rewind(
) : void		 See PHP Iterator
public current(
) : Data_Tree_Node		 See PHP Iterator
public key(
) : string		 See PHP Iterator
public next(
) : void		 See PHP Iterator
public valid(
) : bool		 See PHP Iterator
public count(
) : int		 See PHP Countable
Previous chapter
Working with text - Jet\Data_Text
Next chapter
Jet\Data_Tree_Node
GitHub