/ Design Patterns / Behavioral patterns / Iterator

Iterator Design Pattern in Delphi

Most of the time, when we want to iterate through a list, we tend to go for the option of using a ‘for' loop with an integer variable to access the indexed Items property of the list. That is all very well if the list actually has in indexed property, but there are times when it may not be desirable or even possible to provide an integer based index for a list.

The Iterator - a mechanism for iterating (hence the name) through a list without having to use an integer property.

  TCustomerList = class
  private
    fItems: TObjectList;
  public
    procedure Add(const Item: TCustomer);
    procedure Insert(const Item, Before: TCustomer);
    procedure Insert(Idx: Integer; const Item: TCustomer);
    procedure Delete(Idx: Integer);
    procedure Remove(const Item: TCustomer);
    procedure Clear;
    function Contains(const Item: TCustomer): Boolean;
    function GetCount: Integer;
    function GetItem(Idx: Integer): TCustomer;
  end;

If we take this TCustomerList class, we see that it is possible to use a ‘for' loop to iterate through the list and we will use this class as basis for demonstrating how to implement an Iterator instead.

First, let us take away the public ability to do anything with this list that knows anything about an Integer index:

  TCustomerList = class
  private
    fItems: TObjectList;
  protected
    function GetItem(Idx: Integer): TCustomer;
  public
    procedure Add(const Item: TCustomer);
    procedure Insert(const Item, Before: TCustomer);
    procedure Remove(const Item: TCustomer);
    procedure Clear;
    function Contains(const Item: TCustomer): Boolean;
    function GetCount: Integer;
  end;

Now we can still do everything, apart from retrieving Customers from the list. For the sake of this example, we do not want to be able to access a single Customer by an Integer index, because it is very unusual for a Customer to know what their indexed position is in the list. You will notice that the GetItem method is still in the class, but it has been placed in the protected section of the class to prevent clients of this class accessing it.

  TCustomerIterator = class
  private
    fList: TCustomerList;
    fCurrentItem: Integer;
  protected
    procedure Reset;
    function Next: Boolean; virtual;
    function CurrentItem: TCustomer;
  public
    constructor Create(const List: TCustomerList);
  end;

There are several variations of the Iterator pattern that are available, but I have found that this version promotes the best clarity and ease of coding when it comes to using it in applications. The class takes a TCustomerList as a constructor parameter, to which it keeps a reference for later use. 

implementation
  constructor TCustomerIterator.Create(const List: TCustomerList);
  begin
    inherited Create;
    fList := List;
    Reset;
  end;

  procedure TCustomerIterator.Reset;
  begin
    fCurrentItem := -1;
  end;

  function TCustomerIterator.Next: Boolean;
  begin
    Result := (fList <> nil) and
              (fCurrentItem < (fList.GetCount - 1));
    if Result then
      Inc(fCurrentItem);
  end;

  function TCustomerIterator.CurrentItem: TCustomer;
  begin
    if (fList <> nil) and ((fCurrentItem >= 0) and
       (fCurrentItem < fList.GetCount)) then
    Result := fList.GetItem(fCurrentItem)
  else
    Result := nil;
  end;

Internally to the Iterator class we still have to use an Integer variable to keep track of where we are in the list. Although we have said that we don't want to access the list using an Integer index, that rule only applies to public clients of the list class.

When the Iterator is created, the Reset method sets the internal integer to -1, which is before the first item in the list; this ensures that if someone calls CurrentItem before they call Next, they will not receive a valid object, because the Iterator has not yet 'started'.

The Next method checks to see if there is an item in the list that it can move to and, if so, it increments the internal index ready for any call to the CurrentItem method.

The CurrentItem method does a double check to ensure that it can return a valid item; if yes, it returns that item, if no, it returns nil. You could always change that behaviour to one where an exception is raised if the Iterator has gone beyond the end of the List.

The only problem with the above code is that it will not work if the Iterator class is not in the same unit as the List class. This is because the CurrentItem method tries to access the protected GetItem method of the List class, which it cannot otherwise see.

