c#之对嵌套集合使用 FILO

我有一个我们称之为 Foo 的类型，它可以容纳子 Foo 对象的集合。 Foo 是一次性的，所以当一个 child 被处理掉时，它会把自己添加到 parent 的 child 集合中。

这个用法的示例如下:

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

在此示例中，a1a 仅在被释放时添加到 a1 中，而不是之前。我难以弄清楚的是一种编写 GetAllFoos 方法的简洁方法，该方法以 FILO 顺序返回展平列表中的所有对象。

在这种情况下，我会递归地遍历每个子项，还是可以使用一些奇特的 LINQ 来尝试合并这些集合？我正在使用它来获取整个应用程序的性能测量快照，并且在某些情况下我们可能会在配置文件期间调用 GetAllMeasurements，因此方法调用的性能很重要。

这是一个完整的示例应用，展示了预期的结果。我必须同时支持 FIFO 和 FILO。我有一个 FIFO 实现在工作，但我不确定为 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; 
        } 
    } 
} 

请您参考如下方法:

正如我在评论中提到的，你有一个树结构。没有特别高效的标准 LINQ 解决方案，但您可以利用非常有效的通用 Traverse 方法形成我对 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(); 
        } 
    } 
} 

有了这个助手，GetAllFoosFIFO() 就这么简单:

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

而对于 GetAllFoosFILO()，您需要传递 preorder = false 并以相反的顺序迭代 Children:

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