The Iterator Pattern

This article, the first of two parts, explains how to use the Iterator pattern to manipulate any collection of objects. It is excerpted from chapter eight of the book PHP|architect’s Guide to PHP Design Patterns, written by Jason E. Sweat (PHP|architect, 2005; ISBN: 0973589825).

OBJECT-ORIENTED PROGRAMMING ENCAPSULATES application logic in classes. Classes, in turn, are instantiated as objects, and each individual object has a distinct identity and state. Individual objects are a useful way to organize your code, but often you want to work with a group of objects, or a collection. A set of rows from a SQL query is a collection, as is the list of Property objects in the Monopoly game examples shown earlier in the book.

A collection need not be homogeneous either. A Window object in a graphical user interface framework could collect any number of control objects—a Menu, a Slider, and a Button, among others. Moreover, the implementation of a collection can vary: a PHP array is a collection, but so is a hash table, a linked list, a stack, and a queue.

The Problem

How can one easily manipulate any collection of objects?

The Solution

Use the Iterator pattern to provide uniform access to the contents of a collection.

You may not realize it, but you use the Iterator pattern every day—it’s embodied in PHP’s array type and rich set of array manipulation functions. (Indeed, given the combination of the native array type in the language and a host of flexible functions designed to work with this native type, you need a pretty compelling reason not to use arrays as your means of manipulating collections of objects.)

Here’s native array iteration in PHP:

$test = array(‘one’, ‘two’, ‘three’);
$output = ”;
reset($test);
do {
  $output .= current($test);
} while (next($test));
echo $output; // produces ‘onetwothree’

The reset() function restarts iteration to the beginning of the array; current() returns the value of the current element; and next() advances to the next element in the array and returns the new current()value. When you advance past the end of the array, next() returns false. Using these iteration methods, the internal implementation of a PHP array is irrelevant to you.

Iterator couples the object-oriented programming principles of encapsulation and polymorphism. Using Iterator, you can manipulate the objects in a collection without explicitly knowing how the collection is implemented or what the collection contains (what kinds of objects). Iterator provides a uniform interface to different concrete iteration implementations, which do contain the details of how to manipulate a specific collection, including which items to show (filtering) and in what order (sorting).

Let’s create a simple object to manipulate in a collection. (Though this example is in PHP5, Iterators are not unique to PHP5 and most of the examples in this chapter work in PHP4 as well, albeit with a healthy amount of reference operators added). The object, Lendable, represents media such as movies and albums and is intended to be part of a web site or service to let users review or lend portions of their media collection to other users. (For this example, do not concern yourself with persistence and the like.)

Let’s start with the following test as a basis for the design of Lendable.

// PHP5
class LendableTestCase extends UnitTestCase {
 
function TestCheckout() {
   
$item = new Lendable;
   
$this->assertFalse($item->borrower);
   
$item->checkout(‘John’);
   
$this->assertEqual(‘borrowed’, $item->status);
   
$this->assertEqual(‘John’, $item->borrower);
 
}
 
function TestCheckin() {
   
$item = new Lendable;
   
$item->checkout(‘John’);
   
$item->checkin();
   
$this->assertEqual(‘library’, $item->status);
   
$this->assertFalse($item->borrower);
 
}
}

To implement the requirements of this initial test, let’s create a class with a few public attributes and some methods to toggle the values of these attributes:

class Lendable {
 
public $status = ‘library';
 
public $borrower = ”;
public function checkout($borrower) {
   
$this->status = ‘borrowed';
   
$this->borrower = $borrower;
}
  public function checkin() {
    
$this->status = ‘library';
    
$this->borrower = ”;
  }
}

{mospagebreak title=Extending Lendable}

Lendable is a good, generic start. Let’s extend it to track items like DVDs or CDs.

Media extends Lendable and tracks details about specific media, including the name of the item, the year it was released, and what type of item it is:

class Media extends Lendable {
 
public $name;
 
public $type;
 
public $year;
 
public function _construct($name, $year, $type=’dvd’) {
   
$this->name = $name;
   
$this->type = $type;
   
$this->year = (int)$year;
 
}
}

