Creating a Stack<T> with anonymous type

Question

Hi people, I have the a class Foo like this:

 class Foo
 {
  public int id{get;set;}
  public IEnumerable<Foo> Childs;
       //some other properties
 }

Now I want to process some business logic on a Foo-Object and all it's children like this:

 public void DoSomeWorkWith(Foo x)
 {
  var firstItem = new {level = 0, item = x};
  var s = new Stack<?>(?); //What type to use?
  s.Push(firstItem);
  while(s.Any())
  {
    var current = s.Pop();
    DoSomeBusiness(current.item);
    DoSomeMoreBusiness(current.item);
    Log(current.level, current.item.id);
    foreach(Foo child in current.item.Childs)
       s.Push(new {level = current.level + 1, item = child});
   }
}

I need to keep track of the (relative) level/depth of the childs. How do I create a Stack<T> for the anonymous type? Of course I could create a simple class instead of the anonymous type (or a more complicated recursive function), but how to solve this problem without an additional class?

Answer 1

How about:

public static Stack<T> CreateEmptyStack<T>(T template) {
    return new Stack<T>();
}
...
var stack = CreateEmptyStack(firstItem);

This uses generic type inference to handle the T.

Answer 2

You could just put it into a method like this:

public Stack<T> CreateStackWithInitialItem<T>(T initialItem)
{
    var s = new Stack<T>();
    s.Push(initialItem);
    return s;
}

and then use it like that:

public void DoSomeWorkWith(Foo x)
{
    var s = CreateStackWithInitialItem(new {level = 0, item = x});
    while(s.Any())
    {
        ...
    }
}

Answer 3

You could simplify your code by using recursion instead of pushing things onto a temporary stack and temporary objects. For example:

// (If you're not using C# 4, you can replace the default level with a function
// overload or just remove the default value)

void ProcessFooRecursive(Foo foo, int level = 0) 
{
    DoSomeBusiness(foo);
    DoSomeMoreBusiness(foo);
    Log(level, foo.id);

    var newDepth = level + 1;
    foreach (var child in foo.Childs)
    {
        ProcessFooRecursive(child, newDepth);
    }
}

Answer 4

What about using tuples (System.Tuple<>) instead of anonymous types?

public void DoSomeWorkWith(Foo x)
{
    var firstItem = new Tuple<int, Foo>(0, x);
    var s = new Stack<Tuple<int, Foo>>();
    s.Push(firstItem);
    while (s.Any())
    {
        var current = s.Pop();
        DoSomeBusiness(current.Item2);
        DoSomeMoreBusiness(current.Item2);
        Log(current.Item1, current.Item2.id);
        foreach (Foo child in current.Item2.Childs)
            s.Push(new Tuple<int, Foo>(current.Item1 + 1, child));
    }
}

Even though this is not the primary use case for dynamic objects (through you know all types involved at design time) you could also make use of System.Dynamic.ExpandoObject. If you do so, be sure to test for performance differences because of the overhead.

public void DoSomeWorkWith(Foo x)
{
    dynamic firstItem = new ExpandoObject();
    firstItem.level = 1;
    firstItem.item = x;

    var s = new Stack<dynamic>();
    s.Push(firstItem);
    while (s.Any())
    {
        var current = s.Pop();
        DoSomeBusiness(current.item);
        DoSomeMoreBusiness(current.item);
        Log(current.level, current.item.id);
        foreach (Foo child in current.item.Childs)
        {
            dynamic next = new ExpandoObject();
            next.level = current.level + 1;
            next.item = child;
            s.Push(next);
        }
    }
}