Click here to Skip to main content
Click here to Skip to main content
Add your own
alternative version

Nested Set Model Treebuilder

, 17 Apr 2009 CPOL
An IEnumerable extension method to build a hierarchical tree from your NSM data
NSMTreeBuilder.zip
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace RadixSolutionsUtilities
{
    /// <summary>
    /// Builds hierarchical trees
    /// </summary>
    public static class TreeBuilder
    {
        /// <summary>
        /// Builds the hierarchical instance model based on source data stored as a Nested Set Model(NSM).
        /// </summary>
        /// <typeparam name="T">Class type of the source data items</typeparam>
        /// <typeparam name="U">Class type of the returned root "node"</typeparam>
        /// <param name="sourceData">A "list" of the source data</param>
        /// <param name="left">A delegate of the property where the left side information of a "node" is stored.  NSM concept</param>
        /// <param name="right">A delegate of the property where the right side information of a "node" is stored.  NSM concept</param>
        /// <param name="children">A delegate of the property of the output class that is used to store children.  The property that is named must return an IList(U)</param></param>
        /// <returns>Root of the object hierarchy</returns>
        private static U GetTree<T, U, V>(
            IEnumerable<T> sourceData
            , Func<T, V> left
            , Func<T, V> right
            , Func<U, IList<U>> children)
            where U : IPopulate<T>, new()
            where V : IComparable<V>
        {
            var data = sourceData.OrderBy(left);
            Stack<TreeNodeContainer<U, V>> stack = new Stack<TreeNodeContainer<U, V>>();
            TreeNodeContainer<U, V> node = null;
            U root = default(U);

            foreach (var d in data)
            {
                //create a blank destination object
                var tmpItem = new U();
                //populate it with the source data via IPopulate
                tmpItem.Populate(d);
                //make an NSM object 
                var tmpIndicator = new Pair<V, V>(left(d), right(d));
                //use the NSM object and the destination object to make the navigation object
                var stackItem = new TreeNodeContainer<U, V>(tmpItem, tmpIndicator);
                if (node != null)
                {
                    //not root

                    //find the correct node to add this child to
                    //if the newly created item has rightside value higher than the rightside
                    //value of the item on the stack, discard the item on the stack.
                    //this is a property of left sorted NSM data
                    // while(stackItem.Indicator.Second.CompareTo(node.Indicator.Second) ==1 )

                    while (stackItem.Indicator.Second.CompareTo(node.Indicator.Second) == 1)
                    {
                        node = stack.Pop();
                    }
                    //add the actual child to the parent 
                    children(node.Payload).Add(tmpItem);
                    //make the current node the latest item
                    node = stackItem;
                }
                else
                {
                    //root
                    root = stackItem.Payload;
                    node = stackItem;
                }
                //put the current item on the stack so it can be considered as a potential parent
                stack.Push(node);
            }
            //cleanup.  not sure if absolutely necessary
            stack.Clear();

            return root;
        }

        /// <summary>
        /// Extension method that builds the hierarchical instance model based on source data stored as a Nested Set Model(NSM).
        /// </summary>
        /// <typeparam name="T">Class type of the source data items</typeparam>
        /// <typeparam name="U">Class type of the returned root "node"</typeparam>
        /// <typeparam name="V">Class type of the field used to do the comparison between the Ts.  Must support IComparable(V)</typeparam>
        /// <param name="sourceData">A "list" of the source data</param>
        /// <param name="left">A delegate of the property where the left side information of a "node" is stored.  NSM concept</param>
        /// <param name="right">A delegate of the property where the right side information of a "node" is stored.  NSM concept</param>
        /// <param name="children">A delegate of the property of the output class that is used to store children.  The property that is named must return an IList(U)</param></param>
        /// <returns>Root of the object hierarchy</returns>
        public static U AsTreeFromNSM<T, U, V>(
            this IEnumerable<T> sourceData
           , Func<T, V> left
           , Func<T, V> right
           , Func<U, IList<U>> children)
            where T : class
            where U : IPopulate<T>, new()
            where V : IComparable<V>
        {
            return GetTree<T, U, V>(sourceData, left, right, children);
        }

        /// <summary>
        /// Extension method that builds the hierarchical instance model based on source data stored as a Nested Set Model(NSM).
        /// </summary>
        /// <typeparam name="T">Class type of the source data items</typeparam>
        /// <typeparam name="U">Class type of the returned root "node"</typeparam>        
        /// <param name="sourceData">A "list" of the source data</param>
        /// <param name="left">A delegate of the property where the left side information of a "node" is stored.  NSM concept</param>
        /// <param name="right">A delegate of the property where the right side information of a "node" is stored.  NSM concept</param>
        /// <param name="children">A delegate of the property of the output class that is used to store children.  The property that is named must return an IList(U)</param></param>
        /// <returns>Root of the object hierarchy</returns>
        public static U AsTreeFromNSM<T, U>(
            this IEnumerable<T> sourceData
           , Func<T, int> left
           , Func<T, int> right
           , Func<U, IList<U>> children)
            where T : class
            where U : IPopulate<T>, new()
        {
            return GetTree<T, U, int>(sourceData, left, right, children);
        }

        private class TreeNodeContainer<T, V>
        {
            public T Payload
            {
                get;
                private set;
            }
            public Pair<V, V> Indicator
            {
                get;
                private set;
            }
            public TreeNodeContainer(T payload, Pair<V, V> indicator)
            {
                Payload = payload;
                Indicator = indicator;
            }
        }       
    }

    /// <summary>
    /// Interface that a class should implement to allow population of it by an object of another type.
    /// </summary>
    /// <typeparam name="T">Type of the class that will be used to populate this instance.</typeparam>
    public interface IPopulate<T>
    {
        /// <summary>
        /// Used to populate the instance with an object of another type.
        /// </summary>
        /// <param name="payload">The source type.</param>
        void Populate(T payload);
    }
}

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

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.
 
_

| Advertise | Privacy | Terms of Use | Mobile
Web03 | 2.8.150123.1 | Last Updated 17 Apr 2009
Article Copyright 2009 by Troy Beacleay
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid