.NET - LINQ AsHierarchy() extension method - deel 2

A few months ago I published an article about my LINQ AsHierarchy extension method. This extension method can be used to convert a flat collection of entities to a hierarchical structure of nested collections. I got a lot of enthusiastic responses and questions and so I decided to improve this technique a little further.

• Sample data
• LINQ to Objects AsHierarchy() extension method
  • Parent reference
• Root item parameter
• Max depth parameter
• LINQ to SQL AsHierarchy() extension method
  • String parameters propertyNameId and propertyNameParentId
• IEnumerable AsHierarchy() vs IQueryable AsHierarchy()
• AsHierarchy and LINQ to Entities
• AsHierarchy and RIA Services

Sample data

Before explaining all the improvements, I first will show the data which is being used in all examples in this article. I'm using the Employees table of the Northwind sample database and I have added 10 new employees.

All visualized trees in this article will display the EmployeeId in red and the Depth (=level) of the entity in blue.

When using LINQ to SQL entities call ToList() first! This will retrieve all data and then you can call my LINQ to Objects (IEnumerable) AsHierarchy() method.

When I use my old AsHierarchy() extension method on this data following hierarchical tree will be created.

var tree = dc.Employees.ToList().AsHierarchy(e => e.EmployeeID, e => e.ReportsTo);

LINQ to Objects AsHierarchy extension method

Here is the full source of the new AsHierarchy() extension method.

/// <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 T Parent { get; set; }
}

// Stefan Cruysberghs, July 2008, http://www.scip.be
/// <summary>
/// AsHierarchy extension methods for LINQ to Objects IEnumerable
/// </summary>
public static class LinqToObjectsExtensionMethods
{
  private static IEnumerable<HierarchyNode<TEntity>>
    CreateHierarchy<TEntity, TProperty>(
      IEnumerable<TEntity> allItems, 
      TEntity parentItem, 
      Func<TEntity, TProperty> idProperty, 
      Func<TEntity, TProperty> parentIdProperty,
      object rootItemId, 
      int maxDepth, 
      int depth) where TEntity : class
  {
    IEnumerable<TEntity> childs;
 
    if (rootItemId != null)
    {
      childs = allItems.Where(i => idProperty(i).Equals(rootItemId));
    }
    else
    {
      if (parentItem == null)
      {
        childs = allItems.Where(i => parentIdProperty(i).Equals(default(TProperty)));
      }
      else
      {
        childs = allItems.Where(i => parentIdProperty(i).Equals(idProperty(parentItem)));
      }
    }
 
    if (childs.Count() > 0)
    {
      depth++;
 
      if ((depth <= maxDepth) || (maxDepth == 0))
      {
        foreach (var item in childs)
          yield return
            new HierarchyNode<TEntity>()
              {
                Entity = item,
                ChildNodes =
                  CreateHierarchy(allItems.AsEnumerable(), item, idProperty, parentIdProperty, null, maxDepth, depth),
                Depth = depth,
                Parent = parentItem
              };
      }
    }
  }
 
  /// <summary>
  /// LINQ to Objects (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">Func delegete to Id/Key of entity</param>
  /// <param name="parentIdProperty">Func delegete to parent Id/Key</param>
  /// <returns>Hierarchical structure of entities</returns>
  public static IEnumerable<HierarchyNode<TEntity>> AsHierarchy<TEntity, TProperty>(
    this IEnumerable<TEntity> allItems, 
    Func<TEntity, TProperty> idProperty, 
    Func<TEntity, TProperty> parentIdProperty) where TEntity : class
  {
    return CreateHierarchy(allItems, default(TEntity), idProperty, parentIdProperty, null, 0, 0);
  }
 
