Mini-task: “old-school” tree

Formulation of the problem

Just a few days ago, Eric Lippert published a very simple but entertaining puzzle on his blog Fabulous Adventures In Coding :

There is a tree defined using the Node class, in which there are Children with the same Node and some Text (just below I will give the class code). You need to generate a line of this type (including line breaks):
You need to use the Unicode characters "│ ├ ─ └" (recall the good old pictures with pseudographics). The goal that Eric has set himself is to find out what preferences will be made when making a decision: recursive (because the tree), faster or more readable.

Code source class Node:

class Node<br>{<br> public Node( string text, params Node[] children)<br> {<br> this .Text = text;<br> this .Children = children ?? new Node[] {};<br> }<br> public string Text { get ; private set ; }<br> public IList<Node> Children { get ; private set ; }<br>} <br><br> * This source code was highlighted with Source Code Highlighter .

')
Initial data:

var root = new Node( "a" , <br> new Node( "b" ,<br> new Node( "c" , <br> new Node( "d" )),<br> new Node( "e" ,<br> new Node( "f" ))),<br> new Node( "g" , <br> new Node( "h" ,<br> new Node( "i" )),<br> new Node( "j" ))); <br><br> * This source code was highlighted with Source Code Highlighter .

The task is to fill in the missing lines here:

sealed class Dumper<br>{<br> static public string Dump(Node root) { /* ... */ }<br> /* ... */ <br>} <br><br> * This source code was highlighted with Source Code Highlighter .

Solutions

So, as I did not find the habraparser tag "<spoiler>", and I do not want to bring the solution in open form. In order not to deprive of the pleasure of writing my own solution, I will give references to these solutions and explain a little.

But I would advise you to spend a dozen minutes writing your own decision. If there is no IDE or too lazy to run, I recommend Snippet Compiler (although it is only for .NET 3.5, for 4.0 I did not find anything analogous - so that with code completition, without creating files).

First approach

First, I set myself the task to go the most LINQ-way, absolutely not taking into account the speed of execution. It turned out quite interesting - linq-like option . In the code there is both a recursive enumeration of all nodes of a tree, and iterative. Please note that the calculation is “lazy”, all strings are collected either by StringBuilder or using LinkedList and then by Join, which minimizes unnecessary copying of strings or shifting arrays.

The option came out slow. Highly.

Second approach

Lenvye calculations, etc. Of course it's beautiful, but I wanted to write the most optimal implementation for speed. Noting that the "level" indent is always the same, and we can use it every time you add a new level, I decided to arrange it in such an option . All in one function, only an auxiliary container class is added. The same StringBuilder, but, this time, decided to abandon any arrays for pieces of indents. And again, no recursion - the passage through the tree and the construction of the result occurs simultaneously.

This option refused to be quite good in terms of speed of execution. Immediately I will run a little ahead, I will say that he is even sometimes faster than the Erik variant on the “wide ones” (that is, those in which there are more children than depth).

Eric's Decision

Well, the decision of Eric . Oddly enough, I found in him a lot of what I did in my “quick” decision - for example, how he checks the last item in the list of “children” or not.

Personally, I liked this problem because a couple of times I had to solve something similar. Yes, and knead brains nice.

If anyone comes up with a faster option - write, it is interesting to look at approaches to optimizing C # code. And although the post is similar to what is written in “Sport Programming”, but it seems to me that the task here is too simple to compare implementations with other platforms and languages.

In addition, it is possible that my post will help someone to find interesting approaches that can be used in other tasks: enumerating a tree using IEnumerable, either recursively or not; building strings using LinkedList and maybe something else.

Well, for those to whom the problem seemed trivial, and the solutions are not interesting at all, I apologize for the time spent.

Upd:
A modified version of Eric from lam0x86 in the form of only one function: Watch
Two very concise options from steck are actively using Linq: Watch