In earlier parts of this material (Section 31.6 and Section 45.2) we have at length discussed enumerators in C#, including their relationship to foreach loops.

In this section we first briefly rephrase this to the design pattern known as Iterator. Following that we will show how to implement iterators (enumerators) with use of yield return, which is a variant of the return statement.

48.1 The Iterator Design Pattern 48.2 Making iterators with yield return

 

48.1.  The Iterator Design Pattern
Contents   Up Previous Next   Slide Annotated slide Aggregated slides    Subject index Program index Exercise index 

The Iterator design pattern provides sequential access to an aggregated collection. At an overall level, an iterator

Provides for a smaller client interface of the collection class All members associated with traversals have been refactored to the iterator class Makes it possible to have several simultaneous traversals Does not reveal the internal representation of the collection

As we have seen in Section 31.6 and Section 45.2, traversal of a collection requires a few related operations, such as Current, MoveNext, and Reset. We could imagine a slightly more advanced iterator which could move backwards as well. With use of iterators we have factored these operations out of the collection classes, and organized them in iterators (enumerators). With this refactoring, a collection can be asked to deliver an iterator:

   aCollection.GetEnumerator()

Each iterator maintains the state, which is necessary to carry out a traversal of a collection. If we need two independent, simultaneous traversals we can ask for two iterators of the collections. This could, for instance be used to manage simultaneous iteration from both ends of a list.

In more primitive collections, such as linked lists (see Section 45.14) it is necessary to reveal the object structure that keeps the list together. (In LinkedList<T> this relates to the details of LinkedListNode<T> instances). With use of iterators it is not necessary to reveal such details. An iterator is an encapsulated, abstract representation of some state that manages a traversal. The concrete representation of this state is not leaked to clients. This is very satisfactory in an object-oriented programming context.

Iterators (enumerators) are typically used via foreach loops. As an alternative, it is of course also possible to use the operations in the IEnumerator interface directly to carry out traversals. Exercise 12.4 is a opportunity to train such a more direct use of iterators.

48.2.  Making iterators with yield return
Contents   Up Previous Next   Slide Annotated slide Aggregated slides    Subject index Program index Exercise index 

In this section we will show how to use the special-purpose yield return statement to define iterators, or as they are called in C#, enumerators. First, we will program a very simple collection of up to three, fixed values. Next we will revisit the integer sequence enumeration, which can be found in Section 58.3.

In Program 48.1 we will program a collection class, called GivenCollection, which just covers zero, one, two or three values of some arbitrary type T. As a simpleminded approach, we represent these T values with three instance variables of type T, and with three boolean variables which tells if the corresponding T values are present. As an invariant, the instance variables are filled from the lower end. It would be tempting to use the type T? instead of T, and the value null for a missing value. But this is not possible if T is class.

It is important that the class GivenCollection implements the generic interface IEnumerable<T>. Because this interface, in turn, implements the non-generic IEnumerable, we must both define the generic and the non-generic GetEnumerator method. The latter must be defined as an explicit interface (see Section 31.8), in order not to conflict with the former. If we forget the non-generic GetEnumerator, we get a slightly misleading error message:

'GivenCollection<T>' does not implement interface member 'System.Collections.IEnumerable.GetEnumerator()'.
'GivenCollection<T>' is either static, not public, or has the wrong return type.

This message can cause a lot of headache, because the real problem (the missing, non-generic GetEnumerator method) is slightly camouflaged in the error message.

The implementation of the non-generic enumerator just delegates its work to the generic version.

The implementation of the generic Enumerator method uses the yield return statement. Let us assume that an instance of GivenCollection<T> holds three T values (in first, second, and third). The three boolean variables firstDefined, secondDefined, and thirdDefined are all true. The GetEnumerator method has three yield return statements in sequence (see line 50-52). By means of these, GetEnumerator can return three values before it is done. This is entirely different from a normal method, which only returns once (after which it is done). The GetEnumerator in class GivenCollection acts as a coroutine in relation to its calling place (which is the foreach statement in the client program Program 48.2). A coroutine can resume execution at the place where execution stopped in an earlier call. A normal method always (re)starts from its first statement each time it is called.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

using System;
using System.Collections.Generic;
using System.Collections;

public class GivenCollection<T> : IEnumerable<T>{
 
  private T first, second, third;
  private bool firstDefined, secondDefined, thirdDefined;
 
  public GivenCollection(){
    this.firstDefined = false; 
    this.secondDefined = false;
    this.thirdDefined = false; 
  }

  public GivenCollection(T first){
    this.first = first; 
    this.firstDefined = true;
    this.secondDefined = false;
    this.thirdDefined = false; 
  }

  public GivenCollection(T first, T second){
    this.first = first;
    this.second = second; 
    this.firstDefined = true;
    this.secondDefined = true;
    this.thirdDefined = false; 
  }

  public GivenCollection(T first, T second, T third){
    this.first = first;
    this.second = second;
    this.third = third;
    this.firstDefined = true;
    this.secondDefined = true;
    this.thirdDefined = true; 
  }

  public int Count(){
    int res;
    if (!firstDefined) res = 0;
    else if (!secondDefined) res = 1;
    else if (!thirdDefined) res = 2;
    else res = 3;
    return res;
  }

  public IEnumerator<T> GetEnumerator(){
    if (firstDefined) yield return first;
    if (secondDefined) yield return second;  // not else
    if (thirdDefined) yield return third;    // not else
  }

