Iterator

Interpreter Computer Science Design Patterns
Iterator
Mediator

Provide a way to access the elements of an aggregate object sequentially without exposing its underlying representation.

Examples

In Java, the interface java.util.Iterator<E> is an implementation of the iterator pattern. That way, all the objects that implement the java.lang.Iterable<T> interface don't need a handy implementation of this pattern.

Cost

This pattern has a cost. Only implement this pattern for an important amount of code. IDE refactoring can't help you much.

Creation

This pattern has a cost to create.

Maintenance

This pattern is easy to maintain.

Removal

This pattern has a cost to remove too.

Advises

  • Put the iterator term in the name of the iterator class to indicate the use of the pattern to the other developers.

Implementations

Implementation in Java

Here is an example in Java:

import java.util.BitSet;
import java.util.Iterator;
public class BitSetIterator implements Iterator<Boolean> {
    private final BitSet bitset;
    private int index = 0;
    public BitSetIterator(BitSet bitset) {
        this.bitset = bitset;
    }
    public boolean hasNext() {  
        return index < bitset.length();
    }
    public Boolean next() {
        if (index >= bitset.length()) {
            throw new NoSuchElementException();
        }
        return bitset.get(index++);
    }
    public void remove() {
        throw new UnsupportedOperationException();
    }
}

Two different usage examples:

import java.util.BitSet;
public class TestClientBitSet {
    public static void main(String[] args) {
        // create BitSet and set some bits
        BitSet bitset = new BitSet();
        bitset.set(1);
        bitset.set(3400);
        bitset.set(20);
        bitset.set(47);
        for (BitSetIterator iter = new BitSetIterator(bitset); iter.hasNext(); ) {
            Boolean b = iter.next();              
            String tf = (b.booleanValue() ? "T" : "F");
            System.out.print(tf);
        }
        System.out.println();
    }
}
import java.util.ArrayList;
import java.util.Collection;
public class TestClientIterator  {
    public static void main(String[] args) {
        Collection<Object> al = new ArrayList<Object>();
        al.add(new Integer(42));
        al.add("test");
        al.add(new Double("-12.34"));
        for (Iterator<Object> iter = al.iterator(); iter.hasNext(); ) {
            System.out.println(iter.next());
        }
        for (Object o : al) {
            System.out.println(o);
        }
    }
}
Implementation in C#

Here is an example in C#:

using System;
using System.Collections;
  class MainApp
  {
    static void Main()
    {
      ConcreteAggregate a = new ConcreteAggregate();
      a[0] = "Item A";
      a[1] = "Item B";
      a[2] = "Item C";
      a[3] = "Item D";
      // Create Iterator and provide aggregate
      ConcreteIterator i = new ConcreteIterator(a);
      Console.WriteLine("Iterating over collection:");
 
      object item = i.First();
      while (item != null)
      {
        Console.WriteLine(item);
        item = i.Next();
      }
      // Wait for user
      Console.Read();
    }
  }
  // "Aggregate"
  abstract class Aggregate
  {
    public abstract Iterator CreateIterator();
  }
  // "ConcreteAggregate"
  class ConcreteAggregate : Aggregate
  {
    private ArrayList items = new ArrayList();
    public override Iterator CreateIterator()
    {
      return new ConcreteIterator(this);
    }
    // Property
    public int Count
    {
      get{ return items.Count; }
    }
    // Indexer
    public object this[int index]
    {
      get{ return items[index]; }
      set{ items.Insert(index, value); }
    }
  }
  // "Iterator"
  abstract class Iterator
  {
    public abstract object First();
    public abstract object Next();
    public abstract bool IsDone();
    public abstract object CurrentItem();
  }
  // "ConcreteIterator"
  class ConcreteIterator : Iterator
  {
    private ConcreteAggregate aggregate;
    private int current = 0;
    // Constructor
    public ConcreteIterator(ConcreteAggregate aggregate)
    {
      this.aggregate = aggregate;
    }
    public override object First()
    {
      return aggregate[0];
    }
    public override object Next()
    {
      object ret = null;
      if (current < aggregate.Count - 1)
      {
        ret = aggregate[++current];
      }
 
      return ret;
    }
    public override object CurrentItem()
    {
      return aggregate[current];
    }
    public override bool IsDone()
    {
      return current >= aggregate.Count ? true : false ;
    }
  }
Implementation in PHP 5

As a default behavior in PHP 5, using an object in a foreach structure will traverse all public values. Multiple Iterator classes are available with PHP to allow you to iterate through common lists, such as directories, XML structures and recursive arrays. It's possible to define your own Iterator classes by implementing the Iterator interface, which will override the default behavior. The Iterator interface definition:

interface Iterator
{
    // Returns the current value
    function current();
 
    // Returns the current key
    function key();
    // Moves the internal pointer to the next element
    function next();
 
    // Moves the internal pointer to the first element
    function rewind();
 
    // If the current element is valid (boolean)
    function valid();
}

These methods are all being used in a complete foreach( $object as $key=>$value ) sequence. The methods are executed in the following order:

rewind() 
while valid() {
    current() in $value 
    key() in $key 
    next()
} 
End of Loop

According to Zend, the current() method is called before and after the valid() method.

Implementation in Perl

In Perl, objects providing an iterator interface either overload the <> (iterator operator)[1], or provide a hash or tied hash interface that can be iterated over with each[2]. Both <> and each return undef when iteration is complete. Overloaded <> operator:

# fibonacci sequence
package FibIter;
use overload
    '<>' => 'next_fib';
