Acts_as_tree in Ruby

Ever since I switched from Ruby on Rails to ASP.NET as my main web development platform, I’ve been missing the beauty and elegance of the way plugins work in Ruby on Rails. By just adding one line of code to a Ruby class definition, you can add behavior to objects. A good example is the Rails acts_as_tree plugin, created by Ruby on Rails creator David Heinemeier Hansson. In my opinion, acts_as_tree fits lives up perfectly to WordPress’ Code is poetry motto.

Acts_as_tree is a Ruby on Rails extension which can make instances of a model (entity objects) act like a node in a tree. If you call the acts_as_tree method at the top of a class definition (yes, Ruby allows you to call methods in class definitions), Ruby “automagically” adds methods for parent/child access, like ‘ancestors()’, ‘siblings()’.

A typical usage scenario is a page tree in a CMS. Suppose pages are stored in the database and every page is represented as a row with an id and a parentId column, amongst other columns such as page title. If we wanted to display a page tree in Ruby, the only thing you need to do to have hierarchical access the underlying data is: add the method acts_as_tree to the model definition:

class Page < ActiveRecord::Base
  acts_as_tree  
end

Every Page instance now has knowledge of its children. So, in a view we can write:

<% unless @page.children.empty? %>
<ul id="submenu">
  <% for page in @page.children %>
    <li><%= link_to h(page.name), page %></li>
  <% end %>
</ul>
<% end %>

The magic behind this works, because in Ruby (any many other dynamic languages) you can extend an existing class with functionality (instance methods) at runtime. A class that includes functionalities (rather than inherits) in a subclass is called a Mixin. The theory behind Mixins is beyond the scope of this post, but if you want to know more: how Mixins can be used in Ruby is nicely explained in this tutorial: Ruby Mixin Tutorial.

The thing to remember is: thanks to Mixins and the dynamic nature of Ruby, developers can add behavior, such as tree-like functionality, to (model) classes with a minimal amount of effort.

Mixins in C#

Can we do something similar in C#? Well, kind of.

In C# 3.0 extension methods were introduced. With extension methods, we can realize limited mixin functionality: extension methods provide additional functionality on an existing class without modifying the class. Why limited? Mainly because extension methods cannot add state to an object, nor can they access private fields of the instances they extend.

On a side note: some of the limitations of extension methods can be avoided by using techniques like dynamic proxies in AOP frameworks (e.g. linfu). But since the inner workings of libraries like Linfu are like black magic to me (yes, black magic, not the beautiful acts_as_tree kind of magic), and I would like to keep runtime dependencies to a minimum, I won’t consider them in this post.

So, despite the limitations, using extension methods is my best bet at achieving something similar to acts_as_tree in C#.

AsHierarchy in C#

Good developers avoid the reinventing the wheel anti-pattern, so Google is a good place to start development of my tree extension method.

Because extensions methods are not as hot in the blogging world as they used to be when the were introduced (2006?), it took some searching to find examples of extension methods that add hierarchical functionality to classes. Fortunately I found a good solution by Stefan Cruysberghs (2008): the AsHierarchy extension method. Omer van Kloeten (2006) described something similar all the way back to 2006.

The general idea behind AsHierarchy extension method of both Stefan and Omer is:

  • AsHierarchy() takes an IEnumerable as input. The output is a IEnumerable of tree node objects.
  • A tree node is a wrapper class around an entity. A node has properties to access its parent and children

Here is Stefan’s implementation, in which I made some minor changes:

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

/// <summary>
/// AsHierarchy extension methods for LINQ to Objects IEnumerable
/// </summary>
public static class LinqHierarchyExtensions
{
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> children;

    if (rootItemId != null)
    {
        children = allItems.Where(i => idProperty(i).Equals(rootItemId));
    }
    else
    {
        if (parentItem == null)
            children = allItems.Where(i => parentIdProperty(i).Equals(default(TProperty)));
        else
            children = allItems.Where(i => parentIdProperty(i).Equals(idProperty(parentItem)));
    }


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

        if ((depth <= maxDepth) || (maxDepth == 0))
        {
            foreach (var item in children)
                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 type of Id's</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">Id of root node</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 type of Id's</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">Id of root node</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);
}

Usage is as follows:

static void Main(string[] args)
{
    List<Entity> entities = new List<Entity>
    {
        new Entity { Id = 1, ParentId = 0, Name="Root node" },
        // First level children
        new Entity { Id = 2, ParentId = 1, Name = "Node 1.1"},
        new Entity { Id = 3, ParentId = 1, Name = "Node 1.2"},
        new Entity { Id = 4, ParentId = 1, Name = "Node 1.3"},
        // Second level children
        new Entity { Id = 5, ParentId = 2, Name = "Node 1.1.1"},
        new Entity { Id = 6, ParentId = 2, Name = "Node 1.1.2"},
        new Entity { Id = 7, ParentId = 3, Name = "Node 1.2.1"},
    };

    IEnumerable<HierarchyNode<Entity>> tree = entities.AsHierarchy<Entity, int>(                                
        e => e.Id,
        e => e.ParentId,
        1);
    PrintTree(tree.FirstOrDefault());
}

private static void PrintTree(HierarchyNode<Entity> node)
{
    if (node == null) return;
           
    for (int i = 0; i < node.Depth; i++) Console.Write(' ');  // Identation  
    Console.WriteLine(node.Entity.Name);
    foreach (HierarchyNode<Entity> child in node.ChildNodes)
        PrintTree(child);
}

Once we loaded all entities in memory, we can create a hierarchal structure of those entities with just one method call on our collection. Sweet! And thanks to the use of IEnumerable as return type of AsHierarchy(), the approach is lazy: tree nodes are only constructed when needed.

Hierarchy extension with persistent objects

A drawback of the IEnumerable approach is that all rows must be loaded into memory before a tree can be created. As an alternative, Stefan developed IQueryable version of the AsHierarchy extension method. The principle is the same, but instead of one query that retrieves all rows before the tree is build, now queries are executed when needed during tree construction. This results in more queries (one query for every node), but if your table contains many rows of which you only want to display a few in a tree, the IQueryable approach may perform better.

What’s next?

We have seen that with the help of extension methods, functionality can be added to existing C# (persistent) classes to support tree operations. I think the extension methods we’ve seen can be quite useful, although still a long way from the elegance of act_as_tree. The main differences with “the Ruby Way” are:

  • Acts_as_tree adds tree functionality to individual objects, instead of working on collections of objects.
  • Extension methods on classes add functionality to all child class of a certain type, whereas Ruby mixins (like acts_as_tree) only adds functionality to classes that explicitly include the functionality in their definition.
  • Extension methods don’t have state. Therefore we must provide the id and parentId properties on each call to AsHierarchy.

In part 2 of this mini-series, I’ll address the first two issues. As for the third one: I’m afraid this is something we have to live with until, maybe, C# 5….

Read more

Leave a Reply





Human Verification