To keep things simple, Media has three public instance variables, Media::name, Media::year, and Media::type. The constructor takes two arguments and stores the first in $name and the second in $year. The constructor also allows an optional third parameter to specify type (which defaults to “dvd”).

Given individual objects to manipulate, you can now create a container to hold them: a Library. Like a regular library, Library should be able to add, remove and count the items in the collection. Eventually, Library should also permit access to individual items (objects) in the collection (which is shown momentarily in the Sample Code section of this chapter).

For right now, let’s build a test case for Library.

  class LibraryTestCase extends UnitTestCase {
   
function TestCount() {
     
$lib = new Library;
     
$this->assertEqual(0, $lib->count());
   
}
 
}

It’s easy enough to write a class that satisfies this test:

  class Library {
   
function count() {
     
return 0;
   
}
 
}

Let’s continue and add some interesting features to the test:

  class LibraryTestCase extends UnitTestCase {
    function TestCount() { /* … */ }
    function TestAdd() {
     
$lib = new Library;
     
$lib->add(‘one’);
     
$this->assertEqual(1, $lib->count());
   
}
 
}

An easy way to implement add() is to piggyback on PHP’s flexible array functions: you can add items to an array instance variable and use count() to return the number of items in the collection.

  class Library {
   
protected $collection = array();
    function count() {
     
return count($this->collection);
   
}
   
function add($item) {
    
$this->collection[] = $item;
   
}
 
}

Library is now a collection, but it provides no way to retrieve or manipulate the individual members of the collection.

Let’s move on to the purpose of the chapter, implementation of the Iterator design pattern.

The following UML class diagram shows the GoF Iterator pattern with the Media and Library classes used to make the example concrete.

  • Your collection class must provide a Factory (see Chapter 3) to create an instance of your Iterator.
  • Iterator classes define an interface of first() to go to the beginning of a collection, next() to move to the next item in sequence as you iterate, currentItem() to retrieve the current item from the collection as you iterate, and isDone() to indicate when you have iterated over the entire collection.

In the Sample Code section, the LibraryGofIterator class is an example of a direct implementation of the GoF Iterator design pattern.

{mospagebreak title=Sample Code}

The first step in implementing the GoF Iterator pattern within Library is to write a new test case for the new concrete Iterator. Since each test method will manipulate a Library filled with Media instances, you can employ the UnitTestCase::setUp() method to populate a variable with a Library in a known state for each test.

Start by adding the Library::getIterator() method as a Factory for instances of the LibraryGofIterator class.

  class IteratorTestCase extends UnitTestCase {
   
protected $lib;
   
function setup() {
     
$this->lib = new Library;
     
$this->lib->add(new Media(‘name1′, 2000));
     
$this->lib->add(new Media(‘name2′, 2002));
     
$this->lib->add(new Media(‘name3′, 2001));
   
}
   
function TestGetGofIterator() {
     
$this->assertIsA($it = $this->lib->getIterator()
        ,’LibraryGofIterator’);
   
}
  }

Here’s the implementation:

  class Library {
   
// …
   
function getIterator() {
     
return new LibraryGofIterator($this->collection);
   
}
 
}

The getIterator() method passes the Library‘s $collection to the constructor of the new concrete iterator. This technique has two important implications: each iterator is independent, so multiple iterators can operate at the same time. Additionally, the iterator operates on the collection as it existed at the time the iterator was requested. If another item is added to the collection at any time later, you must request another iterator to display it (at least in this implementation).

Let’s continue enhancing the test suite by adding assertions to the TestGetGofIterator() method to match the Iterator design pattern. The isDone() method should only be true if you’ve iterated over the entire collection. If the iterator’s just been created, isDone() should obviously return false to indicate it’s okay to iterate.

  class IteratorTestCase extends UnitTestCase {
   
function setup() { /* … */ }
   
function TestGetGofIterator() {
     
$this->assertIsA($it = $this->lib->getIterator()
        ,’LibraryGofIterator’);
     
$this->assertFalse($it->isdone());
   
}
 
}

As usual with TDD, implement the simplest possible code that satisfies your test case:

  class LibraryGofIterator {
   
function isDone() {
     
return false;
   
}
 
}

