LINQ: we can create a flat list from a hierarchy

OK ... the name is correct ...

I do not want a hierarchy from a flat list, but with the exact opposite

I have a Folder class that has a list of folders in it stored in the Children property. Thus, this is a typical hierarchical model.

Now I want to smooth out this list ... this will be a preliminary crawl, i.e.

Suppose

  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 

From this hierarchy, the flat list that I expect matches exactly the order in which it appears above!

If LINQ cannot do this, can XSLT make it flat into a list of xml elements?

+6
source share
7 answers

If LINQ cannot do this, then does XSLT flatten it into a list of XML elements?

Several people have shown how to do this with LINQ.

Here is a short and simple XSLT solution that converts the XML representation of the provided list of nested elements into a flat ordered list of elements:

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

when this conversion is applied to the XML representation of your provided input :

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

A properly ordered flat sequence is required :

 <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 This is a non-recursive and even simpler XSLT solution (thanks to Andrew Welch for reminding me of this):

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

This solution works without problems in cases where the recursive solution ends with an overflow of the real file .

+6
source

EDIT: Now that we have a little more context, it looks like you actually have XML for a start. However, we still do not know what processing you are doing on the elements. XSLT may be the right approach, but using LINQ to XML and its Descendants method will be different:

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

This may be even simpler than the XSLT approach. For example, if you want to convert it to List<string> by taking an attribute from each element:

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

One drawback is that it will still load the entire XML file into memory as XElement objects (etc.). It is possible that the XSLT version can handle this in a streaming manner with more efficient use of memory. Dimitre, without a doubt, provides more information, if that matters.


There is nothing in LINQ to smooth out several levels of a hierarchy without performing a recursion. SelectMany performs one level of anti-aliasing, but you will need to reorganize to reduce your multi-level hierarchy to a single list.

Now, if you use LINQ to XML, this is very convenient - you can simply use the Descendants method:

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

To write something like this for your domain class, you will need to write more code. If you can provide more information about what you have (XML or domain classes), we can help you more.

EDIT: Well, it looks like XML is a red herring. But finding all the descendants is quite simple. You can do this with iterator blocks, but it is rather unpleasantly inefficient rather quickly. Here is another simple alternative:

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

You can customize the exact algorithm based on the order in which you want the children back.

+3
source

You can use SelectMany to align the hierarchy.

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

+2
source

Here, the linq-style extension method is used, which does what you ask (without recursion, processed loops).

  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; } } } 
+1
source

This would be from my first attempt:

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

You can write a simple extension method for this:

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

Or shorter, using SelectMany() :

 public static IEnumerable<Folder> GetFolders(this Folder rootFolder) { yield return rootFolder; foreach (var folder in rootFolder.Children.SelectMany(GetFolders)) yield return folder; } 
0
source

There is no standard implementation in the .NET Framework, but you can implement it yourself.

Here's how you can do it:

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

Source: https://habr.com/ru/post/899306/


All Articles