Loyc.Collections.NestedEnumerator< Frame, T > Struct Template Reference

Helper class. An enumerator that helps enumerate tree data structures. It maintains a virtual call stack that avoids the performance hit of using nested "yield return" statements in C#. More...

---

Source file:

• /Core/Loyc.Collections/Other/NestedEnumerator.cs

Inheritance diagram for Loyc.Collections.NestedEnumerator< Frame, T >:

Remarks

Helper class. An enumerator that helps enumerate tree data structures. It maintains a virtual call stack that avoids the performance hit of using nested "yield return" statements in C#.

Template Parameters

Frame	Frame data structure; represents the current 'depth' in a tree data structure, or the current 'stack frame' on a virtual stack. Typically, this parameter will either be EnumeratorFrame{T} or a struct that implements IEnumeratorFrame{Frame, T}.
T	Item data type returned by the enumerator.

This data type helps you solve the performance problem with using "yield return" recursively ().

To illustrate how to use NestedEnumerator{Frame,T} let's consider the case of binary tree traversal. Suppose you define this data structure to hold a subtree of a sorted binary tree of strings:

internal class StringNode : IEnumerable<string>
{
    internal StringNode LeftChild;
    internal string Value;
    internal StringNode RightChild;
    public IEnumerator<string> GetEnumerator() { ... }
}

You want to write an enumerator that returns all the strings in order. So you write this method in the StringNode class:

public IEnumerator<string> GetEnumerator()
{
    foreach(string item in LeftChild)
        yield return item;
    yield return Value;
    foreach(string item in RightChild)
        yield return item;
}

As explained in this web page, this implementation will be slow, and it will get slower and slower as the tree gets deeper.

NestedEnumerator helps to solve this problem using a "virtual stack". It keeps track of all the nested enumerators and always returns values from the current, deepest enumerator. The enumerator objects are called "frames", because they are "stack frames" on the virtual stack.

Each enumerator implements IEnumeratorFrame{Frame,T} instead of just IEnumerator{T}. A normal enumerator can only do one of two actions on each call to MoveNext(): it can return a T value, or stop. But an IEnumeratorFrame can do one of three things: it can return a T value, it can stop, or it can return a new (child) stack frame. These actions are represented by MoveNext return values of 1, 0, and -1 respectively.

You cannot use yield return with NestedEnumerator because it is not supported by the C# compiler, so using NestedEnumerator requires more developer effort. Here's how the GetEnumerator() method can be implemented using NestedEnumerator:

public IEnumerator<string> GetEnumerator()
{
    return new NestedEnumerator<Frame, string>(new Frame(this));
}
struct Frame : IEnumeratorFrame<Frame, string>
{
    StringNode self;
    int step;
    public Frame(StringNode self) { _self = self; step = 0; }

    int MoveNext(ref Frame frame, ref T current)
    {
        switch(++step) {
            case 1: frame = new Frame(self.LeftChild);  return -1;
            case 2: current = Value;                    return 1;
            case 3: frame = new Frame(self.RightChild); return -1;
        }
        return 0;
    }
}

The NestedEnumerator takes care of managing the stack and invoking MoveNext on the deepest instance of IEnumeratorFrame.

IEnumeratorFrame{Frame,T} is an unusual interface that requires Frame to be derived from the interface itself. The purpose of this design is to allow the Frame data type to be a struct, which allows the virtual stack to consist of value types (structs), which improves performance because a new object does not have to be allocated on the heap for every stack frame. Also, if Frame is a struct, NestedEnumerator can call IEnumeratorFrame{Frame,T}.MoveNext directly, rather than via interface dispatch, which also improves performance.

Type Constraints

Frame	:	IEnumeratorFrame
Frame	:	Frame
Frame	:	T

Public fields
T	_current
Frame	_frame
InternalList< Frame >	_stack

Properties
T	Current [get]
object System.Collections.IEnumerator.	Current [get]

Public Member Functions
	NestedEnumerator (Frame root)
bool	MoveNext ()
void System.Collections.IEnumerator.	Reset ()
void IDisposable.	Dispose ()