Mega Code Archive
Iterators
<![CDATA[
Title: Iterators
Question: How can I elegantly traverse a list?
Answer:
Iterators provide an elegant way to iterate lists and other data structures. For those in the know, Iterators are a Design Pattern (see [GAM95]). Design Patterns capture good practices of designing software systems. I strongly recommend reading this book.
In order to demonstrate the iterator pattern, I designed the following classes:
TMyItem = class
private
FValue: boolean;
FName: string;
public
property Name: string read FName write FName;
property Value: boolean read FValue write FValue;
end;
TMyListIterator = class
private
FList: TMyList;
FIndex: integer;
protected
constructor Create(List: TMyList);
public
procedure First;
procedure Next;
function IsDone: boolean;
function CurrentItem: TMyItem;
end;
TMyList = class
private
FList: TList;
function GetItem(Index: integer): TMyItem;
procedure SetItem(Index: integer; const Value: TMyItem);
function GetCount: integer;
public
constructor Create;
destructor Destroy; override;
procedure Add(Item: TMyItem);
procedure Delete(const Index: integer);
procedure Clear;
procedure Iterator(var Iter: TMyListIterator);
property Count: integer read GetCount;
property Items[Index: integer]: TMyItem read GetItem write SetItem; default;
end;
As you can see, the TMyList class is a simple type-safe list wrapper that has the capability of handing out an iterator to the client (the code which uses the list).
But how do we use the iterator? Lets take a look at the way we normally would traverse this list:
procedure OldFashioned;
var
i: integer;
item: TMyItem;
begin
for i := 0 to
item := FMyList[i];
Listbxo1.Items.Add(item.Name);
end;
end;
The problem with the above code is that we cannot see what is really happening. A for loop can have many meanings, for example adding some numbers. But we cannot judge from the mere existance of a for loop that the code traverses a list.
Enter iterator!
The same code fragment using an iterator looks like this:
procedure TheRightWay;
var
iter: TMyIterator;
item: TMyItem;
begin
FMyList.Iterator(Iter);
while not Iter.IsDone do begin
item := iter.CurrentItem;
Listbox1.Items.Add(item.Name);
Iter.Next;
end;
end;
We can judge from the presence of the iterator that this must be some code that traverses a list or some other structure. Those of you who already have used the FindFirst/FindNext functions will see the resemblance of this code fragment with the one used commonly to list the contents of a directory.
In my opinion, iterators are much easier to use than for loops once you understand them. One of their advantages is that you can write for example a reverse iterator that traverses the list in reverse order. If you do so, you won't have to chaneg the client code, since all the traversation logic is handled by the iterator.
Sample code:
///////////////////////////////
unit ListIterator;
///////////////////////////////
interface
uses Classes;
type
TMyItem = class;
TMyList = class;
TMyListIterator = class;
TMyItem = class
private
FValue: boolean;
FName: string;
public
property Name: string read FName write FName;
property Value: boolean read FValue write FValue;
end;
TMyListIterator = class
private
FList: TMyList;
FIndex: integer;
protected
constructor Create(List: TMyList);
public
procedure First;
procedure Next;
function IsDone: boolean;
function CurrentItem: TMyItem;
end;
TMyList = class
private
FList: TList;
function GetItem(Index: integer): TMyItem;
procedure SetItem(Index: integer; const Value: TMyItem);
function GetCount: integer;
public
constructor Create;
destructor Destroy; override;
procedure Add(Item: TMyItem);
procedure Delete(const Index: integer);
procedure Clear;
procedure Iterator(var Iter: TMyListIterator);
property Count: integer read GetCount;
property Items[Index: integer]: TMyItem read GetItem write SetItem; default;
end;
implementation
{ TMyListIterator }
constructor TMyListIterator.Create(List: TMyList);
begin
inherited Create;
FList := List;
FIndex := 0;
end;
procedure TMyListIterator.First;
begin
FIndex := 0;
end;
procedure TMyListIterator.Next;
begin
inc(FIndex);
end;
function TMyListIterator.IsDone: boolean;
begin
Result := FIndex = FList.Count;
end;
function TMyListIterator.CurrentItem: TMyItem;
begin
Result := nil;
if FIndex Result := FList[FIndex];
end;
{ TMyList }
constructor TMyList.Create;
begin
inherited Create;
FList := TList.Create;
end;
destructor TMyList.Destroy;
begin
FList.Free;
inherited;
end;
procedure TMyList.Add(Item: TMyItem);
begin
FList.Add(Item);
end;
procedure TMyList.Clear;
begin
FList.Clear;
end;
procedure TMyList.Delete(const Index: integer);
begin
FList.Delete(Index);
end;
function TMyList.GetCount: integer;
begin
Result := FList.Count;
end;
function TMyList.GetItem(Index: integer): TMyItem;
begin
Result := FList[Index];
end;
procedure TMyList.SetItem(Index: integer; const Value: TMyItem);
begin
if FList[Index] nil then
TMyItem(FList[Index]).Free;
FList[Index] := Value;
end;
procedure TMyList.Iterator(var Iter: TMyListIterator);
begin
Iter := TMyListIterator.Create(self);
end;
end.
///////////////////////////////
unit TestMain;
///////////////////////////////
interface
uses
Windows, Messages, SysUtils,
Classes, Graphics, Controls,
Forms, Dialogs, StdCtrls,
ListIterator;
type
TForm1 = class(TForm)
Button1: TButton;
Button2: TButton;
ListBox1: TListBox;
procedure Button1Click(Sender: TObject);
procedure Button2Click(Sender: TObject);
private
FMyList: TMyList;
public
end;
var
Form1: TForm1;
implementation
{$R *.DFM}
procedure TForm1.Button1Click(Sender: TObject);
var
item: TMyItem;
i: integer;
begin
if FMyList = nil then
FMyList := TMyList.Create;
for i := 0 to 10 do begin
item := TMyItem.Create;
item.Name := 'Test' + inttostr(i);
item.Value := true;
FMyList.Add(item);
end;
end;
procedure TForm1.Button2Click(Sender: TObject);
var
iter: TMyListIterator;
item: TMyItem;
begin
FMyList.Iterator(Iter);
while not Iter.IsDone do begin
item := iter.CurrentItem;
Listbox1.Items.Add(item.Name);
Iter.Next;
end;
end;
end.
References:
[GAM95] Gamma, Erich; Helm, Richard; Johnson, Ralph; Vlissides, John: Design Patterns - Elements of Reusable Object-Oriented Software. Reading, MA: Addison-Wesley, 1995
]]>