Iterating Recursive Structures

How do we iterate an array with one or more nested subarrays, or more generally, how do we iterate a container that contains subcontainers? If we call foreach on this array

<?php
$arr = array(0,
        1 => array(10, 20, 30),
        2,
        3 => array(1, 2, 3)
        );

foreach($arr as $key => $value) {

    echo "$key => $value \n";
}

we get an error when $value equals the first subarray. To avoid calling is_array($value) or writing a recursive function in place of foreach, we can use the RecursiveIterator interface.

Some class structures are tree-like and represent a containment hierarchy. Such composite structures are recursively traversable. RecursiveIterator is the iterator interface that tells if it is. If the class implements the RecursiveIterator interface, or if it has a getIterator() method that returns a RecursiveIterator, then it is recursively traversable; that is, it is a container with nested subconainters.

RecursiveIteratorIterator is the concrete class that uses the RecursiveIterator interface to iterate all the data.

RecursiveIterator

The first interface used to solve the problem of iterating any array with at least one subarray, or for that matter any tree–like container, is RecursiveIterator. It extends Iterator adding the mtehods hasChildren() and getChildren(). hasChildren)= returns true if the current element can be iterated, and getChildren() returns that iterator, which must at least be of type RecursiveIterator.

Here is a implementation of RecursiveIterator that extends MyArrayIterator implemented previously.

<?php
class MyArrayIterator implements Iterator {

    array private $a;

    public function __construct(&$a)
    {
       $this->a = $a;
    }

    public function valid()
    {
       return current($this->a) !== false;
    }

    public function next()
    {
       next($this->a);
       return;
    }

    public function current()
    {
       return current($this->a);
    }

    public function rewind()
    {
       reset($this->a);
    }

    public function key()
    {
       return key($this->a);
    }
}

class MyRecursiveIterator extends MyArrayIterator implements RecursiveIterator {

    public function __construct(array &$a)
    {
        parent::__construct($a);
    }

    // Returns true if an iterator can be created/returned for the current entry.
    public function hasChildren()
    {
        $current = parent::current();
        return is_array($current);
    }

    // Note: getChildren() must return a RecursiveIterator or class derived from RecursiveIterator for the current entry.
    public function getChildren()
    {
        $subarray = parent::current();
        return new MyRecursiveIterator($subarray);
    }
}

Note: To use MyRecursiveIterator directly you use a recursive function. Later we will show how RecursiverIteratorIterator provides a way to avoid writing such a recursive function:

<?php
function recursive_iterate(\RecursiveIterator $it)
{
  while ($it->valid()) { // Still more to do?

    // if there is a subarray or subcontainer that needs to be iterated, we call getChildren() and recurse...
    if ($it->hasChildren()) {

       echo $it->key(). " => (" ;

       recursive_iterate($it->getChildren()); // recurse. Note: getChildren() must return \RecursiveIterator.

       echo "),\n";

    } else {  // the current element is not a nested container, so display its elements

      // otherwise, print the current key and value.
      echo $it->key() . " => " . $it->current() . ", ";
    }

    $it->next();
  }
}

Below we create a array with some subarrays and use our new code:

<?php
$a2 = array(0, 1,
            2 => array(10, 20, 30),
            3, 4,
            5 => array(1, 2, 3));

echo "\n=============\n";

$mri = new MyRecursiveIterator($a2);

recursive_iterate($mri);

// An array containing four elements, the first three are nested subarrays.
$arr = [
     [["sitepoint", "phpmaster"]],      // first nested array
     ["buildmobile", "rubysource"],   // second nested array
     ["designfestival", "cloudspring"], // third nested array
     "not a subarray"                     // one-dimensional array of one element
];

$mri = new MyRecursiveIterator($a2);

echo "\n\n";

recursive_iterate($mri);

which outputs:

0 => 0, 1 => 1, 2 => (0 => 10, 1 => 20, 2 => 30, ),
3 => 3, 4 => 4, 5 => (0 => 1, 1 => 2, 2 => 3, ),


0 => (0 => (0 => sitepoint1, 1 => phpmaster1, ),
1 => (0 => siteporint2, 1 => phpmaster2, ),
),
1 => (0 => buildmobile, 1 => rubysource, ),
2 => (0 => designfestival, 1 => cloudspring, ),
3 => not a subarray,

RecursiveIteratorIterator

