PHP Iterator Design Pattern I: Access to Aggregates

Setting the Table

I tend to think in structural terms to address a given task. I need an object to do “X” and another object to do “Y.” This is in contrast to sequential and procedural thinking; first I’ll do this, and then I’ll do that, and then another thing. Structural thinking is easier on my brain, and it’s a lot easier to make changes and add updates. When it comes to the process of sequentially accessing the elements of an aggregate object (some kind of list), I don’t think of a sequential process, I think of an Iterator design pattern. The Iterator contains both aggregate and iterator objects. That makes it much clearer. Common PHP tasks include iterating through a MySql table. Sometimes MySql table elements are passed to PHP arrays or even XML files. Further, some lists are optimized for searching, such as linked lists and skip lists. We’ll get to those in future posts regarding the Iterator design pattern. However, in PHP, sequential storage outside of a MySql table is typically a numeric or associative array. At this point the focus is on plain vanilla lists stored in aggregate objects we call arrays. Before getting further into this topic, Play the sample and Download the code for an overview:

According to the Gang of Four, the key idea in the Iterator

is to take the responsibility for access and traversal out of the list object and put it into an iterator object.

Typically, iterating through a list involves something like the following:

class StandardIteration
{
    public function __construct()
    {
        $bigList=array('rupiah','peso', 'real', 'rupee',
                       'dollar', 'euro', 'yen', 'pound',
                       'yuan', 'dinar', 'shekel', 'krone',
                       'ringgit', 'rial', 'shilling', 'rand',
                       'ruble', 'dong');
        $counter=0;
        echo "World Currency List 
";
        foreach ($bigList as $currency) 
        {
            echo $counter . ". " . $currency . "
";
            $counter++;
        }
    }
}
$worker=new StandardIteration();
?>

The “list” of elements reside in an array, and using a looping structure, programs can sequentially access all or some of the elements.

Access

Figure 1: Access through a Sequence

Figure 2: Binary tree access

The term traversal refers to a planned path. Consider again, Figure 2. Instead of traversing through the nodes, we could program through the numbered elements, beginning with Element 1 and proceeding to Element 7 through a kind of trial and error. However, a traversal through the nodes is more efficient if we know the organization of the binary tree. The study of list, list organization and optimizing list efficiency is a key one in computer science. So a good design pattern must prepare for more than a single type of list (aggregate) and method of traversing the list (iteration.) All lists are not sequential, and you don’t want them to be. So, how do you plan for different aggregates and iterations? Rather than changing the client’s code for each different type of aggregate and traversal,

a better plan would be to establish a structure for polymorphic iteration.

This is done by separating the aggregate from the iteration and establishing abstract interfaces for both aggregates and iterations. Figure 3 shows the class diagram for the Iterator pattern. There you see how the Client has access to both the Aggregate and Iterator interfaces.

Figure 3: Iterator class diagram

This first example is going to focus on the Iterator methods that the Gang of Four have in their original documentation; both in the abstract and in their concrete example. You may not be able to find PHP examples using the method names that GoF uses, but that does not mean they are examples with missing parts. Rather, as you will see below, PHP uses different names for their Iterator methods in PHP’s built-in Iterator interface. Here, though, I wanted to use the same names and equivalent duties found in the original. (In the download package, you will find example programs in two different folders; one that reflects those shown in this post and another set using the built-in interfaces.)

• first() Positions the iterator to the first element
• next() Advances the current element
• isDone() A boolean to determine whether the list is finished
• currentItem() Returns the element at the current index

You might say that these four methods are the engine in the Iterator pattern. Their purpose is to allow the client to make requests for different kinds of lists. For example, in a binary search of an ordered list, the starting point is in the middle of the list; and so the first() method would start the search at list-length/2 instead of 0 as in a sequential search of a typical array list. The purpose is to separate the list (aggregate) from traversal process and to hide the traversal mechanism from the list itself. In this way, you’re not committed to a single type of list and iteration process.

The Aggregate and Iterator Interfaces

The Aggregate (IAgregate) interface has a single method; createIterator(). The Client can gain access through the Aggregate createIterator() method to the Iterator (IIterator). (We could have used the build-in PHP IteratorAggregate interface with the getIterator() method for equivalent results.) The Iterator interface contains the four methods described above. Those methods reflect the names and purposes of four methods from the C++ built-in Iterator that the Gang of Four use in their Iterator example. As noted PHP also has a built-in Iterator interface but with different method names than the C++ Iterator used by GoF:

• C++ Name: PHP Name
• first: rewind
• next: next
• isDone: valid
• currentItem: current

(The PHP Iterator interface also includes a key() method that is not used in the current example.)

In future posts on the Iterator, we can use the built-in PHP interfaces, IteratorAggregate and Iterator interface, but in this initial example I wanted to keep the terminology close to the original for those of you who use the Gamma et all tome and explore Iterator examples written in languages other than PHP. (You will find two example folders in the downloads: one with the built-in interfaces and one with those reflecting the originals. The functionality is identical.)

With those features in mind, here are the two interfaces:

//IAggregate.php
interface IAggregate
{
    function createIterator();
}
?>
 

//IIterator.php
interface IIterator
{
    function first();
    function next();
    function isDone();
    function currentItem();
}
?>

Like most interfaces these are pretty short, but they give us a good outline of the more general purposes of what their child classes can create.

