LINQ: ¿Podemos crear una lista plana de la jerarquía

Question

bien ... el título es correcto ...

no quiero jerarquía de una lista plana, pero exacta revertir

tengo clase carpeta la cual tiene una lista de Carpetas en su poder en la propiedad Children. Entonces este es un modelo de jerarquía típico.

ahora quiero para aplanar esta lista a cabo ... que será un recorrido en preorden es decir

Supongamos

A 
    - A.1 
    ----- A.1.1 
    ----- A.1.2 
    - A.2 
    ----- A.2.1 
    - A.3 
    B 
    - B.1 
    - B.2 
    ----- B.2.1 
    ----- B.2.2 
    ----------- B.2.2.1 
    ----------- B.2.2.2 

De esta jerarquía, la lista plana que estoy esperando es exactamente el orden en el que aparece arriba!

Si LINQ no puede hacer esto, ¿puede un XSLT hacerlo plano en una lista de elementos xml?

Answer 1

Si LINQ no puede hacer esto, entonces puede que sea un XSLT plana en una lista de xml-elementos?

Varias personas han demostrado cómo hacerlo con LINQ.

Aquí es una solución XSLT corto y simple que transforma una representación XML de la lista proporcionada de elementos anidados en una lista plana ordenada de elementos:

<xsl:stylesheet version="1.0" 
xmlns:xsl="http://www.w3.org/1999/XSL/Transform"> 
<xsl:output omit-xml-declaration="yes" indent="yes"/> 
<xsl:strip-space elements="*"/> 

<xsl:template match="/*"> 
    <xsl:apply-templates select="*[1]"/> 
</xsl:template> 

<xsl:template match="*/*"> 
    <xsl:copy/> 
    <xsl:apply-templates select="*[1]"/> 
    <xsl:apply-templates select="following-sibling::*[1]"/> 
</xsl:template> 
</xsl:stylesheet> 

cuando esta transformación se aplica sobre el XML -Representación de la entrada proporcionada:

<t> 
    <A> 
     <A.1> 
      <A.1.1/> 
      <A.1.2/> 
     </A.1> 
     <A.2> 
      <A.2.1/> 
     </A.2> 
     <A.3/> 
    </A> 
    <B> 
     <B.1/> 
     <B.2> 
      <B.2.1/> 
      <B.2.2> 
       <B.2.2.1/> 
       <B.2.2.2/> 
      </B.2.2> 
     </B.2> 
    </B> 
</t> 

La querían, ordenó correctamente plano secuencia se produce:

<A/> 
<A.1/> 
<A.1.1/> 
<A.1.2/> 
<A.2/> 
<A.2.1/> 
<A.3/> 
<B/> 
<B.1/> 
<B.2/> 
<B.2.1/> 
<B.2.2/> 
<B.2.2.1/> 
<B.2.2.2/> 

ACTUALIZACIÓN: aquí hay una no recursivos y la solución XSLT aún más simple (gracias a Andrew Welch por recordarme sobre este):

<xsl:stylesheet version="1.0" 
xmlns:xsl="http://www.w3.org/1999/XSL/Transform"> 
<xsl:output omit-xml-declaration="yes" indent="yes"/> 

<xsl:template match="/"> 
    <xsl:for-each select="//*"> 
    <xsl:copy/> 
    </xsl:for-each> 
</xsl:template> 
</xsl:stylesheet> 

Esta solución funciona sin problema en los casos donde una solución recursiva termina condesbordamiento de la pila real.

Answer 2

Puede utilizar SelectMany para aplanar una jerarquía

http://msdn.microsoft.com/en-us/library/bb534336.aspx

Answer 3

EDIT: Ahora que tenemos un poco más contexto, parece que realmente has conseguido XML para empezar. Sin embargo, todavía no sabemos qué procesamiento está realizando en los elementos. XSLT puede ser el enfoque correcto, pero otra sería utilizar LINQ para XML y su método Descendants:

var doc = XDocument.Load(stream); 
var descendants = doc.Descendants("Folder"); 
// Use descendants now 

Eso puede llegar a ser aún más simple que el enfoque XSLT. Por ejemplo, si usted quiere transformarlo en un List<string> mediante la adopción de un atributo de cada elemento:

