Mark Johnson

Software EngineerLucky HusbandProud FatherHopeless NerdAmateur BuilderDisney FanaticNeglectful Blogger

Flatten a C# Hierarchy

The most common way to express a hierarchy using objects in C# (or any object oriented languages) is with a type that contains a collection of the same type.

For example, the control tree in an ASP.NET page is represented by a collection of WebControls, each of which contains a collection of their child WebControls.

I had a need this week to flatten a similar hierarchy of objects into a single list. I figured there must be a fancy Linq extension to do the job so I headed on over to MSDN only to discover that there isn’t.

So I decided to write my own extension to flatten any similar object hierarchy.

public static class IEnumerableExtensions
{
    /// <summary>
    /// Flattens an object hierarchy.
    /// </summary>
    /// <param name="rootLevel">The root level in the hierarchy.</param>
    /// <param name="nextLevel">A function that returns the next level below a given item.</param>
    /// <returns><![CDATA[An IEnumerable<T> containing every item from every level in the hierarchy.]]></returns>
    public static IEnumerable<T> Flatten<T>(this IEnumerable<T> rootLevel, Func<T, IEnumerable<T>> nextLevel)
    {
        List<T> accumulation = new List<T>();
        accumulation.AddRange(rootLevel);
        flattenLevel<T>(accumulation, rootLevel, nextLevel);
        return accumulation;
    }

    /// <summary>
    /// Recursive helper method that traverses a hierarchy, accumulating items along the way.
    /// </summary>
    /// <param name="accumulation">A collection in which to accumulate items.</param>
    /// <param name="currentLevel">The current level we are traversing.</param>
    /// <param name="nextLevel">A function that returns the next level below a given item.</param>
    private static void flattenLevel<T>(List<T> accumulation, IEnumerable<T> currentLevel, Func<T, IEnumerable<T>> nextLevel)
    {
        foreach (T item in currentLevel)
        {
            accumulation.AddRange(currentLevel);
            flattenLevel<T>(accumulation, nextLevel(item), nextLevel);
        }
    }
}

Since this is an extension method, you can call it on any collection that implements IEnumerable<T>, such as a List<T> or Array.

The method requires you to pass a lambda expression that it can use to access the children of a given element in the hierarchy.

So, for example, to use it to get a list of every control on an ASP.NET page, you would call the following:

List<Control> allControls = Page.Controls.Flatten(c => c.Controls).ToList();

Or, if you wanted to get a list of all nodes in a TreeView:

List<TreeNode> allNodes = TreeView1.Nodes.Flatten(n => n.ChildNodes).ToList();

You don’t have to use ToList() either. For example, if you wanted to print the name of every tag in an XmlDocument:

foreach (XmlNode node in document.ChildNodes.Flatten(n => n.ChildNodes))
{
    Console.WriteLine(node.Name);
}

And you can combine this extension with existing Linq extensions. For example, if you wanted to print a distinct list of tag names from that XmlDocument:

foreach (string tagName in document.ChildNodes.Flatten(n => n.ChildNodes).Select(n => n.Name).Distinct())
{
    Console.WriteLine(tagName);
}

Leave a comment

Your email address will not be published. Required fields are marked *