Concrete Aggregate and Iterator Classes

In this first example, the ConcreteAggregate class does little more than take the list (an array) passed by the Client and uses it to instantiate a concrete iterator. In the Gang of Four’s example, the AbstractList is based on the C++ built-in List interface, but all that is actually required is to implement the createIterator() method, and since the example interface includes only that method, the implementation is fairly simple:

//ConcreteAggregate.php
class ConcreteAggregate implements IAggregate
{
    private $exchange;
    private $iterator;
    public function __construct(array $curr)
    {
       $this->exchange=$curr;
       /*You can change the array to reverse sorted order */
        sort($this->exchange);
        //rsort($this->exchange);
    }
 
    public function createIterator()
    {
        $this->iterator=new ConcreteIterator($this->exchange);
        return $this->iterator;
    }
}
?>

As you can see, the list includes an option (commented out) to reverse sort the list, but it would be simple to add more to the class to include methods (for example) to add, remove or append the existing list. The sorting is necessary to provide an ordered list.

The ConcreteIterator implements the IITerator methods for a simple ordered list. The Iterator design pattern can implement any number of concrete iterators for different kinds of lists. The following is the basic ordered list implementation.

//ConcreteIterator.php
class ConcreteIterator implements IIterator
{
    private $listNow=array();
    private $position;
 
    public function __construct(array $sentList)
    {
        $this->listNow=$sentList;   
    }
 
    function first()
    {
        $this->position=0;
        //Reverse order
        //$this->position=count($this->listNow)-1;
    }
 
    function next()
    {
        ++$this->position;
        //Reverse order
        //--$this->position;
    }
 
    function isDone()
    {
        return isset($this->listNow[$this->position]);
    }
 
    function currentItem()
    {
        return $this->listNow[$this->position];
    }
}
?>

Had we used the PHP built-in Iterator interface, we’d have to implement the key() method used to return the key of the current element. In this example, it was not needed.

The Client and UI

About the only UI this example needs is a button-click. The HTML calls a PHP Client. You can see the HTML and CSS in the following two listings:

List Iterator
Currency Name:

  

  
  

  

@charset "UTF-8";
/* CSS Document */
/* #413D41 (dkr gray) #4B494A (dk gray) #B9A46F (dk tan)*/
/* #CEB99E(tan) #F4F4F4 (dusty white) */
body
{
    background-color: #F4F4F4;
    color: #413D41;
    font-family: Verdana, helvetica, arial, sans-serif;  
}
 
iframe
{
    background-color: #B9A46F;
}
 
h3
{
    background-color: #413D41;
    color: #CEB99E;
    padding-left: 1em;
    width:250px;
}

As you may have seen, the HTML/CSS are pretty basic. It simply calls the Client class.

The Client is implied in the Iterator design pattern, but it plays a crucial role. Gamma et al, consider two types of iteration control, external and internal. In external control, the Client controls iteration because it sets up the order of the calls made to the concrete iterator (ConcreteIterator). In internal control, the iterator object controls the iteration.

This example uses external iteration control, and on top of that the Client provides the raw list (an array of world currency names). So even though its role is implied in the design pattern, the client has a major role when using external iteration control. The following Client class listing shows the work done by the client.

ERROR_REPORTING( E_ALL | E_STRICT );
ini_set("display_errors", 1);
function __autoload($class_name) 
{
    include $class_name . '.php';
}
//Client.php
class Client
{
    private $currencyTypes;
    private $doIterate;
 
    public function __construct()
    {
         //Generate list
         $currency=array('rupiah','peso', 'real', 'rupee',
                         'dollar', 'euro', 'yen', 'pound',
                         'yuan', 'dinar', 'shekel', 'krone',
                         'ringgit', 'rial', 'shilling', 'rand',
                         'ruble','dong');
 
         //Create aggregate instance and use it to create iterator
         $this->currencyTypes=new ConcreteAggregate($currency);
         $this->doIterate= $this->currencyTypes->createIterator();
 
         //Use the concrete iterator's methods
         $this->doIterate->first();
         while($this->doIterate->isDone())
         {
            echo $this->doIterate->currentItem() . "
";
            $this->doIterate->next();
         }
         unset($this->doIterate);
    }
}
$worker = new Client();
?>

You can break down the role of the Client into the following parts:

• creates a list in an array
• instantiates a concrete aggregate, passing the array to the aggregate object
• instantiates a concrete iterator object through an aggregate method
• uses the iterator an object method to set a pointer to the first list item
• loops through the iterate object until the list is complete
• displays the current item in the list
• moves the pointer to the next item in the list
• destroys the iteration object when finished

When using an external iterator control, you can expect a big role from the from the client object. In this sample, it’s pretty big, but it clearly illustrates the roles of the Aggregate and Iterator participants, and how their methods are used with a list.

Different Iterators for Different Lists

The primary advantage of separating the iteration process from the list is to implement different concrete lists and iterators. In their original work, Gamma et al show a standard list and a skip list with different concrete iterators for each list. In order to see a PHP implementation of that example, the first task will be to understand some fundamental search designs used to find items in a list. In the next post, I’d like to take up search methods and algorithms and forge ahead with our discussion of the Iterator design pattern used in PHP.

Copyright © 2014 William Sanders. All Rights Reserved.