Gfrktyl

I have a collection of items in my database with a ParentId property. I'm reading the categories as a flat structure and I would like to convert it to a hierarchy list by populating the ParentCategory and ChildCategories properties.

// Domain class

public class Category

{

    public Category()

    {

        this.ChildCategories = new HashSet<Category>();

    }



    public int CategoryId { get; set; }    

    public string Name { get; set; }

    public int Position { get; set; }



    // ... many more properties



    public int? CategoryParentId { get; set; }    

    public virtual Category ParentCategory { get; set; }    

    public virtual ICollection<Category> ChildCategories { get; set; }

}



// DTO class

public class CategoryDto

{

    public CategoryDto()

    {

        this.ChildCategories = new HashSet<CategoryDto>();

    }



    public int CategoryId { get; set; }    

    public string Name { get; set; }    

    public int? CategoryParentId { get; set; }    

    public CategoryDto ParentCategory { get; set; }    

    public IEnumerable<CategoryDto> ChildCategories { get; set; }

}

Since that we cannot do hierarchy query directly with Entity Framework Core, I can only retrieve them in a flat list like so:

var result = myDbContext.Categories

                .Select(category => new Dto.CategoryIndexDto()

                {

                    CategoryId = category.CategoryId,

                    Name = category.Name,

                    Position = category.Position,

                    CategoryParentId = category.CategoryParentId,

                });

So I needed a way to convert this list of dto objects into hierarchy list where the ParentCategory and ChildCategories are populated for each dto object. So I've made this extension:

public static IEnumerable<TEntity> AsHierarchy<TEntity, TKeyProperty, TChildrenProperty>(

    this IEnumerable<TEntity> items,

    Func<TEntity, TKeyProperty> keyProperty,

    Func<TEntity, TKeyProperty> parentKeyProperty,

    Expression<Func<TEntity, TEntity>> parentPropertySelector,

    Expression<Func<TEntity, TChildrenProperty>> childrenPropertySelector)

        where TChildrenProperty : IEnumerable<TEntity>

{

    return items.AsHierarchy(keyProperty, parentKeyProperty, parentPropertySelector, childrenPropertySelector, default(TKeyProperty), default(TEntity));

}



private static IEnumerable<TEntity> AsHierarchy<TEntity, TKeyProperty, TChildrenProperty>(

    this IEnumerable<TEntity> items,

    Func<TEntity, TKeyProperty> keyProperty,

    Func<TEntity, TKeyProperty> parentKeyProperty,

    Expression<Func<TEntity, TEntity>> parentPropertySelector,

    Expression<Func<TEntity, TChildrenProperty>> childrenPropertySelector,

    TKeyProperty parentKeyValue,

    TEntity parentValue)

        where TChildrenProperty : IEnumerable<TEntity>

{

    foreach (var item in items.Where(item => parentKeyProperty(item).Equals(parentKeyValue)))

    {

        var parentProperty = (parentPropertySelector.Body as MemberExpression).Member as PropertyInfo;

        var childrenProperty = (childrenPropertySelector.Body as MemberExpression).Member as PropertyInfo;



        parentProperty.SetValue(item, parentValue, null);



        var childrenValues = items.AsHierarchy(keyProperty, parentKeyProperty, parentPropertySelector, childrenPropertySelector, keyProperty(item), item).ToList();

        childrenProperty.SetValue(item, childrenValues, null);



        yield return item;

    }

}

And now I can call my database that way:

var result = myDbContext.Categories

                .Select(category => new Dto.CategoryIndexDto()

                {

                    CategoryId = category.CategoryId,

                    Name = category.Name,

                    Position = category.Position,

                    CategoryParentId = category.CategoryParentId,

                })

                .ToList() // query the database

                .AsHierarchy(x => x.CategoryId, x => x.CategoryParentId, x => x.ParentCategory, x => x.ChildCategories)

                .ToList();

Now my flat list is fully converted to an hierarchy list and they are all linked together by the navigation properties (ParentCategory and ChildCategories).

I would like to know if the AsHierarchy function is well coded for performance and if there's a way to simplify it?

