Iterators

Using iterators is an alternative to fully implementing IEnumerator or IEnumerable interfaces. Iterators also provide an easier way to implement complex enumerators, such as reverse enumerators. Previously in this chapter, different implementation strategies for enumerators have been shown. There are several options. The enumerator could be implemented as a nested class. A versioned collection could be used. The implementation could be generic or nongeneric. Why should all developers consider these options and implement their rendition of an enumerator? This would not appear to be a good 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. It is also more robust if there is one tested solution. Anyway, some developers simply visit the MSDN Web site, from which they can copy and paste an enumerator implementation into their source code. Therefore, the various implementations are undoubtedly quite similar. Iterators augment the implementation of enumerators. Developers no longer have to write enumerators from scratch.

Implementing forward enumeration of a simple collection, as shown in this chapter, is not overly difficult. The real challenge is dealing with more complex enumerations such as reverse enumerations. Coding an enumerator to iterate a sparse collection, nodal list, or binary tree also can be more challenging. What about maintaining multiple enumerators, such as a forward and reverse enumerator? That does not sound fun either. In any of these circumstances, I would gladly pass the baton to the compiler.

.NET 2.0 introduced the iterator, which is a compiler-generated enumerator. When the enumerable object calls GetEnumerator, either directly or indirectly, the compiler generates and returns an appropriate iterator object. The iterator can implement either the enumerable or enumerator interface. 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 brevity, one of the obvious benefits of an iterator block and the yield statement. Previous sample code of a generic enumerator required almost 100 lines of code. The following example implements a similar enumerator using the yield statement with just 3 lines of code:

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

In the preceding code, you explicitly implement the IEnumerable interface but the compiler implements the IEnumerator interface (i.e., the enumerator). The compiler can implement both the IEnumerable and IEnumerator interfaces for the iterator. If the iterator block returns IEnumerable, the compiler responds by creating an enumerable object and an enumerator object. This eliminates the need to implement the GetEnumerator method. The yield statement, as shown in the following sample code, is the key. (Iterator blocks are explained further in the next section of this chapter.)

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

An iterator is a method that contains an iterator block. Iterator methods return either an enumerator or an enumerable object, as defined by the IEnumerator or IEnumerable interfaces. There is one major difference between the enumerator received from an iterator and a normal enumerator: enumerators from iterators do not implement the Reset method. Calling the Reset method on such an enumerator will cause 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 statement iterates the next element of a collection. The 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. While it is suspended, the state of the enumeration should not change. The iterator is a state machine that maintains the state of the enumeration between calls to the MoveNext method.

The yield break statement finishes an enumeration, which ultimately changes the enumerator state to After. The Dispose method is then called to clean up the enumerator. The following is sample code of the yield break statement. The yield break statement in this example 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

An iterator block contains the logic to enumerate a collection, contains a yield statement, and returns an enumerator or an enumerable object. Within the iterator block, there can be one or more yield statements. 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.

The following type of functions cannot be iterators:

  • Event handlers

  • Constructors

  • Destructors

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 are not allowed in anonymous methods.

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

  • Iterator blocks cannot be placed in a finally block.

An iterator, which is a function, also has some restrictions:

  • Iterator methods must return an IEnumerable or an 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. This provides an opportunity to clean up for the enumerator when the enumeration is completed.

Iterator Internals

Iterators are implemented as nested classes 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 accommodate iterators especially. The nested class for an enumerator is a normal class, which is created for each 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 8-1 shows ZClass and the nested classes.

A view of the ZClass type, which includes the nested enumerator classes

Figure 8-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 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_this 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 represent the state of the enumeration.

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

A view of a nested class and fields

Figure 8-2. A view of a nested class and fields

Iterator Examples

This section presents several examples of iterators to demonstrate different implementation strategies and the flexibility of iterators.

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 < 5; ++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 an iterator.

Reverse iteration

The following example iterates a collection forward and in 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 an enumerator object. When an iterator method returns IEnumerable, the nested class generated by the compiler is implemented as both an enumerable and an 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("
Reverse 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 the DateTime structure. The method ToEndOfMonth is enumerable by virtue of the fact that it returns the IEnumerable interface and includes a yield statement. Each iteration 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

Iterators are particularly useful when iterating complex data structures, such as linked lists. Each item in the list is considered a node. Each node maintains a reference to the previous and the next node. From any node, you can walk the linked list either forward or backward. The iteration is more complex for several reasons. First, the linked list can be iterated forward and backward during the same iteration. Second, fenceposts are less obvious than in other data structures. Fenceposts in arrays, stacks, queues, and other sequenced containers are found easily, which helps avoid fencepost error exceptions. Finally, the iteration can start from any node in the linked list, not necessarily just at the beginning or end. For example, if the iteration starts in the middle of the linked list, how do you enumerate all the nodes?

The following code gives a partial listing of the Node class. The key portion of the code is in the GetEnumerator method. In the first while loop, the linked list is iterating in reverse—from the current node to the beginning of the 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 linked list going forward from the current note to the end of the list by walking the nextNode members:

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;
                 this.prevNode = null;
                 temp.prevNode = this;
                 firstNode = this;
                 return;
             }
             prevNode = null;
             nextNode = null;
             firstNode = this;
             lastNode = this;
             return;
        }

        this.prevNode = node;
        this.nextNode = node.nextNode;
        node.nextNode = this;
        if (this.nextNode == null) {
            lastNode = this;
        }
        else {
            this.nextNode.prevNode = this;
        }
    }

    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;
}
..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
3.135.188.121