Click here to Skip to main content
Click here to Skip to main content

Nested Set Model Treebuilder

, 17 Apr 2009
Rate this:
Please Sign up or sign in to vote.
An IEnumerable extension method to build a hierarchical tree from your NSM data

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.

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.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Troy Beacleay
Software Developer (Senior)
United States United States
Been designing, implementing, and maintianing projects in .Net since the beginning of time...or so it seems. I've done a little of everything before that though; java, vb classic, c, c++, assembly, pascal, basic.
 
*I'm not a big fan of UI work.
 
_

Comments and Discussions

 
GeneralOnly Binary Tree [modified] Pinmemberaspbeast21-Sep-10 9:20 
Thanks a lot! Greate article, but how can i use this for not only binary trees?

modified on Tuesday, September 21, 2010 3:57 PM

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web04 | 2.8.140827.1 | Last Updated 17 Apr 2009
Article Copyright 2009 by Troy Beacleay
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid