Apply "yield return" recursively - iterating tree-datastructures

Download TreeIterations_src - 13.64 KB

Introduction

"tree-datastructures" are often used (e.g: Xml, Directory-System, Forms.ControlCollection).
they are very powerfull, 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 by 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.
  

One can do this, and its 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 its 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 explaination not needed, i think)

Then the only open question should be: "how to get _GetChilds?"
I've got it by an reflection-"investigation" of the types "TItem" and "TCollection".
Such "investigations" are very slow operations - for that i do it only once per "generic shape" of the Recurser.
Namely in a 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 3 "deep-iterations": iterate Treenodes, DirectoryInfos, 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 seen: One of my secrets is, how the useful thing called "Depth" is implemented. You can find out in the download ;)

Points of Interest:

The Methods "TopDown()", "BottomUp()" are of DataType "IEnumerable<TItem>". So in c#3.0 they will support type-inferring, and also the wonderful Linq-stuff.

I was unshure about the "skill-level", i had to assign. To beginners its useful to get a way of recursion in simple foreach-manner.
The functionality better fits to "intermediate" or "advanced", because "yield return", "static constructors", "class-redefining" by using-statement, "reflection" - those features seem to me not to be the pure beginner-stuff.