Building tree structure based on flat objects

Question

You can find here a Follow-up question

Description

A List<UnrelatedObects> is returned by a 3rd party webservice, which will then be transformed to a List<ArchiveDefinition>. These ArchiveDefinition objects are connected by Parent'.ArchiveNodeId == 'Child'.ParentId.

The root objects TypeOfArchive property will always have the value ArchiveType.Archive.

The goal of the given class below is to build a List<ArchiveTreeNode> of these flat object list to fill a treeview control.

The class in question

public class ArchiveBuilder
{
    public static List<ArchiveTreeEntry> Build(List<ArchiveDefinition> entries)
    {
        List<ArchiveTreeEntry> rootArchiveTreeEntries = new List<ArchiveTreeEntry>();

        if (entries != null && entries.Count > 0)
        {
            List<ArchiveDefinition> rootEntries = GetRootEntries(entries);

            foreach (ArchiveDefinition definition in rootEntries)
            {
                rootArchiveTreeEntries.Add(new ArchiveTreeEntry(definition));
                entries.Remove(definition);
            }

            foreach (ArchiveTreeEntry parent in rootArchiveTreeEntries)
            {
                FillChildren(parent, entries);
            }
        }
        return rootArchiveTreeEntries;
    }

    private static void FillChildren(ArchiveTreeEntry parent,
                                     List<ArchiveDefinition> entries)
    {
        if (entries.Count > 0)
        {
            List<ArchiveDefinition> children = GetChildren(entries, parent.Id);

            if (children.Count > 0)
            {
                RemoveChildren(entries, parent.Id);

                foreach (ArchiveDefinition child in children)
                {
                    ArchiveTreeEntry treeEntryChild = new ArchiveTreeEntry(child);
                    parent.AddChild(treeEntryChild);
                    FillChildren(treeEntryChild, entries);
                }
            }
        }
    }

    private static List<ArchiveDefinition> GetRootEntries(List<ArchiveDefinition> entries)
    {
        return entries.FindAll(e => e.TypeOfArchive == ArchiveType.Archive);
    }

    private static List<ArchiveDefinition> GetChildren(List<ArchiveDefinition> entries, string parentID)
    {
        return entries.FindAll(e => e.ParentId == parentID);
    }

    private static void RemoveChildren(List<ArchiveDefinition> entries, string parentID)
    {
        entries.RemoveAll(e => e.ParentId == parentID);
    }
}

Related classes and enums

public class ArchiveDefinition
{
    public string ArchiveNodeId { get; private set; }
    public string ParentId { get; private set; }
    public ArchiveType TypeOfArchive { get; private set; }

    public ArchiveDefinition (String parentId, String archiveNodeId,
                              ArchiveType type)
    {
        ParentId = parentId;
        TypeOfArchive = type;
        ArchiveNodeId = archiveNodeId;
    }
}

public enum ArchiveType
{
    Archive, ArchiveGroup, ArchiveEntry
}

public class ArchiveTreeEntry
{
    public ArchiveType ArchiveEntryType { get; private set; }
    public string Id { get; private set; }
    public ReadOnlyCollection<ArchiveTreeEntry> Children
    {
        get
        {
            return new ReadOnlyCollection<ArchiveTreeEntry>(mChildren);
        }
    }

    private List<ArchiveTreeEntry> mChildren = new List<ArchiveTreeEntry>();
    public ArchiveTreeEntry(ArchiveDefinition archiveDefinition)
    {
        Id = archiveDefinition.ArchiveNodeId;
        ArchiveEntryType = archiveDefinition.TypeOfArchive;
    }

    internal void AddChild(ArchiveTreeEntry child)
    {
        if (child != null)
        {
            mChildren.Add(child);
        }
    }
}

I would like to get a review for the ArchiveBuilder class. If you also want to review the related classes and enums, I won't mind.

Answer 1

I think your implementation is pretty clear. Nonetheless I tried some changes, hoping my version is more readable.

I agree with Stuart's post. (using IEnumerable<> if possible, non static Build() function, ...).

In Addition I think you have broken this principles:

• Single Responsibility --> Your FillChildren(...) function is looking for children and removing them from the original list and adding them in the parent's children collection. I mean that are three responsibilities.

• Least Attonishment --> In a function called FillChildren I doesn't expect anything being removed.

I changed also many Names, but this may be a matter of taste.

Here is the changed code:

public class ArchiveBuilder
{
    public List<ArchiveTreeEntry> Build(List<ArchiveDefinition> availableArchiveDefinitions)
    {
        List<ArchiveTreeEntry> rootArchiveTreeEntries = null;

        if (availableArchiveDefinitions != null && availableArchiveDefinitions.Count > 0)
        {
            rootArchiveTreeEntries = CreateRootArchiveTreeEntries(availableArchiveDefinitions);
            availableArchiveDefinitions = RemoveRootArchiveDefinitions(availableArchiveDefinitions);
            foreach (var entry in rootArchiveTreeEntries)
            {
                HandleAvailableEntriesForGivenParent(availableArchiveDefinitions, entry);
            }
        }

        return rootArchiveTreeEntries;
    }

    private static void AssignChildrenToParent(ArchiveTreeEntry parent, 
        IEnumerable<ArchiveDefinition> children)
    {
        parent.AddChildRange(children.Select(x => new ArchiveTreeEntry(x)));
    }

    private static List<ArchiveTreeEntry> CreateRootArchiveTreeEntries(
        IEnumerable<ArchiveDefinition> availableArchiveDefinitions)
    {
        var rootArchiveTreeEntries = new List<ArchiveTreeEntry>();
        rootArchiveTreeEntries.AddRange(
            availableArchiveDefinitions.Where(e => e.TypeOfArchive == ArchiveType.Archive)
                .Select(x => new ArchiveTreeEntry(x)));
        return rootArchiveTreeEntries;
    }

    private static IEnumerable<ArchiveDefinition> GetChildren(
        IEnumerable<ArchiveDefinition> availableArchiveDefinitions,
        string parentId)
    {
        return availableArchiveDefinitions.Where(e => e.ParentId == parentId);
    }

    private static void HandleAvailableEntriesForGivenParent(
        List<ArchiveDefinition> availableArchiveDefinitions,
        ArchiveTreeEntry parent)
    {
        if (availableArchiveDefinitions.Count > 0)
        {
            var children = GetChildren(availableArchiveDefinitions, parent.Id);
            AssignChildrenToParent(parent, children);
            RemoveAssignedItemsFromAvailabeEntries(availableArchiveDefinitions, parent.Id);
            foreach (var nextParent in parent.Children)
            {
                HandleAvailableEntriesForGivenParent(availableArchiveDefinitions, nextParent);
            }
        }
    }

    private static void RemoveAssignedItemsFromAvailabeEntries(
        List<ArchiveDefinition> availableArchiveDefinitions,
        string parentId)
    {
        availableArchiveDefinitions.RemoveAll(e => e.ParentId == parentId);
    }

    private static List<ArchiveDefinition> RemoveRootArchiveDefinitions(
        List<ArchiveDefinition> availableArchiveDefinitions)
    {
        var newEntries =
            availableArchiveDefinitions.Except(
                availableArchiveDefinitions.Where(e => e.TypeOfArchive == ArchiveType.Archive))
                .ToList();
        return newEntries;
    }
}

Answer 2