sub new {
    my $class = shift;
    bless { index => 0, values => [0, 1] }, $class
}
sub next_fib {
    my $self = shift;
    my $i = $self->{index}++;
    $self->{values}[$i] ||=
        $i > 1 ? $self->{values}[-2]+$self->{values}[-1]
               : ($self->{values}[$i]);
}
# reset iterator index
sub reset {
    my $self = shift;
    $self->{index} = 0
}
package main;
my $iter = FibIter->new;
while (my $fib = <$iter>) {
    print "$fib","\n";
}

Iterating over a hash (or tied hash):

# read from a file like a hash
package HashIter;
use base 'Tie::Hash';
sub new {
    my ($class, $fname) = @_;
    my $obj = bless {}, $class;
    tie %$obj, $class, $fname;
    bless $obj, $class;
}
 
sub TIEHASH {
    # tie hash to a file
    my $class = shift;
    my $fname = shift or die 'Need filename';
    die "File $fname must exist"
         unless [-f $fname];
    open my $fh, '<', $fname or die "open $!";
    bless { fname => $fname, fh => $fh }, $class;
}
sub FIRSTKEY {
    # (re)start iterator 
    my $self = shift;
    my $fh = $self->{fh};
    if (not fileno $self->{fh}) {
        open $fh, '<', $self->{fname} or die "open $!";
    }
    # reset file pointer
    seek( $fh, 0, 0 );
    chomp(my $line = <$fh>);
    $line
}
sub NEXTKEY {
    # next item from iterator
    my $self = shift;
    my $fh = $self->{fh};
    return if eof($fh);
    chomp(my $line = <$fh>);
    $line
}
sub FETCH {
    # get value for key, in this case we don't
    # care about the values, just return 
    my ($self, $key) = @_;  
    return
}
sub main;
# iterator over a word file
my $word_iter = HashIter->new('/usr/share/dict/words');
# iterate until we get to abacus
while (my $word = each( %$word_iter )) {
    print "$word\n";
    last if $word eq 'abacus'
}
# call keys %tiedhash in void context to reset iterator
keys %$word_iter;
Implementation in Python

In Python, iterators are objects that adhere to the iterator protocol. You can get an iterator from any sequence (i.e. collection: lists, tuples, dictionaries, sets, etc.) with the iter() method. Another way to get an iterator is to create a generator, which is a kind of iterator. To get the next element from an iterator, you use the next() method (Python 2) / next() function (Python 3). When there are no more elements, it raises the StopIteration exception. To implement your own iterator, you just need an object that implements the next() method (Python 2) / __next__() method (Python 3). Here are two use cases:

# from a sequence
x = [42, "test", -12.34]
it = iter(x)
try:
  while True:
    x = next(it) # in Python 2, you would use it.next()
    print x
except StopIteration:
  pass
# a generator
def foo(n):
  for i in range(n):
    yield i
it = foo(5)
try:
  while True:
    x = next(it) # in Python 2, you would use it.next()
    print x
except StopIteration:
  pass
Implementation in MATLAB

MATLAB supports both external and internal implicit iteration using either "native" arrays or cell arrays. In the case of external iteration where the onus is on the user to advance the traversal and request next elements, one can define a set of elements within an array storage structure and traverse the elements using the for-loop construct. For example,

% Define an array of integers
myArray = [1,3,5,7,11,13];
for n = myArray
   % ... do something with n
   disp(n)  % Echo integer to Command Window
end

traverses an array of integers using the for keyword. In the case of internal iteration where the user can supply an operation to the iterator to perform over every element of a collection, many built-in operators and MATLAB functions are overloaded to execute over every element of an array and return a corresponding output array implicitly. Furthermore, the arrayfun and cellfun functions can be leveraged for performing custom or user defined operations over "native" arrays and cell arrays respectively. For example,

function simpleFun
% Define an array of integers
myArray = [1,3,5,7,11,13];
% Perform a custom operation over each element
myNewArray = arrayfun(@(a)myCustomFun(a),myArray);
 
% Echo resulting array to Command Window          
myNewArray
 
 
function outScalar = myCustomFun(inScalar)
% Simply multiply by 2
outScalar = 2*inScalar;

defines a primary function simpleFun which implicitly applies custom subfunction myCustomFun to each element of an array using built-in function arrayfun.

Alternatively, it may be desirable to abstract the mechanisms of the array storage container from the user by defining a custom object-oriented MATLAB implementation of the Iterator Pattern. Such an implementation supporting external iteration is demonstrated in MATLAB Central File Exchange item Design Pattern: Iterator (Behavioural). This is written in the new class-definition syntax introduced with MATLAB software version 7.6 (R2008a) [3] and features a one-dimensional cell array realisation of the List Abstract Data Type (ADT) as the mechanism for storing a heterogeneous (in data type) set of elements. It provides the functionality for explicit forward List traversal with the hasNext(), next() and reset() methods for use in a while-loop.

References

  1. File handle objects implement this to provide line by line reading of their contents
  2. In Perl 5.12, arrays and tied arrays can be iterated over like hashes, with each
  3. "New Class-Definition Syntax Introduced with MATLAB Software Version 7.6". The MathWorks, Inc. March 2009. http://www.mathworks.com/access/helpdesk/help/techdoc/matlab_oop/brqzfth-1.html#brqzfth-3. Retrieved September 22, 2009. 


Clipboard

To do:
Add more illustrations.


Interpreter Computer Science Design Patterns
Iterator
Mediator


You have questions about this page?
Ask it here:


Create a new page on this book:

Last modified on 14 February 2014, at 20:20