Johan Åhlgren

Iterating over a sequence using “for .. in”

The for .. in construct was added to Delphi 2005 and allows you to iterate over arrays, lists and other container objects. In this article I will show you how to implement a class that provides this capacity. I will also show you that you don’t have to pre-allocate values in an array, a list or in any other container object, but that you may generate them when the user actually requests them.

As an example, I will use the Fibonacci sequence which is a seqence of integers where each element is the sum of the previous two (1, 1, 2, 3, 5, 8, 13 etc.). This may not in itself be a very interesting case, but it makes it easy to illustrate the point. My goal with this article is to be able to write

for i in FibonacciNumbers(100) do
  WriteLn(i);

and see all numbers in the Fibonacci series that are smaller than 100.

Creating the enumerator

The first thing we need is an object that implements the actual iteration over the integers. We may create a class to do this, but I have chosen to use a record. As of Delphi 2006, records may have methods, which we will need in the enumerator. The reason I use a record here, is because I need only one enumerator per Fibonacci object, and by including a record variable, I don’t have to bother with allocating or freeing memory for the enumerator. Here is the code for the enumerator:

type
  TFibonacciEnumerator = record
  private
    MaxNumber: Integer;
    ThisNumber: Integer;
    LastNumber: Integer;
    SecondToLastNumber: Integer;
    function GetCurrent: Integer;
  public
    function MoveNext: Boolean;
    property Current: Integer read GetCurrent;
  end;
  
implementation

  function TFibonacciEnumerator.GetCurrent: Integer;
  begin
    Result := ThisNumber;
  end;
  
  function TFibonacciEnumerator.MoveNext: Boolean;
  begin
    if (ThisNumber = 0) then
      ThisNumber := 1
    else
    begin
      SecondToLastNumber := LastNumber;
      LastNumber := ThisNumber;
      ThisNumber := SecondToLastNumber + LastNumber;
    end;
    Result := (ThisNumber < MaxNumber) or (MaxNumber < 0);
  end;

An object that implements an enumerator must implement two methods: MoveNext() and Current(). MoveNext() moves to the next element in the list. It returns True if such an element exists, and False otherwise. When you call “for .. in”, this method is called first, which means that the first time, it should move to the first element. The Current() method returns the current element (the one previously selected using MoveNext).

In our case, we keep a variable, ThisNumber, which holds the current value. Each time the MoveNext method is called, it calculates the next number. It then returns True if the calculated number is smaller than the supplied max value, and False otherwise.

Creating the Fibonacci class

We also need the actual object, on which a user can ask for the enumerator, i.e. a class that will serve as a “container” for the enumerator. If you were to write an enumerator for a class that already holds values, that class would typically contain e.g. an array of values over which the enumerator will iterate, but in our case, the job of the “container class” is almost exclusively to supply the enumerator. The code for the TFibonacciNumbers class follows:

type
  IFibonacciNumbers = interface ['{642E6631-B8EA-4C6A-9003-6AE5257EDF5D}']
    function GetEnumerator: TFibonacciEnumerator;
  end;

  TFibonacciNumbers = class(TInterfacedObject, IFibonacciNumbers)
  protected
    Enumerator: TFibonacciEnumerator;
  public
    function GetEnumerator: TFibonacciEnumerator;
    constructor Create(MaxNumber: Integer);
  end;

implementation

constructor TFibonacciNumbers.Create(MaxNumber: Integer);
begin
  Enumerator.MaxNumber := MaxNumber;
  Enumerator.SecondToLastNumber := 0;
  Enumerator.LastNumber := 0;
  Enumerator.ThisNumber := 0;
end;

function TFibonacciNumbers.GetEnumerator: TFibonacciEnumerator;
begin
  Result := Enumerator;
end;

To support an enumerator, an object must implement a GetEnumerator() method, that returns an enumerator of the correct type – in our case a TFibonacciEnumerator object. When the object is created, all we have to do is initialize the enumerator. I have chosen to let TFibonacciNumbers implement an interface, and extend the TInterfacedObject class. This way, TFibonacciNumbers objects are automatically reference counted, and the memory they occupy will be released automatically when all references to them are removed. This means that I can write

for i in TFibonacciNumbers.Create(100) do
  WriteLn;

whereas I would otherwise have to write

fn := TFibonacciNumbers.Create(100);
try
  for i in fn do
    WriteLn;
finally
  fn.free;
end;

We are getting close to our original goal now. By adding one more method

function FibonacciNumbers(MaxNumber: Integer = -1): IFibonacciNumbers;
begin
  Result := TFibonacciNumbers.Create(MaxNumber);
end;

we can now write the simple code that was our goal all along:

for i in FibonacciNumbers(100) do
  WriteLn(i);

The complete source code is available here.

Leave a Reply

Your email address will not be published. Required fields are marked *