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

LINQ to Tree - A Generic Technique for Querying Tree-like Structures

, 4 Mar 2010
This article presents a generic approach to applying LINQ queries to tree like structures. Using T4 templates for code generation, LINQ to VisualTree (WPF), LINQ to WinForms, and LINQ to FileSystem APIs are constructed.
<#@ template language="C#3.5" #>

<#@ assembly name="System.Core.dll" #>


using System.Linq;
using System.Collections.Generic;
using System;
 
<#+
/// <summary>
/// Generate a Linq to Tree API for the given type, using the given adpter which implements
/// ILinqToTree<T>, and places the API within the given namespace.
/// </summary
private void GenerateLinqMethods(string typeName, string adapterType, string targetNamespace)
{
	GenerateLinqMethods(typeName, adapterType, targetNamespace, true, "child.Equals(item)");
}

/// <summary>
/// Generate a Linq to Tree API for the given type, using the given adpter which implements
/// ILinqToTree<T>, and places the API within the given namespace.
/// The 'typedMethods' parameter, indicates whether the API should include methods for filtering
/// the axes by object type. The equality string is used to specialise the mechanism for 
/// determining the equality of a 'child' and an 'item' instance. 
/// </summary
private void GenerateLinqMethods(string typeName, string adapterType, string targetNamespace,
	bool typedMethods, string equality)
{
#>
namespace <#=targetNamespace#>
{
	/// <summary>
    /// Defines an interface that must be implemented to generate the LinqToTree methods
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public interface ILinqTree<T>
    {
        IEnumerable<T> Children();

        T Parent { get; }
    }
  
    public static class TreeExtensions
    {
        /// <summary>
        /// Returns a collection of descendant elements.
        /// </summary>
	    public static IEnumerable<<#=typeName#>> Descendants(this <#=typeName#> item)
        {
            ILinqTree<<#=typeName#>> adapter = new <#=adapterType#>(item);
            foreach (var child in adapter.Children())
            {
                yield return child;

                foreach (var grandChild in child.Descendants())
                {
                    yield return grandChild;
                }
            }
        }    
           
        /// <summary>
        /// Returns a collection containing this element and all descendant elements.
        /// </summary>
	    public static IEnumerable<<#=typeName#>> DescendantsAndSelf(this <#=typeName#> item)
        {            
            yield return item;

            foreach (var child in item.Descendants())
            {
                yield return child;
            }
        }
        
        /// <summary>
        /// Returns a collection of ancestor elements.
        /// </summary>
	    public static IEnumerable<<#=typeName#>> Ancestors(this <#=typeName#> item)
        {
            ILinqTree<<#=typeName#>> adapter = new <#=adapterType#>(item);
            
            var parent = adapter.Parent;
            while(parent != null)
            {
                yield return parent;
                adapter = new <#=adapterType#>(parent);
                parent = adapter.Parent;
            }
        } 
        
        /// <summary>
        /// Returns a collection containing this element and all ancestor elements.
        /// </summary>
	    public static IEnumerable<<#=typeName#>> AncestorsAndSelf(this <#=typeName#> item)
        {
            yield return item;

            foreach (var ancestor in item.Ancestors())
            {
                yield return ancestor;
            }
        }
        
        /// <summary>
        /// Returns a collection of child elements.
        /// </summary>
	    public static IEnumerable<<#=typeName#>> Elements(this <#=typeName#> item)
        {
            ILinqTree<<#=typeName#>> adapter = new <#=adapterType#>(item);
            foreach (var child in adapter.Children())
            {
                yield return child;                
            }
        }
        
        /// <summary>
        /// Returns a collection of the sibling elements before this node, in document order.
        /// </summary>
	    public static IEnumerable<<#=typeName#>> ElementsBeforeSelf(this <#=typeName#> item)
        {
			if (item.Ancestors().FirstOrDefault()==null)
				yield break;
            foreach (var child in item.Ancestors().First().Elements())
            {
				if (<#=equality#>)
					break;
                yield return child;                
            }
        }
        
        /// <summary>
        /// Returns a collection of the elements after this node, in document order.
        /// </summary>
	    public static IEnumerable<<#=typeName#>> ElementsAfterSelf(this <#=typeName#> item)
        {
			if (item.Ancestors().FirstOrDefault()==null)
				yield break;
            bool afterSelf = false;
            foreach (var child in item.Ancestors().First().Elements())
            {
				if (afterSelf)
					yield return child;                
                
                if (<#=equality#>)
					afterSelf=true;
            }
        }
        
        /// <summary>
        /// Returns a collection containing this element and all child elements.
        /// </summary>
	    public static IEnumerable<<#=typeName#>> ElementsAndSelf(this <#=typeName#> item)
        {
            yield return item;

            foreach (var child in item.Elements())
            {
                yield return child;
            }
        }
<#+ if (typedMethods)
{
#>      
        /// <summary>
        /// Returns a collection of descendant elements which match the given type.
        /// </summary>
	    public static IEnumerable<<#=typeName#>> Descendants<T>(this <#=typeName#> item)
        {
            return item.Descendants().Where(i => i is T).Cast<<#=typeName#>>();
        }
        


		/// <summary>
        /// Returns a collection of the sibling elements before this node, in document order
        /// which match the given type.
        /// </summary>
	    public static IEnumerable<<#=typeName#>> ElementsBeforeSelf<T>(this <#=typeName#> item)
        {
			return item.ElementsBeforeSelf().Where(i => i is T).Cast<<#=typeName#>>();
        }
        
        /// <summary>
        /// Returns a collection of the after elements after this node, in document order
        /// which match the given type.
        /// </summary>
	    public static IEnumerable<<#=typeName#>> ElementsAfterSelf<T>(this <#=typeName#> item)
        {
			return item.ElementsAfterSelf().Where(i => i is T).Cast<<#=typeName#>>();
        }

        /// <summary>
        /// Returns a collection containing this element and all descendant elements
        /// which match the given type.
        /// </summary>
	    public static IEnumerable<<#=typeName#>> DescendantsAndSelf<T>(this <#=typeName#> item)
        {
            return item.DescendantsAndSelf().Where(i => i is T).Cast<<#=typeName#>>();
        }
        
        /// <summary>
        /// Returns a collection of ancestor elements which match the given type.
        /// </summary>
	    public static IEnumerable<<#=typeName#>> Ancestors<T>(this <#=typeName#> item)
        {
            return item.Ancestors().Where(i => i is T).Cast<<#=typeName#>>();
        }
        
        /// <summary>
        /// Returns a collection containing this element and all ancestor elements
        /// which match the given type.
        /// </summary>
	    public static IEnumerable<<#=typeName#>> AncestorsAndSelf<T>(this <#=typeName#> item)
        {
            return item.AncestorsAndSelf().Where(i => i is T).Cast<<#=typeName#>>();
        }
        
        /// <summary>
        /// Returns a collection of child elements which match the given type.
        /// </summary>
	    public static IEnumerable<<#=typeName#>> Elements<T>(this <#=typeName#> item)
        {
            return item.Elements().Where(i => i is T).Cast<<#=typeName#>>();
        }
        
        /// <summary>
        /// Returns a collection containing this element and all child elements.
        /// which match the given type.
        /// </summary>
	    public static IEnumerable<<#=typeName#>> ElementsAndSelf<T>(this <#=typeName#> item)
        {
            return item.ElementsAndSelf().Where(i => i is T).Cast<<#=typeName#>>();
        }
        
<#+
}
#>
    }
    
    public static class EnumerableTreeExtensions
    {
		/// <summary>
        /// Applies the given function to each of the items in the supplied
        /// IEnumerable.
        /// </summary>
        private static IEnumerable<<#=typeName#>> DrillDown(this IEnumerable<<#=typeName#>> items,
            Func<<#=typeName#>, IEnumerable<<#=typeName#>>> function)
        {
            foreach(var item in items)
            {
                foreach(var itemChild in function(item))
                {
                    yield return itemChild;
                }
            }
        }

<#+ if (typedMethods)
{
#>
       
        /// <summary>
        /// Applies the given function to each of the items in the supplied
        /// IEnumerable, which match the given type.
        /// </summary>
        public static IEnumerable<<#=typeName#>> DrillDown<T>(this IEnumerable<<#=typeName#>> items,
            Func<<#=typeName#>, IEnumerable<<#=typeName#>>> function)
            where T : <#=typeName#>
        {
            foreach(var item in items)
            {
                foreach(var itemChild in function(item))
                {
                    if (itemChild is T)
                    {
                        yield return (T)itemChild;
                    }
                }
            }
        }

<#+
}
#>    
        /// <summary>
        /// Returns a collection of descendant elements.
        /// </summary>
	    public static IEnumerable<<#=typeName#>> Descendants(this IEnumerable<<#=typeName#>> items)
        {
            return items.DrillDown(i => i.Descendants());
        }    
           
        /// <summary>
        /// Returns a collection containing this element and all descendant elements.
        /// </summary>
	    public static IEnumerable<<#=typeName#>> DescendantsAndSelf(this IEnumerable<<#=typeName#>> items)
        {            
            return items.DrillDown(i => i.DescendantsAndSelf());
        }
        
        /// <summary>
        /// Returns a collection of ancestor elements.
        /// </summary>
	    public static IEnumerable<<#=typeName#>> Ancestors(this IEnumerable<<#=typeName#>> items)
        {
            return items.DrillDown(i => i.Ancestors());
        } 
        
        /// <summary>
        /// Returns a collection containing this element and all ancestor elements.
        /// </summary>
	    public static IEnumerable<<#=typeName#>> AncestorsAndSelf(this IEnumerable<<#=typeName#>> items)
        {
            return items.DrillDown(i => i.AncestorsAndSelf());
        }
        
        /// <summary>
        /// Returns a collection of child elements.
        /// </summary>
	    public static IEnumerable<<#=typeName#>> Elements(this IEnumerable<<#=typeName#>> items)
        {
            return items.DrillDown(i => i.Elements());
        }
        
        /// <summary>
        /// Returns a collection containing this element and all child elements.
        /// </summary>
	    public static IEnumerable<<#=typeName#>> ElementsAndSelf(this IEnumerable<<#=typeName#>> items)
        {
            return items.DrillDown(i => i.ElementsAndSelf());
        }

<#+ if (typedMethods)
{
#>
       
        /// <summary>
        /// Returns a collection of descendant elements which match the given type.
        /// </summary>
	    public static IEnumerable<<#=typeName#>> Descendants<T>(this IEnumerable<<#=typeName#>> items)
	        where T : <#=typeName#>
        {
            return items.DrillDown<T>(i => i.Descendants());
        }
        
        /// <summary>
        /// Returns a collection containing this element and all descendant elements.
        /// which match the given type.
        /// </summary>
	    public static IEnumerable<<#=typeName#>> DescendantsAndSelf<T>(this IEnumerable<<#=typeName#>> items)
	        where T : <#=typeName#>
        {
            return items.DrillDown<T>(i => i.DescendantsAndSelf());
        }
        
        /// <summary>
        /// Returns a collection of ancestor elements which match the given type.
        /// </summary>
	    public static IEnumerable<<#=typeName#>> Ancestors<T>(this IEnumerable<<#=typeName#>> items)
	        where T : <#=typeName#>
        {
            return items.DrillDown<T>(i => i.Ancestors());
        }
        
        /// <summary>
        /// Returns a collection containing this element and all ancestor elements.
        /// which match the given type.
        /// </summary>
	    public static IEnumerable<<#=typeName#>> AncestorsAndSelf<T>(this IEnumerable<<#=typeName#>> items)
	        where T : <#=typeName#>
        {
            return items.DrillDown<T>(i => i.AncestorsAndSelf());
        }
        
        /// <summary>
        /// Returns a collection of child elements which match the given type.
        /// </summary>
	    public static IEnumerable<<#=typeName#>> Elements<T>(this IEnumerable<<#=typeName#>> items)
	        where T : <#=typeName#>
        {
            return items.DrillDown<T>(i => i.Elements());
        }
        
        /// <summary>
        /// Returns a collection containing this element and all child elements.
        /// which match the given type.
        /// </summary>
	    public static IEnumerable<<#=typeName#>> ElementsAndSelf<T>(this IEnumerable<<#=typeName#>> items)
	        where T : <#=typeName#>
        {
            return items.DrillDown<T>(i => i.ElementsAndSelf());
        }
<#+
}
#>
    }
}<#+
}
#>

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

Colin Eberhardt
Architect Scott Logic
United Kingdom United Kingdom
I am CTO at ShinobiControls, a team of iOS developers who are carefully crafting iOS charts, grids and controls for making your applications awesome.
 
I am a Technical Architect for Visiblox which have developed the world's fastest WPF / Silverlight and WP7 charts.
 
I am also a Technical Evangelist at Scott Logic, a provider of bespoke financial software and consultancy for the retail and investment banking, stockbroking, asset management and hedge fund communities.
 
Visit my blog - Colin Eberhardt's Adventures in .NET.
 
Follow me on Twitter - @ColinEberhardt
 
-
Follow on   Twitter   Google+

| Advertise | Privacy | Mobile
Web01 | 2.8.140827.1 | Last Updated 5 Mar 2010
Article Copyright 2010 by Colin Eberhardt
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid