C H A P T E R  18

Enumerators and Iterators

Enumerators and Enumerable Types

In Chapter 12, you saw that you can use a foreach statement to cycle through the elements of an array. In this chapter, you’ll take a closer look at arrays and see why they can be processed by foreach statements. You’ll also look at how you can add this capability to your own user-defined classes, using iterators.

Using the foreach Statement

When you use a foreach statement with an array, the statement presents you with each element in the array, one by one, allowing you to read its value. For example, the following code declares an array with four elements, and then uses a foreach loop to print out the values of the items:

   int[] arr1 = { 10, 11, 12, 13 };                // Define the array.

   foreach (int item in arr1)                      // Enumerate the elements.
      Console.WriteLine("Item value:  {0}", item);

This code produces the following output:

Item value:  10
Item value:  11
Item value:  12
Item value:  13

Why does this work with arrays? The reason is that an array can produce, upon request, an object called an enumerator. The enumerator is an object that can return the elements of the array, one by one, in order, as they’re requested. The enumerator “knows” the order of the items and keeps track of where it is in the sequence. It then returns the current item when it is requested.

For a type that has an enumerator, there must be a way of retrieving it. The way to retrieve an object’s enumerator is to call the object’s GetEnumerator method. Types that implement a GetEnumerator method are called enumerable types, or just enumerables. Arrays are enumerables.

Figure 18-1 illustrates the relationship between enumerables and enumerators.

Image

Figure 18-1. Overview of enumerators and enumerables

The foreach construct is designed to work with enumerables. As long as the object it’s given to iterate over is an enumerable type, such as an array, it performs the following actions:

  • It gets the object’s enumerator by calling its GetEnumerator method.
  • It requests each item from the enumerator and makes it available to your code as the iteration variable, which your code can read (but not change).
                           Must be enumerable
                                  ↓
   foreach( Type VarName in EnumerableObject )
   {
      ...
   }

The IEnumerator Interface

An enumerator implements the IEnumerator interface, which contains three function members: Current, MoveNext, and Reset.

  • Current is a property that returns the item at the current position in the sequence.
    • It is a read-only property.
    • It returns a reference of type object, so an object of any type can be returned.
  • MoveNext is a method that advances the enumerator’s position to the next item in the collection. It also returns a Boolean value, indicating whether the new position is a valid position or is beyond the end of the sequence.
    • If the new position is valid, the method returns true.
    • If the new position isn’t valid (that is, the current position is beyond the end), the method returns false.
    • The initial position of the enumerator is before the first item in the sequence, so MoveNext must be called before the first access of Current.
  • Reset is a method that resets the position to the initial state.

Figure 18-2 illustrates a collection of three items, which is shown on the left of the figure, and its enumerator, which is shown on the right. In the figure, the enumerator is an instance of a class called ArrEnumerator.

Image

Figure 18-2. The enumerator for a small collection

The way the enumerator keeps track of the current item in the sequence is entirely implementation-dependent. It might be implemented as a reference to an object, an index value, or something else entirely. In the case of the built-in single-dimensional array type, it’s simply the index of the item.

Figure 18-3 illustrates the states of an enumerator for a collection of three items. The states are labeled 1 through 5.

  • Notice that in state 1, the initial position of the enumerator is −1 (that is, before the first element of the collection).
  • Each transition between states is caused by a call to MoveNext, which advances the position in the sequence. Each call to MoveNext between states 1 and 4 returns true. In the transition between states 4 and 5, however, the position ends up beyond the last item in the collection, so the method returns false.
  • In the final state, any further calls to MoveNext return false.
Image

Figure 18-3. The states of an enumerator

Given a collection’s enumerator, you should be able to simulate a foreach loop by cycling through the items in the collection using the MoveNext and Current members. For example, you know that arrays are enumerable, so the following code does manually what the foreach statement does automatically. In fact, the C# compiler generates code very similar to this (in CIL, of course) when you write a foreach loop.

   static void Main()
   {
      int[] MyArray = { 10, 11, 12, 13 };           // Create an array.
                         Get and store the enumerator.
                                 ↓            
      IEnumerator ie = MyArray.GetEnumerator();
              Move to the next position.
                     ↓     
      while ( ie.MoveNext() )
      {               Get the current item.
                           ↓    
         int i = (int) ie.Current;
         Console.WriteLine("{0}", i);               // Write it out.
      }
   }

