Eric's solution for old school tree dumping
sealed class Dumper
{
private StringBuilder sb;
static public string Dump(Node root)
{
var dumper = new Dumper();
dumper.Dump(root, "");
return dumper.sb.ToString();
}
private Dumper()
{
this.sb = new StringBuilder();
}
private void Dump(Node node, string indent)
{
// Precondition: indentation and prefix has already been output
// Precondition: indent is correct for node's *children*
sb.AppendLine(node.Text);
for (int i = 0; i < node.Children.Count; ++i )
{
bool last = i == node.Children.Count - 1;
var child = node.Children[i];
sb.Append(indent);
sb.Append(last ? '└' : '├');
sb.Append('─');
Dump(child, indent + (last ? " " : "│ "));
}
}
}
Comments
Anonymous
September 09, 2010
I really love the simplicity of this Eric. May I ask how long it took you to write, and how much up front thinking you done?Anonymous
September 09, 2010
The comment has been removedAnonymous
September 10, 2010
The comment has been removedAnonymous
September 10, 2010
All these years of C# coding and this is the first time I see the params keyword. How odd!Anonymous
September 12, 2010
Hmm. My solution is very similar to yours. But I failed to understand why don't you make Dumper static. Is there some useful options about StringBuilder or class instance? Here is my implementation. csharp.pastebin.com/fUGMkQffAnonymous
September 13, 2010
After some time thinking I've come with non-recursive solution with only one function Dump (but with one extra class-container). Interesting that it have some common with recursive (last, parent indent) Also I've benchmarked this solution and it is at least not slower (on toll/deep trees) and sometimes 2x faster (on wide trees) :) thnx for good change to play thinking :) http://pastebin.com/VgapJzMc sealed class MyDumper { private class Helper { public Node Node; public Helper Parent; public string ParentIndent; public bool Last; } public static string Dump(Node root) { var sb = new StringBuilder(); var workStack = new Stack<Helper>(); var droot = new Helper {Parent = null, Node = root, ParentIndent = ""}; workStack.Push(droot); while (workStack.Count > 0) { var current = workStack.Pop(); if (current.Parent != null) { sb.Append(current.Parent.ParentIndent); current.ParentIndent = current.Parent.ParentIndent + (current.Last?" ":"│")+ " "; // my indent sb.Append(current.Last ? "└" : "├"); sb.Append("-"); } else current.ParentIndent = ""; sb.AppendLine(current.Node.Text); for (int index = current.Node.Children.Count-1; index>=0; index--) { var node = current.Node.Children[index]; var dnode = new Helper {Node = node, Parent = current, Last = index==current.Node.Children.Count-1}; workStack.Push(dnode); } } return sb.ToString(); } }Anonymous
September 14, 2010
The comment has been removedAnonymous
September 14, 2010
whoops... shame on me I just noticed "last" can't be hoisted because references the loop variable. Is it worth taking the Count-1 expression out of the loop?Anonymous
September 15, 2010
First i did it nearly similar, then i thought about using LINQ to solve it: sealed class Dumper { public static string Dump(Node root) { return Dump(root, ""); } private static string Dump(Node nod, string str) { return nod.Children.Aggregate(nod.Text, (s, n) => s + "n" + str + (n == nod.Children.Last() ? "└─" : "├─") + Dump(n, str + (n == nod.Children.Last() ? " " : "│ "))); } } Hope there's no error in it.Anonymous
September 16, 2010
A clean, simple solution. I would just make public API a little more flexible to avoid building up a large string when the output is simply needs to be dumped to a stream/console: internal sealed class Dumper { private readonly TextWriter _writer; public static void Dump(Node root, TextWriter writer) { var dumper = new Dumper(writer); dumper.Dump(root, ""); } public static string Dump(Node root) { var writer = new StringWriter(); var dumper = new Dumper(writer); dumper.Dump(root, ""); return writer.ToString(); } private Dumper(TextWriter writer) { _writer = writer; } private void Dump(Node node, string indent) { _writer.WriteLine(node.Text); for (var i = 0; i < node.Children.Count; ++i) { var last = i == node.Children.Count - 1; var child = node.Children[i]; _writer.Write(indent); _writer.Write(last ? '└' : '├'); _writer.Write('─'); Dump(child, indent + (last ? " " : "│ ")); } } } Of course, it still satisfies the original required API.Anonymous
September 17, 2010
Regarding the non-static nature of Eric's solution: we often use a similar paradigm of creating instances inside static methods to do the real work. This is one way to make the public static method "thread safe". Another alternative is to pass all of the state on the stack to private static methods, but this can lead to less readable method signatures. For example, the static entry point could have created a StringBuilder object and passed it to static recursion methods. But if additional state was required in the future, you would end up changing method signatures.Anonymous
July 21, 2011
static public string Dumper(Node root) { string str = ""; Stack<Tuple<Node, int, int, string>> stack = new Stack<Tuple<Node, int, int, string>>(); stack.Push(Tuple.Create(root, 0, 0, "")); while (stack.Count != 0) { var tuple = stack.Pop(); int depth = tuple.Item2; int childCount = tuple.Item3; Node node = tuple.Item1; string depthPrefix = tuple.Item4; string prefix = depthPrefix; if (depth != 0) { if (childCount > 0) prefix += "├─"; else prefix += "└─"; } str += prefix; str += node.Text; str += "n"; for (int i = node.Children.Count - 1; i >= 0; i--) { if (depth > 0) { if (childCount > 0) stack.Push(Tuple.Create(node.Children[i], depth + 1, node.Children.Count - i - 1, depthPrefix + "│ ")); else stack.Push(Tuple.Create(node.Children[i], depth + 1, node.Children.Count - i - 1, depthPrefix + " ")); } else { stack.Push(Tuple.Create(node.Children[i], depth + 1, node.Children.Count - i - 1, "")); } } } return str; }