  /// <summary>
  /// LINQ to Objects (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">Func delegete to Id/Key of entity</param>
  /// <param name="parentIdProperty">Func delegete to parent Id/Key</param>
  /// <param name="rootItemId">Value of root item Id/Key</param>
  /// <returns>Hierarchical structure of entities</returns>
  public static IEnumerable<HierarchyNode<TEntity>> AsHierarchy<TEntity, TProperty>(
    this IEnumerable<TEntity> allItems, 
    Func<TEntity, TProperty> idProperty, 
    Func<TEntity, TProperty> parentIdProperty, 
    object rootItemId) where TEntity : class
  {
    return CreateHierarchy(allItems, default(TEntity), idProperty, parentIdProperty, rootItemId, 0, 0);
  }
 
  /// <summary>
  /// LINQ to Objects (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">Func delegete to Id/Key of entity</param>
  /// <param name="parentIdProperty">Func delegete to parent Id/Key</param>
  /// <param name="rootItemId">Value of root item Id/Key</param>
  /// <param name="maxDepth">Maximum depth of tree</param>
  /// <returns>Hierarchical structure of entities</returns>
  public static IEnumerable<HierarchyNode<TEntity>> AsHierarchy<TEntity, TProperty>(
    this IEnumerable<TEntity> allItems, 
    Func<TEntity, TProperty> idProperty, 
    Func<TEntity, TProperty> parentIdProperty, 
    object rootItemId, 
    int maxDepth) where TEntity : class
  {
    return CreateHierarchy(allItems, default(TEntity), idProperty, parentIdProperty, rootItemId, maxDepth, 0);
  }
}

Parent reference

The first improvement I made, was adding a Parent property to the generic HierarchyNode class.

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 T Parent { get; set; }
}

Each node will have a reference to its parent's node. This can be quite handy when you want to make visual differences depending some values in the parent node. Next example will demonstrate how you can show the Employee name and the name of its boss in a WPF TreeView node.

<HierarchicalDataTemplate x:Key="EmployeeHierarchyParent" ItemsSource="{Binding Path=ChildNodes}">
    <StackPanel Orientation="Vertical">
        <TextBlock Text="{Binding Path=Entity.LastName}" HorizontalAlignment="Center"></TextBlock>
        <TextBlock Text="{Binding Path=Parent.LastName}" HorizontalAlignment="Center" Foreground="Blue"></TextBlock>
    </StackPanel>
</HierarchicalDataTemplate>

Root item parameter

There are circumstances in which you do not need to display the whole tree of data. Therefore I added a new parameter which can be used to specify the ID of the root item. This is useful to skip some parent levels.

A few examples:

var tree = dc.Employees.ToList().AsHierarchy(e => e.EmployeeID, e => e.ReportsTo, 5);

var tree = dc.Employees.ToList().AsHierarchy(e => e.EmployeeID, e => e.ReportsTo,
  dc.Employees.FirstOrDefault(e => e.LastName == "Buchanan").EmployeeID);

Max depth parameter

Furthermore I added a fourth parameter which specifies the maximum depth of the tree.

e.g. Show maximum 2 levels of the tree:

var tree = dc.Employees.ToList().AsHierarchy(e => e.EmployeeID, e => e.ReportsTo, null, 2);

You can also combine these 2 parameters. e.g. Next example will start with employee Dodsworth (EmployeeId=9) and display 3 levels:

var tree = dc.Employees.ToList().AsHierarchy(e => e.EmployeeID, e => e.ReportsTo, 9, 3);

LINQ to SQL AsHierarchy extension method

My new RootItemID and MaxDepth parameters can be very handy to hide data when creating a tree structure. Because it is a LINQ to Objects (IEnumerable) extension method all data is needed in memory before a tree with a subset of the data can be created. When you want to skip a lot of data, this is not the most efficient way. So therefore I started developing an IQueryable LINQ to SQL alternative which will be faster in some cases.

Here is the full source code of the IQueryable AsHierarchy extension method:

