5
\$\begingroup\$

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?

Edit

I have modified the code of the accepted answer a little bit to answer my needs. With my modification, you can have many roots element instead of just one.

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

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)
{
    Dictionary<TID, T> lookUp = elements.ToDictionary(e => idSelector(e));

    foreach (T element in lookUp.Values)
    {
        TID parentId = parentIdSelector(element);

        if (parentId == null)
        {
            yield return element;
            continue;
        }

        if (!lookUp.TryGetValue(parentId, out T parent))
        {
            throw new InvalidOperationException($"Parent not found for: {element}");
        }

        parentSetter(parent, element);
        childAdder(parent, element);
    }
}
\$\endgroup\$
  • \$\begingroup\$ You might find my question about the same task interesting. It's here. \$\endgroup\$ – t3chb0t Dec 20 '18 at 22:18
  • \$\begingroup\$ I think there's a little difference with what I want. I want to move my objects in is own tree, not use another class that will make the tree. But I will read your code carefully and see if I can use some logic in my own implementation. Thank you very much! \$\endgroup\$ – Alexandre Jobin Dec 21 '18 at 13:54
3
\$\begingroup\$

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.


EDIT

You can then call the method like:

  Category[] categories = new Category[1000]; // TODO: Convert from DTO-object
  IEnumerable<Category> tree = categories.AsHierarchy(
    c => c.CategoryId, 
    c => c.CategoryParentId, 
    (child, parent) => child.ParentCategory = parent, 
    (child, parent) => parent.ChildCategories.Add(child), 0);

Here the last 0 is the supposed rootId.

\$\endgroup\$
  • \$\begingroup\$ Presently, I feel more secure to use the one that doesn't require that the data is in order. But how do you use the ParentSetter and ChildSetter? When i call the function, I don't know what to pass for these params. \$\endgroup\$ – Alexandre Jobin Jan 10 at 20:21
  • \$\begingroup\$ @AlexandreJobin: Please see my update... \$\endgroup\$ – Henrik Hansen Jan 11 at 6:17
  • \$\begingroup\$ What is the advantage to use delegates for the parent/child setters vs using a Func<TEntity, TEntity>? Instead of declaring how to set the parent and child, you just have to tell who is the parent and who is the child property. \$\endgroup\$ – Alexandre Jobin Jan 11 at 16:50
  • \$\begingroup\$ I've put an updated version of your code in my description to accept more than one root element. \$\endgroup\$ – Alexandre Jobin Jan 14 at 21:01
  • \$\begingroup\$ @AlexandreJobin: OK, you can do it like that, but it will limit the use to having a parent id as reference or nullable type. Another way would be to inject a delegate, that can determine whether a parent id is the root id or not. \$\endgroup\$ – Henrik Hansen Jan 15 at 7:02
1
\$\begingroup\$

It seems to me that since you have all these Funcs for getting/setting parents/children and their identifiers, any class you want to use this on basically has to be "ready" to be a heirarchy item and already have a notion of parents/children etc.

Because of this I'd create a interface to indicate how the heirarchy items relate to each other. Something like:

public interface IHeirarchyItem<TKey, TItem> where TItem : IComparable<T> {
    TKey HeirarchyKey {get;}
    TKey ParentKey {get;}
}

And a interface for a heirarchy "node":

public interface IHeirarchyNode<TKey, TItem> where TItem : IHeirarchyItem {
    void AddChild(TItem child);
    TItem Parent {get; set; }
}

Category and CategoryDTO can implement these interfaces through existing methods (it is my understanding that those classes are generated by you). Such an implementation would be something like:

public class CategoryDto : IHeirarchyItem<int, CategoryDTO>
{
    public CategoryDto()
    {
        this.ChildCategories = new HashSet<CategoryDto>();
    }

    public int HeirarchyKey { get { return CategoryId;}}
    public int? ParentKey { get { return CategoryParentId ;}}

    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; }
}

Or alternatively:

public class CategoryDto : IHeirarchyItem<int, CategoryDto>, IHeirarchyNode<int, CategoryDto>, IComparable<CategoryDto>
{
    public CategoryDto()
    {
        this.ChildCategories = new HashSet<CategoryDto>();
    }

    public int HeirarchyKey { get { return CategoryId;}}
    public int? ParentKey { get { return CategoryParentId ;}}

    public void AddChild(CategoryDto child) => ChildCategories.Append(child); //not efficient at all! Just an example

    public CategoryDto Parent {
        get => ParentCategory; 
        set => ParentCategory= value;
    }

    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; }

    public int CompareTo (T other) {//do comparison}; 
}

You can also have a concrete HeirarchyNode : IHeirarchyNode where TItem : IHeirarchyItem {...} which has an actual list of children and a reference to a parent e.g.

public class HeirarchyNode<TKey, TItem> : IHeirarchyNode<int, TItem> where TKey : struct where TItem : IHeirarchyItem<int, TItem>, IComparable<TItem> {
        public List<TItem> Children {get;set;}
        public TItem Parent {get;set;}

        public void AddChild(TItem child) => Children.Add(child);
    }

Your code for setting up the heirarchy can then work off these interfaces.

The benefit of this approach is that the Category objects always have control of how they fit into a heirarchy with each other and AsHierarchy() method can have a shorter, more readable signature.

If you cannot or do not want to have classes implementing these heirarchy interfaces directly, you could have a implementation of IHeirarchyItem which takes in Func(s) for getting the keys etc. I recommend you do this using some kind of factory so that you can ensure that the way a IHeirarchyItem for a given type works will be consistent in all cases.

\$\endgroup\$
  • \$\begingroup\$ Can you tell me how it will look like when you use the interface in the class? It's like if you will have 2 properties for the key and 2 properties for the parentKey: CategoryId, HierarchyKey, ParentCategoryId, ParentKey. Am I right? \$\endgroup\$ – Alexandre Jobin Jan 10 at 20:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.