  IEnumerator IEnumerable.GetEnumerator(){
    return GetEnumerator();
  }

}

In Program 48.2 we show a simple program that instantiates a GivenCollection of the integers 7, 5, and 3. The foreach loop in line 11-12 traverses the three corresponding instance variables, and prints each of them.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

using System;

class Client{

  public static void Main(){

     GivenCollection<int> gc = new GivenCollection<int>(7,5,3);

     Console.WriteLine("Number of elements in givenCollection: {0}", 
                        gc.Count());
     foreach(int i in gc){      // Output:  7 5 3
       Console.WriteLine(i); 
     }

  }

}

Let us now revisit the integer enumeration classes of Section 58.3. The main point in our first discussion of these classes was the Composite design pattern, cf. Section 32.1, as illustrated in Figure 58.1 of Section 58.3. The three classes IntInterval, IntSingular, and IntCompSeq all inherit the abstract class IntSequece. You can examine the abstract class IntSequence in Program 58.9 in the appendix of this material. The three concrete subclasses were programmed in Program 58.10, Program 58.11, and Program 58.12.

The GetEnumerator methods of IntInterval, IntSingular, and IntCompSeq are all emphasized below in Program 48.3, Program 48.4, and Program 48.5. Notice the use of yield return in all of them.

In Program 48.3 the if-else of GetEnumerator in line 19-24 distinguishes between increasing and decreasing intervals. The GetEnumerator method of IntSingular is trivial. The GetEnumerator method of IntCompSeq in Program 48.5 is surprisingly simple - at least compared with the counterpart in Program 58.12. The two foreach statements (in sequence) in line 19-22 activate all the machinery, which we programmed manually in Program 58.12. This includes recursive access to enumerators of composite sequences.

The simplicity of enumerators, programmed with yield return, is noteworthy compared to all the underlying stuff of explicitly programmed classes that implement the interface IEnumerator.

Iterators (iterator blocks), programmed with yield return, are only allowed to appear in methods that implement an enumerator or an enumerable interface (such as IEnumerator or IEnumerator or their generic counterparts). Such methods are handled in a very special way by the compiler, and a number of restrictions apply to these methods. The compiler generates all the machinery, which we program ourselves when a class implements the enumerator or enumerable interfaces. Methods with iterator blocks that implement an enumerator or an enumerable interface return an enumerator object, on which the MoveNext can be called a number of times. For more details on iterators please consult Section 10.14 in the C# 3.0 Language Specification [csharp-3-spec].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

public class IntInterval: IntSequence{

  private int from, to;

  public IntInterval(int from, int to){
    this.from = from;
    this.to = to;
  }

  public override int? Min{
    get {return Math.Min(from,to);}
  }

  public override int? Max{
    get {return Math.Max(from,to);}
  }
    
  public override IEnumerator GetEnumerator (){
    if (from < to)
     for(int i = from; i <= to; i++)
       yield return i;
    else
     for(int i = from; i >= to; i--)
       yield return i;
  }

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

public class IntSingular: IntSequence{

  private int it;

  public IntSingular(int it){
    this.it = it;
  }

  public override int? Min{
    get {return it;}
  }

  public override int? Max{
    get {return it;}
  }

  public override IEnumerator GetEnumerator(){
    yield return it;
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

public class IntCompSeq: IntSequence{

  private IntSequence s1, s2;

  public IntCompSeq(IntSequence s1, IntSequence s2) {
    this.s1 = s1;
    this.s2 = s2;
  }

  public override int? Min{
    get {return (s1.Min < s2.Min) ? s1.Min : s2.Min;}
  }

  public override int? Max{
    get {return (s1.Max > s2.Max) ? s1.Max : s2.Max;}
  }

  public override IEnumerator GetEnumerator (){
    foreach(int i in s1)
      yield return i;
    foreach(int i in s2)
      yield return i;
  }

}

An application of integer sequences and the corresponding program output is shown in Program 48.6 and Listing 48.7 respectively.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

using System;

class SeqApp {

  public static void Main(){

    IntSequence isq1 = 
      new IntCompSeq(
            new IntCompSeq(
              new IntInterval(3,5), new IntSingular(17) ),
            new IntCompSeq(
              new IntInterval(12,7), new IntSingular(29) ) );

    IntSequence isq2 = 
      new IntCompSeq(
         new IntCompSeq(
           new IntInterval(3,3),
           new IntCompSeq(new IntInterval(1,5), new IntInterval(15,20))),
         new IntCompSeq(
           new IntCompSeq(new IntInterval(-1,-5), new IntInterval(-15,-20)),
           new IntInterval(12,7)));

    Console.WriteLine("Min: {0} Max: {1}", isq1.Min, isq1.Max);
    Console.WriteLine("Min: {0} Max: {1}", isq2.Min, isq2.Max);

    foreach(int i in isq1)
      Console.Write("{0,4}", i);

    Console.WriteLine();

    foreach(int i in isq2)
      Console.Write("{0,4}", i);
  }

}

1
2
3
4

Min: 3 Max: 29
Min: -20 Max: 20
   3   4   5  17  12  11  10   9   8   7  29
   3   1   2   3   4   5  15  16  17  18  19  20  -1  -2  -3  -4  -5 -15 -16 -17 -18 -19 -20  12  11  10   9   8   7