(Re)Creating a tree from a flat collection (or "unflatten" a tree)

I need to create a tree from a flat collection. The order of elements is defined in a specification so it's rather impossible that it will ever change... but I want the whole algorithm to be configuratble and extendable aka universal... the SOLID virus ;-) so I did the following...

Data Models

I created an attribute that specifies which type is the parent type:

[AttributeUsage(AttributeTargets.Class)]
class ParentAttribute : Attribute
{
    public ParentAttribute(Type type) { Parent = type; }
    public Type Parent { get; private set; }
}

and I decorated a bunch of classes with it:

class Message : ElementCollection { }

abstract class Element : ElementCollection { }

[Parent(typeof(Message))]
class I : Element { }

[Parent(typeof(I))]
class F : Element { }

[Parent(typeof(F))]
class N : Element { }

[Parent(typeof(N))]
class W : Element { }

[Parent(typeof(N))]
class O : Element { }

There is always one message that can contain any number of nested elements.

Desclimer: the class names are not random, they are industry standard element names like I stands for Inbound Flight Information or F stands for Operational Outbound Flight Information and so on. I use full names in the production code but used the letters for testing the tree algorithm.

The ElementCollection is rather straightforward and just implements the ICollection interface (nothing unusual here):

```
[DebuggerDisplay("{DebuggerDisplay,nq}")]
class ElementCollection : ICollection
{
private readonly List _elements = new List();

public int Count { get { return _elements.Count; } }

public bool IsReadOnly { get { return false; } }

public void Add(Element item) { _elements.Add(item); }

public void Clear() { _elements.Clear(); }

public bool Contains(Element item) { return _elements.Contains(item); }

public void CopyTo(Element[] array, int arrayIndex) { _elements.CopyTo(array, arrayIndex); }

public bool Remove(Element item) { return _elements.

• I think you can just inherit ElementCollection from List if all you do is wrap List methods and override ToString.

-
Recursive methods are hard enough to understand and debug in their own right. When you add enumerator which you move manually to the mix, it becomes even harder. I think you should come up with non-recursive solution. Here is a solution I came up with (which might not cover some edge cases):

public static Message ToTree(this IEnumerable elements)
{
    var message = new Message();
    var parents = new Stack();
    parents.Push(message);
    foreach (var element in elements)
    {
        while (element.Parent() != parents.Peek().GetType())
        {
            parents.Pop();
        }
        parents.Peek().Add(element);
        parents.Push(element);
    }
    return message;
}

you can get rid of Stack, if you add Parent property to your elements, and you can further improve it by adding meaningful exceptions when input has incorrect fromat.

StackExchange Code Review Q#138524, answer score: 3