LINQ: Possiamo creare una semplice lista di gerarchia

Question

OK ... il titolo è corretta ...

io non voglio gerarchia da una semplice lista, ma esatto inverso

Ho classe cartella che ha l'elenco delle cartelle in esso detenute dalla proprietà Children. Quindi questo è un tipico modello di gerarchia.

ora vuole appiattire questa lista fuori ... sarà un attraversamento preordine cioè

supponga

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 

Da questa gerarchia, la lista piatta mi aspetto è esattamente l'ordine in cui appare sopra!

Se LINQ non può fare questo, allora un XSLT può renderlo piatto in una lista di elementi xml?

Answer 1

Se LINQ non potete fare questo allora può un XSLT renderla piatta in una lista di xml-elementi?

Diverse persone hanno dimostrato come farlo con LINQ.

Ecco una soluzione XSLT breve e semplice che trasforma una rappresentazione XML dell'elenco disponibile di elementi nidificati in una semplice lista ordinata di oggetti:

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

quando questa trasformazione viene applicata sul XML -Rappresentazione del vostro input fornito:

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

The Wanted, correttamente ordinata sequenza piatta è prodotto:

<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/> 

UPDATE: ecco un non ricorsive e soluzioni XSLT ancora più semplice (grazie a Andrew Welch per avermi ricordato su questo):

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

questa soluzione funziona senza problema nei casi in cui una soluzione ricorsiva termina conoverflow stack reale.

Answer 2

È possibile utilizzare SelectMany per appiattire una gerarchia

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

Answer 3

EDIT: Ora che abbiamo un po 'di più contesto, sembra che tu hai effettivamente avuto XML per cominciare. Tuttavia, non sappiamo ancora quale elaborazione stai eseguendo sugli elementi. XSLT può essere il giusto approccio, ma un altro sarebbe quello di utilizzare LINQ to XML e il suo metodo Descendants:

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

Che può finire per essere ancora più semplice rispetto all'approccio XSLT. Ad esempio, se si vuole trasformarlo in un List<string> prendendo un attributo da ogni elemento:

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

Uno svantaggio è che questo sarà ancora caricare l'intero file XML in memoria come XElement (ecc) oggetti. È del tutto possibile che la versione XSLT sia in grado di gestirlo in streaming con un utilizzo della memoria più efficiente. Dimitre può senza dubbio fornire maggiori informazioni se questo è pertinente.

---

Non c'è niente in LINQ per appiattire multipla livelli gerarchici senza eseguire la ricorsione da soli. SelectMany esegue uno livello di appiattimento, ma è necessario recurse per appiattire la gerarchia multilivello in un unico elenco.

Ora, se si sta utilizzando LINQ to XML, che fa supporto molto facilmente - si può semplicemente utilizzare il metodo Descendants:

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

di scrivere qualcosa di simile per la classe di dominio, però, si' d bisogno di scrivere più codice Se puoi fornire ulteriori informazioni su ciò che hai in realtà ottenuto (classi XML o dominio) potremmo essere in grado di aiutarti di più.

EDIT: Ok, sembra che XML sia una falsa pista qui. Ma trovare tutti i discendenti è abbastanza facile.È possibile farlo utilizzando blocchi iteratore, ma che diventa piuttosto spiacevolmente inefficiente abbastanza rapidamente. Ecco un altro semplice alternativa:

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); 
    } 
} 

è possibile personalizzare l'algoritmo esatto in base all'ordine in cui si desidera ottenere i bambini indietro.

Answer 4

Si potrebbe scrivere un semplice metodo di estensione per fare questo:

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 più corto con 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

Non v'è alcuna implementazione standard framework .Net, ma è possibile implementare da soli .

Ecco come si può fare:

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

Ecco un metodo di estensione LINQ-stile che fa quello che stai chiedendo (senza ricorsione, cicli gestite).

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

Questo sarebbe dal mio primo tentativo:

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