Your algorithm seems to be working as expected, and for very small data sets it is okay. But for larger data sets it is not optimal and for sets larger than 1000 it is very inefficient.

Some minor problems:

foreach (var item in items.Where(item => parentKeyProperty(item).Equals(parentKeyValue)))

{

    var parentProperty = (parentPropertySelector.Body as MemberExpression).Member as PropertyInfo;

    var childrenProperty = (childrenPropertySelector.Body as MemberExpression).Member as PropertyInfo;

The member information for the child and parent properties are invariant per item, so place their statements before the loop:

var parentProperty = (parentPropertySelector.Body as MemberExpression).Member as PropertyInfo;

var childrenProperty = (childrenPropertySelector.Body as MemberExpression).Member as PropertyInfo;



foreach (var item in items.Where(item => parentKeyProperty(item).Equals(parentKeyValue)))

{

Personally I try to only use reflection as the last resort and here it is not necessary. You can change your method signatures to something like this instead:

public static IEnumerable<TEntity> AsHierarchyReview<TEntity, TKeyProperty>(

  this IEnumerable<TEntity> items,

  Func<TEntity, TKeyProperty> keyProperty,

  Func<TEntity, TKeyProperty> parentKeyProperty,

  Action<TEntity, TEntity> parentSetter,

  Action<TEntity, TEntity> childSetter)

{

  return items.AsHierarchyReview(keyProperty, parentKeyProperty, parentSetter, childSetter, default(TKeyProperty), default(TEntity));

}



private static IEnumerable<TEntity> AsHierarchyReview<TEntity, TKeyProperty>(

    this IEnumerable<TEntity> items,

    Func<TEntity, TKeyProperty> keyProperty,

    Func<TEntity, TKeyProperty> parentKeyProperty,

    Action<TEntity, TEntity> parentSetter,

    Action<TEntity, TEntity> childSetter,

    TKeyProperty parentKeyValue,

    TEntity parentValue)

{

  foreach (var item in items.Where(item => parentKeyProperty(item).Equals(parentKeyValue)))

  {

    parentSetter(item, parentValue);



    var childrenValues = items.AsHierarchyReview(keyProperty, parentKeyProperty, parentSetter, childSetter, keyProperty(item), item).ToList();

    foreach (var child in childrenValues)

    {

      childSetter(child, item);

    }



    yield return item;

  }

But the overall problem with your algorithm is this:

  foreach (var item in items.Where(item => parentKeyProperty(item).Equals(parentKeyValue)))

  {

    ...

Here you requery the entire collection for every item in the collection to find possible child elements to the argument parent and that is too expensive.

If you know that the elements in the data set are given in hierarchical order, the most optimized solution would be to go along with Nikita B's answer in the link suggested by t3chb0t.

If not, you could go along the below path:

public delegate void ParentSetter<T>(T child, T parent);

public delegate void ChildSetter<T>(T child, T parent);



public static IEnumerable<T> AsHierarchy<T, TID>(

  this IEnumerable<T> elements,

  Func<T, TID> idSelector,

  Func<T, TID> parentIdSelector,

  ParentSetter<T> parentSetter,

  ChildSetter<T> childAdder,

  TID rootId)

{

  Dictionary<TID, T> lookUp = elements.ToDictionary(e => idSelector(e));



  foreach (T element in lookUp.Values)

  {

    TID parentId = parentIdSelector(element);

    if (!lookUp.TryGetValue(parentId, out T parent))

    {

      if (parentId.Equals(rootId))

      {

        yield return element;

        continue;

      }

      else

        throw new InvalidOperationException($"Parent not found for: {element}");

    }



    parentSetter(element, parent);

    childAdder(element, parent);

  }

}

Here a dictionary is created as a look up table for the parent of each element. To create a dictionary is a remarkable inexpensive operation.

When an elements parent is not found it is checked if the parent id is the root id. If true the element is returned otherwise an exception is thrown.

A pair of explicit delegates for setting the parent and child are provided in order to show which argument is supposed to be the child and which the parent.