Click here to Skip to main content
13,896,212 members
Click here to Skip to main content
Add your own
alternative version

Stats

9.4K views
14 bookmarked
Posted 8 Mar 2017
Licenced CPOL

A C# Extension to Recursively Select All Descendents

, 9 Mar 2017
Rate this:
Please Sign up or sign in to vote.
How to recursively select all descendants using an extension method

Introduction

.NET's SelectMany extension methods select only the immediate children of the source. Here, I present two IEnumerable<T> extension methods called SelectManyRecursive and SelectManyAllInclusive. The first will select only the descendents and the second will select the descendents and the items in the source collection. I include also a test program to show how it works.

Using the Code

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace SelectManyRecursive
{
    public static class Extensions
    {
        public static IEnumerable<T> SelectManyRecursive<T>
                (this IEnumerable<T> source, Func<T, IEnumerable<T>> selector)
        {
            var result = source.SelectMany(selector);
            if (!result.Any())
            {
                return result;
            }
            return result.Concat(result.SelectManyRecursive(selector));
        }
 
        public static IEnumerable<T> SelectManyAllInclusive<T>
               (this IEnumerable<T> source, Func<T, IEnumerable<T>> selector)
        {
            return source.Concat(source.SelectManyRecursive(selector));
        }
    }
 
    class Test
    {
        int _level;
        public List<Test> Children = new List<Test>();
 
        static Random rand = new Random(DateTime.Now.Millisecond);
        public static int maxLevels = 5;
        public static int total = 0;
 
        public Test() : this(1)
        {
        }
 
        private Test(int level)
        {
            ++total;
            _level = level;
            if (level < maxLevels)
            {
                int numChildren = rand.Next(10) + 1;
                ++level;
                while (numChildren-- > 0)
                {
                    Children.Add(new Test(level));
                }
            }
        }
    }
 
    class Program
    {
        static void Main(string[] args)
        {
            List<Test> root = new List<Test> { new Test(), new Test() };
            var descendents = root.SelectManyRecursive(t => t.Children);
            int descendantsCount = descendents.Count();
 
            var all = root.SelectManyAllInclusive(t => t.Children);
            var count = all.Count();
 
            Console.WriteLine($@"Total Test instances = {Test.total}
Total descendents collected = {descendantsCount}.
 
Note that 'Total descendents' will correctly be {root.Count} less than
'Total Test instances' because SelectManyRecursive selects only the descendents.
 
SelectManyAllInclusive (count = {count}) will select all items including from the source.
 
Press enter to continue:");
            Console.Read();
        }
    }
}

Points of Interest

There's a more efficient non-recursive algorithm than the one presented.

History

  • 8 March 2017: First version
  • 9 March 2017: changed to use result.Any() instead of .ToList() and .Count because .ToList() can result in unnecessary overhead.

License

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

Share

About the Author

TheGreatAndPowerfulOz
United States United States
No Biography provided

You may also be interested in...

Comments and Discussions

 
GeneralRe: My vote of 1 PinPopular
Sean Ewington20-Apr-17 5:44
staffSean Ewington20-Apr-17 5:44 
GeneralRe: My vote of 1 PinPopular
Sean Ewington20-Apr-17 6:22
staffSean Ewington20-Apr-17 6:22 
GeneralRe: My vote of 1 Pin
Sean Ewington20-Apr-17 6:38
staffSean Ewington20-Apr-17 6:38 
GeneralRe: My vote of 1 Pin
Andrew Osman21-Apr-17 7:47
memberAndrew Osman21-Apr-17 7:47 
SuggestionNon-recursive version Pin
Richard Deeming9-Mar-17 8:51
mveRichard Deeming9-Mar-17 8:51 
PraiseRe: Non-recursive version Pin
TheGreatAndPowerfulOz9-Mar-17 8:57
memberTheGreatAndPowerfulOz9-Mar-17 8:57 
GeneralRe: Non-recursive version Pin
Richard Deeming9-Mar-17 9:21
mveRichard Deeming9-Mar-17 9:21 
PraiseRe: Non-recursive version Pin
TheGreatAndPowerfulOz9-Mar-17 10:01
memberTheGreatAndPowerfulOz9-Mar-17 10:01 
GeneralRe: Non-recursive version Pin
Richard Deeming9-Mar-17 10:21
mveRichard Deeming9-Mar-17 10:21 
GeneralRe: Non-recursive version Pin
TheGreatAndPowerfulOz9-Mar-17 10:56
memberTheGreatAndPowerfulOz9-Mar-17 10:56 
GeneralRe: Non-recursive version Pin
BillWoodruff12-Mar-17 19:31
mveBillWoodruff12-Mar-17 19:31 

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

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

Permalink | Advertise | Privacy | Cookies | Terms of Use | Mobile
Web01 | 2.8.190306.1 | Last Updated 9 Mar 2017
Article Copyright 2017 by TheGreatAndPowerfulOz
Everything else Copyright © CodeProject, 1999-2019
Layout: fixed | fluid