将FILO与嵌套集合一起使用 [英] Using FILO with nested collections
问题描述
我有一个我们称为Foo的类型，它可以容纳子Foo对象的集合. Foo是一次性的，因此，无论何时处置一个孩子，它都会将其添加到父母的Children系列中.
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.
此示例用法如下:
using (var a = AddChild(Root, "a"))
{
using (var a1 = AddChild(a, "a1"))
{
using (var a1a = AddChild(a1, "a1a"))
{
}
}
在此示例中，仅将a1a添加到a1时(而不是之前).我很难弄清的是一种干净的方式来编写GetAllFoos方法，该方法以FILO顺序返回展平列表中的所有对象.
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.
在这种情况下，我只是递归地遍历每个孩子，还是可以使用一些精美的LINQ来尝试合并这些集合?我正在使用它来获取整个应用程序的性能评估快照，并且在某些情况下，我们有可能在配置文件中调用GetAllMeasurements，因此方法调用的性能很重要.
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.
这是一个完整的示例应用程序，显示了预期的结果.我必须同时支持FIFO和FILO.我有一个FIFO实现正在工作，但是我不确定在FILO中以相反方式处理此问题的最佳方法.
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;
}
}
}
推荐答案
正如我在评论中提到的，您具有树结构.没有花哨的高效标准LINQ解决方案，但是您可以使用相当高效的通用Traverse方法来形成我对:
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();
}
}
}
有了该帮助器，GetAllFoosFIFO()就这么简单:
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);
}
对于GetAllFoosFILO()，您需要传递preorder = false并以相反的顺序迭代Children:
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);
}
这篇关于将FILO与嵌套集合一起使用的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
