• Provide a way to access the elements of an aggregate object sequentially without exposing its underlying representation.
• The C++ and Java standard library abstraction that makes it possible to decouple collection classes and algorithms.
• Promote to “full object status” the traversal of a collection.
• Polymorphic traversal

Problem

Need to “abstract” the traversal of wildly different data structures so that algorithms can be defined that are capable of interfacing with each transparently.

Discussion

“An aggregate object such as a list should give you a way to access its elements without exposing its internal structure. Moreover, you might want to traverse the list in different ways, depending on what you need to accomplish. But you probably don’t want to bloat the List interface with operations for different traversals, even if you could anticipate the ones you’ll require. You might also need to have more than one traversal pending on the same list.” And, providing a uniform interface for traversing many types of aggregate objects (i.e. polymorphic iteration) might be valuable.

The Iterator pattern lets you do all this. The key idea is to take the responsibility for access and traversal out of the aggregate object and put it into an Iterator object that defines a standard traversal protocol.

The Iterator abstraction is fundamental to an emerging technology called “generic programming”. This strategy seeks to explicitly separate the notion of “algorithm” from that of “data structure”. The motivation is to: promote component-based development, boost productivity, and reduce configuration management.

As an example, if you wanted to support four data structures (array, binary tree, linked list, and hash table) and three algorithms (sort, find, and merge), a traditional approach would require four times three permutations to develop and maintain. Whereas, a generic programming approach would only require four plus three configuration items.

Structure

The Client uses the Collection class’ public interface directly. But access to the Collection’s elements is encapsulated behind the additional level of abstraction called Iterator. Each Collection derived class knows which Iterator derived class to create and return. After that, the Client relies on the interface defined in the Iterator base class.

Example

The Iterator provides ways to access elements of an aggregate object sequentially without exposing the underlying structure of the object. Files are aggregate objects. In office settings where access to files is made through administrative or secretarial staff, the Iterator pattern is demonstrated with the secretary acting as the Iterator. Several television comedy skits have been developed around the premise of an executive trying to understand the secretary’s filing system. To the executive, the filing system is confusing and illogical, but the secretary is able to access files quickly and efficiently.

On early television sets, a dial was used to change channels. When channel surfing, the viewer was required to move the dial through each channel position, regardless of whether or not that channel had reception. On modern television sets, a next and previous button are used. When the viewer selects the “next” button, the next tuned channel will be displayed. Consider watching television in a hotel room in a strange city. When surfing through channels, the channel number is not important, but the programming is. If the programming on one channel is not of interest, the viewer can request the next channel, without knowing its number.

Check list

1. Add a create_iterator() method to the “collection” class, and grant the “iterator” class privileged access.
2. Design an “iterator” class that can encapsulate traversal of the “collection” class.
3. Clients ask the collection object to create an iterator object.
4. Clients use the first(), is_done(), next(), and current_item() protocol to access the elements of the collection class.

Rules of thumb

