Is it OK to reuse IEnumerable collections more than once?

Question

Basically I am wondering if it's ok to use an enumeration more than once in code subsequently. Whether you break early or not, would the enumeration always reset in every foreach case below, so giving us consistent enumeration from start to end of the effects collection?

var effects = this.EffectsRecursive;

foreach (Effect effect in effects)
{
...
}

foreach (Effect effect in effects)
{
    if(effect.Name = "Pixelate")
        break;
}

foreach (Effect effect in effects)
{
...
}

EDIT: The implementation of EffectsRecursive is this:

public IEnumerable<Effect> Effects
{
    get
    {
        for ( int i = 0; i < this.IEffect.NumberOfChildren; ++i )
        {
            IEffect effect = this.IEffect.GetChildEffect ( i );
            if ( effect != null )
                yield return new Effect ( effect );
        }
    }
}

public IEnumerable<Effect> EffectsRecursive
{
    get
    {
        foreach ( Effect effect in this.Effects )
        {
            yield return effect;
            foreach ( Effect seffect in effect.ChildrenRecursive )
                yield return seffect;
        }
    }
}

Answer 1

Yes this is legal to do. The IEnumerable<T> pattern is meant to support multiple enumerations on a single source. Collections which can only be enumerated once should expose IEnumerator instead.

Answer 2

The code that consumes the sequence is fine. As spender points out, the code that produces the enumeration might have performance problems if the tree is deep.

Suppose at the deepest point your tree is four deep; think about what happens on the nodes that are four deep. To get that node, you iterate the root, which calls an iterator, which calls an iterator, which calls an iterator, which passes the node back to code that passes the node back to code that passes the node back... Instead of just handing the node to the caller, you've made a little bucket brigade with four guys in it, and they're tramping the data around from object to object before it finally gets to the loop that wanted it.

If the tree is only four deep, no big deal probably. But suppose the tree is ten thousand elements, and has a thousand nodes forming a linked list at the top and the remaining nine thousand nodes on the bottom. Now when you iterate those nine thousand nodes each one has to pass through a thousand iterators, for a total of nine million copies to fetch nine thousand nodes. (Of course, you've probably gotten a stack overflow error and crashed the process as well.)

The way to deal with this problem if you have it is to manage the stack yourself rather than pushing new iterators on the stack.

public IEnumerable<Effect> EffectsNotRecursive() 
{     
    var stack = new Stack<Effect>();
    stack.Push(this);
    while(stack.Count != 0)
    {
        var current = stack.Pop();
        yield return current;
        foreach(var child in current.Effects)
            stack.Push(child);
    }
}

The original implementation has a time complexity of O(nd) where n is the number of nodes and d is the average depth of the tree; since d can in the worst case be O(n), and in the best case be O(lg n), that means that the algorithm is between O(n lg n) and O(n^2) in time. It is O(d) in heap space (for all the iterators) and O(d) in stack space (for all the recursive calls.)

The new implementation has a time complexity of O(n), and is O(d) in heap space, and O(1) in stack space.

One down side of this is that the order is different; the tree is traversed from top to bottom and right to left in the new algorithm, instead of top to bottom and left to right. If that bothers you then you can just say

        foreach(var child in current.Effects.Reverse())

instead.

For more analysis of this problem, see my colleague Wes Dyer's article on the subject:

http://blogs.msdn.com/b/wesdyer/archive/2007/03/23/all-about-iterators.aspx

Answer 3

Legal, yes. Whether it will function as you expect depends on:

• The implementation of the IEnumerable returned by EffectsRecursive and whether it always returns the same set;

• Whether you want to enumerate the same set both times

If it returns an IEnumerable that requires some intensive work, and it doesn't cache the results internally, then you may need to .ToList() it yourself. If it does cache the results, then ToList() would be slightly redundant but probably no harm.

Also, if GetEnumerator() is implemented in a typical/proper (*) way, then you can safely enumerate any number of times - each foreach will be a new call to GetEnumerator() which returns a new instance of the IEnumerator. But it could be that in some situations it returns the same IEnumerator instance that's already been partially or fully enumerated, so it all really just depends on the specific intended usage of that particular IEnumerable.

*^{I'm pretty sure returning the same enumerator multiple times is actually a violation of the implied contract for the pattern, but I have seen some implementations that do it anyway.}