for-in loop

From Lazarus wiki
Jump to navigationJump to search

"for-in" loop exists in delphi starting from 2005 version.

Delphi implementation

It has the next syntax:

String loop

<delphi> procedure StringLoop(S: String); var

 C: Char;

begin

 for C in S do
   DoSomething(C);

end; </delphi>

Array loop

<delphi> procedure ArrayLoop(A: Array of Byte); var

 B: Byte;

begin

 for B in A do
   DoSomething(B);

end; </delphi>

Set loop

<delphi> type

 TColor = (cRed, cGren, cBlue);
 TColors = set of TColor;

procedure SetLoop(Colors: TColors); var

 Color: TColor;

begin

 for Color in Colors do
   DoSomething(Color);

end; </delphi>

Traversing container

To traverse some container class you need to add an enumerator for it. Enumerator is a class built by the next template:

<delphi> TSomeEnumerator = class public

 function MoveNext: Boolean;
 property Current: TSomeType;

end; </delphi>

There are only 2 things required for the enumerator: MoveNext method which asks enumerator to step forward and property Current which can return any desired type.

Next thing is to add magic GetEnumerator method to the container class which returns an enumerator instance.

For example: <delphi> type

 TEnumerableTree = class;
 TTreeEnumerator = class
 private
   FTree: TEnumerableTree;
   FCurrent: TNode;
 public
   constructor Create(ATree: TEnumerableTree); 
   function MoveNext: Boolean;
   property Current: TNode read FCurrent;
 end;
 TEnumerableTree = class
 public
   function GetEnumerator: TTreeEnumerator;
 end;

constructor TTreeEnumerator.Create(ATree: TEnumerableTree); begin

 inherited Create;
 FTree := ATree;
 FCurrent := nil;

end;

function TTreeEnumerator.MoveNext: Boolean; begin

 // some logic to get the next node from a tree
 if FCurrent = nil then
   FCurrent := FTree.GetFirstNode
 else
   FCurrent := FTree.GetNextNode(FCurrent);
 Result := FCurrent <> FTree.GetLastNode;

end;

function TEnumerableTree.GetEnumerator: TTreeEnumerator; begin

 Result := TTreeEnumerator.Create(Self);

end;

</delphi>

After this you are able to execute the next code:

<delphi> procedure TreeLoop(ATree: TEnumerableTree); var

 ANode: TNode;

begin

 for ANode in ATree do
   DoSomething(ANode);

end; </delphi>

Of course enumerator support is built into the basic classes: TList, TStrings, TCollection, TComponent, ...

For-in loop can be easily translated into the while loop. Two next examples doing same things:

Example 1. <delphi> procedure TraverseStrings(AStrings: TStrings); var

 S: String;

begin

 for S in AStrings do
   DoSomething(S);

end; </delphi>

Example 2. <delphi> procedure TraverseStrings(AStrings: TStrings); var

 S: String;
 Enumerator: TStringsEnumerator;

begin

 Enumerator := AStrings.GetEnumerator;
 while Enumerator.MoveNext do
   DoSomething(Enumerator.Current);

end; </delphi>

It is also possible to make some class enumerable if you implement the next interface for the container: <delphi>

 IEnumerable = interface(IInterface)
   function GetEnumerator: IEnumerator;
 end;

</delphi>

Where IEnumerator is declared as: <delphi>

 IEnumerator = interface(IInterface)
   function GetCurrent: TObject;
   function MoveNext: Boolean;
   procedure Reset;
   property Current: TObject read GetCurrent;
 end;

</delphi>

Proposed extensions

The following examples are not supported by Delphi, and proposed for FPC mode only.

Traverse enumerations and ranges

In Delphi, it is impossible to traverse neither enumerated nor ranged type:

<delphi> type

 TColor = (clRed, clBlue, clBlack);

var

 Color: TColor;
 ch: Char;

begin

 for Color in TColor do
   DoSomething(Color);
 for ch in 'a'..'z' do
   DoSomethingOther(ch);

end. </delphi> Note: the case of ranged type is probably invalid, because 'a'..'z' notation defines a separate type which is distinct from char. It is the same reason for which expressions like function foo(arg: 'a'..'z') are forbidden in Pascal.

Although you can traverse a set. So the next code is valid even in Delphi: <delphi> type

 TColor = (clRed, clBlue, clBlack);

var

 Color: TColor;

begin

 for Color in [clRed..clBlack] do
   DoSomething(Color);

end. </delphi>

Add enumerators to the already defined types and classes

It is also not possible to add an enumerator without modifying the class, as well as add enumerator to non-class type. It is proposed to allow this by adding new operator type GetEnumerator. Like in the next example:

<delphi> type

 TMyRecord = record F1: Integer; F2: array of TMyType; end;
 TMyArrayEnumerator = class
   constructor Create(const A: TMyRecord);
   function Current: TMyType;
   function MoveNext: Boolean;
 end;
 // This is new built-in operator.
 operator GetEnumerator(const A: TMyRecord): TMyArrayEnumerator;
 begin
   Result := TMyArrayEnumerator.Create(A);
 end;