In order to overcome this problem, the Iterator class should be regarded as a friend of the List class and allowed privileged access to the protected GetItem method of the list. This can be arranged in one of two ways: If it is envisaged that there will only be the need for one type of iterator, then the Iterator class can be placed in the same unit as the List class, thus allowing access to the non-public members of the List class. If there may be more than one type of Iterator for the List, then we can use a trick in Delphi that allows us to see the protected members of a class in another unit.

implementation
type

  TCustomerListFriend = class(TCustomerList)
  end;

  //...

  function TCustomerIterator.CurrentItem: TCustomer;
  begin
    if (fList <> nil) and ((fCurrentItem >= 0) and
       (fCurrentItem < fList.GetCount)) then
      Result := TCustomerListFriend(fList).GetItem(fCurrentItem)
    else
      Result := nil;
  end;

By declaring a ‘friend' class that derives from the TCustomerList class in the same unit as the Iterator, we bring any protected members of the TCustomerList class into the visibility of the Iterator class. All that is needed now is to alter the line that calls the GetItem method by typecasting the List to the derived class.

The Iterator class that we have just described can be created in one of two ways: If it is possible that more than one type of Iterator may be necessary, both the List and the Iterator could be created into local variables and the List passed to the constructor of the Iterator in the calling method:

  procedure TTest.PrintCustomers;
  var
    list: TCustomerList;
    iter: TCustomerIterator;
  begin
    list := TCustomerList.Create;
    try
      iter := TCustomerIterator.Create(list);
      try
        while iter.Next do
          WriteLn(iter.CurrentItem.Name);
      finally
        iter.Free;
      end;
    finally
      list.Free;
    end;
  end;

There is, however, an alternative way of creating the Iterator - from within the List itself. We need to add a method to the List class.

  TCustomerList = class
   //...
  public
   //...
    function GetIterator: TCustomerIterator;
  end;

implementation

  //...

  TCustomerList.GetIterator: TCustomerIterator;
  begin
    Result := TCustomerIterator.Create(self);
  end;

Or we could even change the Iterator class to accept a TObjectList as the parameter to the constructor and keep a reference to that for the Iterator to use instead of the Customer List; this would remove the need for the protected GetItem method in the List class, as the Iterator could use the indexed GetItem method of the TObjectList. But this would only work if you could guarantee that the internal list would always be a TObjectList and that the Iterator would be constructed inside the List class.

Using this method of asking the List for an Iterator gives us calling code like this:

  procedure TTest.PrintCustomers;
  var
    list: TCustomerList;
    iter: TCustomerIterator;
  begin
    list := TCustomerList.Create;
    try
      iter := list.GetIterator;
      try
        while iter.Next do
          WriteLn(iter.CurrentItem.Name);
      finally
        iter.Free;
      end;
    finally
      list.Free;
    end;
  end;

Creating the Iterator from within the list class also has other advantages; it will allow us to simplify the code internal to the List class and to provide more features.

  TCustomerList = class
    //...
  public
    //...
    function Contains(const Item: TCustomer): Boolean;
    procedure Assign(const Other: TCustomerList);
  end;

Without an Iterator, we would normally use an Integer ‘for' loop to implement the Contains method: 

  function TCustomerList.Contains(const Item: TCustomer): Boolean;
  var
    i: Integer;
  begin
    Result := False;
    for i := 0 to Pred(fItems.Count) do
      if fItems[i] = Item then
      begin
        Result := True;
        Break;
      end;
  end;

Now, we can replace that code with the iterator that we have just created:

  function TCustomerList.Contains(const Item: TCustomer): Boolean;
  var
    iter: TCustomerIterator;
  begin
    Result := False;
    iter := GetIterator;
    try
      while iter.Next and not Result do
        if iter.CurrentItem = Item then
          Result := True;
    finally
      iter.Free;
    end;
  end;

We can also use the Iterator to simplify the code required for assigning the contents of one list to another:

  procedure TCustomerList.Assign(const Other: TCustomerList);
  var
    iter: TCustomerIterator;
  begin
    Clear;
    iter := Other.GetIterator;
    try
      while iter.Next do
        Add(Iter.CurrentItem);
    finally
      iter.Free;
    end;
  end;

Skip Iterators

There are occasions when we may want to be selective in the items that we iterate over in a list. For example, we may only want to print out all Customers that have their Credit put on stop.

Using integer indexes we would have to write the code that selects those Customers in the calling routine.

  procedure TTest.PrintBadCustomers;
  var
    list: TCustomerList;
    i: Integer;
  begin
    list := TCustomerList.Create;
    try
      for i := 0 to Pred(list.Count) do
        if list[i].CreditStop then
          WriteLn(list[i].Name);
    finally
      list.Free;
    end;
  end;

But we can reuse our PrintCustomers routine almost without alteration by creating an Iterator that will only return bad Customers to the CurrentItem method.

  TBadCustomerIterator = class(TCustomerIterator)
    //...
  protected
    //...
    function Next: Boolean; override;
    //...
  end;

All we need to do is to override the Next method to implement any filtering that is required.

  function TBadCustomerIterator.Next: Boolean;
  begin
    repeat
      Result := inherited Next;
    until Result and CurrentItem.CreditStop.
  end;

  //...

  procedure TTest.PrintCustomers(Bad: Boolean);
  var
    list: TCustomerList;
    iter: TCustomerIterator;
  begin
    list := TCustomerList.Create;
    try
      if Bad then
        iter := TBadCustomerIterator.Create(list)
      else
        iter := TCustomerIterator.Create(list)
      try
        while iter.Next do
          WriteLn(iter.CurrentItem.Name);
      finally
        iter.Free;
      end;
    finally
      list.Free;
    end;
  end;

Traversing Trees

The following code is from an old project and is not meant to be fully comprehensible; it is just meant to show that iterators can be used with a tree structure that has no concept of Integer indexing. Each node uses an iterator to access its children and the main iterator traverses the tree using a pointer to the current node rather than an Integer.

type
  TTreeTopDownIterator = class
  public
    function CurrentItem: TTreeNode;
    function IsDone: Boolean;
    procedure Next;
    procedure Reset;
  end;

implementation

  //...

  procedure TTreeTopDownIterator.Next;
  var
    TestNode: TTreeNode;
  begin
    if fCurrentNode.IsLeaf then
    // there are no children
    begin
      if fCurrentNode = fRootNode then // there is only one node
        fCurrentNode := nil
      else
      begin
        TestNode := fCurrentNode.Parent;
        repeat
          // test for siblings
          TestNode.Children.Next;
          if TestNode.Children.IsDone then
 
          // no siblings found
          begin
            TestNode := TestNode.Parent;
            if TestNode = nil then

            // we are in root node
            begin
              fCurrentNode := nil;
              Break;
            end;
          end
          else
          // siblings found
          begin
            // move to next sibling
            fCurrentNode := TestNode.Children.CurrentNode;
            Break;
          end;
        // recurse up tree to find next node
        until (TestNode = fRootNode) and TestNode.Children.IsDone;
      end;
    end
    else
    // there are children
    begin
      fCurrentNode.Children.First;
      fCurrentNode := fCurrentNode.Children.CurrentNode;
    end;
  end;

This example uses the pattern of Iterator found in the GoF book; the only real differences between this style and the first one we looked at are: the next method is a procedure rather than a Boolean function, and there is an IsDone method to test for the end of the iteration. For those reasons the calling code is slightly different:

  var
    iter: TTreeTopDownIterator;
  begin
    iter := TTreeTopDownIterator.Create(aTree);
    while not iter.IsDone do
    begin
      WriteLn(iter.CurrentItem.Text);
      iter.Next;
    end;
  end;

Code examples

Java Iterator in Java: Before and after Iterator in Java
C++ Iterator in C++ Iterator in C++: Using operators instead of methods
PHP Iterator in PHP
Delphi Iterator in Delphi
Python Iterator in Python