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,