Convert hierarchical sort method to an extension in C#

Question

I have a method that sorts a parent-child list into a hierarchy. It works great, but is possible to convert this into a generic extension method?

List<Task> tasks = new List<Task>( );

tasks.Add( new Task { Id = 1, ParentId = null, Title = "" } );
tasks.Add( new Task { Id = 2, ParentId = 4, Title = "" } );
tasks.Add( new Task { Id = 3, ParentId = 2, Title = "" } );
tasks.Add( new Task { Id = 4, ParentId = null, Title = "" } );
tasks.Add( new Task { Id = 5, ParentId = 2, Title = "" } );
tasks.Add( new Task { Id = 6, ParentId = null, Title = "" } );
tasks.Add( new Task { Id = 7, ParentId = 6, Title = "" } );

The method:

var lookup = tasks.ToLookup( x => x.ParentId );

IEnumerable<Task> heirarchySort( int? pid ) => lookup[pid]
    .SelectMany(
        x => new[] { x }.Concat( heirarchySort( x.Id ) )
    );

IEnumerable<Task> sortedTasks = heirarchySort( null );

Thanks in advance.

Answer 1

The following solution uses two expressions to access the Id and ParentId of the items; the order returned if depth-first as in your code:

static class Extension
{
    public static IEnumerable<T> DFS<T>(this IEnumerable<T> list, Func<T, int> getId, Func<T, int?> getParentId)
    {
        var lookup = list.ToLookup(x => getParentId(x));
        IEnumerable<T> hierarchySort(int? pid) => lookup[pid].SelectMany(x => new[] { x }.Concat(hierarchySort(getId(x))));
        return hierarchySort(null);
    }
}

Usage:

IEnumerable<Task> sortedTasks = tasks.DFS(t => t.Id, t => t.ParentId);

it still hard-codes the type of Id as int; this could be made an additional template parameter if needed.