Sunday, December 13, 2009

C# 2.0 - Iterators


Hi all,


C# 2.0 came up with new features and one of new was the "Iterators" construct. The C# team greatly reduce the complexity of providing an enumerator for a collection.


When using an iterator, the compiler generates the IEnumerator class at build time.
The keyword yield is used with a return statement to return a single item at a time.


Each yield return corresponds to getting the current item. Then when the next item is requested, the compiler resumes the execution after the last yield return was called. In reality, the execution of the method does not begin at the beginning of the method each time. The compiler turns the single yield method into an entire IEnumerator class with its own state, MoveNext and Current.


1) Enumerator (C# 1.0)


C# 1.0 comes with 2 interfaces namely IEnumerabale and IEnumerator.


---------------------------------------------------------------
public interface IEnumerable 
{
    IEnumerator   GetEnumerator();

}



public interface IEnumerator 
{
    object Current {get;} // a property

    bool MoveNext(); // 2 methods

    void Reset();

}
--------------------------------------------------------------


That time Generics were not there, and therefore Current returns System.Object.
Now, we try to implement the IEnumerator it would will like this
--------------------------------------------------------------
public class ArrayList : IEnumerable, ... {....}


ArrayList list = new ArrayList();
list.Add("Aroh");
...
foreach (string item in list)
Console.Writeline(item);
.....
//pseudo-code which C# complier will generate behind the scenes:
IEnumerator e = list.GetEnumerator(); // foreach
while(e.MoveNext())                             // in
Console.Writeline((string)e.Current);  // item
------------------------------------------------------------------------
(string) cast has to be noted.


2) (C# 2.0 - Generic Enumerators) 


-------------------------------------------------------------
public interface IEnumerable<T> : IEnumerable // IEnumerable = Non-Generic IEnumerator
{
IEnumerator<T>GetEnumerator();
}


public interface IEnumerator<T> : IEnumerator, ....
{
T Current {get;} // a property
}
---------------------------------------------------

T
will be a strongly typed return variable.

Now, we try to implement the IEnumerator it would will like this:


-----------------------------------------
public class List<T>: IEnumerable<T>, ...{....}


//sample use
List<string> list = new List<string>();
list.Add("Aroh"); 
...
foreach(string item in list)
Console.Writeline(item);
.............


//pseudo-code which C# complier will generate behind the scenes, no cast on Current:
IEnumerator e = list.GeEnumerator(); // foreach
while(e.MoveNext())                             // in
Console.Writeline(e.Current);              // item


----------------------------------------


T will be a strongly typed return variable (string, in this case).  


3) Implementing enumerators: 


When we implement enumerators, we have to come across nested enumerator class which is has at least 40 lines of code even for the forward simple enumerator list. Moreover, there is very monotonous code which is prone to errors.Also think of enumerators which are complex like data structure.


It will be a big headache to implement this.
For e.g.


We create 2 classes:
i) Animal
ii) AnimalList
-------------------------------------------------------
public class Animal {....}


public class AnimalList : IEnumerable<Animal>
{
  public IEnumerator<Animal> GetEnumerator()
   { return new Enumerator (this);}


  IEnumerator IEnumerable.GetEnumerator()
   { return (( IEnumerable<Animal>)this).GetEnumerator();}


  //nested enumerator class
  public class Enumerator : IEnumerator<Animal> {....}
  {...}

}
----------------------------------------------------------------


4) Iterators


We will ask C# complier to write the enumerator for us.


------------------------------------------------------------------------------

class AnimalList : IEnumerable<Animal>
{
  private List<Animal> list = new List<Animal>();
  
  // let C# 2.0 compiler write the enumerator 
 IEnumerator<Animal> IEnumerable<Animal>.GetEnumerator()

{

for( i = 0; i < list.Count ; i++)
   yield return list[i]; 
}



  IEnumerator IEnumerable.GetEnumerator()
   { return (( IEnumerable<Animal>)this).GetEnumerator();}
  

}

 ---------------------------------------------------------------------------
   
We have to use new keyword: "yield". The complier writes a state machine, maintain the state, and every time it executes, pick the execution previous yield let off.


We can even the reverse using the Reverse property.
-------------------------------------------------------
class AnimalList : IEnumerable<Animal>
{
  public IEnumerable<Animal> Reverse
  get
 {
     for( int i = list.Count -1; i >=0 ; i--)
     yield return list[i]

 }
.....
  //using the reverse iterator
  foreach(Animal item in list.Reserve)
  Console.Writeline(item);

}
-------------------------------------------------------


More details on yield keyword - implementing iterators with yield statements


Iterators are useful programming constructs and but in past they have been bit of a nuisance to write. They were not difficult to code though but we have to take extra care and we had to create an extra class to store the state of where you've got up to in the collection.


