LINQ: Can we create a flat list from hierarchy

OK... the title is correct...

I dont want hierarchy from a flat list but exact reverse

I have Folder class which has list of Folders in it held by property Children. So this is a typical hierarchy model.

I now want to flatten this list out... it will be an pre-order traversal i.e.

Assume

   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 I am expecting is exactly the orde开发者_StackOverflow中文版r in which it is appearing above!

If LINQ cant do this then can an XSLT make it flat into a list of xml-elements?

If LINQ cant do this then can an XSLT make it flat 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 transforms an XML representation of the provided list of nested items into a flat ordered list of items:

<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 transformation is applied on 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>

The wanted, correctly ordered flat sequence is produced:

<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: Here is a non-recursive and even simpler XSLT solution (thanks to Andrew Welch for reminding me about 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 problem in cases where a recursive solution ends up with real stack overflow.

EDIT: Now that we've got a bit more context, it sounds like you've actually got XML to start with. However, we still don't know what processing you're performing on the elements. XSLT may be the right approach, but another would be to use LINQ to XML and its Descendants method:

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

That may end up being even simpler than the XSLT approach. For example, if you want to transform it into a 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 downside is that this will still load the whole XML file into memory as XElement (etc) objects. It's entirely possible that the XSLT version can handle this in a streaming fashion with more efficient memory usage. Dimitre can no doubt give more information if this is relevant.

There's nothing in LINQ to flatten multiple levels of hierarchy without performing recursion yourself. SelectMany performs one level of flattening, but you'd need to recurse to flatten your multi-level hierarchy to a single list.

Now if you're using LINQ to XML, that does support it very easily - you can just use the Descendants method:

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

To write something similar for your domain class though, you'd need to write more code. If you can give more information about what you've really got (XML or domain classes) we may be able to help you more.

EDIT: Okay, it sounds like XML is a red herring here. But finding all the descendants is pretty easy. You can do it using iterator blocks, but that becomes pretty unpleasantly inefficient fairly quickly. Here's 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 tailor the exact algorithm based on the order in which you want to get the children back.

You can use SelectMany to flatten a heirarchy

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

Here's a linq-style extension method which does what you're asking (no recursion, cycles handled).

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

This would by my first try:

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

You could write a simple extension method to do 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;
}

There is no standard implementation in .Net framework, but you can implement it yourself.

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