Monday, February 22, 2010

Practical Php Patterns: Iterator

This post is part of the Practical Php Pattern series.
 
The behavioral pattern of the day is the Iterator pattern, which provides an abstraction over a very common process: the iteration over a collection of objects [or scalars] located in an unspecified part of the object graph.
The iteration may be performed in very different concrete ways: over an array property, a collection object, an array, even a query result set.
In a world of objects, Iterators maintain array-like capabilities as a non invasive facet of objects. The Client class is often totally decoupled from the actual implementations of objects and refer to an Iterator interface. Whenever possible, we can pass around references to an Iterator instead of a reference to a concrete or abstract class which may change in the future.

Participants:
  • Client: refers to Iterator's methods to perform a loop on a set of values or objects.
  • Iterator: abstraction over the iteration process. Contains methods such as next(), isFinished(), current() and so on.
  • ConcreteIterators: implements an iteration over a particular set of objects, such as an array, a tree, a Composite, a collection.
Php supports natively the Iterator pattern via the Traversable interface, which is extended by Iterator and IteratorAggregate. Not only a set of standard methods is defined by these two subinterfaces, but every Traversable object can be passed to foreach() as-is. The foreach construct is the primary Client of Iterators.
Iterator implementations are real iterators, while IteratorAggregate are Traversable objects with other responsibilities which return an Iterator via a public getIterator() method. The Standard Php Library, which is the only general purpose object-oriented library bundled with php, defines additional interfaces and utility classes that implement or compose them.
OuterIterator implementations decorate an Iterator. CachingIterator and LimitIterator are examples of this interface.
RecursiveIterator is an extension of the Iterator interface for tree-like structures, which defines a pair of additional methods to check for the presence of children in the current element of an iteration.
RecursiveArrayIterator and RecursiveDirectoryIterator are implementation examples of this interface. These type of Iterators can be used as-is or bridged to a plain Iterator's contract with a RecursiveIteratorIterator. This OuterIterator implementation will perform a depth-first or breadth-first traversal depending on the construction parameters.
When RecursiveIteratorIterator is used, it can be passed to foreach. See the code sample for the differences in usage of RecursiveIterators and their superset Iterators.
Finally, SeekableIterators add a seek() method to the contract, which can be used for moving the internal state of the Iterator into a particular point of the Iteration.
Note that Iterator is a greater abstraction than an object collection, since we can have InfiniteIterators, NoRewindIterators, etc, which have no correspondence in the plain arrays domain. For this reason, Iterators lack some functionalities such as a count() function.
The complete list of SPL iterators can be found in the php official manual.

Thanks to the powerful support of php, most of the work in using the Iterator pattern in this language consists in wiring the standard implementations correctly. The code sample exploits the functionalities of standard Iterators and of RecursiveIterators.
<?php
/**
 * Collection that wraps a numeric array.
 * All five public methods are needed to implement
 * the Iterator interface.
 */
class Collection implements Iterator
{
    private $_content;
    private $_index = 0;

    public function __construct(array $content)
    {
        $this->_content = $content;
    }

    public function rewind()
    {
        $this->_index = 0;
    }

    public function valid()
    {
        return isset($this->_content[$this->_index]);
    }

    public function current()
    {
        return $this->_content[$this->_index];
    }

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

    public function next()
    {
        $this->_index++;
    }
}

$array = array('A', 'B', 'C', 'D');
echo "Collection: ";
foreach (new Collection($array) as $key => $value) {
    echo "$key => $value. ";
}
echo "\n";

/**
 * Usually IteratorAggregate is the interface to implement.
 * It has only one method, which must return an Iterator
 * already defined as another class (e.g. ArrayIterator)
 * Iterator gives a finer control over the algorithm,
 * because all the hook points of Iterator' contract
 * are available for implementation.
 */
class NumbersSet implements IteratorAggregate
{
    private $_content;

    public function __construct(array $content)
    {
        $this->_content = $content;
    }

    public function contains($number)
    {
        return in_array($number, $this->_content);
    }

    /**
     * Only this method is necessary to implement IteratorAggregate.
     * @return Iterator
     */
    public function getIterator()
    {
        return new ArrayIterator($this->_content);
    }
}

echo "NumbersSet: ";
foreach (new NumbersSet($array) as $key => $value) {
    echo "$key => $value. ";
}
echo "\n";

// let's play with RecursiveIterator implementations
$it = new RecursiveArrayIterator(array(
    'A',
    'B',
    array(
        'C',
        'D'
    ),
    array(
        array(
            'E',
            'F'
        ),
        array(
            'G',
            'H',
            'I'
        )
    )
));
// $it is a RecursiveIterator but also an Iterator,
// so it loops normally over the four elements
// of the array.
echo "Foreach over a RecursiveIterator: ";
foreach ($it as $value) {
    echo $value;
    // but RecursiveIterators specify additional
    // methods to explore children nodes
    $children = $it->hasChildren() ? '{Yes}' : '{No}';
    echo $children, ' ';
}
echo "\n";
// we can bridge it to a different contract via
// a RecursiveIteratorIterator, whose cryptic name
// should be read as 'an Iterator that spans over
// a RecursiveIterator'.
echo "Foreach over a RecursiveIteratorIterator: ";
foreach (new RecursiveIteratorIterator($it) as $value) {
    echo $value;
}
echo "\n";

1 comment:

Forest Dean said...

I've enjoyed the practical php patterns series.

Here is a simple api server based on the Iterator pattern.
http://tw3k.net/Index.phps
http://api.tw3k.net

ShareThis