Johnathon Sullinger Johnathon Sullinger - 1 month ago 17
C# Question

Using FILO with nested collections

I've got a Type that we'll call

Foo
that can hold a collection of children
Foo
objects. Foo is Disposable, so when ever a child is disposed of, it will then add itself to the parent's Children collection.

An example usage of this looks like:

using (var a = AddChild(Root, "a"))
{
using (var a1 = AddChild(a, "a1"))
{
using (var a1a = AddChild(a1, "a1a"))
{

}
}


In this example
a1a
is only added to
a1
when it is disposed, and not before. What I am having difficulty in figuring out is a clean way of writing a
GetAllFoos
method that returns all of the objects in a flattened list, in a FILO order.

In this case, would I just recursively iterate over each child, or is there some fancy LINQ I can use to try and consolidate these collections? I'm using this to take performance measurement snapshots through-out the app, and it's possible that we would call GetAllMeasurements in some cases during a profile so the performance of the method call is important.

This is a complete example app that shows what the expected results would look like. I have to support both FIFO and FILO. I've got a FIFO implementation working but I'm not sure on the best way to handle this inversely for FILO.

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

namespace FILO_Example
{
public class Foo : IDisposable
{
internal Foo parent;

public Foo(Foo parent = null)
{
this.parent = parent;
}

public string Name { get; set; }
public List<Foo> Children { get; } = new List<Foo>();

public void Dispose() => this.parent.Children.Add(this);
}

class Program
{
public static Foo Root { get; } = new Foo { Name = "Root" };

static void Main(string[] args)
{
// level 1
using (var a = AddChild(Root, "a"))
{
using (var a1 = AddChild(a, "a1"))
{
using (var a1a = AddChild(a1, "a1a"))
{

}
}

using (var a2 = AddChild(a, "a2"))
{

}
}

using (var b = AddChild(Root, "b"))
{
using (var b1 = AddChild(b, "b1"))
{

}
}

List<Foo> allFoos = GetAllFoosFILO().ToList();

Console.WriteLine(allFoos[0]); // Should be b1
Console.WriteLine(allFoos[1]); // Should be b
Console.WriteLine(allFoos[2]); // Should be a2
Console.WriteLine(allFoos[3]); // Should be a1a
Console.WriteLine(allFoos[4]); // Should be a1
Console.WriteLine(allFoos[5]); // Should be a
}

static IEnumerable<Foo> GetAllFoosFILO()
{
return new List<Foo>();
}

static IEnumerable<Foo> GetAllFoosFIFO()
{
var fooStack = new Stack<Foo>();
fooStack.Push(Root);
while (fooStack.Count > 0)
{
Foo currentFoo = fooStack.Pop();
yield return currentFoo;

// If we have children, add them in reverse order so that it's a First-In-First-Out stack
// then the while loop will yield each child element.
if (currentFoo.Children.Count > 0)
{
List<Foo> fooChildren = currentFoo.Children;
for (int currentIndex = fooChildren.Count - 1; currentIndex >= 0; currentIndex--)
{
fooStack.Push(fooChildren[currentIndex]);
}
}
}
}

static Foo AddChild(Foo parent, string name)
{
var child = new Foo(parent) { Name = name };
return child;
}
}
}

Answer

As I mentioned in the comments, you have a tree structure. There is no fancy efficient standard LINQ solution, but you can utilize the quite efficient generic Traverse method form my answer to Enumerating Directories iteratively in "postorder":

public static class TreeHelper
{
    public static IEnumerable<T> Traverse<T>(T node, Func<T, IEnumerable<T>> childrenSelector, bool preOrder = true)
    {
        var stack = new Stack<IEnumerator<T>>();
        var e = Enumerable.Repeat(node, 1).GetEnumerator();
        try
        {
            while (true)
            {
                while (e.MoveNext())
                {
                    var item = e.Current;
                    var children = childrenSelector(item);
                    if (children == null)
                        yield return item;
                    else
                    {
                        if (preOrder) yield return item;
                        stack.Push(e);
                        e = children.GetEnumerator();
                    }
                }
                if (stack.Count == 0) break;
                e.Dispose();
                e = stack.Pop();
                if (!preOrder) yield return e.Current;
            }
        }
        finally
        {
            e.Dispose();
            while (stack.Count != 0) stack.Pop().Dispose();
        }
    }
}

With that helper, the GetAllFoosFIFO() is simple as that:

static IEnumerable<Foo> GetAllFoosFIFO()
{
    return TreeHelper.Traverse(Root, foo => foo.Children.Count > 0 ? foo.Children : null);
}

while for GetAllFoosFILO() you need to pass preorder = false and iterate Children in reverse order:

static IEnumerable<Foo> GetAllFoosFILO()
{
    return TreeHelper.Traverse(Root, foo => foo.Children.Count > 0 ?
        Enumerable.Range(0, foo.Children.Count)
        .Select(i => foo.Children[foo.Children.Count - 1 - i]) : null, false);
}
Comments