Click here to Skip to main content
Click here to Skip to main content
Go to top

Apply "yield return" recursively - iterating tree data structures

, 21 Feb 2008
Rate this:
Please Sign up or sign in to vote.
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:

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 Wink | ;) :

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 Wink | ;)

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)

Share

About the Author

Mr.PoorEnglish

Germany Germany
No Biography provided

Comments and Discussions

 
General[My vote of 2] A better solution! PinmemberMember 224161228-Aug-10 10:10 
GeneralRe: [My vote of 2] A better solution! PinmemberMr.PoorEnglish28-Aug-10 10:49 
GeneralRe: [My vote of 2] A better solution! PinmemberMember 224161230-Aug-10 2:59 
GeneralVote 4: Stanford has a better solution running on n(O) time, and creates an ordered list from Tree PinmemberTheArchitectmc25-Mar-10 1:39 
The Great Tree-List Recursion Problem[^]
 
~TheArch
Thumbs Up | :thumbsup:

GeneralRe: Vote 4: Stanford has a better solution running on n(O) time, and creates an ordered list from Tree PinmemberMr.PoorEnglish28-Aug-10 11:13 
Generalum Pinmemberkonikula6-Jan-10 21:31 
GeneralSomething similar Pinmvpleppie31-Mar-09 23:05 
GeneralVery nice! PinmemberHuanacaraz28-Mar-09 8:19 

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

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

| Advertise | Privacy | Mobile
Web02 | 2.8.140916.1 | Last Updated 21 Feb 2008
Article Copyright 2008 by Mr.PoorEnglish
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid