Enumerators allow you to iterate over a collection of objects. The enumerators in C# are not you father's C++ iterators. This is a new animal that allows you to get a sequence of objects from any collection using the pull-model, even collections that promote recursive access.
Consider the challenge of in-order element retrieval from a binary-tree. This is a recursive problem, which lends itself to a push-model, not a pull-model. There is no traditional for loop that returns each element in increasing order. One would need to push the elements to a list first, and then walk the list.
Enumerators solve this problem with some compiler-magic. See Eric Lippert's blog on details of this.
Problem Statement: We need a generic collection that supports fast searching, and that we can iterate in two directions (increasing, and decreasing).
Solution: A generic Binary Tree. Let's code it up.
public class BinaryTree<T> where T : IComparable
We need it to be
IComparable so that we can insert it in the correct place.
It makes it easier to find also. Later we'll add the ability to return a
sequence that meets a LessThanEquals clause.
{
public enum Order { Forward, Reverse } // the transversal order
private class Node<X>
{
public Node(X value) { this.Value = value; }
public X Value;
public Node<X> Left, Right;
}
private Node<T> root;
A useful Binary Tree needs to have a good insert function. We'll use
the fact that the items support IComparable in order to put them in
the right place.
public void Add(T value)
{
if (null == this.root) this.root = new Node<T>(value);
else Add(Node<T> node, T value)
}
private static void Add(Node<T> node, T value)
{
Node<T> current = node;
bool done = false;
while (!done)
switch (current.Value.CompareTo(value)) {
case 1:
if (null != current.Left) current = current.Left;
else { current.Left = new Node<T>(value); done = true; }
break;
case -1:
if (null != current.Right) current = current.Right;
else { current.Right = new Node<T>(value); done = true; }
break;
case 0: done = true; break;
}
}
A fast Find function is the hallmark of a useful Binary Tree collection.
public bool Find(T value)
{
bool found = false;
Node<T> current = this.root;
while ((null != current) && (!found))
switch (current.Value.CompareTo(value)) {
case 1: current = current.Left; break;
case -1: current = current.Right; break;
case 0: found = true; break;
}
return found;
}
For techniques on balancing binary trees, see
algorithms + data structures = programs by Nicolas Wirth.
The function to return a sequence is recursive. We will use the yield return
statement to return the current item. You'll note that we appear to suspend
our function at each yield return statement, and then resume at that point when
the next value is requested. The "automatics" in the function are actually stored
between calls, giving IEnumerable functions the flavor of a state-machine. In fact,
that characteristic is exploited by some to create support for green-threads and
micro-threading applications (ala computer games). There are many cool patterns
that are available to state-machine coders that we'll explore in later posts.
public IEnumerable<T> GetAll(Order order)
{
if (null != this.root)
foreach (T t in getAll(order, this.root))
yield return t;
}
private static IEnumerable<T> getAll(Order order, Node<T> node)
{
Node<T> first, last;
if (Order.Forward == order) {
first = node.Left; last = node.Right;
} else {
first = node.Right; last = node.Left;
}
if (null != first)
foreach (T t in getAll(order, first)) yield return t;
yield return node.Value;
if (null != last)
foreach (T t in getAll(order, last)) yield return t;
}
I'll come back and modify that last function with an optional depth parameter once C# 4 ships. We'll code one more function to round it out.
public IEnumerable<T> LessThanEqual(Order order, T value)
{
if (null != this.root)
foreach (T t in lessThanEqual(order, this.root, value))
yield return t;
}
private static IEnumerable<T> lessThanEqual(Order order, Node<T> node, T value)
{
switch (node.Value.CompareTo(value)) {
case -1:
if (Order.Forward == order) {
if (null != node.Left)
foreach (T t in getAll(order, node.Left))
yield return t;
} else {
if (null != node.Right)
foreach (T t in lessThanEqual(order, node.Right, value))
yield return t;
}
yield return node.Value;
if (Order.Forward == order) {
if (null != node.Right)
foreach (T t in lessThanEqual(order, node.Right, value))
yield return t;
} else {
if (null != node.Left)
foreach (T t in getAll(order, node.Left))
yield return t;
}
break;
case 1:
if (null != node.Left)
foreach (T t in lessThanEqual(order, node.Left, value))
yield return t;
break;
case 0:
if (Order.Forward == order) {
if (null != node.Left)
foreach (T t in getAll(order, node.Left))
yield return t;
yield return node.Value;
} else {
yield return node.Value;
if (null != node.Left)
foreach (T t in getAll(order, node.Left))
yield return t;
}
break;
}
}
Let's test it:
static void Main(sting[] args)
{
BinaryTree<int> bt = new BinaryTree();
bt.Add(17);
bt.Add(6);
bt.Add(3);
bt.Add(35);
bt.Add(14);
bt.Add(26);
bt.Add(44);
bt.Add(11);
bt.Add(9);
bt.Add(10);
bt.Add(11);
foreach (int n in bt.LessThanEqual(BinaryTree<int>.Order.Reverse,16))
Console.WriteLine("{0} ", n);
Console.WriteLine("Finding 35 {0}", bt.Find(35));
Console.WriteLine("Finding 112 {0}", bt.Find(112));
}
OUTPUT
14
11
10
9
6
3
Finding 35 True
Finding 112 False
There it is. Enumerating through a collection recursively using the pull model.
