Omer van Kloeten's .NET Zen

Programming is life, the rest is mere details

News

Note: This blog has moved to omervk.wordpress.com.

Omer van Kloeten's Facebook profile

Omer has been professionally developing applications over the past 8 years, both at the IDF’s IT corps and later at the Sela Technology Center, but has had the programming bug ever since he can remember himself.
As a senior developer at NuConomy, a leading web analytics and advertising startup, he leads a wide range of technologies for its flagship products.

Get Firefox


powered by Dapper 

.NET Resources

Articles :: CodeDom

Articles :: nGineer

Culture

Projects

Hierarchical Linq Queries

After reading Bill Wagner's excellent introduction to Linq, I really liked what I saw and decided that I wanted to create an extension method as an exercise. I sat and thought what I would have wanted from Linq and decided I wanted to write a method that lets you select hierarchical data.

Here's a mockup of how a query would look like:
from   node in tree.ByHierarchy<HierarchicalData>(startWith, connectBy)
select node;
Each 'node' in the query will be an object holding the original item, its level of depth in the hierarchy and its parent (for convenience's sake):
public class Node<T>
{
    public int Level;
    public Node<T> Parent;
    public T Item;
}
This node will be used to determine what the item is and where it's located.
Let's take an example:
Tree t7 = new Tree { Value = 7 };
Tree t6 = new Tree { Value = 6 };
Tree t5 = new Tree { Value = 5, Left = t6, Right = t7 };
Tree t4 = new Tree { Value = 4 };
Tree t3 = new Tree { Value = 3 };
Tree t2 = new Tree { Value = 2, Left = t3, Right = t4 };
Tree t1 = new Tree { Value = 1, Left = t2, Right = t5 };
 
Tree[] treeNodes = new Tree[] { t1, t2, t3, t4, t5, t6, t7 };
 
var nodes = from   node in treeNodes.ByHierarchy<Tree>(
                               t => t == t1,
                               (parent, child) => (parent.Left == child) ||
                                                  (parent.Right == child))
            select node;
 
foreach (LinqExtensions.Node<Tree> n in nodes)
{
    for (int i = 0; i < n.Level; i++) Console.Write(' ');
 
    Console.WriteLine("Node {0}, child of {1}.",
                      n.Item.Value,
                      (n.Parent != null ? n.Parent.Item.Value.ToString() : "no one"));
}
This example will walk on the tree (which so happens to be a three-tiered complete binary tree) and print it in the order of hierarchy:
Node 1, child of no one.
Node 2, child of 1.
Node 3, child of 2.
Node 4, child of 2.
Node 5, child of 1.
Node 6, child of 5.
Node 7, child of 5.
And here's the code that does this:
using System;
using System.Collections.Generic;
using System.Query;

namespace DotNetZen.Linq
{
    public static partial class LinqExtensions
    {
        public class Node<T>
        {
            internal Node()
            {
            }
 
            public int Level;
            public Node<T> Parent;
            public T Item;
        }
 
        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)
            {
                Node<T> newNode = new Node<T> { Level = level, Parent = parent, Item = value };
 
                yield return newNode;
 
                foreach (Node<T> subNode in source.ByHierarchy<T>(possibleSub => connectBy(value, possibleSub),
                                            connectBy, newNode))
                {
                    yield return subNode;
                }
            }
        }
    }
}

Comments

No Comments