Problem
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<Element>
{
private readonly List<Element> _elements = new List<Element>();
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.Remove(item); }
public IEnumerator<Element> GetEnumerator() { return _elements.GetEnumerator(); }
IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); }
private string DebuggerDisplay { get { return ToString(); } }
public override string ToString() { return Name; }
public string Name { get; set; }
}
ToTree Extension
To turn a flat array back into a tree I wrote this extension method:
static class TreeCreator
{
public static Message ToTree(this IEnumerable<Element> elements)
{
var message = new Message();
var element = elements.GetEnumerator();
element.MoveNext();
ToTree(element, message);
return message;
}
// This is recursive.
private static bool ToTree(IEnumerator<Element> element, ElementCollection parent)
{
var moveNext = true;
while (moveNext)
{
if (element.Current.Parent() == parent.GetType())
{
parent.Add(element.Current);
// Move-next only when parent found.
moveNext = element.MoveNext();
// There are no more elements.
if (!moveNext) { return false; }
}
else
{
// Last element of this parent might be the parent of the next element.
parent = parent.LastOrDefault();
if (parent == null) { return true; }
if (!ToTree(element, parent)) { return false; }
}
}
return false;
}
// Helps to find the parent type.
private static Type Parent(this Element element)
{
return element
.GetType()
.GetCustomAttributes()
.OfType<ParentAttribute>()
.Single()
.Parent;
}
// Prints the tree for debugging.
public static void PrintTree(this ElementCollection elements, int depth = 0)
{
Console.WriteLine(new string('.', depth) + elements.Name);
foreach (var element in elements)
{
element.PrintTree(depth + 1);
}
}
}
Example
Here’s an example how such a tree might look like:
void Main()
{
// This is one dimensional, identation is mine to show the tree structure.
var elements = new Element[]
{
new I { Name = "I1" },
new F { Name = "F1" },
new N { Name = "N1" },
new N { Name = "N2" },
new W { Name = "W1" },
new F { Name = "F2" },
new N { Name = "N3" },
new O { Name = "O1" },
new O { Name = "O2" },
};
var tree = elements.ToTree();
tree.PrintTree();
}
result:
.I1 ..F1 ...N1 ...N2 ....W1 ..F2 ...N3 ....O1 ....O2
Solution
- I think you can just inherit
ElementCollectionfromList<Element>if all you do is wrapListmethods and overrideToString. -
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<Element> elements) { var message = new Message(); var parents = new Stack<ElementCollection>(); 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 addParentproperty to your elements, and you can further improve it by adding meaningful exceptions when input has incorrect fromat.
You can simplify the ToTree() method a little bit by skipping the if (!moveNext) { return false; } and changing if (!ToTree(element, parent)) { return false; } like so
private static bool ToTree(IEnumerator<Element> element, ElementCollection parent)
{
var moveNext = true;
while (moveNext)
{
if (element.Current.Parent() == parent.GetType())
{
parent.Add(element.Current);
// Move-next only when parent found.
moveNext = element.MoveNext();
}
else
{
// Last element of this parent might be the parent of the next element.
parent = parent.LastOrDefault();
if (parent == null) { return true; }
moveNext = ToTree(element, parent)
}
}
return false;
}
You can skip if (!moveNext) { return false; } because it will have the same effect if the while condition will be evaluated.
By assigning the returned value form the recursive call to the moveNext the next evaluation of the while condition will lead to the same result as the former code.
Data Model
I would add a restriction on the attribute and move the convenience method from the creator to this class.
[AttributeUsage(AttributeTargets.Class)]
class ParentAttribute : Attribute
{
public ParentAttribute(Type type) { Parent = type; }
public Type Parent { get; private set; }
}
[AttributeUsage(AttributeTargets.Class, AllowMultiple=false)]
public class ParentAttribute : Attribute
{
public ParentAttribute(Type type) { Parent = type; }
public Type Parent { get; private set; }
public static Type GetParentType(object source) {
return source
.GetType()
.GetCustomAttributes<ParentAttribute>()
.Single() // <- AllowMultiple=false
.Parent;
}
}
I would also agree with others to have a simpler ElementCollection and to add the Parent to Element.
public class ElementCollection : List<Element> {
public string Name { get; set; }
}
public abstract class Element : ElementCollection
{
public ElementCollection Parent { get; set; }
}
Tree Builder
I know you are a fan of Enumerator. But I feel the TreeCreator could be simplified. It is also important to note that the sequence is ordered. If the order changes of your flattened list, different results could yield. (parhaps not the best design)
public static Message ToTree(this IEnumerable<Element> elements)
{
var message = new Message();
var element = elements.GetEnumerator();
element.MoveNext();
ToTree(element, message);
return message;
}
static class TreeCreator
{
public static Message ToTree(this IEnumerable<Element> elements) {
var message = new Message();
ElementCollection parent = message;
foreach (var element in elements) {
while (parent != null && !ParentAttribute.GetParentType(element).Equals(parent.GetType())) {
parent = parent = parent is Element ? ((Element)parent).Parent : null;
}
if (parent == null) break;
parent.Add(element);
element.Parent = parent;
parent = element;
}
return message;
}
}
Text Printer
It’s ok for debugging. But if you want to implement a standardized way for rendering a tree: have a look at this post SurveyTextRenderer.
// Prints the tree for debugging.
public static void PrintTree(this ElementCollection elements, int depth = 0) {
Console.WriteLine(new string('.', depth) + elements.Name);
foreach (var element in elements) {
element.PrintTree(depth + 1);
}
}