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
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'.
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 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
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.
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
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
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
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;
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;
Iterator, we would normally use an Integer ‘for' loop to implement the
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;
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
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;
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
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;