So, what should happen during the first iteration?currentItem() should return the first Media object added in the IteratorTestCase::setUp() method and isDone() should continue to be false, since two additional items remain to be iterated over.

  class IteratorTestCase extends UnitTestCase {
   
function setup() { /* … */ }
   
function TestGetGofIterator() {
     
$this->assertIsA($it = $this->lib->getIterator()
        ,’LibraryGofIterator’);
     
$this->assertFalse($it->isdone());
     
$this->assertIsA($first = $it->currentItem(), ‘Media’);
     
$this->assertEqual(‘name1′, $first->name);
     
$this->assertFalse($it->isdone());
   
}
 
}

It’s critical that LibraryGofIterator receives the $collection in the constructor (see the minimal implementation of Library above) and returns the current() item of that array from the currentItem()method.

  class LibraryGofIterator {
   
protected $collection;
   
function __construct($collection) {
     
$this->collection = $collection;
   
}
   
function currentItem() {
     
return current($this->collection);
   
}
   
function isDone() {
     
return false;
   
}
 
}

What should happen in the next iteration? The next()method should change what item is returned by the currentItem() method. This next test captures that expected behavior:

  class IteratorTestCase extends UnitTestCase {
   
function setup() { /* … */ }
   
function TestGetGofIterator() {
     
$this->assertIsA($it = $this->lib->getIterator(), ‘LibraryGofIterator’);
     
$this->assertFalse($it->isdone());
     
$this->assertIsA($first = $it->currentItem(), ‘Media’);
     
$this->assertEqual(‘name1′, $first->name);
     
$this->assertFalse($it->isdone());
     
$this->assertTrue($it->next());
     
$this->assertIsA($second = $it->currentItem(), ‘Media’);
     
$this->assertEqual(‘name2′, $second->name);
     
$this->assertFalse($it->isdone());
   
}
 
}

Piggybacking again on PHP’s array functions, use next() on the array:

  class LibraryGofIterator {
   
protected $collection;
   
function __construct($collection) {
     
$this->collection = $collection;
   
}
   
function currentItem() {
     
return current($this->collection);
   
}
   
function next() {
     
return next($this->collection);
   
}
   
function isDone() {
     
return false;
   
}
 
}

The third iteration looks much like the others, except the isDone() method must return true. You also want next() to indicate success of moving to the next iteration:

  class IteratorTestCase extends UnitTestCase {
    
function setup() { /* … */ }
   
function TestGetGofIterator() {
      
$this->assertIsA($it = $this->lib->getIterator(), ‘LibraryGofIterator’);
     
$this->assertFalse($it->isdone());
      
$this->assertIsA($first = $it->currentItem(), ‘Media’);
     
$this->assertEqual(‘name1′, $first->name);
     
$this->assertFalse($it->isdone());
      
$this->assertTrue($it->next());
     
$this->assertIsA($second = $it->currentItem(), ‘Media’);
     
$this->assertEqual(‘name2′, $second->name);
     
$this->assertFalse($it->isdone());
     
$this->assertTrue($it->next());
     
$this->assertIsA($third = $it->currentItem(), ‘Media’);
     
$this->assertEqual(‘name3′, $third->name);
     
$this->assertFalse($it->next());
     
$this->assertTrue($it->isdone());
   
}
 
}

With small modifications to the next() and isDone()methods, all of the tests pass Here’s the code so far:

  class LibraryGofIterator {
   
protected $collection;
   
function __construct($collection) {
     
$this->collection = $collection;
    
}
   
function first() {
      
reset($this->collection);
   
}
   
function next() {
     
return (false !== next($this->collection));
   
}
   
function isDone() {
     
return (false === current($this->collection));
   
}
   
function currentItem() {
     
return current($this->collection);
   
}
 
}

There’s just one problem with the Iterator test case: it doesn’t reflect how iterators are typically used. Yes, it tests all of the features of the Iterator pattern, but application code uses the Iterator in a much simpler way. So, the next step is to write a test using more realistic code.

  class IteratorTestCase extends UnitTestCase {
   
protected $lib;
   
function setup() { /* … */ }
   
function TestGetGofIterator() { /* … */ }
    function TestGofIteratorUsage() {
     
$output = ”;
     
for ($it=$this->lib->getIterator(); !$it->isDone(); $it->next()){
       
$output .= $it->currentItem()->name;
     
}
     
$this->assertEqual(‘name1name2name3′, $output);
   
}
 
}

