Comment aplatir un arbre via LINQ ?

Question

J'ai donc un arbre simple :

class MyNode
{
 public MyNode Parent;
 public IEnumerable<MyNode> Elements;
 int group = 1;
}

J'ai un IEnumerable<MyNode> . Je veux obtenir une liste de tous les MyNode (y compris les objets de nœuds internes ( Elements )) comme une liste plate Where group == 1 . Comment faire une telle chose via LINQ ?

Answer 1

En se basant sur la réponse de Konamiman, et sur le fait que l'ordre est inattendu, voici une version avec un paramètre de tri explicite :

public static IEnumerable<T> TraverseAndFlatten<T, V>(this IEnumerable<T> items, Func<T, IEnumerable<T>> nested, Func<T, V> orderBy)
{
    var stack = new Stack<T>();
    foreach (var item in items.OrderBy(orderBy))
        stack.Push(item);

    while (stack.Count > 0)
    {
        var current = stack.Pop();
        yield return current;

        var children = nested(current).OrderBy(orderBy);
        if (children == null) continue;

        foreach (var child in children)
            stack.Push(child);
    }
}

Et un exemple d'utilisation :

var flattened = doc.TraverseAndFlatten(x => x.DependentDocuments, y => y.Document.DocDated).ToList();

Answer 2

Ci-dessous, le code d'Ivan Stoev avec la particularité d'indiquer l'index de chaque objet dans le chemin. Par exemple, recherchez "Item_120" :

Item_0--Item_00
        Item_01

Item_1--Item_10
        Item_11
        Item_12--Item_120

retournerait l'élément et un tableau d'int [1,2,0]. Évidemment, le niveau d'imbrication est également disponible, comme la longueur du tableau.

public static IEnumerable<(T, int[])> Expand<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> getChildren) {
    var stack = new Stack<IEnumerator<T>>();
    var e = source.GetEnumerator();
    List<int> indexes = new List<int>() { -1 };
    try {
        while (true) {
            while (e.MoveNext()) {
                var item = e.Current;
                indexes[stack.Count]++;
                yield return (item, indexes.Take(stack.Count + 1).ToArray());
                var elements = getChildren(item);
                if (elements == null) continue;
                stack.Push(e);
                e = elements.GetEnumerator();
                if (indexes.Count == stack.Count)
                    indexes.Add(-1);
                }
            if (stack.Count == 0) break;
            e.Dispose();
            indexes[stack.Count] = -1;
            e = stack.Pop();
        }
    } finally {
        e.Dispose();
        while (stack.Count != 0) stack.Pop().Dispose();
    }
}

Answer 3

De temps en temps, j'essaie de m'attaquer à ce problème et de concevoir ma propre solution qui prend en charge des structures arbitrairement profondes (sans récursion), effectue une traversée en largeur d'abord, et n'abuse pas trop des requêtes LINQ ou n'exécute pas de manière préemptive la récursion sur les enfants. Après avoir creusé dans le Source .NET et en essayant de nombreuses solutions, j'ai finalement trouvé cette solution. Elle est finalement très proche de la réponse de Ian Stoev (dont je viens de voir la réponse), mais la mienne n'utilise pas de boucles infinies et n'a pas de flux de code inhabituel.

public static IEnumerable<T> Traverse<T>(
    this IEnumerable<T> source,
    Func<T, IEnumerable<T>> fnRecurse)
{
    if (source != null)
    {
        Stack<IEnumerator<T>> enumerators = new Stack<IEnumerator<T>>();
        try
        {
            enumerators.Push(source.GetEnumerator());
            while (enumerators.Count > 0)
            {
                var top = enumerators.Peek();
                while (top.MoveNext())
                {
                    yield return top.Current;

                    var children = fnRecurse(top.Current);
                    if (children != null)
                    {
                        top = children.GetEnumerator();
                        enumerators.Push(top);
                    }
                }

                enumerators.Pop().Dispose();
            }
        }
        finally
        {
            while (enumerators.Count > 0)
                enumerators.Pop().Dispose();
        }
    }
}

Un exemple de travail peut être trouvé aquí .

Answer 4

Le moyen le plus simple et le plus clair de résoudre ce problème est d'utiliser une requête LINQ récursive. Cette question : Exprimer la récursion dans LINQ a beaucoup de discussions à ce sujet, et cette réponse particulière http://stackoverflow.com/a/793531/1550 explique en détail comment le mettre en œuvre.

Answer 5

void Main()
{
    var allNodes = GetTreeNodes().Flatten(x => x.Elements);

    allNodes.Dump();
}

public static class ExtensionMethods
{
    public static IEnumerable<T> Flatten<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> childrenSelector = null)
    {
        if (source == null)
        {
            return new List<T>();
        }

        var list = source;

        if (childrenSelector != null)
        {
            foreach (var item in source)
            {
                list = list.Concat(childrenSelector(item).Flatten(childrenSelector));
            }
        }

        return list;
    }
}

IEnumerable<MyNode> GetTreeNodes() {
    return new[] { 
        new MyNode { Elements = new[] { new MyNode() }},
        new MyNode { Elements = new[] { new MyNode(), new MyNode(), new MyNode() }}
    };
}

class MyNode
{
    public MyNode Parent;
    public IEnumerable<MyNode> Elements;
    int group = 1;
}