Implementing an Enumerator by Using an Iterator

Implementing an Enumerator by Using an Iterator

As you can see, the process of making a collection enumerable can become complex and potentially error-prone. To make life easier, C# 2.0 includes iterators which can automate much of this process.

According to the C# 2.0 specification, an iterator is a block of code that yields an ordered sequence of values. Additionally, an iterator is not actually a member of an enumerable class. Rather, it specifies the sequence that an enumerator should use for returning its values. In other words, an iterator is just a description of the enumeration sequence that the C# compiler can use for creating its own enumerator. This concept requires a little thought to understand it properly, so let's consider a basic example before returning to binary trees and recursion.

A Simple Iterator

The BasicCollection<T> class shown below illustrates the basic principles of implementing an iterator. The class uses a List<T> for holding data, and provides the FillList method for populating this list. Notice also that the BasicCollection<T> class implements the IEnumerable<T> interface. The GetEnumerator method is implemented by using an iterator:

class BasicCollection<T> : IEnumerable<T> {     private List<T> data = new List<T>();     public void FillList(params T [] items)     {         for (int i = 0; i < items.Length; i++)             data.Add(items[i]);     }     IEnumerator<T> IEnumerable<T>.GetEnumerator()     {         for (int i = 0; i < data.Count; i++)             yield return data[i];     }     IEnumerator IEnumerable.GetEnumerator()     {         // Not implemented in this example     } }

The GetEnumerator method appears to be straightforward, but bears closer examination. The first thing you should notice is that it doesn't appear to return an IEnumerator<T> type. Instead, it loops through the items in the data array, returning each item in turn. The key point is the use of the yield keyword. The yield keyword indicates the value that should be returned by each iteration. If it helps, you can think of the yield statement as calling a temporary halt to the method, passing back a value to the caller. When the caller needs the next value, the GetEnumerator method continues at the point it left off, looping round and then yielding the next value. Eventually, the data will be exhausted, the loop will finish, and the GetEnumerator method will terminate. At this point the iteration is complete.

Remember that this is not a normal method in the usual sense. The code in the GetEnumerator method defines an iterator. The compiler uses this code to generate an implementation of the IEnumerator<T> class containing a Current and a MoveNext method. This implementation will exactly match the functionality specified by the GetEnumerator method. You don't actually get to see this generated code (unless you decompile the assembly containing the compiled code), but that is a small price to pay for the convenience and reduction in code that you need to write. You can invoke the enumerator generated by the iterator in the usual manner, as shown in this block of code:

BasicCollection<string> bc = new BasicCollection<string>(); bc.FillList("Twas", "brillig", "and", "the", slithy", "toves"); foreach (string word in bc)     Console.WriteLine(word);

This code simply outputs the contents of the bc object in this order:

Twas, brillig, and, the, slithy, toves

If you want to provide alternative iteration mechanisms presenting the data in a different sequence, you can implement additional properties that implement the IEnumerable interface and that use an iterator for returning data. For example, the Reverse property of the BasicCollection<T> class, shown below, emits the data in the list in reverse order:

public IEnumerable<T> Reverse {     get     {         for (int i = data.Count - 1; i >= 0; i--)             yield return data[i];     } }

You can invoke this property as follows:

BasicCollection<string> bc = new BasicCollection<string>(); bc.FillList("Twas", "brillig", "and", "the", slithy", "toves"); ... foreach (string word in bc.Reverse)     Console.WriteLine(word);

This code outputs the contents of the bc object in reverse order:

toves, slithy, the, and, brillig, Twas

Defining an Enumerator for the Tree<T> Class by Using an Iterator

In the next exercise, you will implement the enumerator for the Tree<T> class by using an iterator. Unlike the previous set of exercises which required the data in the tree to be preprocessed into a queue by the MoveNext method, you can define an iterator that traverses the tree by using the more natural recursive mechanism, similar to the WalkTree method discussed in Chapter 17.

Add an enumerator to the Tree<T> class

1. Start Visual Studio 2005 if it is not already running.

2. Open the Visual C# solution \Microsoft Press\Visual CSharp StepBy Step\Chapter 18\IteratorBinaryTree\BinaryTree.sln. This solution contains another working copy of the BinaryTree project you created in Chapter 17.

3. Display the file Tree.cs in the Code and Text Editor window. Modify the definition of the Tree<T> class so that it implements the IEnumerable<T> interface:

   public class Tree<T> : IEnumerable<T> where T : IComparable<T> {     ... }

4. Right-click the IEnumerable<T> interface in the class definition, point to Implement Interface, and then click Implement Interface Explicitly.

   The IEnumerable<T>.GetEnumerator and IEnumerable.GetEnumerator methods are added to the class.

5. Locate the IEnumerable<T>.GetEnumerator method. Replace the contents of the GetEnumerator method as shown below:

   IEnumerator<T> IEnumerable<T>.GetEnumerator() {     if (this.LeftTree != null)     {         foreach (T item in this.LeftTree)         {             yield return item;         }     }     yield return this.NodeData;     if (this.RightTree != null)     {         foreach (T item in this.RightTree)         {             yield return item;         }     } }

   It might not look like it at first glance, but this code is recursive. If the LeftTree is not empty, the first foreach statement implicitly calls the GetEnumerator method (which you are currently defining) over it. This process continues until a node is found that has no left sub-tree. At this point, the value in the NodeData property is yielded, and the right sub-tree is examined in the same way. When the right sub-tree is exhausted, the process unwinds to parent node, outputting its NodeData property and examining its right sub-tree. This course of action continues until the entire tree has been enumerated and all the nodes have been output.

Test the new enumerator

1. On the File menu, point to Add and then click Existing Project. Move to the folder \Microsoft Press\Visual CSharp StepBy Step\Chapter 18\BinaryTree\EnumeratorTest and click the EnumeratorTest.csproj file. This is the project that you created to test the enumerator you developed manually, earlier in this chapter. Click Open.

2. Right-click the EnumeratorTest project in the Solution Explorer, and then click Set as Startup Project.

3. Expand the References folder for the EnumeratorTest project in the Solution Explorer. Right-click the BinaryTree assembly and then click Remove.

   This action removes the reference to the BinaryTree assembly from the project.

4. On the Project menu, click Add Reference. In the Add Reference dialog box, click the Projects tab. Click the BinaryTree project and then click OK.

   The BinaryTree assembly appears in the list of references for the EnumeratorTest project in the Solution Explorer.

   NOTE
   These two steps ensure that the EnumeratorTest project references the version of the BinaryTree assembly that uses the iterator to create its enumerator, rather than the earlier version.

5. Review the Main method in the Program.cs file. Recall that this method instantiates a Tree<int> object, fills it with some data, and then uses a foreach statement to display its contents.

6. Build the solution, correcting any errors if necessary.

7. On the Debug menu, click Start Without Debugging.

   When the program runs, the values should be displayed in the same sequence as before:

   –12, –8, 0, 5, 5, 10, 10, 11, 14, 15

8. Press Enter and return to Visual Studio 2005.

• If you want to continue to the next chapter

  Keep Visual Studio 2005 running and turn to Chapter 19.

• If you want to exit Visual Studio 2005 now

  On the File menu, click Exit. If you see a Save dialog box, click Yes.