// Stefan Cruysberghs, July 2008, http://www.scip.be
/// <summary>
/// AsHierarchy extension methods for LINQ to SQL IQueryable
/// </summary>
public static class LinqToSqlExtensionMethods
{
  private static IEnumerable<HierarchyNode<TEntity>>
    CreateHierarchy<TEntity>(IQueryable<TEntity> allItems,
      TEntity parentItem,
      string propertyNameId, 
      string propertyNameParentId,
      object rootItemId,
      int maxDepth,
      int depth) where TEntity : class
  {
    ParameterExpression parameter = Expression.Parameter(typeof(TEntity), "e");
    Expression<Func<TEntity, bool>> predicate;
 
    if (rootItemId != null)
    {
      Expression left = Expression.Property(parameter, propertyNameId);
      left = Expression.Convert(left, rootItemId.GetType());
      Expression right = Expression.Constant(rootItemId);
 
      predicate = Expression.Lambda<Func<TEntity, bool>>(Expression.Equal(left, right), parameter);
    }
    else
    {
      if (parentItem == null)
      {
        predicate = 
          Expression.Lambda<Func<TEntity, bool>>(
            Expression.Equal(Expression.Property(parameter, propertyNameParentId),
                             Expression.Constant(null)), parameter);
      }
      else
      {
        Expression left = Expression.Property(parameter, propertyNameParentId);
        left = Expression.Convert(left, parentItem.GetType().GetProperty(propertyNameId).PropertyType);
        Expression right = Expression.Constant(parentItem.GetType().GetProperty(propertyNameId).GetValue(parentItem, null));
 
        predicate = Expression.Lambda<Func<TEntity, bool>>(Expression.Equal(left, right), parameter);
      }
    }
 
    IEnumerable<TEntity> childs = allItems.Where(predicate).ToList();
 
    if (childs.Count() > 0)
    {
      depth++;
 
      if ((depth <= maxDepth) || (maxDepth == 0))
      {
        foreach (var item in childs)
          yield return
            new HierarchyNode<TEntity>()
            {
              Entity = item,
              ChildNodes =
                CreateHierarchy(allItems, item, propertyNameId, propertyNameParentId, null, maxDepth, depth),
              Depth = depth,
              Parent = parentItem
            };
      }
    }
  }
 
  /// <summary>
  /// LINQ to SQL (IQueryable) AsHierachy() extension method
  /// </summary>
  /// <typeparam name="TEntity">Entity class</typeparam>
  /// <param name="allItems">Flat collection of entities</param>
  /// <param name="propertyNameId">String with property name of Id/Key</param>
  /// <param name="propertyNameParentId">String with property name of parent Id/Key</param>
  /// <returns>Hierarchical structure of entities</returns>
  public static IEnumerable<HierarchyNode<TEntity>> AsHierarchy<TEntity>(
    this IQueryable<TEntity> allItems,
    string propertyNameId,
    string propertyNameParentId) where TEntity : class
  {
    return CreateHierarchy(allItems, null, propertyNameId, propertyNameParentId, null, 0, 0);
  }
 
  /// <summary>
  /// LINQ to SQL (IQueryable) AsHierachy() extension method
  /// </summary>
  /// <typeparam name="TEntity">Entity class</typeparam>
  /// <param name="allItems">Flat collection of entities</param>
  /// <param name="propertyNameId">String with property name of Id/Key</param>
  /// <param name="propertyNameParentId">String with property name of parent Id/Key</param>
  /// <param name="rootItemId">Value of root item Id/Key</param>
  /// <returns>Hierarchical structure of entities</returns>
  public static IEnumerable<HierarchyNode<TEntity>> AsHierarchy<TEntity>(
    this IQueryable<TEntity> allItems,
    string propertyNameId,
    string propertyNameParentId,
    object rootItemId) where TEntity : class
  {
    return CreateHierarchy(allItems, null, propertyNameId, propertyNameParentId, rootItemId, 0, 0);
  }
 
