Enumerating the Elements in Collection

Enumerating the Elements in Collection

In Chapter 10, you saw an example of using the foreach statement to list the items in a simple array. The code looked like this:

int[] pins = { 9, 3, 7, 2 }; foreach (int pin in pins) {    Console.WriteLine(pin); }

The foreach construct provides an elegant mechanism that greatly simplifies the code that you need to write, but it can only be exercised under certain circumstances—you can only use foreach to step through an enumerable collection. So, what exactly is an enumerable collection? The quick answer is that it is a collection that implements the System.Collections.IEnumerable interface.

NOTE
Remember that all arrays in C# are actually instances of the System.Array class. The System.Array class is a collection class that implements the IEnumerable interface.

The IEnumerable interface contains a single method called GetEnumerator:

IEnumerator GetEnumerator();

The GetEnumerator method returns an enumerator object that implements the System.Collections.IEnumerator interface. The enumerator object is used for stepping through (enumerating) the elements of the collection. The IEnumerator interface itself specifies the following property and methods:

object Current {get;} bool MoveNext(); void Reset();

Think of an enumerator as a pointer pointing to elements in a list. Initially the pointer points before the first element. You call the MoveNext method to move the pointer down to the next (first) item in the list; the MoveNext method should return true if there actually is another item, and false if there isn't. You use the Current property to access the item currently pointed to, and the Reset method to return the pointer back to before the first item in the list. By creating an enumerator by using the GetEnumerator method of a collection, and repeatedly calling the MoveNext method and retrieving the value of the Current property by using the enumerator, you can move forward through the elements of a collection one item at a time. This is exactly what the foreach statement does. So, if you want to create your own enumerable collection class, you must implement the IEnumerable interface in your collection class, and also provide an implementation of the IEnumerator interface to be returned by the GetEnumerator method of the collection class.

If you are observant, you will have noticed that the Current property of the IEnumerator interface exhibits non-typesafe behavior inasmuch that it returns an object rather than a specific type. However, you should be pleased to know that the .NET Framework class library also provides the generic IEnumerator<T> interface, providing a Current property that returns a T instead. Likewise, there is also an IEnumerable<T> interface containing a GetEnumerator method that returns an Enumerator<T> object. If you are building applications for the .NET Framework version 2.0, you should make use of these generic interfaces when defining enumerable collections rather than using the non-generic definitions.

NOTE
The IEnumerator<T> interface has some further differences from the IEnumerator interface; it does not contain a Reset method, but extends the IDisposable interface.

Manually Implementing an Enumerator

In the next exercise you will define a class that implements the generic IEnumerator<T> interface and create an enumerator for the binary tree class that you built in Chapter 17, “Introducing Generics.” In Chapter 17 you saw how easy it was to traverse a binary tree and display its contents. You would therefore be inclined to think that defining an enumerator that retrieves each element in a binary tree in the same order would be a simple matter. Sadly, you would be mistaken. The main problem is that when defining an enumerator you need to remember where you are in the structure so that subsequent calls to the MoveNext method can update the position appropriately. Recursive algorithms, such as that used when walking a binary tree, do not lend themselves to maintaining state information between method calls in an easily accessible manner. For this reason, you will first pre-process the data in the binary tree into a more amenable data structure (a queue) and actually enumerate this data structure instead. Of course, this deviousness will be hidden from the user iterating through the elements of the binary tree!

Create the TreeEnumerator 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\BinaryTree\BinaryTree.sln. This solution contains a working copy of the BinaryTree project you created in Chapter 17.

3. Add a new class to the project: click Add Class on the Project menu, select the Class template, and type TreeEnumerator.cs for the Name, and then click Add.

4. The TreeEnumerator class will generate an enumerator for a Tree<T> object. To ensure that the class is typesafe, it is necessary to provide a type parameter and implement the IEnumerator<T> interface. Also, the type parameter must be a valid type for the Tree<T> object that the class enumerates, so it must be constrained to implement the IComparable<T> interface.

   Modify the class definition to satisfy these requirements. It should look like this:

   public class TreeEnumerator<T> : IEnumerator<T> where T : IComparable<T> { }

