Elegant solution for the recursive iterator

December 21, 2010

Update: I attached the sources to this post.


Hi again,

As I mentioned in the earlier post, while I wrote it I realized that even though I can use recursive iterators, I must iterate though all the “child” elements from the parent iterator, which makes the algorithm less efficient (e.g. O(n*logn) instead of O(n)). On the other hand, when I tried to write the same algorithm without recursion I ended up in a pretty cumbersome and ugly code compared to the recursive version. I didn’t see a good reason why the C# design team couldn’t make it possible to “yield” another enumerator. If they’ve done it, the generated object would need to keep track of the stack of the iterators and always use the top-most iterator. Of course that it will make the generated class more complicated, but I was convinced that it shouldn’t be that hard, and it would allow recursive (or nested) iterators that are efficient exactly as if you would write the traversal algorithm directly and not though iterators.

At first, the fact that there’s no such feature frustrated me, but then, as I often do in these situations, I tried to think whether I can implement something close to this myself. After some sketches in my notebook and then in Visual Studio I came to a simple reusable class that solves this problem very elegantly!

The class has the following public interface:

 

public class NestableIterator<T> : IEnumerable<T>, IEnumerator<T>
{
       public delegate IEnumerable<T> NestableIteratorDelegate(NestableIterator<T> chainableIterator);
       public NestableIterator(NestableIteratorDelegate iterator);
       public T Embed(IEnumerable<T> nestedIterator);
       public T Embed(NestableIteratorDelegate<T> nestedIterator);
       // explicit implementation of the interfaces…
}

 

The way to use it is as follows:

  • Create your public IEnumerable<T> method of property

  • Create a private IEnumerable<T> iterator method that accepts a pointer to an NestableIterator<T> object

  • In the public method, create an instance of NestableIterator<T> and pass the reference to the private iterator; Return the created instance.

  • Implement the private iterator. Use “yield return” to return any immediate element. Use “yield return NestableIterator.Embed(…)” to embed another iterator “inside” the current iterator.

For example, the Inorder iterator (from last post) will now look simply like this:

internal IEnumerable<T> Inorder(NestableIterator<T> nestableIterator)
{
       if (m_leftSon != null)
       {
              yield return nestableIterator.Embed(m_leftSon.Inorder);
       }
       yield return m_value;
       if (m_rightSon != null)
       {
              yield return nestableIterator.Embed(m_rightSon.Inorder);
       }
}

 

Elegant, isn’t it?! 🙂

This time I’ll leave it up to you to understand the source code of the NestableIterator class (but feel free to ask me if you don’t understand something)

Enjoy,

 

Arnon.  

 

Add comment
facebook linkedin twitter email

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

2 comments

  1. ArielDecember 22, 2010 ב 16:21

    You need to take a look at Enumerable.SelectMany.

    It’s exactly what you need here.

    Reply
  2. ArnonADecember 23, 2010 ב 22:51

    You almost got me confused with this one 😉

    Indeed you can use SelectMany and give it the method that the SelectMany resides in, and thus create a recursive iterator. But the way it works is similiar to the way I used in the previous post, and that means going over all the results at each level of the recursion, which makes it O(nlogn) or O(n^2) instead of O(n).
    I had to look at Reflector and decipher all the goo that that the compiler generates for the iterator in order to make sure 🙂

    Reply