• The abstract syntax tree of Interpreter is a Composite (therefore Iterator and Visitor are also applicable).
• Iterator can traverse a Composite. Visitor can apply an operation over a Composite.
• Polymorphic Iterators rely on Factory Methods to instantiate the appropriate Iterator subclass.
• Memento is often used in conjunction with Iterator. An Iterator can use a Memento to capture the state of an iteration. The Iterator stores the Memento internally.

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

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

  1: TCustomerList = class

  2: private

  3:   fItems: TObjectList;

  4: public

  5:   procedure Add(const Item: TCustomer);

  6:   procedure Insert(const Item, Before: TCustomer);

  7:   procedure Insert(Idx: Integer; const Item: TCustomer);

  8:   procedure Delete(Idx: Integer);

  9:   procedure Remove(const Item: TCustomer);

 10:   procedure Clear;

 11:   function Contains(const Item: TCustomer): Boolean;

 12:   function GetCount: Integer;

 13:   function GetItem(Idx: Integer): TCustomer;

 14: end;

 15: 

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:

  1: TCustomerList = class

  2: private

  3:   fItems: TObjectList;

  4: protected

  5:   function GetItem(Idx: Integer): TCustomer;

  6: public

  7:   procedure Add(const Item: TCustomer);

  8:   procedure Insert(const Item, Before: TCustomer);

  9:   procedure Remove(const Item: TCustomer);

 10:   procedure Clear;

 11:   function Contains(const Item: TCustomer): Boolean;

 12:   function GetCount: Integer;

 13: 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.

  1:   TCustomerIterator = class

  2:   private

  3:     fList: TCustomerList;

  4:     fCurrentItem: Integer;

  5:   protected

  6:     procedure Reset;

  7:     function Next: Boolean; virtual;

  8:     function CurrentItem: TCustomer;

  9:   public

 10:     constructor Create(const List: TCustomerList);

 11:   end;

 12: 

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.

  1: implementation

  2:   constructor TCustomerIterator.Create(const List: TCustomerList);

  3:   begin

  4:     inherited Create;

  5:     fList := List;

  6:     Reset;

  7:   end;

  8: 

  9:   procedure TCustomerIterator.Reset;

 10:   begin

 11:     fCurrentItem := -1;

 12:   end;

 13: 

 14:   function TCustomerIterator.Next: Boolean;

 15:   begin

 16:     Result := (fList <> nil) and

 17:               (fCurrentItem < (fList.GetCount - 1));

 18:     if Result then

 19:       Inc(fCurrentItem);

 20:   end;

 21: 

 22:   function TCustomerIterator.CurrentItem: TCustomer;

 23:   begin

 24:     if (fList <> nil) and ((fCurrentItem >= 0) and

 25:        (fCurrentItem < fList.GetCount)) then

 26:     Result := fList.GetItem(fCurrentItem)

 27:   else

 28:     Result := nil;

 29:   end;

 30: 

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.

  1: implementation

  2: type

  3:   TCustomerListFriend = class(TCustomerList)

  4:   end;

  5:   //...

  6:   function TCustomerIterator.CurrentItem: TCustomer;

  7:   begin

  8:     if (fList <> nil) and ((fCurrentItem >= 0) and

  9:        (fCurrentItem < fList.GetCount)) then

 10:       Result := TCustomerListFriend(fList).GetItem(fCurrentItem)

 11:     else

 12:       Result := nil;

 13:   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:

  1: procedure TTest.PrintCustomers;

  2:   var

  3:     list: TCustomerList;

  4:     iter: TCustomerIterator;

  5:   begin

  6:     list := TCustomerList.Create;

  7:     try

  8:       iter := TCustomerIterator.Create(list);

  9:       try

 10:         while iter.Next do

 11:           WriteLn(iter.CurrentItem.Name);

 12:       finally

 13:         iter.Free;

 14:       end;

 15:     finally

 16:       list.Free;

 17:     end;

 18:   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.

  1: TCustomerList = class

  2:    //...

  3:   public

  4:    //...

  5:     function GetIterator: TCustomerIterator;

  6:   end;

  7: 

  8: implementation

  9: 

 10:   //...

 11: 

 12:   TCustomerList.GetIterator: TCustomerIterator;

 13:   begin

 14:     Result := TCustomerIterator.Create(self);

 15:   end;

 16: 

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:

  1: procedure TTest.PrintCustomers;

  2:   var

  3:     list: TCustomerList;

  4:     iter: TCustomerIterator;

  5:   begin

  6:     list := TCustomerList.Create;

  7:     try

  8:       iter := list.GetIterator;

  9:       try

 10:         while iter.Next do

 11:           WriteLn(iter.CurrentItem.Name);

 12:       finally

 13:         iter.Free;

 14:       end;

 15:     finally

 16:       list.Free;

 17:     end;

 18:   end;

 19: 

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.

  1: TCustomerList = class

  2:     //...

  3:   public

  4:     //...

  5:     function Contains(const Item: TCustomer): Boolean;

  6:     procedure Assign(const Other: TCustomerList);

  7:   end;

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

  1:   function TCustomerList.Contains(const Item: TCustomer): Boolean;

  2:   var

  3:     i: Integer;

  4:   begin

  5:     Result := False;

  6:     for i := 0 to Pred(fItems.Count) do

  7:       if fItems[i] = Item then

  8:       begin

  9:         Result := True;

 10:         Break;

 11:       end;

 12:   end;

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

  1:   function TCustomerList.Contains(const Item: TCustomer): Boolean;

  2:   var

  3:     iter: TCustomerIterator;

  4:   begin

  5:     Result := False;

  6:     iter := GetIterator;

  7:     try

  8:       while iter.Next and not Result do

  9:         if iter.CurrentItem = Item then

 10:           Result := True;

 11:     finally

 12:       iter.Free;

 13:     end;

 14:   end;

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

  1:   procedure TCustomerList.Assign(const Other: TCustomerList);

  2:   var

  3:     iter: TCustomerIterator;

  4:   begin

  5:     Clear;

  6:     iter := Other.GetIterator;

  7:     try

  8:       while iter.Next do

  9:         Add(Iter.CurrentItem);

 10:     finally

 11:       iter.Free;

 12:     end;

 13:   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.

  1: procedure TTest.PrintBadCustomers;

  2:   var

  3:     list: TCustomerList;

  4:     i: Integer;

  5:   begin

  6:     list := TCustomerList.Create;

  7:     try

  8:       for i := 0 to Pred(list.Count) do

  9:         if list[i].CreditStop then

 10:           WriteLn(list[i].Name);

 11:     finally

 12:       list.Free;

 13:     end;

 14:   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.

  1:   TBadCustomerIterator = class(TCustomerIterator)

  2:     //...

  3:   protected

  4:     //...

  5:     function Next: Boolean; override;

  6:     //...

  7:   end;

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

  1:   function TBadCustomerIterator.Next: Boolean;

  2:   begin

  3:     repeat

  4:       Result := inherited Next;

  5:     until Result and CurrentItem.CreditStop.

  6:   end;

  7: 

  8:   //...

  9: 

 10:   procedure TTest.PrintCustomers(Bad: Boolean);

 11:   var

 12:     list: TCustomerList;

 13:     iter: TCustomerIterator;

 14:   begin

 15:     list := TCustomerList.Create;

 16:     try

 17:       if Bad then

 18:         iter := TBadCustomerIterator.Create(list)

 19:       else

 20:         iter := TCustomerIterator.Create(list)

 21:       try

 22:         while iter.Next do

 23:           WriteLn(iter.CurrentItem.Name);

 24:       finally

 25:         iter.Free;

 26:       end;

 27:     finally

 28:       list.Free;

 29:     end;

 30:   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.

  1: 

  2: 

  3: type

  4:   TTreeTopDownIterator = class

  5:   public

  6:     function CurrentItem: TTreeNode;

  7:     function IsDone: Boolean;

  8:     procedure Next;

  9:     procedure Reset;

 10:   end;

 11: 

 12: implementation

 13: 

 14:   //...

 15: 

 16:   procedure TTreeTopDownIterator.Next;

 17:   var

 18:     TestNode: TTreeNode;

 19:   begin

 20:     if fCurrentNode.IsLeaf then

 21:     // there are no children

 22:     begin

 23:       if fCurrentNode = fRootNode then // there is only one node

 24:         fCurrentNode := nil

 25:       else

 26:       begin

 27:         TestNode := fCurrentNode.Parent;

 28:         repeat

 29:           // test for siblings

 30:           TestNode.Children.Next;

 31:           if TestNode.Children.IsDone then

 32:  

 33:           // no siblings found

 34:           begin

 35:             TestNode := TestNode.Parent;

 36:             if TestNode = nil then

 37: 

 38:             // we are in root node

 39:             begin

 40:               fCurrentNode := nil;

 41:               Break;

 42:             end;

 43:           end

 44:           else

 45:           // siblings found

 46:           begin

 47:             // move to next sibling

 48:             fCurrentNode := TestNode.Children.CurrentNode;

 49:             Break;

 50:           end;

 51:         // recurse up tree to find next node

 52:         until (TestNode = fRootNode) and TestNode.Children.IsDone;

 53:       end;

 54:     end

 55:     else

 56:     // there are children

 57:     begin

 58:       fCurrentNode.Children.First;

 59:       fCurrentNode := fCurrentNode.Children.CurrentNode;

 60:     end;

 61:   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:

  1:   var

  2:     iter: TTreeTopDownIterator;

  3:   begin

  4:     iter := TTreeTopDownIterator.Create(aTree);

  5:     while not iter.IsDone do

  6:     begin

  7:       WriteLn(iter.CurrentItem.Text);

  8:       iter.Next;

  9:     end;

 10:   end;