Using FILO with nested collections

Question

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 1

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

Answer 2

This should work:

private static IEnumerable<Foo> GetAllFoosFILO(Foo foo)
{
    foreach (var c in ((IEnumerable<Foo>)foo.Children).Reverse())
    {
        var cc = GetAllFoosFILO(c);
        foreach (var ccc in cc)
        {
            yield return ccc;
        }
        yield return c;
    }
}

The weird cast in first foreach loop is for preventing use of List<T>.Reverse instead of Enumerable.Reverse<TSource> extension method which helps us to traverse tree in so called FILO way.

Bonus

With some small touches you can write FIFO like:

private static IEnumerable<Foo> GetAllFoosFIFO(Foo foo)
{
    foreach (var c in foo.Children)
    {
        yield return c;

        var cc = GetAllFoosFIFO(c);
        foreach (var ccc in cc)
        {
            yield return ccc;
        }
    }
}