var doc = XDocument.Load(stream); 
var names = doc.Descendants("Folder") 
       .Select(x => (strong) x.Attribute("name")) 
       .ToList(); 

Una desventaja es que esto todavía va a cargar todo el archivo XML en la memoria como XElement objetos (etc). Es muy posible que la versión XSLT pueda manejar esto de forma continua con un uso de memoria más eficiente. Dimitre sin duda puede dar más información si esto es relevante.

---

No hay nada en LINQ para aplanar múltiples niveles de jerarquía sin realizar recursividad mismo. SelectMany realiza uno nivel de aplanamiento, pero debe recurse para aplanar su jerarquía de niveles múltiples a una sola lista.

Ahora bien, si usted está utilizando LINQ to XML, que hace apoyo que sea muy fácil - sólo puede utilizar el método de Descendants:

var allFolders = root.Descendants("Folder"); 

escribir algo similar para su dominio de clase, sin embargo, que' Necesito escribir más código. Si puede proporcionar más información acerca de lo que realmente obtuvo (clases XML o de dominio), podemos ayudarle más.

EDITAR: Bueno, parece que XML es una amenaza. Pero encontrar a todos los descendientes es bastante fácil.Usted puede hacerlo usando bloques iteradores, pero eso se vuelve bastante desagradablemente ineficiente con bastante rapidez. Aquí hay otra alternativa simple:

public IList<Folder> SelfAndDescendants() 
{ 
    List<Folder> ret = new List<Folder>(); 
    AddSelfAndDescendants(ret); 
    return ret; 
} 

private void AddSelfAndDescendants(IList<Folder> list) 
{ 
    list.Add(this); 
    foreach (var child in children) 
    { 
     AddSelfAndDescendants(list); 
    } 
} 

que pueda adaptar el algoritmo exacto basado en el orden en el que desea que los niños regresen.

Answer 4

Se puede escribir un método de extensión simple de hacer esto:

public static IEnumerable<Folder> GetFolders(this Folder rootFolder) 
{ 
    yield return rootFolder; 

    foreach (var child in rootFolder.Children) 
     foreach(var folder in GetFolders(child)) 
      yield return folder; 
} 

o más corto usando SelectMany():

public static IEnumerable<Folder> GetFolders(this Folder rootFolder) 
{ 
    yield return rootFolder; 

    foreach (var folder in rootFolder.Children.SelectMany(GetFolders)) 
     yield return folder; 
} 

Answer 5

No hay ninguna aplicación estándar en el marco .Net, pero se puede aplicar por sí mismo .

Aquí es cómo puede hacerlo:

public static IEnumerable<T> FlattenTree<T>(this T root, Func<T, IEnumerable<T>> getChildren) 
{ 
    var state = new Stack<T>(); 
    state.Push(root); 

    while (state.Count != 0) 
    { 
     T top = state.Pop(); 
     yield return top; 

     IEnumerable<T> children = getChildren(top) ?? Enumerable.Empty<T>(); 
     foreach (T child in children.Reverse()) 
     { 
      state.Push(child); 
     } 
    } 
} 

Answer 6

Aquí está un método de extensión de estilo de LINQ, que hace lo que estás pidiendo (sin recursividad, ciclos manejados).

public static IEnumerable<T> WalkTreeDepthFirst<T>(this IEnumerable<T> source, 
     Func<T, IEnumerable<T>> childFunction) 
    { 
     // http://en.wikipedia.org/wiki/Depth-first_search 
     HashSet<T> seenIt = new HashSet<T>(); 
     Stack<T> toVisit = new Stack<T>(); 

     foreach (T item in source.Reverse()) 
     { 
      toVisit.Push(item); 
     } 

     while (toVisit.Any()) 
     { 
      T item = toVisit.Pop(); 
      if (!seenIt.Contains(item)) 
      { 
       seenIt.Add(item); 
       foreach (T child in childFunction(item).Reverse()) 
       { 
        toVisit.Push(child); 
       } 
       yield return item; 
      } 
     } 
    } 

Answer 7

Esto haría por mi primera prueba:

public static IEnumerable<Folder> SelfPlusChildren(Folder f) 
    { 
     return new[] {f}.Concat(f.Children.SelectMany(SelfPlusChildren)); 
    }