5. Add the following three private variables to the TreeEnumerator<T> class:

   private Tree<T> currentData = null; private T currentItem = default(T); private Queue<T> enumData = null;

   The currentData variable will be used to hold a reference to the tree being enumerated, and the currentItem variable will hold the value returned by the Current property. You will populate the enumData queue with the values extracted from the nodes in the tree, and the MoveNext method will return each item from this queue in turn.

6. Add a TreeEnumerator constructor that take a single Tree<T> parameter called data. In the body of the constructor, add a statement that initializes the currentData variable to data:

   public TreeEnumerator(Tree<T> data) {     this.currentData = data; }

7. Add the following private method, called populate, to the TreeEnumerator<T> class, after the constructor:

   private void populate(Queue<T> enumQueue, Tree<T> tree) {     if (tree.LeftTree != null)     {         populate(enumQueue, tree.LeftTree);     }     enumQueue.Enqueue(tree.NodeData);     if (tree.RightTree != null)     {         populate(enumQueue, tree.RightTree);     } }

   This method walks a binary tree, adding the data it contains to the queue. The algorithm used is very similar to that used by the WalkTree method in the Tree<T> class, and which was described in Chapter 17. The main difference is that rather than outputting NodeData values to the screen, they are stored in the queue.

8. Return to the definition of the TreeEnumerator<T> class. Right-click anywhere in the IEnumerator<T> interface in the class declaration, point to Implement Interface, and then click Implement Interface Explicitly.

   This action generates stubs for the methods of the IEnumerator<T> interface and the IEnumerator interface, and adds them to the end of the class. It also generates the Dispose method for the IDisposable interface.

   NOTE
   The IEnumerator<T> interface inherits from the IEnumerator and IDisposable interfaces, which is why their methods also appear. In fact, the only item that belongs to the IEnumerator<T> interface is the generic Current property. The MoveNext and Reset methods belong to the non-generic IEnumerator interface. The IDisposable interface was described in Chapter 13, “Using Garbage Collection and Resource Management.”

9. Examine the code that has been generated. The bodies of the properties and methods contain a default implementation that simply throws an Exception with the message “The method or operation is not implemented.” You will replace this code with a real implementation in the following steps.

10. Replace the body of the MoveNext method with the code shown below:

    bool System.Collections.IEnumerator.MoveNext()  {     if (this.enumData == null)     {         this.enumData = new Queue<T>();         populate(this.enumData, this.currentData);     }     if (this.enumData.Count > 0)     {         this.currentItem = this.enumData.Dequeue();         return true;     }     return false; }

    The purpose of the MoveNext method of an enumerator is actually twofold. The first time it is called it should initialize the data used by the enumerator and advance to the first piece of data to be returned. (Remember that prior to calling MoveNext for the first time, the value returned by the Current property is undefined and should result in an exception). In this case, the initialization process consists of instantiating the queue, and calling the populate method to extract the data from the tree and using it to fill the queue.

    Subsequent calls to the MoveNext method should just move through data items until there are no more left, dequeuing items from the queue until it is empty in this example. It is important to bear in mind that MoveNext does not actually return data items—that is the purpose of the Current property. All MoveNext does is update internal state in the enumerator (the value of the currentItem variable is set to the data item extracted from the queue) for use by the Current property, returning true if there is a next value, false otherwise.

11. Modify the definition of the get accessor of the Current property as follows:

    T IEnumerator<T>.Current {     get     {         if (this.enumData == null)             throw new InvalidOperationException("Use MoveNext before calling Current");         return this.currentItem;     } }

    The Current property examines the enumData variable to ensure that MoveNext has been called (this variable will be null prior to the first call to MoveNext). If this is not the case, the property throws an InvalidOperationException—this is the conventional mechanism used by .NET Framework applications to indicate that an operation cannot be performed in the current state. If MoveNext has been called beforehand, it will have updated the currentItem variable, so all the Current property needs to do is return the value in this variable.