So far, the implementation of Iterator copies an array (the collection) and uses PHP’s internal pointer to track the iteration. You can also implement the Iterator by keeping track of the collection index by yourself. This requires a new accessor method in Library to fetch an object by key.

  class Library {
   
// …
   
function get($key) {
     
if (array_key_exists($key, $this->collection)) {
       
return $this->collection[$key];
     
}
   
}
 
}

Also, you’d pass $this (the library itself) to the constructor instead of $this->collection (the array containing the Media collection) in the Library::getIterator() method.

The “external” iterator would then just track a pointer internally to know which element of the Library collection it’s currently referencing, and would use the reference to the Library passed in the constructor to call the get() method to retrieve the current object.

  class LibraryGofExternalIterator {
   
protected $key = 0;
   
protected $collection;
   
function __construct($collection) {
     
$this->collection = $collection;
   
}
   
function first() {
     
$this->key=0;
   
}
   
function next() {
     
return (++$this->key < $this->collection->count());
   
}
   
function isDone() {
     
return ($this->key >= $this->collection->count());
   
}
   
function currentItem() {
     
return $this->collection->get($this->key);
   
}
 
}

This implementation assumes your collection array is indexed starting with 0 and is completely sequential.

{mospagebreak title=A Variant Iterator API}

While the foregoing code is a complete implementation of the Iterator pattern as described by GoF, you may find the four-method API a bit cumbersome. If so, you can collapse next(), currentItem(), and isDone()into justnext() by having the latter either advance and return the current item from the collection or return false if the entire collection has been processed.

Here’s one way to write a test for this variation of the API:

  class IteratorTestCase extends UnitTestCase {
   
// …
   
function TestMediaIteratorUsage() {
     
$this->assertIsA(
       
$it = $this->lib->getIterator(‘media’)
        ,’LibraryIterator’);
     
$output = ”;
     
while ($item = $it->next()) {
      
$output .= $item->name;
     
}
     
$this->assertEqual(‘name1name2name3′, $output);
   
}
 
}

In the code above, notice the simplified control structure for looping. next() returns an object or false, allowing you to perform the assignment inside the while loop conditional.

The next few examples explore variations of the Iterator pattern using the smaller interface. As a convenience, change the Library::getIterator() method to a parameterized Factory so you can get either the four-method iterator or the two-method iterator (next() and reset()) from that single method.

  class Library {
   
// …
   
function getIterator($type=false) {
     
switch (strtolower($type)) {
      
case ‘media':
        
$iterator_class = ‘LibraryIterator';
       
break;
      
default:
       
$iterator_class =  
‘LibraryGofIterator';
      
}
     
return new $iterator_class($this->collection);
    }
 
}

Here, Library::getIterator() now accepts a parameter to select what kind of iterator to return. The default is LibraryGofIterator (so the existing tests still pass). Passing the string media to the method creates and returns a LibraryIterator instead.

This is some code to implement LibraryIterator:

  class LibraryIterator {
   
protected $collection;
   
function __construct($collection) {
     
$this->collection = $collection;
   
}
   
function next() {
     
return next($this->collection);
   
}
 
}

Oops! The dreaded red bar! What happened to get the error “Equal expectation fails at character 4 with name1name2name3 and name2name3“? Somehow, the first iteration was skipped—that’s a bug. To fix the error, return current() for the first call of the next()method.

  class LibraryIterator {
   
protected $collection;
   
protected $first=true;
   
function __construct($collection) {
     
$this->collection = $collection;
   
}
   
function next() {
     
if ($this->first) {
       
$this->first = false;
       
return current($this->collection);
     
}
     
return next($this->collection);
   
}
 
}

Presto! A green bar and a streamlined while loop iterator.

[gp-comments width="770" linklove="off" ]
antalya escort bayan antalya escort bayan