Click here to Skip to main content
15,867,594 members
Articles / Programming Languages / C#

Apply "yield return" recursively - iterating tree data structures

Rate me:
Please Sign up or sign in to vote.
4.29/5 (16 votes)
21 Feb 2008CPOL2 min read 52.6K   179   27   8
A generic function that enables "deep-iterating" the leafs of arbitrary tree data structures simply using foreach.

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:

C#
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 ;):

C#
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:

C#
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:

C#
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.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Germany Germany
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

 
General[My vote of 2] A better solution! Pin
Member 224161228-Aug-10 10:10
Member 224161228-Aug-10 10:10 
Hi,

I have a much better solution to this problem, which you can find here. The advantages of my solution are:
1. The efficiency of the algorithm isn't affected. E.g. A simple traversal of a binary tree (in-order, pre-order or post-order) is generally O(n), but with your solution it's between O(n*log n) and O(n^2) - depending whether the tree is balanced or not. This is because in every level in the tree you iterate again over all of its ancestors, and not only on its direct children. And the reason for that is that you can only "yield return" a single element at a time, so you must iterate each time on the entire result of the recursive call. (You can't "yield return TopDown(...);"). I used a "dirty" trick to do it, which works like a charm Smile | :)

2. My solution is a simple and very generic reusable class that you can use to create any iterator that "embeds" another iterator inside it, in a very easy way.

Please tell me what you think.

Thanks,
Arnon.
GeneralRe: [My vote of 2] A better solution! Pin
Mr.PoorEnglish28-Aug-10 10:49
Mr.PoorEnglish28-Aug-10 10:49 
GeneralRe: [My vote of 2] A better solution! Pin
Member 224161230-Aug-10 2:59
Member 224161230-Aug-10 2:59 
GeneralVote 4: Stanford has a better solution running on n(O) time, and creates an ordered list from Tree Pin
ProtoBytes25-Mar-10 1:39
ProtoBytes25-Mar-10 1:39 
GeneralRe: Vote 4: Stanford has a better solution running on n(O) time, and creates an ordered list from Tree Pin
Mr.PoorEnglish28-Aug-10 11:13
Mr.PoorEnglish28-Aug-10 11:13 
Generalum Pin
konikula6-Jan-10 21:31
konikula6-Jan-10 21:31 
GeneralSomething similar Pin
leppie31-Mar-09 23:05
leppie31-Mar-09 23:05 
GeneralVery nice! Pin
Huanacaraz28-Mar-09 8:19
Huanacaraz28-Mar-09 8:19 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.