Apply yield return recursively - iterating tree data structures

• Download source code - 15.2 KB

Introduction

"Tree-data structures" are very commonly used (e.g.: XML, Directory system, Forms.ControlCollection). They are very powerful, but a little unhandy:

• you cannot enumerate them by foreach. For each action you want to execute on each tree-leaf you have to implement a specialized recursive method.
• its not trivial to leave the recursive execution before it reaches its natural end.
• passing some arguments (e.g. search-patterns of a recursive search) blows out the function-stack.

How nice it would be if one could do a "deep-iteration" of the tree-leafs using a simple foreach!

• no more recursive functions
• leave the "recursion" with "break"
• the leafs come to the search-patterns, not the other way round: injecting search-patterns into recursive calls.

We can do this, and it is not that complicated:

public static class Recurser<TItem, TCollection> 
       where TCollection : IEnumerable {

  private static MethodInfo _GetChilds;
  
  // ...
  
  public static IEnumerable<TItem> TopDown(TCollection Coll) {
     foreach (TItem Itm in Coll) {
        yield return Itm;
        TCollection Coll2 = (TCollection)_GetChilds.Invoke(Itm, null);
        foreach (TItem Itm2 in TopDown(Coll2)) { yield return Itm2; }
     }
  }
}

Why the hack is it called "TopDown"? Ha, because I've done a "BottomUp" too ;):

public static IEnumerable<TItem> BottomUp(TCollection Coll) {
 foreach (TItem Itm in Coll) {
    TCollection Coll2 = (TCollection)_GetChilds.Invoke(Itm, null);
    foreach (TItem Itm2 in BottomUp(Coll2)) { yield return Itm2; }
    yield return Itm;
 }
}

"TopDown" first yields the root-items, later the ... (more explanation not needed, I think).

Then, the only open question should be: "how to get _GetChilds?" I've got it using a Reflection-"investigation" of the types "TItem" and "TCollection". Such "investigations" are very slow operations - for that, I do them only once per "generic shape" of the Recurser. Namely in the static constructor:

static Recurser() {
    // since Reflection is very slow, this static constructor will be
    // executed only once per generic shaping
    Type tpItm = typeof(TItem);
    Type tpColl = typeof(TCollection);
    const BindingFlags BindFlags = BindingFlags.Public | BindingFlags.Instance;
    foreach (MemberInfo mi in tpItm.GetMembers(BindFlags)) {
        MethodInfo Proposed = null;
        switch (mi.MemberType) {
           case MemberTypes.Property:
              PropertyInfo p = (PropertyInfo)mi;
              if (p.PropertyType == tpColl) {
                 Proposed = p.GetGetMethod();
                 break;
              }
              continue;
           case MemberTypes.Method:
              MethodInfo m = (MethodInfo)mi;
              if (m.ReturnType == tpColl) {
                 Proposed = m;
                 break;
              }
              continue;
           default:
              continue;
        }
        if (Proposed.GetParameters().Length == 0) {
           _GetChilds = Proposed;
           return;
        }
    }
    throw new ArgumentException(string.Concat("can't find a " + 
       "recursive member in ", tpItm.Name, "!"));
}

Using the Code

Here, we have three "deep-iterations": iterate the TreeNodes, DirectoryInfos, and Controls on a Form:

using System;
using System.Drawing;
using System.Windows.Forms;
using System.Collections.Generic;
// To declare a generic shape of Recurser causes a quite long codeline.
// For that I prefer to pull it together in an using-statement
using Allnodes = Globals.Recurser<System.Windows.Forms.TreeNode,
   System.Windows.Forms.TreeNodeCollection>;
using AllDirs = Globals.Recurser<System.IO.DirectoryInfo,
   System.IO.DirectoryInfo[]>;
using AllControls = Globals.Recurser<System.Windows.Forms.Control,
   System.Windows.Forms.Control.ControlCollection>; 

namespace TreeIterations {
   public partial class frmMain : Form {

      public frmMain() {
         InitializeComponent();
         this.treeView1.ExpandAll();
      }

      private void btTest_Click(object sender, EventArgs e) {
         textBox1.Clear();
         WriteLine("Enumerating Treenodes from bottom upwards");
         foreach (TreeNode Nd in Allnodes.BottomUp(treeView1.Nodes)) {
            WriteLine("Depth: ", Allnodes.Depth, ", Name: ", Nd.ToString());
         }
         WriteLine();
         WriteLine("Enumerating Directories TopDown");
         System.IO.DirectoryInfo Root = new System.IO.DirectoryInfo(@"..\..\");
         foreach (System.IO.DirectoryInfo DI in AllDirs.TopDown(Root)) {
            WriteLine("Depth: ", AllDirs.Depth, ", FullName: ", DI.FullName);
         }
         WriteLine();
         WriteLine("Enumerating Controls TopDown");
         // call Recurser without using the useful "using AllControls" - Statement
         foreach (Control Ctl in Globals.Recurser
               <Control, Control.ControlCollection>.TopDown(this)) {
            // display tree indented
            WriteLine(
               new String(' ', AllControls.Depth * 2), 
               Ctl.GetType().Name, @" """, Ctl.Name, @"""");
         }
      }

      private void WriteLine(params object[] Segments) {
         textBox1.AppendText(string.Concat(Segments));
         textBox1.AppendText(Environment.NewLine);
      }
   }
}

Maybe you've noticed: one of my secrets is, how the useful thing called "Depth" is implemented. You can find this out in the attached download ;)

Points of Interest

The methods "TopDown()" and "BottomUp()" are of data type "IEnumerable<TItem>". So in C# 3.0, they will support type-inferring, and also the wonderful LINQ stuff.

I was unsure about the "skill-level" I had to assign. To beginners, this is useful as a way of recursion in a simple foreach-manner. The functionality better fits for "intermediate" or "advanced" levels, because "yield return", static constructors, class-redefining with the using-statement, Reflection - those features seem to me not to be pure beginner-stuff.