Nested Set Model Treebuilder

• Download source code - 1.92 KB

Introduction

The code described here takes Nested Set Model (NSM) data and constructs an object tree from it.

Background

An explanation of Nested Set Models and the relative pros and cons of them are beyond the scope of this article. I suggest Googling for articles by Joe Celko and/or Michael J. Kamfonas. Here are a few articles to get you started though.

• Managing Hierarchical Data in MySQL
• Recursive Hierarchies: The Relational Taboo!
• Trees in SQL - nested set model

Using the Code

In order to construct a hierarchy from a set of NSM data, each data point must contain left and right values. These values are typically integers, but the extension method presented does contain an overload that allows them to be any type that supports IComparable<T>. Here is a sample table storing some simple NSM data:

ItemData:

id          description                                  lft          rgt
----------- ----------------------------------------- ---------     --------
1           Root                                          1            12
2           RootChild1                                    2            3
3           RootChild2                                    4            11
4           RChild2_Child1                                5            8
5           RChild2_Child2                                9            10
7           RC2_C1_C1                                     6            7

This set of data represents the following tree structure:

* For an explanation of the numbering scheme, refer to the articles listed above.

You might query that data like this, for instance:

data = (from d in db.ItemDatas
       select d).ToList();

Once you have an IEnumerable<T> of your data, you need a class which supports a hierarchical structure of that class, i.e., a class which has a property responsible for holding "children" of the same type as itself. This class must also support the IPopulate<T> interface. This is necessary so the TreeBuilder can use the data from your list to construct the target "nodes". Simply implement IPopulate<T>.Populate(T payload) to populate the target object with the data from the source. For our example, we might have something like this:

public class Item :
RadixSolutionsUtilities.IPopulate<ItemData>
{
    public List<Item> Children
    {
        get;
        private set;
    }

    public string Name { get; set; }

    public Item()
    {
        Children = new List<Item>();
    }

    #region IPopulate<ItemData> Members

    public void Populate(ItemData payload)
    {
        //here you would populate all the properties of your object
        //from the source data
        Name = payload.description;
    }

    #endregion
}

Now that we have our data and a class to express the hierarchy of that data, we simply construct our tree with:

//uses the common extension method relying on ints for left
//and right
var hierarchy1 = data.AsTreeFromNSM<ItemData, Item>(
    e => e.lft
    , e => e.rgt
    , f => f.Children);
//uses the more generic extension method allowing for any type
//of data to be used for left and right
var hierarchy2 = data.AsTreeFromNSM<ItemData, Item, int>(
    e => e.lft
    , e => e.rgt
    , f => f.Children);

The first lambda points to the property holding the "left" data. The second lambda points to the property holding the "right" data. The third lambda points to the property on the target type where the subordinate hierarchy should be stored.

In the second invocation, the third generic used is int because in our sample, the columns lft and rgt are ints. If you have some alien space data that you would like to use to represent a counting system, specify its type in the third generic parameter. Just remember the generic constraint that it must implement IComparable<T> so that TreeBuilder will know how to order the data.

Points of Interest

I'm sure tons of people will point out more efficient ways to do some of this stuff, and please do post that information, but I am just happy to get this working.