Navigating a node tree

A common requirement is to navigate presentation linkbase node hierarchies efficiently. This is most easily done using a function that is called recursively. The example here shows a pattern that can be reused to implement a depth first traversal of a node hierarchy. This function expects to receive an array of nodes that have an element called 'children' which contains an of further child nodes. The [node] array uses this structure.

This function will be used as a closure and uses a reference 'nodes' parameter. Passing nodes as a reference improves performance so only a reference to the nodes array is passed and the PHP engine does not need to create an in-memory copy of the nodes array.

In this illustration the function returns the total number of nodes in the nodes hierarchy and identifies the maximum depth of the tree. Neither of these are essential and are implemented only to illustrate possibilities.

$traverse = function ( &$nodes, $depth = 0 ) use( &$traverse, &$maxDepth )
{
	$totalNodes = count( $nodes );

	foreach ( $nodes as $key => $node )
	{
		// Perform node processing here.  This function
		// could be made generic by passing in a callback
		// which is called here

		if ( ! isset( $node['children'] ) || 
		     ! is_array( $node['children'] ) ||
		     count( $node['children'] ) == 0
		) continue;

		// Have children so call recursively
		$totalNodes += $traverse( $node['children'] );
	}

	return $totalNodes;
};

Here's an example of how it might be used to traverse the hierarchy nodes of each role in the presentation linkbase of a taxonomy. Again note that roles are assigned using a reference to minimize the times the PHP has to create in-memory copies of the node arrays. In this case $taxonomy is an instance of XBRL or one of the descendants.

$roles =& $taxonomy->getPresentationRoleRefs();

$maxDepth = 0;
$totalNodes = 0;
foreach ( $roles as $uri => &$role )
{
	$totalNodes += $traverse( $role['hierarchy'] );
}