.NET 2.0 team provided a simpler way and gave us a new keyword called yield. 


Definition:
yield statements allow you to write iterators "in-line" in a single method, with the compiler doing all the hard work of keeping track of state behind the scenes. 




yield statements are only valid in a method/operator/property which returns one of IEnumerable, IEnumerable, IEnumerator or IEnumerator. You can't mix and match - if a member uses yield statements, it can't use normal return statements too.


There are 2 kind of yield statements:
i) yield return (for returning the next item)
ii) yield break (to signify the end of the iterator)


A) 
Lets a create a very simple console application to demonstrate IEnumerable with yield statements. 


--------------------------------------------------------
using System;
using System.Collections;

class Test
{
    static void Main(string[] args)
    {
        foreach (string x in Foo())
        {
            Console.WriteLine (x);
        }
    }
    
    static IEnumerable Foo()
    {
        yield return "Hello";
        yield return "there";
    }

}
---------------------------------------------------

The important thing to understand is that although Foo() is only called once,
the compiler has effectively built a state machine - the yield return "there";
statement is only executed after "Hello" has already been printed on the screen.
 
Every time MoveNext() is called on the iterator (in this case MoveNext() is called 
implicitly by the foreach statement) execution continues from where it had got to in 
what we've declared as the Foo() method, until it next reaches a yield statement. 
If you're familiar with coroutines  from other languages, that's effectively 
what is going on here - it's just that the compiler has done all the hard work.
 
The output will be: 
Hello
there
 
If we want to experiment with this simple program and remove both the yield 
keyword: 
 
 static IEnumerable Foo()
    {
        return "Hello";
        return "there";
    }
 
The program will compile successfully, but if try the run the program you will get 
an exception 
InvalidCastException: Unable to cast object of type 'System.Char' to type 'System.String'.

B) 
Lets see another program: 
-----------------------------------
 using System;
using System.Collections;

class Test
{
    static void Main(string[] args)
    {
        NameAndPlaces t = new NameAndPlaces("Jon",
            new string[]{"London", "Hereford", "Cambridge", "Reading"});
        
        foreach (string x in t)
        {
            Console.WriteLine (x);
        }
    }
}

public class NameAndPlaces : IEnumerable
{
    string name;
    string[] places;    
    
    public NameAndPlaces (string name, string[] places)
    {
        this.name = name;
        this.places = places;
    }
    
    public IEnumerator GetEnumerator()
    {
        yield return "My name is "+name;
        yield return "I have lived in: ";
        foreach (string place in places)
        {
            yield return place;
        }
    }
}

----------------------------------- 
 
In this example, class NameAndPlaces has inherited IEnumerable interface. The
most important part of code is implementation of GetEnumerator() method. 
In this method, there are 3 yield statements. Firstly is the name, secondly is 
the places and thirdly each places. 
 
Output will look this: 
My name is Jon
I have lived in:
London
Hereford
CambridgeReading
 
C) 
 
When it is necessary to process a array in normal order, we can use statement foreach.

But
if we want to process the array in reverse order: from last array's
element to first (0) element, we have a problem. Sure, we can use loop
for (in reverse order) or call method Array.Reverse() and reverse
elements of original array. Now we can suggest a additional way to get
reverse processing of array with help of generics and yield. 

Sample: process (output to console) int and string array in "normal" and "reverse" orders:

static void SampleReverese()
{
    int[] intArray = new int[] {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    string[] strArray = new string[] { "zero", "one", "two", "three", "four", "five" };           
    DisplayArray(intArray);
    DisplayArray(Reverse(intArray));
    DisplayArray(Reverse(strArray));
}

We can note, methods DisplayArray() and ReverseArray() can receive array of any elements.

It is implemented with help of c# generics.

Method Display():
static void DisplayArray(IEnumerable displayedArray)
{
    Console.WriteLine();
    foreach (T item in displayedArray)
    {
        Console.Write("{0} ", item);
    }
}

More interesting how to implement method Reverse() without creation of new array or changing original array.
We use statement yield:

static IEnumerable Reverse(T[] originalArray)
{
   for (int i = originalArray.Length - 1; i>=0; i--)
   {
       yield return originalArray[i];
   }
} 
 
Happy programming
Cheers,
--Aroh 
 
References: 
1) Channel 9 - C# 2.0 Iterators 
2) Yoda - C# Iterators  
3) C Sharp Iterators 
4) C sharp on line
 
 






No comments:

How to display Sharegate administrative dynamic reports via Power BI on SharePoint Online

After working in the SharePoint domain for a couple of years as SharePoint consultant , I am fortunate enough to help customers from man...