• You could use the AddRange combined with the Except method inside of Build:

  public static List<ArchiveTreeEntry> Build(List<ArchiveDefinition> entries)
  {
      List<ArchiveTreeEntry> rootArchiveTreeEntries = new List<ArchiveTreeEntry>();
  
      if (entries != null && entries.Count > 0)
      {
          List<ArchiveDefinition> rootEntries = GetRootEntries(entries);
  
          entries = rootArchiveTreeEntried.AddRange(rootEntries.Select(definition=> new ArchiveTreeEntry(definition)).Except(entries);
  
          foreach (ArchiveTreeEntry parent in rootArchiveTreeEntries)
          {
              FillChildren(parent, entries);
          }
      }
      return rootArchiveTreeEntries;
  }
  

• You have made the public method static, which in this case is probably fine but it does make it harder to unit test dependencies. I envisage the class being consumed, like this:

  in app

  var builder = new ArchiveBuilder();  
  builder.Build(entities);
  

• That said, the private methods are fine as static methods because the are an implementation detail.

• The private methods can return/accept IEnumerable<> instead of List<>

• From there, you could then re-write the method above to be:

  public static List<ArchiveTreeEntry> Build(List<ArchiveDefinition> entries)
  {
      List<ArchiveTreeEntry> rootArchiveTreeEntries = new List<ArchiveTreeEntry>();
  
      if (entries != null && entries.Count > 0)
      {
          entries = rootArchiveTreeEntried.AddRange(GetRootEntries(entries).Select(entry => new ArchiveTreeEntry(definition)).Except(entries);
  
          foreach (ArchiveTreeEntry parent in rootArchiveTreeEntries)
          {
              FillChildren(parent, entries);
          }
      }
      return rootArchiveTreeEntries;
  }
  

  So here is the completely re-written class:

  public class ArchiveBuilder
  {
      public IEnumerable<ArchiveTreeEntry> Build(IEnumerable<ArchiveDefinition> entries)
      {
          IEnumerable<ArchiveTreeEntry> rootArchiveTreeEntries = new List<ArchiveTreeEntry>();
  
          if (entries != null && entries.Count > 0)
          {
              entries = rootArchiveTreeEntried.AddRange(GetRootEntries(entries).Select(entry => new ArchiveTreeEntry(definition)).Except(entries);
  
              foreach (ArchiveTreeEntry parent in rootArchiveTreeEntries)
              {
                  FillChildren(parent, entries);
              }
          }
          return rootArchiveTreeEntries;
      }
  
      private static void FillChildren(ArchiveTreeEntry parent,
                                   IEnumerable<ArchiveDefinition> entries)
      {
          if (entries.Count > 0)
          {
              IEnumerable<ArchiveDefinition> children = GetChildren(entries, parent.Id);
  
              if (children.Count > 0)
              {
                  RemoveChildren(entries, parent.Id);
  
                  foreach (ArchiveDefinition child in children)
                  {
                      ArchiveTreeEntry treeEntryChild = new ArchiveTreeEntry(child);
                      parent.AddChild(treeEntryChild);
                      FillChildren(treeEntryChild, entries);
                  }
              }
          }
      }
  
      private static IEnumerable<ArchiveDefinition> GetRootEntries(IEnumerable<ArchiveDefinition> entries)
      {
          return entries.FindAll(e => e.TypeOfArchive == ArchiveType.Archive);
      }
  
      private static IEnumerable<ArchiveDefinition> GetChildren(IEnumerable<ArchiveDefinition> entries, string parentID)
      {
          return entries.FindAll(e => e.ParentId == parentID);
      }
  
      private static void RemoveChildren(IEnumerable<ArchiveDefinition> entries, string parentID)
      {
          entries.RemoveAll(e => e.ParentId == parentID);
      }
  }
  

NB: I haven't compiled the class or tested it, so it might not work out the box.

Answer 3

Review

• ArchiveBuilder should be declared static. It does not have any non-static state or operations.
• Both the argument and return value of Build should be IEnumerable<>. There is no reason to use a List<>. You should not remove values from entries anyway, there is an alternative.
• The alternative to removing elements from entries is to use a ILookup<string, ArchiveDefinition> and iterate the children from this local cache.
• entries is an unfortunate name, since the return values are entries, not the arguments. Use items instead.
• You are not taking advantage of enum ArchiveType. Items of type ArchiveEntry are leafs and should not be walked further down the tree.

Proposed changes

Implementing the lookup and exiting recursion early at leaf nodes, we could create a simple and performant strategy, with only side-effect additional memory usage in constructing the intermediate lookup table.

ArchiveBuilder

public static class ArchiveBuilder
{
    public static IEnumerable<ArchiveTreeEntry> Build(IEnumerable<ArchiveDefinition> items)
    {
        var rootItems = items.Where(x => x.TypeOfArchive == ArchiveType.Archive);
        var lookup = items.ToLookup(x => x.ParentId);
        var entries = rootItems.Select(x => new ArchiveTreeEntry(x)).ToArray();

        foreach (var entry in entries)
        {
            Build(entry, lookup);
        }

        return entries;
    }

    private static void Build(ArchiveTreeEntry current, ILookup<string, ArchiveDefinition> lookup)
    {
        if (current.ArchiveEntryType == ArchiveType.ArchiveEntry) return;

        foreach (var childItem in lookup[current.Id])
        {
            var child = new ArchiveTreeEntry(childItem);
            current.AddChild(child);
            Build(child, lookup);
        }
    }
}

Use Case

[TestMethod]
public void UseCase()
{
    var root1 = new ArchiveDefinition(null, "1", ArchiveType.Archive);
    var root1node1 = new ArchiveDefinition("1", "11", ArchiveType.ArchiveGroup);
    var root1node1leaf1 = new ArchiveDefinition("11", "111", ArchiveType.ArchiveEntry);
    var root1node1leaf2 = new ArchiveDefinition("11", "112", ArchiveType.ArchiveEntry);

    var root2 = new ArchiveDefinition(null, "2", ArchiveType.Archive);
    var root2node1 = new ArchiveDefinition("2", "21", ArchiveType.ArchiveGroup);
    var root2node1node1 = new ArchiveDefinition("21", "211", ArchiveType.ArchiveGroup);
    var root2node1node1leaf1 = new ArchiveDefinition("211", "2111", ArchiveType.ArchiveEntry);

    var items = new[] {
        root1, root1node1, root1node1leaf1, root1node1leaf2,
        root2, root2node1, root2node1node1, root2node1node1leaf1
    };

    var nodes = ArchiveBuilder.Build(items).ToArray();

    Assert.AreEqual("1", nodes[0].Id);
    Assert.AreEqual("11", nodes[0].Children[0].Id);
    Assert.AreEqual("111", nodes[0].Children[0].Children[0].Id);
    Assert.AreEqual("112", nodes[0].Children[0].Children[1].Id);

    Assert.AreEqual("2", nodes[1].Id);
    Assert.AreEqual("21", nodes[1].Children[0].Id);
    Assert.AreEqual("211", nodes[1].Children[0].Children[0].Id);
    Assert.AreEqual("2111", nodes[1].Children[0].Children[0].Children[0].Id);
}

Further Improvements

• Guards arguments against null
• Guard trees against cyclic entries
• Refactor the algorithm to use a generic functional approach, unaware of your classes and reusable for any flattened list to tree builder (that adheres to some sort of rules)

---

EDIT: I went on for the functional, generic approach. Not sure whether this is a useful extension or tailored to very specific situations.

So the code above can be refactored to use the extension method..

public static IEnumerable<ArchiveTreeEntry> Build(IEnumerable<ArchiveDefinition> items)
{
    return items.ToTree(
        x => x.ArchiveNodeId,
        x => x.ParentId,
        x => new ArchiveTreeEntry(x),
        (parent, child) => parent.AddChild(child),
        x => x.TypeOfArchive == ArchiveType.Archive,
        x => x.TypeOfArchive == ArchiveType.ArchiveEntry);
}

And the extension method..

public static IEnumerable<TResult> ToTree<TSource, TResult, TId>(
    this IEnumerable<TSource> source,
    Func<TSource, TId> idSelector,
    Func<TSource, TId> parentIdSelector,
    Func<TSource, TResult> resultFactory,
    Action<TResult, TResult> childAppender,
    Func<TSource, bool> rootPredicate = null,
    Func<TSource, bool> leafPredicate = null) where TSource : class
{
    if (source == null) throw new ArgumentNullException(nameof(source));
    if (idSelector == null) throw new ArgumentNullException(nameof(idSelector));
    if (parentIdSelector == null) throw new ArgumentNullException(nameof(parentIdSelector));
    if (resultFactory == null) throw new ArgumentNullException(nameof(resultFactory));
    if (childAppender == null) throw new ArgumentNullException(nameof(childAppender));

    rootPredicate = rootPredicate ?? (x => idSelector(x) == default);
    leafPredicate = leafPredicate ?? (x => false);
    var visited = new List<TSource>();

    return BuildTreeInternal(
        source, idSelector, parentIdSelector, resultFactory, childAppender, 
        rootPredicate, leafPredicate, visited);
}

private static IEnumerable<TResult> BuildTreeInternal<TSource, TResult, TId>(
    this IEnumerable<TSource> source,
    Func<TSource, TId> idSelector,
    Func<TSource, TId> parentIdSelector,
    Func<TSource, TResult> resultFactory,
    Action<TResult, TResult> childAppender,
    Func<TSource, bool> rootPredicate,
    Func<TSource, bool> leafPredicate,
    List<TSource> visited) where TSource : class
{
    var sourceRoots = source.Where(rootPredicate);
    var lookup = source.ToLookup(parentIdSelector);
    var results = sourceRoots.Select(
        x => (source: x, result: resultFactory(x))).ToArray();

    foreach (var result in results)
    {
        BuildTreeInternal(
            result, lookup, idSelector, resultFactory, 
            childAppender, leafPredicate, visited);
    }

    return results.Select(x => x.result);
}

private static void BuildTreeInternal<TSource, TResult, TId>(
    (TSource source, TResult result) current, 
    ILookup<TId, TSource> lookup,
    Func<TSource, TId> idSelector,
    Func<TSource, TResult> resultFactory,
    Action<TResult, TResult> childAppender,
    Func<TSource, bool> leafPredicate,
    List<TSource> visited)
{
    if (leafPredicate(current.source)) return;
    if (visited.Contains(current.source))
        throw new InvalidOperationException("cyclic graph not allowed");
    visited.Add(current.source);

    foreach (var sourceChild in lookup[idSelector(current.source)])
    {
        var resultChild = resultFactory(sourceChild);
        childAppender(current.result, resultChild);

        BuildTreeInternal(
            (sourceChild, resultChild), lookup, idSelector,
            resultFactory, childAppender, 
            leafPredicate, visited);
    }
}