There are a number of cases in programming where you are often forced to store data in one format but need to convert that data to a different format for display.  One of the situations where this seems to come up quite often is in the storage hierarchical data structures.  SQL Server has traditionally had very poor support for dealing with hierarchical data.  SQL 2005 and 2008 have made some effort to try and simplify solving this problem, unfortunately, there is still a lot of data that is stored in a format that is not readily able to take advantage of these new SQL Features.

When working with legacy data, or legacy business tiers which expose the data as flat collections with ID and ParentID fields, you will likely need a simple way to convert these records into some form of nested collection.  This is a problem where people often resort to brute force methods for doing this conversion.  Unfortunately, the brute force approach is often slow and very specific to a specific set of data.

I recently had the need to convert some data coming from the DotNetNuke business tier into a hierarchical collection.  Since I was using this data in a module, I was restricted from modifying the core framework to use a CTE or to handle the conversion in the core.  Instead I needed to find a solution that I could use in my own module, but that would also be generic enough that I could re-use it for many different types of data.

While researching this issue, I found a great blog post by Stefan Cruysberghs which discussed this exact issue and provided a nice, elegant LINQ Extension to handle just this case.  Stefan also has a nice follow-up article with some additional enhancements. 

While his original article was good, I quickly found that it wasn’t quite generic enough for my purposes.  DotNetNuke has long used a convention for how to deal with nullable integers that predates official support for nullable value types in .Net.  DotNetNuke uses a specific value for most common types that the system equates with a null.  This becomes important because most hierarchical data sets follow some convention for designating root elements.  Usually this is a special value in the ParentId field which indicates that the record has no parent.  This value is often NULL or 0.  The LINQ extensions by Stefan assumed that when the ParentId is the default value for a type, then the record represented a root element.  This does not work for DotNetNuke which uses –1 as the representation for a null integer value and thus the indication of a root element.  I have modified the code as indicated below to allow the calling code to designate the value for root elements.

using System;
using System.Collections.Generic;
using System.Linq;

namespace ScipBe.Common.LinqExtensions
{
    // Stefan Cruysberghs, http://www.scip.be, March 2008

    /// <summary>
    /// Hierarchy node class which contains a nested collection of hierarchy nodes
    /// </summary>
    /// <typeparam name="T">Entity</typeparam>
    public class HierarchyNode<T> where T : class
    {
        public T Entity { get; set; }
        public IEnumerable<HierarchyNode<T>> ChildNodes { get; set; }
        public int Depth { get; set; }
    }

    public static class LinqExtensionMethods
    {
        private static System.Collections.Generic.IEnumerable<HierarchyNode<TEntity>> CreateHierarchy<TEntity, TProperty>
          (IEnumerable<TEntity> allItems,
           TEntity parentItem,
           Func<TEntity, TProperty> idProperty,
           Func<TEntity, TProperty> parentIdProperty,
           int depth,
           object rootValue) where TEntity : class
        {
            IEnumerable<TEntity> children;

            if (parentItem == null)
                //children = allItems.Where(i => parentIdProperty(i).Equals(default(TProperty)));
                children = allItems.Where(i => parentIdProperty(i).Equals(rootValue));
            else
                children = allItems.Where(i => parentIdProperty(i).Equals(idProperty(parentItem)));

            if (children.Count() > 0)
            {
                depth++;

                foreach (var item in children)
                    yield return new HierarchyNode<TEntity>()
                    {
                        Entity = item,
                        ChildNodes = CreateHierarchy<TEntity, TProperty>
                            (allItems, item, idProperty, parentIdProperty, depth, rootValue),
                        Depth = depth
                    };
            }
        }

        /// <summary>
        /// LINQ IEnumerable AsHierachy() extension method
        /// </summary>
        /// <typeparam name="TEntity">Entity class</typeparam>
        /// <typeparam name="TProperty">Property of entity class</typeparam>
        /// <param name="allItems">Flat collection of entities</param>
        /// <param name="idProperty">Reference to Id/Key of entity</param>
        /// <param name="parentIdProperty">Reference to parent Id/Key</param>
        /// <returns>Hierarchical structure of entities</returns>
        public static System.Collections.Generic.IEnumerable<HierarchyNode<TEntity>> AsHierarchy<TEntity, TProperty>
          (this IEnumerable<TEntity> allItems,
            Func<TEntity, TProperty> idProperty,
            Func<TEntity, TProperty> parentIdProperty,
            object rootValue)
          where TEntity : class
        {
            return CreateHierarchy(allItems, default(TEntity), idProperty, parentIdProperty, 0, rootValue);
        }
    }
}