Rendering a hierarchy using LINQ?

Question

Let say we have a class

Category
{
   ID,
   Name,
   ParentID
}

and a List

1, 'Item 1', 0
2, 'Item 2', 0
3, 'Item 3', 0
4, 'Item 1.1', 1
5, 'Item 3.1', 3
6, 'Item 1.1.1', 4
7, 'Item 2.1', 2

Can we using LINQ to render a tree like:

Item 1
 Item 1.1
  Item 1.1.1
Item 2
 Item 2.1
Item 3
 Item 3.1

Any help is appreciated!

Answer 1

Here's the "LINQ-only" version:

Func<int, int, string[]> build = null;
build = (p, n) =>
{
    return (from x in categories
            where x.ParentID == p
            from y in new[]
            {
                "".PadLeft(n)+ x.Name
            }.Union(build(x.ID, n + 1))
            select y).ToArray();
};
var lines = build(0, 0);

Yes, it's recursive LINQ.

---

Per NVA's request, here's the way to make all "orphan" records become root records:

Func<IEnumerable<int>, int, string[]> build = null;
build = (ps, n) =>
{
    return (from x in categories
            where ps.Contains(x.ParentID)
            from y in new[]
    {
        "".PadLeft(n)+ x.Name
    }.Union(build(new [] { x.ID }, n + 1))
            select y).ToArray();
};

var roots = (from c in categories
             join p in categories on c.ParentID equals p.ID into gps
             where !gps.Any()
             orderby c.ParentID
             select c.ParentID).Distinct();

var lines = build(roots, 0);

Answer 2

These extension methods do exactly what you want:

public static partial class LinqExtensions
{
    public class Node<T>
    {
        internal Node() { }

        public int Level { get; internal set; }
        public Node<T> Parent { get; internal set; }
        public T Item { get; internal set; }
        public IList<Node<T>> Children { get; internal set; }
    }

    public static IEnumerable<Node<T>> ByHierarchy<T>(
        this IEnumerable<T> source,
        Func<T, bool> startWith, 
        Func<T, T, bool> connectBy)
    {
        return source.ByHierarchy<T>(startWith, connectBy, null);
    }

    private static IEnumerable<Node<T>> ByHierarchy<T>(
        this IEnumerable<T> source,
        Func<T, bool> startWith,
        Func<T, T, bool> connectBy,
        Node<T> parent)
    {
        int level = (parent == null ? 0 : parent.Level + 1);

        if (source == null)
            throw new ArgumentNullException("source");

        if (startWith == null)
            throw new ArgumentNullException("startWith");

        if (connectBy == null)
            throw new ArgumentNullException("connectBy");

        foreach (T value in from   item in source
                            where  startWith(item)
                            select item)
        {
            var children = new List<Node<T>>();
            Node<T> newNode = new Node<T>
            {
                Level = level,
                Parent = parent,
                Item = value,
                Children = children.AsReadOnly()
            };

            foreach (Node<T> subNode in source.ByHierarchy<T>(possibleSub => connectBy(value, possibleSub),
                                                              connectBy, newNode))
            {
                children.Add(subNode);
            }

            yield return newNode;
        }
    }

    public static void DumpHierarchy<T>(this IEnumerable<Node<T>> nodes, Func<T, string> display)
    {
        DumpHierarchy<T>(nodes, display, 0);
    }

    private static void DumpHierarchy<T>(IEnumerable<LinqExtensions.Node<T>> nodes, Func<T, string> display, int level)
    {
        foreach (var node in nodes)
        {
            for (int i = 0; i < level; i++) Console.Write("  ");
            Console.WriteLine (display(node.Item));
            if (node.Children != null)
                DumpHierarchy(node.Children, display, level + 1);
        }
    }

}

You can use them as follows:

categories.ByHierarchy(
        cat => cat.ParentId == null, // assuming ParentId is Nullable<int>
        (parent, child) => parent.Id == child.ParentId)
     .DumpHierarchy(cat => cat.Name);