This code produces the following output, just as if you had used the built-in foreach statement:

10
11
12
13

Figure 18-4 illustrates the structure of the array in the code sample.

Image

Figure 18-4. The .NET Array class implements IEnumerable.

The IEnumerable Interface

An enumerable class is one that implements the IEnumerable interface. The IEnumerable interface has only a single member, method GetEnumerator, which returns an enumerator for the object.

Figure 18-5 shows class MyClass, which has three items to enumerate, and implements the IEnumerable interface by implementing the GetEnumerator method.

Image

Figure 18-5. The GetEnumerator method returns an enumerator object for the class.

The following code shows the form for the declaration of an enumerable class:

   using System.Collections;
                  Implements the IEnumerable interface
                      ↓
   class MyClass : IEnumerable
   {
      public IEnumerator GetEnumerator { ... }
         ...     ↑
   }     Returns an object of type IEnumerator

The following code gives an example of an enumerable class that uses an enumerator class called ColorEnumerator, which implements IEnumerator. I’ll show the implementation of ColorEnumerator in the next section.

   using System.Collections;
   
   class MyColors: IEnumerable
   {
      string[] Colors = { "Red", "Yellow", "Blue" };
   
      public IEnumerator GetEnumerator()
      {
         return new ColorEnumerator(Colors);
      }                      ↑
   }            An instance of the enumerator class

Example Using IEnumerable and IEnumerator

The following code shows a full example of an enumerable class called Spectrum and its enumerator class ColorEnumerator. Class Program creates an instance of MyColors in method Main and uses it in a foreach loop.

   using System;
   using System.Collections;

   class ColorEnumerator : IEnumerator
   {
      string[] _colors;
      int      _position = -1;

      public ColorEnumerator( string[] theColors )        // Constructor
      {
         _colors = new string[theColors.Length];
         for ( int i = 0; i < theColors.Length; i++ )
            _colors[i] = theColors[i];
      }

      public object Current                               // Implement Current.
      {
         get
         {
            if ( _position == -1 )
               throw new InvalidOperationException();
            if ( _position >= _colors.Length )
               throw new InvalidOperationException();

            return _colors[_position];
         }
      }

      public bool MoveNext()                              // Implement MoveNext.
      {
         if ( _position < _colors.Length - 1 )
         {
            _position++;
            return true;
         }
         else
            return false;
      }

      public void Reset()                                 // Implement Reset.
      {
         _position = -1;
      }
   }
    class Spectrum : IEnumerable
   {
      string[] Colors = { "violet", "blue", "cyan", "green", "yellow", "orange", "red" };

      public IEnumerator GetEnumerator()
      {
         return new ColorEnumerator( Colors );
      }
   }

   class Program
   {
      static void Main()
      {
         Spectrum spectrum = new Spectrum();
         foreach ( string color in spectrum )
            Console.WriteLine( color );
      }
   }

This code produces the following output:

violet
blue
cyan
green
yellow
orange
red

The Generic Enumeration Interfaces

The enumeration interfaces I’ve describe so far are nongeneric versions. In reality, you should mostly be using the generic versions of the interfaces, which are IEnumerable<T> and IEnumerator<T>. They’re called generic because they use C# generics, which are covered in Chapter 17. Using them is mostly the same as using the nongeneric forms.

The essential differences between the two are the following:

  • With the nongeneric interface form
    • The GetEnumerator method of interface IEnumerable returns an enumerator class instance that implements IEnumerator.
    • The class implementing IEnumerator implements property Current, which returns a reference of type object, which you must then cast to the actual type of the object.
  • With the generic interface form
    • The GetEnumerator method of interface IEnumerable<T> returns an instance of a class that implements IEnumerator<T>.
    • The class implementing IEnumerator<T> implements property Current, which returns an instance of the actual type, rather than a reference to the base class object.

The most important point to notice, though, is that the nongeneric interface implementations we’ve been looking at so far are not type safe. They return a reference to type object, which must then be cast to the actual type.