RecursiveIterator is the interface that unifies recursion. PHP provides the concrete RecursiveIteratorIterator class that uses RecursiveIterator internally to do the actual recursion for us when foreach is called. This eliminates the need of writing our own recursive function that uses RecursiveIterator.

RecursiveIteratorIterator allows you to iterate a multi–dimenstional array or tree structure with foreach. It “flattens” a RecursiveIterator. Its constructor takes a RecursiveIterator instance (the constructor actually takes an Iterator or IteratorAggregate, but it is intended to be used with a RecursiveIterator).

PHP 5 in Practice, by White and Einsenhamer explain that:

RecursiveIteratorIterator implements OuterIterator and is a wrapper that will activate Iterators that implement the RecursiveIterator interface.

This example shows how RecursiveIteratorIterator eliminates the need for a custom recursive function

<?php
$it = new RecursiveIteratorIterator(new MyRecusvieIterator($a2)) {

foreach($it as $value)

      // print the value.
      echo $it->current() . ", ";
}

If we change foreach to return both the current key and value

<?php
$it = new RecursiveIteratorIterator(new MyRecusvieIterator($a2)) {
foreach($it as $value)

      // print the curren tkey and value.
     echo $it->key() . " => " . $it->current() . ", ";
}

the output is

0 => 0, 1 => 1, 0 => 10, 1 => 20, 2 => 30, 3 => 3, 4 => 4, 0 => 1, 1 => 2, 2 => 3,

instead of

0 => 0, 1 => 1, 2 => (0 => 10, 1 => 20, 2 => 30, ), 3 => 3, 4 => 4, 5 => (0 => 1, 1 => 2, 2 => 3, ),

The keys 2 and 5 in the outer array were not returned because the default mode of traversal is RecursiveIteratorIterator::LEAVES_ONLY. If we passed RecursiveIteratorIterator::SELF_FIRST as a 2nd parameter to the constructor, this would return the key of 2, when it was first encountered, and its enitre associated arrays as the value. Then, the next time through the loop, the individual elements of the same subarray would be returned (as in the default case).

RecursiveIteratorIterator::CHILD_FIRST behaves just like RecursiveIteratorIterator::SELF_FIRST but it first iterates the subarray then, the next time through the loop, it returns the entire subarray. For example

RecursiveIteratorIterator modes of operation

By default RecursiveIteratorIterator uses LEAVES_ONLY iteration. There are three modes of operation in all:

  • LEAVES_ONLY: Iterates over all nodes that have no children.
  • SELF_FIRST: When a node with children is found, process it first, then iterate over its children.
  • CHILD_FIRST: Iterate first over children, then process the node.

See the built–in RecursiveArrayIterator class class for iterating nested arrays.

RecursiveArrayIterator and RecursiveIteratorIterator examples:

<?php
echo "\nRecursiveArrayIterator and RecursiveIteratorIterator examples\n\n";

 // An array containing four elements, the first three are nested subarrays.
 $arr = [
     ["sitepoint", "phpmaster"],      // first nested array
     ["buildmobile", "rubysource"],   // second nested array
     ["designfestival", "cloudspring"], // third nested array
     "not a subarray"                     // one-dimensional array of one element
 ];

 $riteriter = new RecursiveIteratorIterator(new RecursiveArrayIterator($arr)); // RecursiveIteratorIterator::CHILD_FIRST);

 foreach($riteriter as $key => $value ) {

     echo $key . " => " . $value  . "\n";

 }

Produces this output:

0 => sitepoint
1 => phpmaster
0 => buildmobile
1 => rubysource
0 => designfestival
1 => cloudspring
3 => not a subarray

Doing RecursiveIteratorIterator(new RecursiveArrayIterator(Array), RecursiveIteratorIterator::CHILD_FIRST) below:

<?php
error_reporting(E_WARNING | E_ERROR | E_PARSE);

echo "\nNow doing  RecursiveIteratorIterator(new RecursiveArrayIterator($arr), RecursiveIteratorIterator::CHILD_FIRST)\n\n";

$riteriter2 = new RecursiveIteratorIterator(new RecursiveArrayIterator($arr), RecursiveIteratorIterator::CHILD_FIRST); // RecursiveIteratorIterator::CHILD_FIRST);

foreach ($riteriter2 as $key => $leaf) {

   echo $key . " => " . $leaf, PHP_EOL;
}

gives this output:

0 => sitepoint
1 => phpmaster
0 => Array
0 => buildmobile
1 => rubysource
1 => Array
0 => designfestival
1 => cloudspring
2 => Array
3 => not a subarray