6
\$\begingroup\$

I have a domain object that I have no control over which itself contains a collection of this same type. This is a classical hierarichal representation like in a tree node hierarchy. I would like to be able to enumerate the whole hierarchy in a single call so I came up with this extension method:

public static class MyObjectExtensions
{
    public static IEnumerable<MyObject> FindAllObjectsRecursive(this MyObject myObject)
    {
        var objects = new List<MyObject>();

        objects.Add(myObject);

        foreach (MyObject innerObject in myObject.Objects)
        {
            objects.AddRange(innerObject.FindAllObjectsRecursive());
        }

        return objects;
    }
}

Unfortunately I am not really satisfied by this method because it would definitely cause issues in a large tree span scenario. So I was wondering if anyone would have a solution for that. I did think of using a parameter for the list but I was thinking there must be a better solution.

Here is how I intend to use this method:

var myObject = new MyObject();
var allObjects = myObject.FindAllObjectsRecursive();

And here is the domain object:

public class MyObject
{
    public IEnumerable<MyObject> Objects { get; set; }
}
\$\endgroup\$
3
\$\begingroup\$

If you afraid that your tree can be too deep, as mentioned already, you can use Stack or Queue, depending on how you would like to traverse the tree. Here the sample code how to accomplish your task with Queue:

using System.Collections.Generic;
using System.Linq;

public static IEnumerable<MyObject> FindAllObjectsRecursive(this MyObject obj)
{
    var queue = new Queue<MyObject>();
    queue.Enqueue(obj); // Note that you can add first object in the queue constructor

    var result = new List<MyObject>();

    while (queue.Any())
    {
        var current = queue.Dequeue();
        result.Add(current);
        if (null != current.Objects)
        {
            foreach (MyObject inner in current.Objects)
            {
                queue.Enqueue(inner);
            }
        }            
    }

    return result;
}
\$\endgroup\$
  • \$\begingroup\$ Exactly the kind of solution I was look for :) I removed the null check though because if you try to call a method on a null object, your problem is somewhere else! I will wait to see if there is other interesting solutions and then accept it. \$\endgroup\$ – Ucodia Dec 19 '14 at 11:01
  • \$\begingroup\$ There were a number of edits to the question after you posted. You may want to double check to make sure your answer is still valid. \$\endgroup\$ – RubberDuck Dec 19 '14 at 13:51
  • 1
    \$\begingroup\$ Yoda conditions I do not like. Odd to read they are. \$\endgroup\$ – ANeves Dec 19 '14 at 14:58
  • \$\begingroup\$ @ANeves I never use null on the left side either but there used to be a valid reason for it: stackoverflow.com/questions/2369226/null-check-in-java \$\endgroup\$ – Ucodia Dec 19 '14 at 15:32
  • \$\begingroup\$ @Ucodia But it never applied to C# (or Java). \$\endgroup\$ – ANeves Dec 19 '14 at 18:48
5
\$\begingroup\$

There is a way, and it is beautiful. Instead of using recursion, you use iteration by placing the top level object on a Stack (or Queue depending on whether you want a depth-first or a breadth-first search). Then you go into a loop where you pop off the first item, check to see if it has descendants, and add them to the stack. By the time the stack/queue is empty you'll have traversed the entire tree.

You were halfway there with your decision to manage a collection that represents the entire set of objects, but the nature of the Stack/Queue allows you to access deeper and deeper properties without having to go deeper and deeper in the call stack.

Example from MSDN on how to traverse a directory tree: http://msdn.microsoft.com/en-us/library/bb513869.aspx

Whether you choose to implement this as an extension method or not is up to you. I also strongly advise asking yourself whether you really need a collection of all descendants, or if you simply want to iterate through all descendants of a certain object? The answer to that question will determine whether the traversal belongs in what would be acting on the top-level object or whether the traversal should be abstracted away.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the great solution, it seems to be what @stukselbax proposed too. \$\endgroup\$ – Ucodia Dec 19 '14 at 11:04
  • \$\begingroup\$ There were a number of edits to the question after you posted. You may want to double check to make sure your answer is still valid. \$\endgroup\$ – RubberDuck Dec 19 '14 at 13:52
  • \$\begingroup\$ Yes, while there were issues around this question in terms of whether the example compiled or not, the intent of OP's question was quite clear to me. I'm going to post on meta about this post, actually, I think it merits discussion. \$\endgroup\$ – moarboilerplate Dec 19 '14 at 15:02
  • \$\begingroup\$ Also, I proposed it first :) \$\endgroup\$ – moarboilerplate Dec 19 '14 at 15:05
  • \$\begingroup\$ You indeed proposed this solution first but has there is no clear code sample for people looking into the same issue later, I had to accept the other reply with code. If you edit I will change the accepted answer. \$\endgroup\$ – Ucodia Dec 21 '14 at 12:37
2
\$\begingroup\$

Option 1 - don't create children lists

One improvement is to avoid creating multiple lists that feed into each-other.
We can do this by passing the list as an argument.

public static ICollection<MyObject> GetDescendents(this MyObject item)
{
    // This could be a List<T>, a Queue<T>, a Stack<T>, etc. Take your pick.
    var allObjects = new List<MyObject>();
    item.GetDescendentsInto(allObjects);
    return allObjects;
}
private static void GetDescendentsInto(this MyObject myObject, ICollection<MyObject> listToPopulate)
{
    listToPopulate.Add(myObject);

    foreach (MyObject innerObject in myObject.Objects)
    {
        innerObject.GetDescendentsInto(listToPopulate);
    }
}

Option 2 - use enumerators and yield

Depending on your concrete situation, you could also use yield to only enumerate the results as you need them.

public static IEnumerable<MyObject> GetDescendentsLazily(this MyObject item)
{
    yield return item;

    foreach (MyObject child in item.Objects)
    {
        var descendents = child.GetDescendents();
        foreach (var descendent in descendents)
        {
            yield return descendent;
        }
    }
}

This has advantages and drawbacks. It gives you support for infinite lists, but it also creates a lot of enumerators.

If you're interested in this, you could avoid recursion by unrolling the list. It will give you a result similar to what @moarboilerplate proposes, but using yield.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.