With the generic interfaces, however, the enumerator is type safe, returning a reference to the actual type. If you’re creating your own enumerables by implementing the interfaces, this is the approach you should take. The nongeneric interface forms are for legacy code developed before C# 2.0 when generics were introduced.

Although the generic versions are the same or easier to use than the nongeneric versions, their structures are a bit more complex. Figures 18-6 and 18-7 illustrate their structures.

Image

Figure 18-6. The structure of a class implementing the IEnumerator<T> interface

Image

Figure 18-7. The structure of a class implementing the IEnumerable<T> interface

Iterators

Enumerable classes and enumerators are used extensively in the .NET collection classes, so it’s important that you’re familiar with how they work. But now that you know how to create your own enumerable classes and enumerators, you might be pleased to learn that, starting with C# 2.0, the language provides a much simpler way of creating enumerators and enumerables. In fact, the compiler will create them for you. The construct that produces them is called an iterator. You can use the enumerators and enumerables generated by iterators wherever you would use manually coded enumerators or enumerables.

Before I explain the details, let’s take a look at two examples. The following method declaration implements an iterator that produces and returns an enumerator.

  • The iterator returns a generic enumerator that returns three items of type string.
  • The yield return statements declare that this is the next item in the enumeration.
        Return an enumerator that returns strings.
                  ↓              
   public IEnumerator<string> BlackAndWhite()                 // Version 1
   {
      yield return "black";                                   // yield return
      yield return "gray";                                    // yield return
      yield return "white";                                   // yield return
   }

The following method declaration is another version that produces the same result:

        Return an enumerator that returns strings.
                     ↓       
   public IEnumerator<string> BlackAndWhite()                  // Version 2
   {
      string[] theColors = { "black", "gray", "white" };
   
      for (int i = 0; i < theColors.Length; i++)
         yield return theColors[i];                            // yield return
   }

I haven’t explained the yield return statement yet, but on inspecting these code segments, you might have the feeling that something is different about this code. It doesn’t seem quite right. What exactly does the yield return statement do?

For example, in the first version, if the method returns on the first yield return statement, then the last two statements can never be reached. If it doesn’t return on the first statement, but continues through to the end of the method, then what happens to the values? And in the second version, if the yield return statement in the body of the loop returns on the first iteration, then the loop will never get to any subsequent iterations.

And besides all that, an enumerator doesn’t just return all the elements in one shot—it returns a new value with each access of the Current property. So, how does this give you an enumerator? Clearly this code is different from anything shown before.

Iterator Blocks

An iterator block is a code block with one or more yield statements. Any of the following three types of code blocks can be iterator blocks:

  • A method body
  • An accessor body
  • An operator body

Iterator blocks are treated differently than other blocks. Other blocks contain sequences of statements that are treated imperatively. That is, the first statement in the block is executed, followed by the subsequent statements, and eventually control leaves the block.

An iterator block, on the other hand, is not a sequence of imperative commands to be executed at one time. Instead, it’s declarative; it describes the behavior of the enumerator class you want the compiler to build for you. The code in the iterator block describes how to enumerate the elements.

Iterator blocks have two special statements:

  • The yield return statement specifies the next item in the sequence to return.
  • The yield break statement specifies that there are no more items in the sequence.

The compiler takes this description of how to enumerate the items and uses it to build an enumerator class, including all the required method and property implementations. The resulting class is nested inside the class where the iterator is declared.

You can have the iterator produce either an enumerator or an enumerable depending on the return type you use for the iterator block, as shown in Figure 18-8.

Image

Figure 18-8. You can have an iterator block produce either an enumerator or an enumerable depending on the return type you specify.

Using an Iterator to Create an Enumerator

The following code illustrates how to use an iterator to create an enumerable class.

  • Method BlackAndWhite is an iterator block that produces a method that returns an enumerator for class MyClass.
  • MyClass also implements method GetEnumerator, which just calls BlackAndWhite, and returns the enumerator that BlackAndWhite returns to it.
  • Notice that in Main, you can use an instance of the class directly in the foreach statement since the class implements GetEnumerator and is therefore enumerable.
   class MyClass
   {
      public IEnumerator<string> GetEnumerator()
      {
         return BlackAndWhite();                   // Returns the enumerator
      }
            Returns an enumerator
                    ↓          
      public IEnumerator<string> BlackAndWhite()  // Iterator
      {
         yield return "black";
         yield return "gray";
         yield return "white";
      }
   }

   class Program
   {
      static void Main()
      {
         MyClass mc = new MyClass();
                        Use the instance of MyClass.
                                 ↓
         foreach (string shade in mc)
            Console.WriteLine(shade);
      }
   }