var

 A: MyRecord;
 V: TMyType

begin

 for V in A do
   DoSomething(V);

end. </delphi>

As a particularly useful example, the above extension would allow to traverse UTF-8 strings efficiently:

<delphi> type

 TUTF8StringEnumerator = class
 private
   FByteIndex: Integer;
   FCharIndex: Integer;
 public
   constructor Create(const A: UTF8String);
   function Current: UTF8Char;
   function MoveNext: Boolean;
 end;
 operator GetEnumerator(A: UF8String): TUF8StringEnumerator;
 begin
   Result := TUF8String.Create(A);
 end;

var

 s: UF8String;
 ch: UF8Char;
 i: Integer;

begin

 // This requires O(N^2) operations
 for i := 1 to Length(s) do
   DoSomething(ch[i]);
 // This requires only O(N) operations
 for ch in s do
   DoSomething(ch);

end. </delphi>

Select which enumerator to use

It is impossible to choose among different possible enumerators. For example you can traverse a tree using different orders. The well known algorithms are: preorder, postorder, inorder and breadth‑first traversals. Therefore it would be useful to have an ability to choose an enumerator. For example using the following syntax:

<delphi> type

 TTreeEnumeratorType = (tePreOrder, tePostOrder, teInOrder, teBreadthFirst)

procedure TraverseTree(Tree: TTree); var

 Node: TNode;

begin

 // Variant1. For the class instances we can call the method Tree.GetEnumerator(teInOrder). 
 // For the classes we can call a class method
 for Node in Tree using GetEnumerator(teInOrder) do
   Dosomething(Node);
 // Variant2. Or we can call the global function
 for Node in Tree using GetEnumerator(Tree, teInOrder) do
   Dosomething(Node);
 // Variant3. In the previous variant 'in Tree' is useless so the next code is a simplified form:
 for Node using GetEnumerator(Tree, teInOrder) do
   Dosomething(Node);
 // Variant4. We can try to avoid new context key-word 'using' by calling method:
 for Node in Tree.GetSomeEnumerator(teInOrder) do
   Dosomething(Node);
 // but this brings ambiguity to the compiler since Tree.GetSomeEnumerator(teInOrder) can be translated into
 // Tree.GetSomeEnumerator(teInOrder).GetEnumerator
 // This ambiguity might be resolvable by checking whether the class implements IEnumerator interface

end;

// for basic type we will call only the apropriate function procedure TraverseString(S: String); var

 C: Char;

begin

 for C in S using GetReverseStringEnumerator(S) do
   DoSomething(C);

end; </delphi>

Get enumerator Position if available

Finally, it is impossible to extract any information from the iterator except the current item. Sometimes other data, such as current index, may be useful:

<delphi> type

 TUTF8StringEnumerator = class
 private
   FByteIndex: Integer;
   FCharIndex: Integer;
 public
   constructor Create(const A: UTF8String);
   function Current: UTF8Char;
   function CurrentIndex: Integer;
   function MoveNext: Boolean;
 end;
 operator GetEnumerator(A: UF8String): TUF8StringEnumerator;
 begin
   Result := TUF8String.Create(A);
 end;

var

 s: UF8String;
 ch: UF8Char;
 i: Integer;

begin

 // Inefficient, as discussed above
 for i := 1 to Length(s) do
   Writeln(i, ': ', ch[i]);
 // Ok, but ugly
 i := 1;
 for ch in s do begin
   Writeln(i, ': ', ch);
   Inc(i);
 end;
 // Proposed extension
 for ch in s index i do
   Writeln(i, ': ', ch);

end. </delphi>

Note that index might return arbitrary type, not necessarily integer. For example, in the case of tree traversal, the index might return an array of nodes from on the path from the tree root to the current node.

Proposed implementation

1. Generic for-in loop implementation for enumerations translates for-in loop into the for-to loop: <delphi> for Color in TColor do => for Color := Low(TColor) to High(TColor) do </delphi>

2. Generic for-in loop implementation for string expressions creates an internal block of statements:

- create temp for-loop counter variable
- create a for-loop body as a merge of:
   - loopvariable := string_expression[temp for-loop counter]
   - actual for-in loop body statements
- create an internal for-loop with 1, length(string_expression) bounds
- delete temp for-loop counter

3. Generic for-in loop implementation for array expressions implements things simiar to for-in loop for strings but uses low(array_expression), high(array_expression) for the internal for-loop bounds

4. Generic for-in loop implementation for sets: todo.
5. Implementation for container classes is also a translation into the while loop: <delphi> for Color in ColorList do => Enumerator := <find enumerator>; try

 while Enumerator.MoveNext do begin
    Color := Enumerator.Current;
    // body
 end;

finally

 Enumerator.Free;

end; </delphi > 'Enumerator := <find enumerator>;' consists of the next steps:

  • check if particular enumerator is requested
  • if not then search for available operator
  • if not found then search for GetEnumerator method

Reference