Astackmiento de lista recursiva

Probablemente podría escribir esto yo mismo, pero la forma específica en que estoy tratando de lograrlo es echarme. Estoy intentando escribir un método de extensión genérico similar a los otros introducidos en .NET 3.5 que tomará un IEnumerable nested de IEnumerables (y así sucesivamente) y lo aplanará en un IEnumerable. ¿Alguien tiene alguna idea?

Específicamente, tengo problemas con la syntax del método de extensión en sí mismo para poder trabajar en un algoritmo de aplanamiento.

Hmm … No estoy seguro exactamente de lo que quieres aquí, pero aquí hay una opción de “un nivel”:

public static IEnumerable Flatten (this IEnumerable sequences) where TSequence : IEnumerable { foreach (TSequence sequence in sequences) { foreach(TElement element in sequence) { yield return element; } } } 

Si eso no es lo que quieres, ¿podrías proporcionar la firma de lo que quieres? Si no necesita un formulario genérico, y solo desea hacer el tipo de cosas que hacen los constructores de LINQ a XML, eso es razonablemente simple, aunque el uso recursivo de bloques de iteradores es relativamente ineficiente. Algo como:

 static IEnumerable Flatten(params object[] objects) { // Can't easily get varargs behaviour with IEnumerable return Flatten((IEnumerable) objects); } static IEnumerable Flatten(IEnumerable enumerable) { foreach (object element in enumerable) { IEnumerable candidate = element as IEnumerable; if (candidate != null) { foreach (object nested in candidate) { yield return nested; } } else { yield return element; } } } 

Tenga en cuenta que eso tratará una cadena como una secuencia de caracteres, sin embargo, es posible que desee que las cadenas de casos especiales sean elementos individuales en lugar de aplanarlos, según su caso de uso.

¿Eso ayuda?

Aquí hay una extensión que podría ayudar. Atravesará todos los nodos en su jerarquía de objetos y seleccionará los que coincidan con un criterio. Asume que cada objeto en su jerarquía tiene una propiedad de colección que contiene sus objetos secundarios.

Aquí está la extensión:

 /// Traverses an object hierarchy and return a flattened list of elements /// based on a predicate. /// /// TSource: The type of object in your collection. /// source: The collection of your topmost TSource objects. /// selectorFunction: A predicate for choosing the objects you want. /// getChildrenFunction: A function that fetches the child collection from an object. /// returns: A flattened list of objects which meet the criteria in selectorFunction. public static IEnumerable Map( this IEnumerable source, Func selectorFunction, Func> getChildrenFunction) { // Add what we have to the stack var flattenedList = source.Where(selectorFunction); // Go through the input enumerable looking for children, // and add those if we have them foreach (TSource element in source) { flattenedList = flattenedList.Concat( getChildrenFunction(element).Map(selectorFunction, getChildrenFunction) ); } return flattenedList; } 

Ejemplos (pruebas unitarias):

Primero necesitamos un objeto y una jerarquía de objetos nesteds.

Una clase de nodo simple

 class Node { public int NodeId { get; set; } public int LevelId { get; set; } public IEnumerable Children { get; set; } public override string ToString() { return String.Format("Node {0}, Level {1}", this.NodeId, this.LevelId); } } 

Y un método para obtener una jerarquía profunda de nodos de 3 niveles

 private IEnumerable GetNodes() { // Create a 3-level deep hierarchy of nodes Node[] nodes = new Node[] { new Node { NodeId = 1, LevelId = 1, Children = new Node[] { new Node { NodeId = 2, LevelId = 2, Children = new Node[] {} }, new Node { NodeId = 3, LevelId = 2, Children = new Node[] { new Node { NodeId = 4, LevelId = 3, Children = new Node[] {} }, new Node { NodeId = 5, LevelId = 3, Children = new Node[] {} } } } } }, new Node { NodeId = 6, LevelId = 1, Children = new Node[] {} } }; return nodes; } 

Primera prueba: aplanar la jerarquía, no filtrar

 [Test] public void Flatten_Nested_Heirachy() { IEnumerable nodes = GetNodes(); var flattenedNodes = nodes.Map( p => true, (Node n) => { return n.Children; } ); foreach (Node flatNode in flattenedNodes) { Console.WriteLine(flatNode.ToString()); } // Make sure we only end up with 6 nodes Assert.AreEqual(6, flattenedNodes.Count()); } 

Esto mostrará:

 Node 1, Level 1 Node 6, Level 1 Node 2, Level 2 Node 3, Level 2 Node 4, Level 3 Node 5, Level 3 

Segunda prueba: obtenga una lista de nodos que tengan un NodeId con número par

 [Test] public void Only_Return_Nodes_With_Even_Numbered_Node_IDs() { IEnumerable nodes = GetNodes(); var flattenedNodes = nodes.Map( p => (p.NodeId % 2) == 0, (Node n) => { return n.Children; } ); foreach (Node flatNode in flattenedNodes) { Console.WriteLine(flatNode.ToString()); } // Make sure we only end up with 3 nodes Assert.AreEqual(3, flattenedNodes.Count()); } 

Esto mostrará:

 Node 6, Level 1 Node 2, Level 2 Node 4, Level 3 

¿No es eso para lo que [SelectMany] [1] es?

 enum1.SelectMany( a => a.SelectMany( b => b.SelectMany( c => c.Select( d => d.Name ) ) ) ); 

Pensé que compartiría un ejemplo completo con el manejo de errores y un apporoach de lógica única.

El aplanamiento recursivo es tan simple como:

Versión LINQ

 public static class IEnumerableExtensions { public static IEnumerable SelectManyRecursive(this IEnumerable source, Func> selector) { if (source == null) throw new ArgumentNullException("source"); if (selector == null) throw new ArgumentNullException("selector"); return !source.Any() ? source : source.Concat( source .SelectMany(i => selector(i).EmptyIfNull()) .SelectManyRecursive(selector) ); } public static IEnumerable EmptyIfNull(this IEnumerable source) { return source ?? Enumerable.Empty(); } } 

Versión no LINQ

 public static class IEnumerableExtensions { public static IEnumerable SelectManyRecursive(this IEnumerable source, Func> selector) { if (source == null) throw new ArgumentNullException("source"); if (selector == null) throw new ArgumentNullException("selector"); foreach (T item in source) { yield return item; var children = selector(item); if (children == null) continue; foreach (T descendant in children.SelectManyRecursive(selector)) { yield return descendant; } } } } 

Decisiones de diseño

Yo decidí:

  • no permitir el aplanamiento de un IEnumerable nulo, esto se puede cambiar eliminando el lanzamiento de excepción y:
    • agregando source = source.EmptyIfNull(); antes de return en la primera versión
    • agregando if (source != null) antes de foreach en la segunda versión
  • Permitir el retorno de una colección nula por parte del selector. De esta forma eliminaré la responsabilidad de la persona que llama para asegurar que la lista de niños no esté vacía, esto se puede cambiar de la siguiente manera:
    • eliminando .EmptyIfNull() en la primera versión, tenga en cuenta que SelectMany fallará si el selector devuelve null
    • eliminando if (children == null) continue; en la segunda versión, tenga en cuenta que foreach fallará en un parámetro IEnumerable nulo
  • Permitir filtrar a los niños con la cláusula .Where en el lado de la persona que llama o dentro del selector de niños en lugar de pasar un parámetro selector de filtro secundario:
    • no afectará la eficiencia porque en ambas versiones es una llamada diferida
    • sería mezclar otra lógica con el método y prefiero mantener la lógica separada

Uso de muestra

Estoy usando este método de extensión en LightSwitch para obtener todos los controles en la pantalla:

 public static class ScreenObjectExtensions { public static IEnumerable FindControls(this IScreenObject screen) { var model = screen.Details.GetModel(); return model.GetChildItems() .SelectManyRecursive(c => c.GetChildItems()) .OfType() .Select(c => screen.FindControl(c.Name)); } } 

Aquí hay una respuesta modificada de Jon Skeet para permitir más que “un nivel”:

 static IEnumerable Flatten(IEnumerable enumerable) { foreach (object element in enumerable) { IEnumerable candidate = element as IEnumerable; if (candidate != null) { foreach (object nested in Flatten(candidate)) { yield return nested; } } else { yield return element; } } } 

descargo de responsabilidad: no sé C #.

Lo mismo en Python:

 #!/usr/bin/env python def flatten(iterable): for item in iterable: if hasattr(item, '__iter__'): for nested in flatten(item): yield nested else: yield item if __name__ == '__main__': for item in flatten([1,[2, 3, [[4], 5]], 6, [[[7]]], [8]]): print(item, end=" ") 

Imprime:

 1 2 3 4 5 6 7 8 

Función:

 public static class MyExtentions { public static IEnumerable RecursiveSelector(this IEnumerable nodes, Func> selector) { if(nodes.Any()) return nodes.Concat(nodes.SelectMany(selector).RecursiveSelector(selector)); return nodes; } } 

Uso:

 var ar = new[] { new Node { Name = "1", Chilren = new[] { new Node { Name = "11", Children = new[] { new Node { Name = "111", } } } } } }; var flattened = ar.RecursiveSelector(x => x.Children).ToList(); 

El método de extensión SelectMany ya lo hace.

Proyecta cada elemento de una secuencia a un IEnumerable < (Of <(T>)>) y aplana las secuencias resultantes en una secuencia.

Dado que el rendimiento no está disponible en VB y LINQ proporciona tanto la ejecución diferida como una syntax concisa, también puede usar.

  Public Function Flatten(Of T)(ByVal objects As Generic.IEnumerable(Of T), ByVal selector As Func(Of T, Generic.IEnumerable(Of T))) As Generic.IEnumerable(Of T) Return objects.Union(objects.SelectMany(selector).Flatten(selector)) End Function 

Tuve que implementar el mío desde cero porque todas las soluciones proporcionadas se romperían en caso de que hubiera un ciclo, es decir, un niño que apuntara a su antecesor. Si tiene los mismos requisitos que los míos, eche un vistazo a esto (también avíseme si mi solución se rompería en circunstancias especiales):

Cómo utilizar:

 var flattenlist = rootItem.Flatten(obj => obj.ChildItems, obj => obj.Id) 

Código:

 public static class Extensions { ///  /// This would flatten out a recursive data structure ignoring the loops. The end result would be an enumerable which enumerates all the /// items in the data structure regardless of the level of nesting. ///  /// Type of the recursive data structure /// Source element /// a function that returns the children of a given data element of type T /// a function that returns a key value for each element /// a faltten list of all the items within recursive data structure of T public static IEnumerable Flatten(this IEnumerable source, Func> childrenSelector, Func keySelector) where T : class { if (source == null) throw new ArgumentNullException("source"); if (childrenSelector == null) throw new ArgumentNullException("childrenSelector"); if (keySelector == null) throw new ArgumentNullException("keySelector"); var stack = new Stack( source); var dictionary = new Dictionary(); while (stack.Any()) { var currentItem = stack.Pop(); var currentkey = keySelector(currentItem); if (dictionary.ContainsKey(currentkey) == false) { dictionary.Add(currentkey, currentItem); var children = childrenSelector(currentItem); if (children != null) { foreach (var child in children) { stack.Push(child); } } } yield return currentItem; } } ///  /// This would flatten out a recursive data structure ignoring the loops. The end result would be an enumerable which enumerates all the /// items in the data structure regardless of the level of nesting. ///  /// Type of the recursive data structure /// Source element /// a function that returns the children of a given data element of type T /// a function that returns a key value for each element /// a faltten list of all the items within recursive data structure of T public static IEnumerable Flatten(this T source, Func> childrenSelector, Func keySelector) where T: class { return Flatten(new [] {source}, childrenSelector, keySelector); } } 

De acuerdo, aquí hay otra versión que se combina con aproximadamente 3 respuestas anteriores.

Recursivo. Utiliza el rendimiento. Genérico. Predicado de filtro opcional. Función de selección opcional. Casi tan conciso como pude hacerlo.

  public static IEnumerable Flatten( this IEnumerable nodes, Func filterBy = null, Func> selectChildren = null ) { if (nodes == null) yield break; if (filterBy != null) nodes = nodes.Where(filterBy); foreach (var node in nodes) { yield return node; var children = (selectChildren == null) ? node as IEnumerable : selectChildren(node); if (children == null) continue; foreach (var child in children.Flatten(filterBy, selectChildren)) { yield return child; } } } 

Uso:

 // With filter predicate, with selection function var flatList = nodes.Flatten(n => n.IsDeleted == false, n => n.Children); 
 static class EnumerableExtensions { public static IEnumerable Flatten(this IEnumerable> sequence) { foreach(var child in sequence) foreach(var item in child) yield return item; } } 

Tal vez así? ¿O quiere decir que podría ser infinitamente profundo?

 class PageViewModel { public IEnumerable ChildrenPages { get; set; } } Func, IEnumerable> concatAll = null; concatAll = list => list.SelectMany(l => l.ChildrenPages.Any() ? concatAll(l.ChildrenPages).Union(new[] { l }) : new[] { l }); var allPages = concatAll(source).ToArray(); 

Básicamente, necesitas tener un IENumerable maestro que esté fuera de tu función recursiva, luego en tu función recursiva (código Psuedo)

 private void flattenList(IEnumerable list) { foreach (T item in list) { masterList.Add(item); if (item.Count > 0) { this.flattenList(item); } } } 

Aunque realmente no estoy seguro de lo que quieres decir con IEnumerable nested en un IEnumerable … ¿qué hay dentro de eso? ¿Cuántos niveles de anidación? ¿Cuál es el tipo final? obviamente mi código no es correcto, pero espero que te haga pensar.