  /// <summary>
  /// LINQ to SQL (IQueryable) AsHierachy() extension method
  /// </summary>
  /// <typeparam name="TEntity">Entity class</typeparam>
  /// <param name="allItems">Flat collection of entities</param>
  /// <param name="propertyNameId">String with property name of Id/Key</param>
  /// <param name="propertyNameParentId">String with property name of parent Id/Key</param>
  /// <param name="rootItemId">Value of root item Id/Key</param>
  /// <param name="maxDepth">Maximum depth of tree</param>
  /// <returns>Hierarchical structure of entities</returns>
  public static IEnumerable<HierarchyNode<TEntity>> AsHierarchy<TEntity>(
    this IQueryable<TEntity> allItems,
    string propertyNameId,
    string propertyNameParentId,
    object rootItemId, 
    int maxDepth) where TEntity : class
  {
    return CreateHierarchy(allItems, null, propertyNameId, propertyNameParentId, rootItemId, maxDepth, 0);
  }
}

String parameters propertyNameId and propertyNameParentId

I couldn't find a way to convert the lambda delegate (Func) parameters, which are used to specify the child and parent Id property, to an expression tree. So that is why I had to change these lambda delegate parameters into string parameters. In the LINQ to SQL AsHierarchy() method you have to pass the property names as strings. Internally an Expression object will be created by using reflection. Finally LINQ to SQL will translate these expressions to the corresponding SQL where-clause.

IEnumerable AsHierarchy() vs IQueryable AsHierarchy()

So what is the big difference between the LINQ to Objects and the LINQ to SQL AsHierarchy() method? I will try to explain this by comparing the 2 methods.

IEnumerable (LINQ to Objects) AsHierarchy() method

The IEnumerable AsHierarchy() method uses lambda delegate parameters to specify the ID and ParentID properties. All data should be available in memory (therefore call ToList()). All records which are not needed will be skipped in memory when creating the collection of HierarchyNodes.

var tree = dc.Employees.ToList().AsHierarchy(e => e.EmployeeID, e => e.ReportsTo, 9, 3);

IQueryable (LINQ to SQL) AsHierarchy() method

The IQueryable AsHierarchy() method uses string parameters to specify the ID and ParentID propertynames. For each node a LINQ to SQL statement will be executed. So several SQL statements will be executed but only the data which is needed will be retrieved from the database.

var tree = dc.Employees.AsHierarchy("EmployeeID", "ReportsTo", 9, 3);

I'm sure you are wondering which technique is the most performant. It depends on the situation. When you have 1000 records in the database and you only need to display 5 of them, then the IQueryable version will be faster. If you have 10 records in the database then it is probably better retrieving 10 records with 1 SQL statement and skip 5 records in memory when creating the collection of HierarchyNodes.

AsHierarchy and LINQ to Entities

I didn't create a AsHierarchy extension method for LINQ to Entities yet, but the LINQ to Objects version works quite good with data from the Entity Data Model. There is only one caveat; the Entity Framework Model does not generate foreign key properties but it will create navigation properties for them. Therefore you have to create a partial class and add your own computed foreign key field. Following example shows how you can add the ReportsToID field to the Employee EntityType.

public partial class Employee
{
    [DataMember]
    public int? ReportsToID
    {
        get
        {
            if ((ReportsToReference == null) || (ReportsToReference.EntityKey == null))
            {
                return null;
            }
 
            return (int)ReportsToReference.EntityKey.EntityKeyValues[0].Value;
        }
 
        internal set
        {
 
        }
    }
}

var tree = northwindEntities.Employees.ToList().AsHierarchy(e => e.EmployeeID, e => e.ReportsToID);

AsHierarchy and RIA Services

Using the AsHierarchy extension method together with RIA Services also works smoothly. RIA Services generates EntityType objects on client side and they always have foreign key properties. So in Silverlight you can call the AsHierarchy method for the flat collections which are returned by the DomainContext.

private void GetEmployeesCompleted(object sender, EventArgs e)
{
   EmployeeHierarchy = employeesDomainContext.Employees.AsHierarchy(e => e.EmployeeID, e => e.ReportsTo);

I hope you like my AsHierarchy() extension methods. Use these techniques wisely! If you have any remarks or suggestions, please let me know.