This code produces the following output:

black
gray
white

Figure 18-9 shows the code for MyClass on the left and the resulting objects on the right. Notice how much is built for you automatically by the compiler.

  • The iterator’s code is shown on the left side of the figure and shows that its return type is IEnumerator<string>.
  • On the right side of the figure, the diagram shows that the nested class implements IEnumerator<string>.
Image

Figure 18-9. An iterator block that produces an enumerator

Using an Iterator to Create an Enumerable

The previous example created a class comprising two parts: the iterator that produced the method that returned an enumerator and the GetEnumerator method that returned that enumerator. In this example, the iterator produces an enumerable rather than an enumerator. There are some important differences between this example and the last:

  • In the previous example, iterator method BlackAndWhite returned an IEnumerator<string>, and MyClass implemented method GetEnumerator by returning the object created by BlackAndWhite.
  • In this example, the iterator method BlackAndWhite returns an IEnumerable<string> rather than an IEnumerator<string>. MyClass, therefore, implements its GetEnumerator method by first calling method BlackAndWhite to get the enumerable object and then calling that object’s GetEnumerator method and returning its results.
  • Notice that in the foreach statement in Main, you can either use an instance of the class or call BlackAndWhite directly, since it returns an enumerable. Both ways are shown.
   class MyClass
   {
      public IEnumerator<string> GetEnumerator()
      {
         IEnumerable<string> myEnumerable = BlackAndWhite(); // Get enumerable.
         return myEnumerable.GetEnumerator();                // Get enumerator.
      }        Returns an enumerable
                     ↓           
      public IEnumerable<string> BlackAndWhite()
      {
         yield return "black";
         yield return "gray";
         yield return "white";
      }
   }

   class Program
   {
      static void Main()
      {
         MyClass mc = new MyClass();
                            Use the class object.
                                   ↓
         foreach (string shade in mc)
            Console.Write("{0}  ", shade);
                               Use the class iterator method.
                                        ↓       
         foreach (string shade in mc.BlackAndWhite())
            Console.Write("{0}  ", shade);
      }
   }

This code produces the following output:

black  gray  white  black  gray  white

Figure 18-10 illustrates the generic enumerable produced by the enumerable iterator in the code.

  • The iterator’s code is shown on the left side of the figure and shows that its return type is IEnumerable<string>.
  • On the right side of the figure, the diagram shows that the nested class implements both IEnumerator<string> and IEnumerable<string>.
Image

Figure 18-10. The compiler produces a class that is both an enumerable and an enumerator. It also produces the method, BlackAndWhite, that returns the Enumerable object.

Common Iterator Patterns

The previous two sections showed that you can create an iterator to return either an enumerableM or an enumerator. Figure 18-11 summarizes how to use the common iterator patterns.

  • When you implement an iterator that returns an enumerator, you must make the class enumerable by implementing GetEnumerator so that it returns the enumerator returned by the iterator. This is shown on the left of the figure.
  • In a class, when you implement an iterator that returns an enumerable, you can make this class itself enumerable or not by either making it implement GetEnumerator or not.
    • If you implement GetEnumerator, make it call the iterator method to get an instance of the automatically generated class that implements IEnumerable. Next, return the enumerator built by GetEnumerator from this IEnumerable object, as shown on the right of the figure.
    • If you decide against making the class itself enumerable, by not implementing GetEnumerator, you can still use the enumerable returned by the iterator, by calling the iterator method directly, as shown in the second foreach statement on the right.
Image

Figure 18-11. The common iterator patterns

Producing Multiple Enumerables

In the following example, class Spectrum has two enumerable iterators—one enumerating the colors of the spectrum from the ultraviolet end to the infrared end, and the other in the opposite direction. Notice that although it has two methods that return enumerables, the class itself is not enumerable since it doesn’t implement GetEnumerator.

   using System;
   using System.Collections.Generic;

   class Spectrum
   {
      string[] colors = { "violet", "blue", "cyan", "green", "yellow", "orange", "red" };
                                Returns an enumerable
                                    ↓
      public IEnumerable<string> UVtoIR()
      {
         for ( int i=0; i < colors.Length; i++ )
            yield return colors[i];
      }
                                Returns an enumerable
                                    ↓
      public IEnumerable<string> IRtoUV()
      {
         for ( int i=colors.Length - 1; i >= 0; i-- )
            yield return colors[i];
      }
   }

   class Program
   {
      static void Main()
      {
         Spectrum spectrum = new Spectrum();

         foreach ( string color in spectrum.UVtoIR() )
            Console.Write( "{0}  ", color );
         Console.WriteLine();

         foreach ( string color in spectrum.IRtoUV() )
            Console.Write( "{0}  ", color );
         Console.WriteLine();
      }
   }

This code produces the following output:

violet  blue  cyan  green  yellow  orange  red
red  orange  yellow  green  cyan  blue  violet

Iterators As Properties

The previous example used iterators to produce a class with two enumerables. This example shows two things. First, it uses iterators to produce a class with two enumerators. Second, it shows how iterators can be implemented as properties rather than methods.

The code declares two properties that define two different enumerators. The GetEnumerator method returns one or the other of the two enumerators, depending on the value of the Boolean variable _listFromUVtoIR. If _listFromUVtoIR is true, then the UVtoIR enumerator is returned. Otherwise, the IRtoUV enumerator is returned.

   using System;
   using System.Collections.Generic;

   class Spectrum
   {
      bool _listFromUVtoIR;

      string[] colors = { "violet", "blue", "cyan", "green", "yellow", "orange", "red" };

      public Spectrum( bool listFromUVtoIR )
      {
         _listFromUVtoIR = listFromUVtoIR;
      }

      public IEnumerator<string> GetEnumerator()
      {
         return _listFromUVtoIR
                     ? UVtoIR
                     : IRtoUV;
      }

      public IEnumerator<string> UVtoIR
      {
         get
         {
            for ( int i=0; i < colors.Length; i++ )
               yield return colors[i];
         }
      }

      public IEnumerator<string> IRtoUV
      {
         get
         {
            for ( int i=colors.Length - 1; i >= 0; i-- )
               yield return colors[i];
         }
      }
   }

    class Program
   {
      static void Main()
      {
         Spectrum startUV = new Spectrum( true );
         Spectrum startIR = new Spectrum( false );

         foreach ( string color in startUV )
            Console.Write( "{0}  ", color );
         Console.WriteLine();

         foreach ( string color in startIR )
            Console.Write( "{0}  ", color );
         Console.WriteLine();
      }
   }

This code produces the following output:

violet  blue  cyan  green  yellow  orange  red
red  orange  yellow  green  cyan  blue  violet

Behind the Scenes with Iterators

The following are some other important things to know about iterators:

  • Iterators require the System.Collections.Generic namespace, so you should include it with a using directive.
  • In the compiler-generated enumerators, the Reset method is not supported. It is implemented, since it is required by the interface, but the implementation throws a System.NotSupportedException exception if it is called. Notice that the Reset method is shown grayed out in Figure 18-9.

Behind the scenes, the enumerator class generated by the compiler is a state machine with four states:

  • Before: The initial state before the first call to MoveNext.
  • Running: The state entered when MoveNext is called. While in this state, the enumerator determines and sets the position for the next item. It exits the state when it encounters a yield return, a yield break, or the end of the iterator body.
  • Suspended: The state where the state machine is waiting for the next call to MoveNext.
  • After: The state where there are no more items to enumerate.

If the state machine is in either the before or suspended states and there is a call to the MoveNext method, it goes into the running state. In the running state, it determines the next item in the collection and sets the position.

If there are more items, the state machine goes into the suspended state. If there are no more items, it goes into the after state, where it remains. Figure 18-12 shows the state machine.

Image

Figure 18-12. An iterator state machine

..................Content has been hidden....................

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