Iterators

Iterators implement the enumerator pattern. This chapter has demonstrated different implementation strategies for enumerators. The chosen implementation depends on the answer to relevant questions. Should the enumerator be implemented as a nested class? Should a version collection be used? Should the implementation be generic or nongeneric? Having every developer answer these questions and author a proprietary enumerator is not a productive use of their collective mental prowess. Almost assuredly, the various implementations of the enumerator pattern are within an acceptable delta in performance and memory requirements. Anyway, a certain number of developers simply visit the MSDN Web site, from which they copy and paste the enumerator implementation. Therefore, the various implementations are undoubtedly quite similar. Iterators standardize the enumerator pattern for developers.

When implementing enumerators ourselves, the real challenge is complex enumerations. As shown, forward iterations are usually straightforward. Reverse iterations are more complex, however. Coding an enumerator to iterate a sparse collection, nodal list, or binary tree can also be daunting. What about enumerating a temporary collection? This often requires maintaining multiple enumerators, such as a forward and reverse enumerator. Does this sound like fun? Actually, I would gladly pass the baton to the compiler.

.NET 2.0 introduced the iterator, which is a compiler-manifested enumerator. When the enumerable object calls GetEnumerator, either directly or indirectly, the compiler generates and returns an appropriate iterator object. Optionally, the iterator can be a combined enumerable and enumerator object. You are not completely excluded from the process. Developers can affect the enumeration in an iterator block. The essential ingredient of an iterator block is the yield statement.

Yield Statement

The following code demonstrates one of the obvious benefits of the yield statement and an iterator block: brevity. The previous sample code of a generic enumerator required more than 50 lines of code. The following example implements a similar enumerator using the yield statement, which requires three lines of code:

 public IEnumerator<T> GetEnumerator() {     foreach(T item in items) {         yield return item;     } } 

In the previous code, the C# compiler implements the enumerator. You are still coding the IEnumerable interface. Optionally, the compiler can implement both the enumerable and enumerator object in the iterator. If the iterator block returns IEnumerable, the compiler responds by creating an enumerable and enumerator object. Iterator blocks are explained soon. This removes even having to implement the GetEnumerator method.

 public IEnumerable<T> MethodA() {     foreach(T item in items) {         yield return item;     } } 

For clients, iterators are similar to enumerators. Clients call GetEnumerator or other iterator methods to obtain an iterator object. You then use the IEnumerator or IEnumerator<T> interface to enumerate the collection. There is one big difference between iterators and enumerators: Iterators do not implement the Reset method. Calling the Reset method on an iterator causes an exception.

The pivotal statement of an iterator is yield. This is the syntax of the yield statement:

• yield return expression;

• yield break;

The yield return statements iterate the next element of a collection. The statement expression is assigned to the Current property. Enumerators start in the Before state. The initial MoveNext method calls the first yield statement. After the Current property is set, the enumerator is suspended. The next MoveNext calls the next yield. This pattern continues until the enumeration is finished. The iterator block is not called anew for each MoveNext. Between yield statements of the same iterator block, enumeration is suspended. The iterator is a state machine that maintains the state of the enumeration between calls to the MoveNext method.

The yield break statements finish an enumeration, which ultimately changes the enumerator state to after. The Dispose method is then called to clean up the enumerator. This is sample code of the yield break statement. The yield break statement stops the enumeration after the fourth element.

 public IEnumerator<T> GetEnumerator() {     int count=0;     foreach(T item in items) {         ++count;         yield return item;         if(count==4) {             yield break;         }     } } 

Iterator Blocks

Iterator blocks contain the logic to enumerate a collection. This includes one or more yield statements. Methods, properties, and operator functions can be iterator blocks. Iterator blocks are not executed continuously and are sometimes suspended. The function is suspended between successive yield statements, which are controlled by the MoveNext method. As mentioned, the iterator block maintains the state machine of the enumerator between iterations.

