将FILO与嵌套集合一起使用

我有一个我们称之为Foo的Type，它可以容纳一个孩子Foo对象的集合。 Foo是Disposable，所以当孩子被处理掉时，它会将自己添加到父母的Children系列中。

这个示例用法如下：

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

在这个例子中， a1a仅在a1a被添加到a1 ，而不是之前。 我弄清楚的是一种编写GetAllFoos方法的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 Children { get; } = new List(); 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 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 GetAllFoosFILO() { return new List(); } static IEnumerable GetAllFoosFIFO() { var fooStack = new Stack(); 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 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

正如我在评论中提到的，你有一个树形结构。 没有高效的标准LINQ解决方案，但您可以使用非常有效的通用Traverse方法形成我在“postorder”中迭代枚举目录的答案：

 public static class TreeHelper { public static IEnumerable Traverse(T node, Func> childrenSelector, bool preOrder = true) { var stack = new Stack>(); 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 GetAllFoosFIFO() { return TreeHelper.Traverse(Root, foo => foo.Children.Count > 0 ? foo.Children : null); } 

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

 static IEnumerable 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

这应该工作：

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

第一个foreach循环中的奇怪转换是为了防止使用List.Reverse而不是Enumerable.Reverse扩展方法，这有助于我们以所谓的FILO方式遍历树。

奖金

通过一些小的触摸，您可以编写FIFO，如：

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