12. Locate the IDisposable.Dispose method. Comment out the throw new Exception statement. The enumerator does not use any resources that require explicit disposal, so this method does not need to do anything. It must still be present, however. For more information about the Dispose method, refer to Chapter 13.

13. Build the solution and fix any errors that are reported.

Initializing a Variable Defined with a Type Parameter

You should have noticed that the statement that defines and initializes the currentItem variable uses the default keyword. This keyword is a new feature in C# 2.0.

The currentItem variable is defined by using the type parameter T. When the program is written and compiled, the actual type that will be substituted for T might not be known—this issue is only resolved when the code is executed. This makes it difficult to specify how the variable should be initialized. The temptation would be to set it to null. However, if the type substituted for T is a value type, then this is an illegal assignment (you cannot set value types to null, only reference types). Similarly, if you set it to 0 in the expectation that the type will be numeric, then this will be illegal if the type used is actually a reference type. There are other possibilities as well—T could be a boolean for example. The default keyword solves this problem. The value used to initialize the variable will be determined when the statement is executed; if T is a reference type default(T) returns null, if T is numeric, default(T) returns 0, and if T is a boolean, default(T) returns false. If T is a struct, the individual fields in the struct are initialized in the same way (reference fields are set to null, numeric fields are set to 0, and boolean fields are set to false.)

Implementing the IEnumerable Interface

In the following exercise, you will modify the binary tree class to implement the IEnumerable interface. The GetEnumerator method will return a TreeEnumerator<T> object.

Implement the IEnumerable<T> interface in the Tree<T> class

1. In the Solution Explorer, double click the file Tree.cs to display the Tree<T> class in the Code and Text Editor window.

2. Modify the definition of the Tree<T> class so that it implements the IEnumerable<T> interface, as shown below:

   public class Tree<T> : IEnumerable<T> where T : IComparable<T>

   Notice that constraints are always placed at the end of the class definition.

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

   This action generates implementations of the IEnumerable<T>.GetEnumerator and the IEnumerable.GetEnumerator methods and adds them to the close. The IEnumerable interface method is implemented because the IEnumerable<T> interface inherits from IEnumerable.

4. Locate the IEnumerable<T>.GetEnumerator method near the end of the class. Modify the body of the GetEnumerator() method, replacing the existing throw statement as follows:

   IEnumerator<T> IEnumerable<T>.GetEnumerator() {     return new TreeEnumerator<T>(this); }

   The purpose of the GetEnumerator method is to construct an enumerator object for iterating through the collection. In this case, all we need to do is build a new TreeEnumerator<T> object by using the data in the tree.

5. Build the solution.

   The project should compile cleanly, so correct any errors that are reported and rebuild the solution if necessary.

You will now test the modified Tree<T> class by using a foreach statement to display the contents of a binary tree.

Test the enumerator

1. On the File menu, point to Add and then click New Project. Add a new project by using the Console Application template. Name the project EnumeratorTest and set the Location to \Microsoft Press\Visual CSharp StepBy Step\Chapter 18\BinaryTree, and then click OK.

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

3. 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 will appear in the list of references for the EnumeratorTest project in the Solution Explorer.

4. In the Code and Text Editor window displaying the Program class, add the following using directive to the list at the top of the file:

   using BinaryTree;

5. Add the following statements that create and populate a binary tree of integers to the Main method:

   Tree<int> tree1 = new Tree<int>(10); tree1.Insert(5); tree1.Insert(11); tree1.Insert(5);  tree1.Insert(-12); tree1.Insert(15); tree1.Insert(0); tree1.Insert(14); tree1.Insert(-8); tree1.Insert(10);

6. Add a foreach statement that enumerates the contents of the tree and displays the results:

   foreach (int data in tree1) Console.WriteLine(data);

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

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

   When the program runs, the values should be displayed in the following sequence:

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

   Press Enter to return to Visual Studio 2005.