[Mono-dev] Action<T> used

[Jonathan Gilbert]

Just a little clean-up for any readers who don't already understand the
techniques being used:

At 10:41 AM 11/07/2006 +0200, Alejandro Serrano wrote:
>public void ForEach (Node node, Action<Node> action)
>{
>    action (node)

;

>    foreach (Node child in this.Subnodes) ForEach (child, action);
>}

This method could also be made an instance method of the "Node" class. I
think this is actually what the original poster had in mind:

public class Node
{
  ...

  public void ForEach(Action<Node> action)
  {
    action(this);

    foreach (Node child in Subnodes)
      child.ForEach(action);
  }
}

The original method shown for counting nodes shows a breadth-first search,
while this recursion will give a depth-first search. To do a ForEach with
breadth-first order, one uses a queue instead of a stack:

public class Node
{
  ...

  public void ForEach(Action<Node> action)
  {
    Queue<Node> remaining = new Queue<Node>();

    remaining.Enqueue(this);

    while (remaining.Count > 0)
    {
      Node node = remaining.Dequeue();

      action(node);

      foreach (Node child in node.Subnodes)
        remaining.Enqueue(child);
    }
  }
}

>Hope this helps ;-)
>
>Other solution would be using IEnumerable
>
>public class Node : IEnumerable<Node>

Implementing this interface here has nothing to do with being able to add
an arbitrary member that returns IEnumerator<Node>. It is not necessary for
EnumerateDescendents() and forces only a GetEnumerator() with the
IEnumerator<Node> return type.

>{
>    ...
>
>    public IEnumerator<Node> EnumerateDescendants ()
>    {
>       Queue<Node> todo = new Queue<Node> ();
>       todo.Enqueue (this);
>       while (todo.Count > 0)
>       {
>          Node node = todo.Enqueue ();

I'm pretty sure this should be a call to .Dequeue() :-)

>          yield node;

yield return node;

>          foreach (Node child in node.Subnodes) todo.Enqueue (child);
>       }
>    }
>}
>
>Now you can use:
>
>foreach (Node node in firstNode.EnumerateDescendants ())
>    doWhatYouWant (node);
>
>Alejandro Serrano

This enumerator could also be implemented recursively:

public class Node
{
  ...

  public IEnumerator<Node> EnumerateDescendents()
  {
    yield return this;
    foreach (Node child in Subnodes)
      foreach (Node descendent in child.EnumerateDescendents())
        yield return descendent;
  }
}

The code is shorter, and despite the foreach nesting it isn't really an
O(n^2) loop since the subtrees are disjoint. Overhead will be somewhat
higher, though, as the recursive call to EnumerateDescendents entails the
creation of a new object for maintaining the state of the enumeration, and
then every call to .MoveNext on the top-level enumerator will recurse down
along the path to the next child node to be returned, only to discard those
stack frames in order to return the node. Such is the penalty for faking
coroutines with state machines. :-)

The recursive implementation will return the nodes in a depth-first tree
walk order, while the queue-based approach will return the nodes in a
breadth-first tree walk order.

Jonathan Gilbert