Language of your choice: library documentation
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...
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#.
|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:
You want to write an enumerator that returns all the strings in order. So you write this method in the StringNode class:
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 takes care of managing the stack and invoking
MoveNext on the deepest instance of
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.
|InternalList< Frame >||_stack|
|NestedEnumerator (Frame root)|
|void System.Collections.IEnumerator.||Reset ()|
|void IDisposable.||Dispose ()|