There are restrictions on iterator blocks. For example, iterator blocks cannot have a return statement. Only yield return statements are allowed:

 public IEnumerator<T> GetEnumerator() {    foreach(T item in items) {        yield return item;        return;  // not allowed    } } 

There are several other restrictions on iterator blocks:

• Iterator blocks can be contained only in method, operator, or property functions.

• Iterator blocks cannot be in anonymous methods.

• Iterator blocks cannot be contained in a try with a catch handler.

• Iterator blocks cannot be placed in a finally block.

Functions with iterators or iterator methods also have certain restrictions:

• Iterator methods must return a generic or nongeneric IEnumerable or IEnumerator interface.

• Iterator methods cannot have ref parameters.

• Iterator methods cannot have out parameters.

• Iterator methods cannot be unsafe.

When an iterator block is exited, the Dispose method of the enumerator is called. Internally, the iterator creates the enumerator in a using block. This provides an opportunity to clean up for the enumerator when the enumeration is completed.

Iterator Internals

Iterators are implemented as nested classes, which are created by the C# compiler. The nested class maintains the state of the current enumeration. It persists the enumeration state between yield statements. Iterators are created by the language compiler, not by the Common Language Runtime (CLR). Neither Microsoft intermediate language (MSIL) nor metadata has changed to especially accommodate iterators. The nested class for an enumerator is a normal class, which is created for a method that contains an iterator block. If three methods within a class have enumerator blocks, the compiler adds three nested classes to that class.

This is how the nested class is named:

• <membername>uniqueid<T>

• <membername>uniqueid

If the iterator method returns either the IEnumerator<T> or IEnumerable<T> interfaces, the name of the nested class has the <T> suffix.

In this code, ZClass has multiple iterator methods:

 public class ZClass {     public IEnumerator GetEnumerator() {        int [] array=new int [] {1,2,3,4};        int count=0;         for(count=0;count<4;++count){             yield return array[count];         }     }     public IEnumerator MethodA() {         int [] array=new int [] {1,2,3,4};         int count=0;         for(count=0;count<4;++count){             yield return array[count];         }     }     public IEnumerable<T> MethodB<T>() {         T local=default(T);         yield return local;     } } 

The compiler adds three nested classes, one for each enumerator method, to the ZClass type. The various nested classes represent the state machine for different enumerators. Figure 7-1 shows ZClass and the nested classes.

Figure 7-1: A view of the ZClass type, which includes the nested enumerator classes

The nested enumerator class has several private fields. The local variables of the iterator method are lifted to fields of the nested class. The fields maintain the state of these local variables throughout the enumeration. The nested class also has three special purpose fields. The state of the enumeration, such as running or after, is in the <>1__state field. The <>2__current field is the result of the last iteration. It is the current item. The <4>__field is a back pointer to the outer class. If the iterator method is static, the back pointer is not initialized; it is initialized only for instance methods. Combined, the lifted and specialty fields are the state of the enumeration.

Figure 7-2 shows the fields of a typical nested class for an enumerator.

Figure 7-2: A view of a nested class and fields

Iterator Examples

This section presents several examples of iterators to demonstrate the flexibility of iterators and provide techniques for using them.

Dual iteration The first example iterates two collections simultaneously:

 using System; using System.Collections.Generic; namespace Donis.CSharpBook{     public class Starter{         public static void Main(){             ZClass obj=new ZClass();             foreach(int item in obj) {                 Console.Write(item);             }         }     }     public class ZClass {         private int [] list1=new int [] {0,2,4,6,8};         private int [] list2=new int [] {1,3,5,7,9};         public IEnumerator<int> GetEnumerator() {             for(int index=0; index<4; ++index) {                 yield return list1[index];                 yield return list2[index];             }         }     } } 

The preceding code alternates between yielding list1 and list2. As the iteration moves between collections, the even and odd numbers are intermixed. The result is 0123456789. ZClass does not inherit the IEnumerable interface. However, it adheres to the enumerator pattern by implementing the GetEnumerator method. This is sufficient for defining enumerable objects. The following examples implement the iteration pattern but not explicitly the interfaces.

Reverse iteration The following example iterates a collection forward and reverse. Two iterators are exposed for this reason. GetEnumerator exposes the standard forward iterator. The reverse iterator is implemented in the Reverse property. Because the property returns IEnumerable, the Reverse property is both an enumerable and enumerator object. When an iterator method returns IEnumerable, the nested class generated by the compiler is implemented as both an enumerable and enumerator object. In Main, there are two foreach loops: The first foreach loop uses the forward iterator, whereas the reverse iterator is requested in the second loop:

 using System; using System.Collections.Generic; namespace Donis.CSharpBook{     public class Starter{         public static void Main(){             Console.WriteLine("Forward List");             ZClass obj=new ZClass();             foreach(int item in obj) {                 Console.Write(item);             }             Console.WriteLine("\nReverse List");             foreach(int item in obj.Reverse) {                 Console.Write(item);             }         }     }     public class ZClass {         private int [] list1=new int [] {0,2,4,6,8};         public IEnumerator<int> GetEnumerator() {             for(int index=0; index<5; ++index) {                 yield return list1[index];             }         }         public IEnumerable<int> Reverse {             get {                 for(int index=4; index>=0; --index) {                    yield return list1[index];                 }             }         }     } } 

Temporary collections Temporary collections are calculated at run time and are useful in a variety of circumstances. The list of prime numbers, the records of a file, and fields in a dataset are examples of collections that can be calculated. Temporary collections can be populated lazily. You can read a flat file or dataset on demand at run time to hydrate a temporary collection.

The following code enumerates days from the current date until the end of the month, which is calculated using DateTime structure. The method ToEndOfMonth is enumerable by virtue of returning the IEnumerable interface and possessing a yield statement. Each repeat of the while loop extrapolates the next day until the end of the month is reached. The yield statement iterates the days as they are calculated.

 using System; using System.Collections; namespace Donis.CSharpBook{     public class Starter{         public static void Main(){             foreach(string day in ToEndOfMonth()) {                 Console.WriteLine(day);             }         }         public static IEnumerable ToEndOfMonth() {             DateTime date=DateTime.Now;             int currMonth=date.Month;             while(currMonth==date.Month) {                 string temp=currMonth.ToString()+                     "/"+date.Day.ToString();                 date=date.AddDays(1);                 yield return temp;             }         }     } } 

Complex iteration Link lists are complex data structures. Iterators are particularly useful when iterating complex data structures, such as a link list. Each item in the list is considered a node. Nodes maintain a reference to the previous and next node. From any node, you can walk the link list either forward or backward. For several reasons, the iteration is more complex. First, data structure must be iterated forward and backward during the same iteration. Second, fence posts are not as definable. Fence posts in arrays, stacks, queues, and other sequenced containers are easily found, which helps avoid fence post error exceptions. Finally, the iteration can start from any node in the link list, not necessarily just the beginning or end of the list.

Below is a partial listing of the Node class. The key code is in the GetEnumerator method. In the first while loop, the link list is iterating in reverse—from the current node to the beginning of list. This is accomplished by walking the prevNode member of the node class. The current node is enumerated next. Finally, the second while loop iterates the link list going forward from the current note to the end of the list. The nextNode members are walked.

 public class Node<T> {     public Node(Node<T> node, T data) {         m_Info=data;         if(node==null) {            if(firstNode != null) {                 Node<T> temp=firstNode;                 this.nextNode=temp;                 temp.prevNode=this;                 firstNode=this;                 return;            }            prevNode=null;            nextNode=null;            firstNode=this;            return;         }            this.prevNode=node;            this.nextNode=node.nextNode;            node.nextNode=this;            if(node.nextNode==null) {                lastNode=null;            }     }     public void AddNode(T data) {         this.nextNode=new Node<T>(this, data);     }     public IEnumerator<T> GetEnumerator () {         Node<T> temp=prevNode;        while(temp!=null) {             yield return temp.m_Info;             temp=temp.prevNode;         }         yield return m_Info;         temp=nextNode;          while(temp!=null) {             yield return temp.m_Info;             temp=temp.nextNode;         }     }     private T m_Info;     private static Node<T> lastNode=null;     private static Node<T> firstNode=null;     private Node<T> prevNode=null;     private Node<T> nextNode=null; }