Enumerating Collections that are not inherently IEnumerable ?

Question

When you want to recursively enumerate a hierarchical object, selecting some elements based on some criteria, there are numerous examples of techniques like "flattening" and then filtering using Linq : like those found here :

link text

But, when you are enumerating something like the Controls collection of a Form, or the Nodes collection of a TreeView, I have been unable to use these types of techniques because they seem to require an argument (to the extension method) which is an IEnumerable collection : passing in SomeForm.Controls does not compile.

The most useful thing I found was this :

link text

Which does give you an extension method for Control.ControlCollection with an IEnumerable result you can then use with Linq.

I've modified the above example to parse the Nodes of a TreeView with no problem.

public static IEnumerable<TreeNode> GetNodesRecursively(this TreeNodeCollection nodeCollection)
{
    foreach (TreeNode theNode in nodeCollection)
    {
        yield return theNode;

        if (theNode.Nodes.Count > 0)
        {
            foreach (TreeNode subNode in theNode.Nodes.GetNodesRecursively())
            {
                yield return subNode;
            }
        }
    }
}

This is the kind of code I'm writing now using the extension method :

    var theNodes = treeView1.Nodes.GetNodesRecursively();

    var filteredNodes = 
    (
        from n in theNodes
            where n.Text.Contains("1")
                select n
    ).ToList();

And I think there may be a more elegant way to do this where the constraint(s) are passed in.

What I want to know if it is possible to define such procedures generically, so that : at run-time I can pass in the type of collection, as well as the actual collection, to a generic parameter, so the code is independent of whether it's a TreeNodeCollection or Controls.Collection.

It would also interest me to know if there's any other way (cheaper ? fastser ?) than that shown in the second link (above) to get a TreeNodeCollection or Control.ControlCollection in a form usable by Linq.

A comment by Leppie about 'SelectMany in the SO post linked to first (above) seems like a clue.

My experiments with SelectMany have been : well, call them "disasters." :)

Appreciate any pointers. I have spent several hours reading every SO post I could find that touched on these areas, and rambling my way into such exotica as the "y-combinator." A "humbling" experience, I might add :)

Answer 1

I'm not sure about TreeNodes, but you can make the Controls collection of a form IEnumerable by using System.Linq and, for example

var ts = (from t in this.Controls.OfType<TextBox>
                 where t.Name.Contains("fish")
                 select t);
//Will get all the textboxes whose Names contain "fish"

Sorry to say I don't know how to make this recursive, off the top of my head.

Answer 2

This code should do the trick

public static class Extensions
{
    public static IEnumerable<T> GetRecursively<T>(this IEnumerable collection,
        Func<T, IEnumerable> selector)
    {
        foreach (var item in collection.OfType<T>())
        {
            yield return item;

            IEnumerable<T> children = selector(item).GetRecursively(selector);
            foreach (var child in children)
            {
                yield return child;
            }
        }
    }
}

Here's an example of how to use it

TreeView view = new TreeView();

// ...

IEnumerable<TreeNode> nodes = view.Nodes.
    .GetRecursively<TreeNode>(item => item.Nodes);

Update: In response to Eric Lippert's post.

Here's a much improved version using the technique discussed in All About Iterators.

public static class Extensions
{
    public static IEnumerable<T> GetItems<T>(this IEnumerable collection,
        Func<T, IEnumerable> selector)
    {
        Stack<IEnumerable<T>> stack = new Stack<IEnumerable<T>>();
        stack.Push(collection.OfType<T>());

        while (stack.Count > 0)
        {
            IEnumerable<T> items = stack.Pop();
            foreach (var item in items)
            {
                yield return item;

                IEnumerable<T> children = selector(item).OfType<T>();
                stack.Push(children);
            }
        }
    }
}

I did a simple performance test using the following benchmarking technique. The results speak for themselves. The depth of the tree has only marginal impact on the performance of the second solution; whereas the performance decreases rapidly for the first solution, eventually leadning to a StackOverflowException when the depth of the tree becomes too great.

Answer 3

I guess you are asking for something like this.

public static IEnumerable<T> <T,TCollection> GetNodesRecursively(this TCollection nodeCollection, Func<T, TCollection> getSub)
 where T, TCollection: IEnumerable
{   
    foreach (var theNode in )
    {
        yield return theNode;
        foreach (var subNode in GetNodesRecursively(theNode, getSub))
        {
            yield return subNode;
        }
    }
}

var all_control = GetNodesRecursively(control, c=>c.Controls).ToList();

Answer 4

Based on mrydengren's solution:

public static IEnumerable<T> GetRecursively<T>(this IEnumerable collection,
    Func<T, IEnumerable> selector,
    Func<T, bool> predicate)
{
    foreach (var item in collection.OfType<T>())
    {
        if(!predicate(item)) continue;

        yield return item;

        IEnumerable<T> children = selector(item).GetRecursively(selector, predicate);
        foreach (var child in children)
        {
            yield return child;
        }
    }
}


var theNodes = treeView1.Nodes.GetRecursively<TreeNode>(
    x => x.Nodes,
    n => n.Text.Contains("1")).ToList();

Edit: for BillW

Answer 5

You seem to be on the right track and the answers above have some good ideas. But I note that all these recursive solutions have some deep flaws.

Let's suppose the tree in question has a total of n nodes with a max tree depth of d <= n.

First off, they consume system stack space in the depth of the tree. If the tree structure is very deep, then this can blow the stack and crash the program. Tree depth d is O(lg n), depending on the branching factor of the tree. Worse case is no branching at all -- just a linked list -- in which case a tree with only a few hundred nodes will blow the stack.

Second, what you're doing here is building an iterator that calls an iterator that calls an iterator ... so that every MoveNext() on the top iterator actually does a chain of calls that is again O(d) in cost. If you do this on every node, then the total cost in calls is O(nd) which is worst case O(n^2) and best case O(n lg n). You can do better than both; there's no reason why this cannot be linear in time.

The trick is to stop using the small, fragile system stack to keep track of what to do next, and to start using a heap-allocated stack to explicitly keep track.

You should add to your reading list Wes Dyer's article on this:

http://blogs.msdn.com/wesdyer/archive/2007/03/23/all-about-iterators.aspx

He gives some good techniques at the end for writing recursive iterators.

Answer 6

I have an elegant, efficient and reusable solution for recusrive iterators. See my blog post about it.

Thanks, Arnon.

PS: I'd really like to know what you think about my solution. Please let me know :-)