The Iterator Pattern

Posted by on in Blogs

Introduction

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 listactually 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.

Enter 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 Customer List 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 Customer List 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 Customer List class in the same unit as the Iterator, we bring any protected members of the Customer List 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;



Comments

  • Guest
    Lionel Friday, 2 July 2004

    Good!

  • Guest
    Lee Grissom Thursday, 8 July 2004

    Is it possible to get back the iterator as an Interface to avoid the try..finally block? Would that be bad or good?

  • Guest
    Joanna Carter Friday, 9 July 2004

    The only time you will experience problems mixing object and interface references is with Delphi for Win32. However, in this case, there should be no problem as the GetIterator method is essentially a Factory Method. The Iterator as an interface would live for as long as needed and then become invalid at the end of the method it was used in.

  • Guest
    Ben Kalegin Monday, 12 July 2004

    Thank you Joanna, good article. I will recommend you following things:

    1. Follow naming patterns like Java has, for example, Next method usually returns object(like your method CurrentItem) and hasNext returns boolean

    2. IMHO it is not good idea to increment in .Next, this method can be additionally called for some purposes inside loop.

    3. You omit most exciting part of iterators: multithread synchronization patterns.

  • Guest
    Joanna Carter Monday, 12 July 2004

    Ben



    The article is aimed at Delphi including .NET and the patttern implementation is the same as that provided by the .NET framework. I know there are other signatures around, but that is for the reader to research.

    Multithreading iterators is a whole other subject; if you have experience with this that would work in Delphi, then why not post an article to BDN?

  • Guest
    Wilbert Tuesday, 27 July 2004

    Just a small point. I thought that the iterator was supposed to hold its own list of items rather than depending on the original list?



    The purpose of this would be



    while it.Next do

    CustomerList.Delete(it.CurrentItem);



    Which in your example would cause an index out of bounds.

  • Guest
    Joanna Carter Tuesday, 27 July 2004

    You would never normally use an Iterator for deletions unless you first created a List that contains the items to be deleted and then use the Iterator from that list to get the items to delete from the main list.



    My standard Iterator is attached as an Observer to the list and when the contents of the list changes the Iterator is automatically invalidated by setting it to the end of the list.

  • Guest
    Wilbert Wednesday, 28 July 2004

    > You would never normally use an Iterator for deletions



    I disagree with this point. I think that an iterator can be used to perform any operation on a list.





    > My standard Iterator is attached as an Observer to the list



    A re-evaluation every time the list changes could be very costly, especially when the structure is not linear (a tree or something).



    The GoF book says that it is too costly to duplicate the list of items, but I disagree, there would have to be a lot of items in that list to be of any severe consequence when you are simply holding pointers to objects.



    You could however write a ReverseOrderIterator.

  • Guest
    Joanna Carter Wednesday, 28 July 2004

    > A re-evaluation every time the list changes could

    > be very costly, especially when the structure is

    > not linear (a tree or something).



    The Observer Pattern does not re-evaluate the list it merely notifies the Iterator when a Deletion has occurred.



    > The GoF book says that it is too costly to

    > duplicate the list of items, but I disagree, there

    > would have to be a lot of items in that list to be

    > of any severe consequence when you are simply

    > holding pointers to objects.



    Duplicating the list is not the same as creating a list of references to items in an existing list. It involves creating a list of objects that are copies of the objects in the original list.



    > You could however write a ReverseOrderIterator.



    That's the beauty of Iterators:-)

  • Guest
    Marcos Barreto Sunday, 19 September 2004

    Could you post a sample deletion with iterators?

    Thanks!

  • Guest
    VitoJeng Monday, 18 October 2004

    Good article, Joanna!

  • Guest
    Stephen Melnyk Tuesday, 23 November 2004

    Thanks for the article, Joanna. I appreciate you taking the time to write it.



    Could you clarify one point for me? In the Skip Iterators section, you implement TBadCustomerIterator.Next with:



    repeat

    Result := inherited Next;

    until Result and CurrentItem.CreditStop



    Isn't this an infinite loop? The last item in the list is going to return False from the inherited Next.



    Stephen

  • Guest
    Shawn Stamps Sunday, 10 July 2005

    Yes, it is an infinite loop. The correct code would be:



    Repeat

    Result := inherited Next;

    Until Not Result Or Result And CurrentItem.CreditStop;



    I've coded that kind of error so many times that I usually catch it right after I type it in. ;)

  • Guest
    Jose Luis Saturday, 20 August 2005

    If I add the "friendly" class to be able to declare the iterator class into another unit separated from TCustomerList class, I would need to add into the TCustomerIterator unit the uses of the TCustomerList.

    Then, when I would like to add the GetIterator into the TCustomerList to create the iterator from withing the list ifself, am I going to have a circular reference?

  • Guest
    giulio Tuesday, 8 August 2006

    Why don't to add an implementation template using C# enerics? Anyway... very good! ;-)



    Bye,

    Giulio

  • Please login first in order for you to submit comments
  • Page :
  • 1

Check out more tips and tricks in this development video: