Old school tree display
I'm back from my various travels, refreshed and ready for more fabulous adventures in coding. A while back I did a coding challenge for you all: to turn a sequence of strings into a fancy comma-separated list. You might also recall that I did a bit on how to generate all possible arbitrary trees, which I notated with a simple bracing format. Today, let's combine those two problems.
What I want to do is create a function which takes an arbitrary tree where each node has some string data, and turns it into a fancy string that has some nice properties. It should be compact and easy to read; the structure of the tree should be apparent from the output string. I'd like to have one node per line, and each line ends with the data in the string (which we can think of as the name of the node.)
Here's my Node class:
class Node
{
public Node(string text, params Node[] children)
{
this.Text = text;
this.Children = children ?? new Node[] {};
}
public string Text { get; private set; }
public IList<Node> Children { get; private set; }
}
Pretty straightforward. Note that there are no parent pointers.
My challenge to you is to fill in the blanks here:
sealed class Dumper
{
static public string Dump(Node root) { /* ... */ }
/* ... */
}
such that the Dump method produces this string:
a
├─b
│ ├─c
│ │ └─d
│ └─e
│ └─f
└─g
├─h
│ └─i
└─j
when given this tree:
var root = new Node("a",
new Node("b",
new Node("c",
new Node("d")),
new Node("e",
new Node("f"))),
new Node("g",
new Node("h",
new Node("i")),
new Node("j")));
Notice that I am using the Unicode "box drawing" characters │ ├ ─ └. I used to write code to build user interfaces like this back in my Commodore 64 programming days. Ah, the halcyon days of my youth.
I've posted my solution here, but NO CHEATING. Write your own solution first, and then see how yours compares to mine.
When I discussed how to build a graph colourizer / Sudoku solver in July I did some analysis of the design decisions I made along the way. What are your design criteria as you approach this problem? For example, are you going to automatically go for a recursive solution because tree problems are usually most easily solved with recursion? Or are you going for an iterative solution? Will you prioritize obvious correctness over cleverness or vice versa? Did you miss having parent pointers? And so on - I'd be interested to know what your design criteria and choices were.
And... go!
Comments
Anonymous
September 09, 2010
The comment has been removedAnonymous
September 09, 2010
The comment has been removedAnonymous
September 09, 2010
The comment has been removedAnonymous
September 09, 2010
The comment has been removedAnonymous
September 09, 2010
Recursive because it's short and simple. static public string Dump(Node root) { StringBuilder sb = new StringBuilder(); DoDump(sb, "", "", root); return sb.ToString(); } static private void DoDump(StringBuilder sb, string prefixRoot, string prefixChild, Node root) { sb.Append(prefixRoot); sb.Append(root.Text); sb.Append('n'); for (int i = 0; i != root.Children.Count; ++i) { if (i == root.Children.Count - 1) { // Final child DoDump(sb, prefixChild + "└─", prefixChild + " ", root.Children[i]); } else { // Not final child DoDump(sb, prefixChild + "├─", prefixChild + "│ ", root.Children[i]); } } }Anonymous
September 09, 2010
quick and dirty. sealed class Dumper
{
static public string Dump(Node root)
{
TextWriter writer = new StringWriter();
Action<Node> requestParentWrite = n => {}; // no-op
DFS(root, requestParentWrite, writer);
return writer.ToString();
}
/* ... */
private static void DFS(Node n, Action<Node> requestParentWrite, TextWriter writer)
{
requestParentWrite(n);
writer.WriteLine(n.Text);
string nonDirectChildren = "│ ";
Action<Node> newRequestParentWrite = (actual) =>
{
requestParentWrite(actual);
if (n.Children.Contains(actual))
{
if (n.Children.Last() == actual)
{
writer.Write("└");
nonDirectChildren = " ";
}
else
{
writer.Write("├");
}
writer.Write("─");
}
else
{
writer.Write(nonDirectChildren);
}
};
for (int i = 0; i < n.Children.Count; i++)
DFS(n.Children[i], newRequestParentWrite, writer);
}
} I note two assumptions here. First, that repeatedly searching the child list for a particular node is efficient; if the tree is very broad and shallow then this becomes a quadratic algorithm. And second, that nodes are not re-used. In immutable trees it is commonplace to re-use nodes; what happens if the same node is referred to in both the first and second positions of a parent with two children? - EricAnonymous
September 09, 2010
I'm surprised no-one has posted the shortest meets-the-literal-specification solution: static public string Dump(Node root)
{
return "an├─bn│ ├─cn│ │ └─dn│ └─en│ └─fn└─gn ├─hn │ └─in └─jn";
} Do you by any chance write video card drivers? - EricAnonymous
September 09, 2010
Here's mine: I decided that I didn't want to pass any information to lower levels, so each level of recursion indents the whole subtree that was returned, simply because the correct tree "growing" out of the simple single indents seems the most elegant to me. I used a trailing loop to make the code a bit more flexible: we have an IList, but I wanted to make sure it would work if it was IEnumerable instead. And finally, I used iterator blocks because they allow me to write this recursive code that makes sense to me, but which in the end gets turned into (effectively) a single loop over the nodes. sealed class Dumper { static public string Dump(Node root) { StringBuilder sb = new StringBuilder(); foreach (string s in DumpLines(root)) { sb.AppendLine(s); } return sb.ToString(); } static public IEnumerable<string> DumpLines(Node root) { yield return root.Text; IEnumerable<string> last = null; foreach (Node node in root.Children) { if (last != null) { foreach (string line in Indent(last, "├─", "│ ")) { yield return line; } } last = DumpLines(node); } if (last != null) { foreach (string line in Indent(last, "└─", " ")) { yield return line; } } } private static IEnumerable<string> Indent(IEnumerable<string> lines, string first, string rest) { bool isFirst = true; foreach (string line in lines) { if (isFirst) { yield return first + line; isFirst = false; } else { yield return rest + line; } } } }Anonymous
September 09, 2010
Straightforward DFS recursive solution. In order to maintain state, I pass along a boolean array "isLastPath", which contains an entry for every node in the current path (excluding the root) - true if that ancestor is the last child of its parent, false otherwise. http://gist.github.com/572285Anonymous
September 09, 2010
I wrote this. (Sorry that the language is not C#, though translation should be obvious.) def show(text, blist) if blist.size == 0 puts text else s = blist[0..-2].map{|b| b ? "| " : " "}.join puts(s + (blist[-1] ? "+" : "") + "-" + text) end end def dump(node, blist = []) show(node.text, blist) blist.push true for n in node.children blist[-1] = n != node.children.last dump(n, blist) end blist.pop end Ah, I am ashamed, for your solution is simpler. String being an immutable value type beats using a list of bool. Also, I notice that you did not separate the iterating and printing logic, but there's no point to it in such a small example. Here's the rest of the code, for testing. class Node attr_accessor :text, :children def initialize(text, *children) @text, @children = text, children end end n = Node.new("a", Node.new("b", Node.new("c", Node.new("d")), Node.new("e", Node.new("f"))), Node.new("g", Node.new("h", Node.new("i")), Node.new("j"))) dump(n)Anonymous
September 09, 2010
I actually wrote this very thing a few months ago for a project that I was working on. (I also wrote something similar last year, which was just for binary trees, and had the parent on the middle left and the children above right and below right.) Here's my version adapted to this excersize: static public string Dump(Node root) { StringBuilder sb = new StringBuilder(); DumpCore(root, sb, string.Empty, string.Empty); return sb.ToString(); } static private void DumpCore(Node node, StringBuilder sb, string initialPrefix, string followingPrefix) { sb.Append(initialPrefix); sb.Append(node.Text); sb.AppendLine(); if (node.Children.Count == 0) return; string nextInitialPrefix = followingPrefix + "├─"; string nextFollowingPrefix = followingPrefix + "│ "; string lastInitialPrefix = followingPrefix + "└─"; string lastFollowingPrefix = followingPrefix + " "; for (int childIndex = 0; childIndex < node.Children.Count; childIndex++) if (childIndex < node.Children.Count - 1) DumpCore(node.Children[childIndex], sb, nextInitialPrefix, nextFollowingPrefix); else DumpCore(node.Children[childIndex], sb, lastInitialPrefix, lastFollowingPrefix); } I went with the recursive solution, because it was the most obvious. I was just going for simplicity. I never even considered parent pointers. My approach was basically to draw a tree in notepad and then figure out the essense of the problem and create the simplist design I could that embodied that essense.Anonymous
September 09, 2010
I should read my code before I post it! I should definitely have taken the if-statement out of the loop. I'm guessing that is an unfortunate artifact of an early unsuccessful design.Anonymous
September 09, 2010
I tried to come up with some ideas for how you could use a parent pointer, but I couldn't think of anything useful to do with it off the top of my head. I was able to come up with a purely functional approach to the problem, though (with a bit of augmentation to LINQ): static class Dumper { const string vbar = "│ ", hbar = "─", branch = "├" + hbar, corner = "└" + hbar, blank = " "; static public string Dump(Node root) { return Dump(root, Enumerable.Empty<bool>()); } static public string Dump(Node root, IEnumerable<bool> isLastPath) { return string.Join("", // draw vertical bars for parent nodes isLastPath.Take(isLastPath.Count() - 1).Select(isLast => isLast ? blank : vbar) // draw connector for current node .Concat(isLastPath.Any() ? (isLastPath.Last() ? corner : branch) : "") // text for this node .Concat(root.Text) // new line .Concat(Environment.NewLine) // recurse for child nodes .Concat(root.Children.Select((node, index) => Dump(node, isLastPath.Concat(index == root.Children.Count - 1))))); } // sadly, LINQ doesn't include the "return" part of the IEnumerable monad, so we make a Concat that accepts a scalar public static IEnumerable<T> Concat<T>(this IEnumerable<T> list, T item) { foreach (T i in list) yield return i; yield return item; } } Coincidentally, the other Gabe came up with a similar solution (using isLast) while I was writing mine.Anonymous
September 09, 2010
Here's mine, without looking at yours or any of the others just yet (posting it on PasteBin because I am afraid of what your blog is going to do to the formatting): http://pastebin.com/KJLvqgRj My design criteria:It should be a small amount of code. As much as I love coding, I hate code.
It should not take me long to write. (I considered using LINQ to objects, but I ruled it out because I was not confident that I could do it quickly without hitting a snag - in particular I was worried about whether it would be easy to treat the last child specially without having to write an entire extra method, and about how I would assemble the string. I think both are possible, but I could have easily seen me wasting 20 minutes looking stuff up.) I'm not sure I did very well on these counts. The only thing worth mentioning there is that my first attempt was wrong and printed extraneous vertical bars to the left of children of a last child. When I fixed that I ended up with an if statement in the middle of the loop to check whether we were at the last child and if so tweak our prefix and children's prefixes. I didn't like the extra indentation and the assignments in different branches. After some humming and hawing I decided that two uses of the conditional operator were preferable to the if statement, since it reduced the number of assignments and the indentation of the code. I find it's slightly nicer to read, but that might be very subjective.
Anonymous
September 09, 2010
Hm no iterative BFS so far? Here you are. sealed class Dumper { static public string Dump(Node root) { StringBuilder output = new StringBuilder(); foreach(string line in subTreePicture(root)) { output.Append(line); output.Append('n'); } return output.ToString(); } private struct NodesAndPrefix { public LinkedListNode<string> listNodeToAddAfter; public Node treeNode; public string prefix; public NodesAndPrefix(LinkedListNode<string> listNodeToAddAfter, Node treeNode, string prefix) { this.listNodeToAddAfter = listNodeToAddAfter; this.treeNode = treeNode; this.prefix = prefix; } } static private IEnumerable<string> subTreePicture(Node root) { LinkedList<string> thePicture = new LinkedList<string>(); Queue<NodesAndPrefix> queueOfNodesToProcess = new Queue<NodesAndPrefix>(); LinkedListNode<string> listNode = thePicture.AddLast(root.Text); queueOfNodesToProcess.Enqueue(new NodesAndPrefix(listNode, root, "")); while(queueOfNodesToProcess.Count > 0) { NodesAndPrefix nextItem = queueOfNodesToProcess.Dequeue(); LinkedListNode<string> nodeToAddAfter = nextItem.listNodeToAddAfter; IList<Node> children = nextItem.treeNode.Children; int lastIndex = children.Count - 1; for(int i = 0; i < lastIndex; ++i) { nodeToAddAfter = thePicture.AddAfter(nodeToAddAfter, nextItem.prefix + "├─" + children[i].Text); queueOfNodesToProcess.Enqueue(new NodesAndPrefix(nodeToAddAfter, children[i], nextItem.prefix + "│ ")); } if(lastIndex >= 0) { nodeToAddAfter = thePicture.AddAfter(nodeToAddAfter, nextItem.prefix + "└─" + children[lastIndex].Text); queueOfNodesToProcess.Enqueue(new NodesAndPrefix(nodeToAddAfter, children[lastIndex], nextItem.prefix + " ")); } } return thePicture; } }Anonymous
September 09, 2010
Here's my solution. Main trade off is going for simplicity and readability (building from the deeper levels out and using string concatenation) instead of speed (using a StringBuilder and appending everything in order). public static string Dump(Node root) { return string.Join(Environment.NewLine, DumpSubTree(root).ToArray()); } private static IEnumerable<string> DumpSubTree(Node node) { yield return node.Text; for (int i = 0; i < node.Children.Count; i++) { bool last = i == node.Children.Count - 1; bool first = true; foreach (string line in DumpSubTree(node.Children[i])) { if (first && last) yield return "└─" + line; else if (first) yield return "├─" + line; else if (last) yield return " " + line; else yield return "│ " + line; first = false; } } }Anonymous
September 09, 2010
Here's my attempt (it's been awhile since I've done any coding!) I split the presentation logic as much as I could, but it probably could use a thorough code review. I really am happy that "var" exists now, BTW: it gets rid of needless redundancies.
using System; using System.Collections.Generic; using System.Text; public class TreeDump { public static void Main() { var root = new Node("a", new Node("b", new Node("c", new Node("d")), new Node("e", new Node("f"))), new Node("g", new Node("h", new Node("i")), new Node("j"))); Console.WriteLine(StringNodeDump.ShowTree(root)); } } public class Node { public Node(string text, params Node[] children) { this.Text = text; this.Children = children ?? new Node[] {}; } public string Text { get; private set; } public IList<Node> Children { get; private set; } } public abstract class GenericNodeDump { public GenericNodeDump(Node root) { DumpNodes(root, new bool[] {}); } private void DumpNodes(Node start, IList<bool> levels) { DisplayNode(start.Text, levels); /* Each element indicates whether that level contains more nodes / var newlevels = new List<bool>(levels); newlevels.Add(true); IEnumerator<Node> children = start.Children.GetEnumerator(); if(children.MoveNext()) { Node current = children.Current; Node next; do { DisplaySpace(newlevels); if(children.MoveNext()) { next = children.Current; } else { / Indicate that this level is finished / newlevels[newlevels.Count - 1] = false; next = null; } DumpNodes(current, newlevels); current = next; } while (next != null); } } protected abstract void DisplayNode(string text, IList<bool> levels); protected abstract void DisplaySpace(IList<bool> levels); } public sealed class StringNodeDump: GenericNodeDump { public StringNodeDump(Node root): base(root) { } private StringBuilder output = new StringBuilder(); protected override void DisplayNode(string text, IList<bool> levels) { for(int i = 0; i < levels.Count - 1; ++i) { output.Append(levels[i] ? "│ " : " "); } if(levels.Count > 0) { / Display the appropriate branch indicator */ output.Append(levels[levels.Count - 1] ? "├── " : "└── "); } output.Append(text); output.Append('n'); } protected override void DisplaySpace(IList<bool> levels) { for(int i = 0; i < levels.Count; ++i) { output.Append(levels[i] ? "│ " : " "); } output.Append('n'); } public string GetResult() { return output.ToString(); } public static string ShowTree(Node root) { return new StringNodeDump(root).GetResult(); } }
Anonymous
September 09, 2010
The comment has been removedAnonymous
September 09, 2010
The comment has been removedAnonymous
September 09, 2010
mcherm: I was curious what cool language feature you used in Python that wasn't available in C#, so I did a strict line-by-line translation. Aside from having to know what type to use in one place (dumper_helper has to return IEnumerable) and having to declare variables (mostly dynamic to stay faithful to the original), the only feature that didn't directly translate was the array slice (translated to a loop iterating over array indices). While it's certainly a useful feature, it hardly seems worth mentioning. For reference, here's the main part of my faithful (non-idiomatic) C# 4 translation of your Python 3 code: static class main { class Node { public dynamic text, children; public Node(dynamic text, params dynamic[] children) { this.text = text; this.children = children; } } static dynamic NEWLINE = "n"; static dynamic dumper(dynamic root) { // string.Join(x, y) == x.join(y) return string.Join("", dumper_helper(root, new dynamic[]{})); } static dynamic sequence_and_item(dynamic sequence, dynamic item) { // Enumerable.Concat == itertools.chain return Enumerable.Concat(sequence, new[] { item }); } static IEnumerable dumper_helper(dynamic node, dynamic prefix) { yield return node.text; yield return NEWLINE; var children = node.children; if (children.Length >= 1) { // we have to emulate list slicing here by iterating over array indices dynamic child; for (var i = 0; i < children.Length - 1; i++) { // could have used foreach (child in children.Take(children.Length-1)) child = children[i]; foreach (var x in prefix) yield return x; yield return "├─"; foreach (var x in dumper_helper(child, sequence_and_item(prefix, "│ "))) yield return x; } child = children[children.Length - 1]; foreach (var x in prefix) yield return x; yield return "└─"; foreach (var x in dumper_helper(child, sequence_and_item(prefix, " "))) yield return x; } } }Anonymous
September 09, 2010
Design criteria: Short and simple, not overengineered. Can always change/rewrite if additional requirements pop up. Solution: static public string Dump(Node root) { var head = root.Text + "n"; if (root.Children.Count != 0) { var s = string.Join("", root.Children.Select(Dump)).Split('n'); var i = s.Length - 2; for (; "│├└ ".Contains(s[i][0]); --i) s[i] = " " + s[i]; s[i] = "└─" + s[i]; for (--i; i >= 0; --i) s[i] = ("│├└ ".Contains(s[i][0]) ? "│ " : "├─") + s[i]; head += string.Join("n", s); } return head; }Anonymous
September 09, 2010
Alternate, much simpler effort. Done as a series of state machines with triggers from the parent node node and transitions done as ti cascades. Obviously recursive (but your indication that wrapping doesn't matter would suggest that unless your using one of these dev.eyevis.net/.../EYE-LCD5600QHD_en.pdf). It will work on a shared node structure and will scale fine vertically and up to the stack bounds horizontally. It doesn't do string concatenation, only the (amortized constant in most cases) appends to the machine which is basically a 'stack with benefits' It has the advantage you can send it to any writer, not just a string It's probably equivalent to someone else's as I haven't been looking. sealed class Dumper { static public string Dump(Node root) { TextWriter writer = new StringWriter(); DFS(root, new List<State>(), writer); return writer.ToString(); } /* ... */ private enum State { NonTrailingChild, Filler, TrailingChild, Blank, } private static void DFS(Node n, List<State> machine, TextWriter writer) { // run the state machine for (int i = 0; i < machine.Count; i++) { switch (machine[i]) { case State.Blank: writer.Write(" "); break; case State.Filler: writer.Write("│ "); break; case State.NonTrailingChild: writer.Write("├─"); machine[i] = State.Filler; break; case State.TrailingChild: writer.Write("└─"); machine[i] = State.Blank; break; } } writer.WriteLine(n.Text); int index = machine.Count; machine.Add(State.NonTrailingChild); for (int i = 0; i < n.Children.Count; i++) { if (i == n.Children.Count - 1) machine[index] = State.TrailingChild; else machine[index] = State.NonTrailingChild; DFS(n.Children[i], machine, writer); } machine.RemoveAt(index); } }Anonymous
September 09, 2010
Nice question. I went for a very straightforward, recursive method. I wanted to write a simple solution quickly. I chose not to complicate the code by passing any extra information down in the recursive calls; opting instead to build the indentation each time. If I were to use this for deeper trees, I might optimize that. Posting the Dumper class only. sealed class Dumper { int level = 0; Dictionary<int, Tuple<int,int>> levelChildMap = new Dictionary<int, Tuple<int,int>> (); StringBuilder output = new StringBuilder(); public string Dump(Node root) { level++; output.Append( root.Text ); output.Append( Environment.NewLine ); int children = root.Children.Count, currentChild=0; foreach(var child in root.Children) { currentChild++; levelChildMap[level] = new Tuple<int,int>(children, currentChild); for(int i=1; i<level; i++) output.Append(levelChildMap[i].Item2 < levelChildMap[i].Item1 ? "│ " : " "); output.Append( currentChild < children ? "├─" : "└─" ); Dump(child); } level--; return output.ToString(); } }Anonymous
September 09, 2010
My humble solution: http://pastebin.com/BXxV8Nez Not quite as short and simple as Eric's, but in the same spirit I believe.Anonymous
September 09, 2010
I used simple stack to remember where in the tree I am and list for current path. No recursion was required as I didn't know how deep the tree will go. http://pastebin.com/tSAc6ja7Anonymous
September 09, 2010
Gabe: Thanks for looking at it and converting. The "feature" I was talking about was "yield". Apparently, .Net DOES have this feature, which I didn't know. It's STILL a useful feature which no language should be without; just another point in favor of .Net. None of the other differences were fundamental -- mere syntax trivialities.Anonymous
September 09, 2010
I went iterative, because I didn't know if this would be used where one can run into depth limits. I should have probably asked on this requirement first. I tried to make it as readable as possible, but I felt that with iterative I cannot come even close to a solution that someone would like to read. I do miss the parent property. I guess I wouldn't need the parent stack if I had it. sealed class Dumper { private Stack<int> child = new Stack<int>(); private Stack<Node> parent = new Stack<Node>(); static public string Dump(Node root) { Dumper d = new Dumper(); return d.DoDump(root); } private string DoDump(Node root) { StringBuilder builder = new StringBuilder(); builder.AppendLine(root.Text); if (root.Children.Any()) { StringBuilder indent = new StringBuilder(); child.Push(0); parent.Push(root); do { builder.Append(indent.ToString()); Node next = NextChild(); if (IsLastChild()) builder.Append("└-"); else builder.Append("├-"); builder.AppendLine(next.Text); child.Push(child.Pop() + 1); if (next.Children.Any()) { if (IsNoChild()) indent.Append(" "); else indent.Append("│ "); parent.Push(next); child.Push(0); } while (child.Any() && IsNoChild()) { child.Pop(); parent.Pop(); if (indent.Length >= 2) indent.Remove(indent.Length - 2, 2); } } while (child.Any()); } return builder.ToString(); } private Node NextChild() { return parent.Peek().Children[child.Peek()]; } private bool IsNoChild() { return child.Peek() >= parent.Peek().Children.Count || child.Peek() < 0; } private bool IsLastChild() { return child.Peek() == parent.Peek().Children.Count - 1; } } I don't like the indent being a StringBuilder so much. I guess I could save some time when counting how much indentation steps to take back and then do it all at once after the loop. That would introduce another variable though. In any case, thanks for the challenge.Anonymous
September 09, 2010
I wrote this to be "in the style of The Daily WTF". I'm not sure if I did a good job or not, after a while the question "how can I make this rely more on array manipulation?" becomes fairly difficult. sealed class Dumper { const string VERTICAL = "│"; const string TEE = "├"; const string HORIZONTAL = "─"; const string HOOK = "└"; const string SPACE = " "; static public string Dump(Node root) { int breadth = MaxDepth(root) + 1; int depth = TotalDepth(root) + 1; string[,] grid = new string[breadth, depth]; StringBuilder tree = new StringBuilder(); int x = 0, y = 0; FillGrid(root, ref grid, ref x, ref y); for (y = 0; y < depth; y += 1) { for (x = 0; x < breadth; x += 1) { if (grid[x, y] == null) { tree.Append(SPACE); } else { tree.Append(grid[x, y]); } } tree.AppendLine(); } return tree.ToString(); } static private int MaxDepth(Node root) { Node n = root; int depth = 0; while (n.Children.Count > 0) { depth += n.Text.Length + 1; n = n.Children[0]; } if (depth == 0) { return 0; } else { return Math.Max(depth, MaxDepth(root.Children[0])); } } static private int TotalDepth(Node root) { Node n = root; int depth = 0; while (n.Children.Count > 0) { depth += n.Children.Count; n = n.Children[0]; } if (depth == 0) { return 0; } else { return depth + TotalDepth(root.Children[0]); } } static private void FillGrid(Node root, ref string[,] grid, ref int x, ref int y) { int verticals = 0; grid[x, y] = root.Text; if (root.Children.Count > 0) { verticals = MaxDepth(root.Children[0]) + 1; if (verticals > 1) { grid[x, y + 1] = TEE; grid[x + 1, y + 1] = HORIZONTAL; for (int i = 1; i < verticals; i += 1) { grid[x, (y + 1) + i] = VERTICAL; } if (x == 0) { grid[x, (y + verticals)] = VERTICAL; grid[x, (y + verticals + 1)] = HOOK; grid[x + 1, (y + verticals + 1)] = HORIZONTAL; } else { grid[x, (y + verticals)] = HOOK; grid[x + 1, (y + verticals)] = HORIZONTAL; } } else { grid[x, y + 1] = HOOK; grid[x + 1, y + 1] = HORIZONTAL; } foreach (Node child in root.Children) { x += 2; y += 1; FillGrid(child, ref grid, ref x, ref y); x -= 2; } } } }Anonymous
September 10, 2010
Well, all the maintainable ones were taken, so I went for clever (and functional) ;-) (note this is not how I code in IRL) sealed class Dumper { static public string Dump(Node root) { return root.Text + "n" + DumpChildren( root, "" ); } static private string DumpChildren(Node node, string indent) { return node.Children.Count > 0 ? string.Join( "", node.Children.Take(node.Children.Count - 1).ToList() .ConvertAll( new Converter<Node, String>( child => string.Format("{0}├─{1}n{2}", indent, child.Text, DumpChildren(child, indent + "│ ") ) ) ).ToArray() ) + string.Format("{0}└─{1}n{2}", indent, node.Children.Last().Text, DumpChildren(node.Children.Last(), indent + " ") ) : ""; } }Anonymous
September 10, 2010
Argh! That double spacing kills it - here's a pastebin version: http://pastebin.com/5mT6tJxD I'm sure it could be cleaned up a bit with some LINQ pixie dusty, but my LINQ is rusty and I only had while waiting for a C++ build to finish to do it!Anonymous
September 10, 2010
Ok - slightly cleaner version - using Aggregate: http://pastebin.com/K7VQYxhqAnonymous
September 10, 2010
Last refinement, I promise (could now see how to factor the text+"n" up to the top): http://pastebin.com/VbYxZe1zAnonymous
September 10, 2010
Spoke too soon! http://pastebin.com/seQ5By6t - almost readable now. That's it - before I tweak it anymore. Eric I hate you (and I mean that in the best possible way).Anonymous
September 10, 2010
BTW: My design criteria. I already mentioned that I allowed myself to be a little more "clever" simply because the "KISS" space was already well represented. However, I also wanted to do it in an entirely functional style, using only immutable constructs (so I didn't use StringBuilder, for example). There is a loss of efficiency as a result (insignificant in this example, but if scaled up it may become a problem). However I think I have still minimised the number of new string allocations (at least in this version: http://pastebin.com/NxnKEqsu - yes I couldn't resist it, sorry). While it started out ugly, as I iterated it a bit it got cleaner and cleaner. I think the last result (or perhaps the penultimate one) is perhaps as readable as the imperative versions (maybe more so if you're used to looking at functional code). Obviously, being functional, I had to go for recursion. If I was trying to do it iteratively (with an imperative approach) I would have had to maintain my own stack anyway. This could be minimised if there were parent pointers. That's the only time I would have missed them.Anonymous
September 10, 2010
Eric, your solution is quite elegant, and along the same lines I was originally thinking. Rather than post a doppleganger, here's a functional version I came up with. It's a recursive implementation as well that uses a divide & conquer strategy. It relies on two streaming extension methods: UniqueFirst( ) and UniqueLast( ) which address the problem of "do something different with the first/last element of a sequence". This implementation isn't ideal for large trees, as the string allocation will rapidly become a significant fraction of the runnng time. It would, however, be fairly easy to restructure it to pass a StringBuilder around - I leave that as an exercise for others. Here's the code: sealed class Dumper { static public string Dump(Node root) { // Uncomment the ToArray() call if not using .NET 4.0 return string.Join("n", DumpLines(root)/.ToArray()/); } static private IEnumerable<string> DumpLines(Node node) { yield return node.Text; // return self first // apply different line-connectors to last child than the first // divide into equivalent subproblems, and recurse (divide+conquer) foreach (var line in node.Children.UniqueLast( c => DumpLines(c).UniqueFirst(s => "├─" + s, s => "│ " + s), c => DumpLines(c).UniqueFirst(s => "└─" + s, s => " " + s)) .SelectMany(s => s)) yield return line; } } static class RecurseExt { // Applies the first() selector to the first item of the sequence, and other() to all others. Streams the results. public static IEnumerable<TR> UniqueFirst<T,TR>( this IEnumerable<T> seq, Func<T,TR> first, Func<T,TR> other ) { using (var iter = seq.GetEnumerator()) { if (iter.MoveNext()) yield return first(iter.Current); while (iter.MoveNext()) yield return other(iter.Current); } } // Applies the last() selector to the last item of the sequence, and other() to all others. Streams the results. public static IEnumerable<TR> UniqueLast<T,TR>( this IEnumerable<T> seq, Func<T,TR> other, Func<T,TR> last ) { T current = default(T); using (var iter = seq.GetEnumerator()) { if (iter.MoveNext()) { current = iter.Current; while (iter.MoveNext()) { yield return other(current); current = iter.Current; } yield return last(current); } } } }Anonymous
September 10, 2010
Interestingly, after thinking about this on my drive home. I realized that I could have used Aggregate() instead of UniqueFirst() and UniqueLast() - but it would make the code that much harder to understand. So I'm going to stand by my implementation even though it's a bit more code. I also could have pushed the string.Join( ) call down into the DumpLines( ) method which would cut down on the total number of string allocations/concatenations. I'm just not sure it's worth the added complexity.Anonymous
September 10, 2010
(I thought I posted this earlier, so apologies if I double post) Here is my solution. I opted for a recursive solution because I find it natural for a recursive structure. My main goal was obvious correctness and simplicity. As far as the parent pointers question, I barely noticed their abscence. Very little data was necessary from up the tree, and it was easy enough to pass that data in. From a time/space perspective, I used some extra space (tracking a flag and the indentation), but saved a (potentially) large numbers of tree traversals by precalculating it. I also opted for a StringWriter instead of a StringBuilder since using a StringWriter made it trivial to add an overload of Dump that would write directly to another output such as the console or a file instead of returning the resultant string. static string Dump(Node root) { StringWriter stringWriter = new StringWriter(); stringWriter.WriteLine(root.Text); DumpChildren(root, stringWriter, string.Empty); return stringWriter.ToString(); } private static void DumpChildren(Node node, TextWriter writer, string indent) { for (int i = 0; i < node.Children.Count; i++) { Node child = node.Children[i]; bool childIsLastOfParent = i == node.Children.Count - 1; DumpRecursive(child, writer, indent, childIsLastOfParent); } } static void DumpRecursive(Node node, TextWriter writer, string indent, bool lastChildOfParent) { writer.Write(indent); WritePrefix(writer, lastChildOfParent); writer.WriteLine(node.Text); string childIndent = indent + (lastChildOfParent ? " " : "│ "); DumpChildren(node, writer, childIndent); } private static void WritePrefix(TextWriter writer, bool lastChildOfParent) { if (lastChildOfParent) { writer.Write("└─"); } else { writer.Write("├─"); } }Anonymous
September 12, 2010
Here's my attempt, I'd appreciate any feedback http://pastebin.com/UaVHXM7tAnonymous
September 12, 2010
This is my solution, not sure its the most effecient static public string Dump(Node root) { var sb = new StringBuilder(); var q = new Stack<KeyValuePair<Node, string>>(); q.Push(new KeyValuePair<Node, string>(root, string.Empty)); while (q.Count > 0) { var node = q.Pop(); sb.AppendLine(node.Value + node.Key.Text); for (var i = node.Key.Children.Count; i > 0; i--) q.Push(new KeyValuePair<Node, string>(node.Key.Children[i - 1], node.Value.Replace("└─", " ").Replace("├─","| ") + (i == node.Key.Children.Count ? "└─" : "├─"))); } return sb.ToString(); }Anonymous
September 12, 2010
Here's my solution: sealed class Dumper { static public string Dump(Node root) { var sb = new StringBuilder(); Dump(sb, root, new bool[] { }); return sb.ToString(); } static private void Dump(StringBuilder builder, Node node, bool[] isLast) { int level = isLast.Length; for (int i = 0; i < level; i++) { if (i == level - 1) builder.Append(isLast[i] ? "u2514u2500" : "u251cu2500"); else builder.Append(isLast[i] ? " " : "u2502 "); } builder.AppendLine(node.Text); for (int i = 0; i < node.Children.Count; i++) { Dump( builder, node.Children[i], isLast.Concat(new[] { i == node.Children.Count - 1 }).ToArray()); } } }Anonymous
September 13, 2010
I posted last week but I didn't see it show up, apologies if it turns out to be a double post. Design Considerations And Approach: I chose an iterative solution because I wanted to avoid potential stack overflows through an arbitrarily-deep tree being handed in. We don't have memory or size boundaries as a part of the code requirements except for the words 'arbitrary tree', so I chose to err on the side of taking up more space vs. blowing up the stack. Recursion would allow keeping our place in each node's child collection during a depth-first traversal, but an iterative approach needs to manage that on its own, so I created a small iterator wrapper for the Node objects that would handle that. Nobody else needs to know about this class and there's no reason to extend it, so it's a nested private sealed class. It should just iterate over the node contents without mutating anything, so it only returns iterators for the children and only exposes Get properties. A stack of iterators represents how many open nodes we currently have, each of which manages their current position. Whether children are left to read in the current node's collection determines what kind of line is drawn for each child and their children. Because of the output format, I'm guaranteed one child per line throughout the diagram. Because the length of the ancestor lines connecting its children together depends on the structure of its children and their descendents, a depth-first approach is ideal (and because I'm writing the tree as I go). All parent line structures remain constant for a given child heirarchy, so a single string pattern for a given level in the heirarchy can be reused and concatenated with children fairly easily. I chose to store that information as a part of each iterator for ease of reuse and to pass that on to any children. I didn't miss having parent pointers, per se, because I was keeping the ancestor state contained and the Stack was enough of the current heirarchy to suit my purposes. This kind of thing could easily get confusing to understand, so I tried to minimize the cleverness as much as I could. Maybe I succeeded. sealed class Dumper { private const string OpenParent = "│ "; private const string ClosedParent = " "; private const string NonEndChildOpening = "├─"; private const string EndChildOpening = "└─"; private sealed class NodeIterator { private Node node; private int index; public bool HasMoreChildren { get; private set; } public string Text { get { return node.Text; } } public string AncestorState { get; private set; } public NodeIterator(Node node) { this.node = node; this.AncestorState = string.Empty; this.HasMoreChildren = node.Children.Count > 0; } public NodeIterator GetNextChild() { var nextChild = node.Children[this.index]; this.index++; if (this.node.Children.Count <= this.index) this.HasMoreChildren = false; var childIterator = new NodeIterator(nextChild); childIterator.AncestorState = string.Format("{0}{1}", this.AncestorState, this.HasMoreChildren ? Dumper.OpenParent : Dumper.ClosedParent); return childIterator; } } static public string Dump(Node root) { var stringBuilder = new StringBuilder(); var openNodes = new Stack<NodeIterator>(); var openNextChildNode = new Action<NodeIterator>((currentIterator) => { var childIterator = currentIterator.GetNextChild(); openNodes.Push(childIterator); stringBuilder.Append(currentIterator.AncestorState); stringBuilder.Append(currentIterator.HasMoreChildren ? Dumper.NonEndChildOpening : Dumper.EndChildOpening); stringBuilder.AppendLine(childIterator.Text); }); var rootIterator = new NodeIterator(root); stringBuilder.AppendLine(rootIterator.Text); openNodes.Push(rootIterator); while (openNodes.Count > 0) { var currentNode = openNodes.Peek(); if (currentNode.HasMoreChildren) openNextChildNode(currentNode); else openNodes.Pop(); } return stringBuilder.ToString(); } }Anonymous
September 13, 2010
Here is a solutions that:
- Not recursive (but has commented version of recursive solution)
- All string operations (concats) are done using String.Join and StringBuilder (note back-building of string using Lists's quick pre-pending)
- lazy LINQ-ed - result is build only when aggregation is done
- 54 lines with comments :) http://pastebin.com/23YdYQA1 sealed class Dumper { public static string Dump(Node root) { // get all nodes (used later for "to parent" iteration var allNodeTuples = EnumerateNodes(root, null); // main query, later we'll agregate results var query = allNodeTuples.Select(tuple => { var node = tuple.Item1; var parent = tuple.Item2; var s = new List<string> {node.Text, Environment.NewLine}; if (parent != null) { // thats for 'closest' childs s.Insert(0, parent.Children.Last() != node ? "├" : "└"); s.Insert(1,"-"); do { // build indention node = parent; var oldParent = parent; parent = allNodeTuples.Where(t => t.Item1 == oldParent).FirstOrDefault().Item2; if (parent != null) s.Insert(0, (parent.Children.Last() != node ? "│ " : " ")); } while (parent != null); } // joins results into single line return string.Join(String.Empty,s); }); // run query with string builder to aggregate return query.Aggregate(new StringBuilder(), (s, v) => s.Append(v)).ToString(); } // Enumerate all tree nodes, returning tuple with first item as node, second as node's parent private static IEnumerable<Tuple<Node,Node>> EnumerateNodes(Node root, Node parent) { /* recursive: yield return new Tuple<Node,Node>(root, parent); foreach (var child in root.Children) foreach (var sub in EnumerateNodes(child, root)) yield return sub;*/ var workStack = new Stack<Tuple<Node,Node>>(); workStack.Push(new Tuple<Node, Node>(root, parent)); while (workStack.Count>0) { var current = workStack.Pop(); yield return current; foreach (var child in current.Item1.Children.Reverse()) workStack.Push(new Tuple<Node, Node>(child, current.Item1)); } } }
Anonymous
September 13, 2010
Used a stack and recursion - designed for readability over performance. using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace FAIC.OldSchoolTreeDisplay { sealed class Dumper { private static Stack<string> _indents = new Stack<string>(); private static StringBuilder _sb = new StringBuilder(); static public string Dump(Node root) { DumpInternal(root); return _sb.ToString(); } static private void DumpInternal(Node node) { _sb.AppendLine(node.Text); if (node.Children.Count > 0) { node.Children .Take(node.Children.Count - 1) .ForEach(child => { // print the indents first _indents.Reverse().ForEach(indent => _sb.Append(indent)); // then print the pointer _sb.Append("├─"); _indents.Push("│ "); DumpInternal(child); _indents.Pop(); }); // print the indents first _indents.Reverse().ForEach(indent => _sb.Append(indent)); // then print the pointer _sb.Append("└─"); _indents.Push(" "); DumpInternal(node.Children.Last()); _indents.Pop(); } } } internal static class Helpers { public static void ForEach<T>(this IEnumerable<T> stuff, Action<T> action) { foreach (var s in stuff) { action(s); } } } }Anonymous
September 14, 2010
class Dumper { static string[][] ar = new string[][]{new []{ "├─", "| " },new []{ "└─", " " }}; private static string Dump(Node root, string prefix = "") { var str = root.Text + "rn"; for (var i = 0; i < root.Children.Count; i++) { var pos = root.Children.Count - 1 == i ? 1 : 0; str += prefix + ar[pos][0] + Dump(root.Children[i], prefix + ar[pos][1]); } return str; } }Anonymous
September 14, 2010
sealed class Dumper { static public string Dump(Node root) { return root.Text + "n" + string.Join("n", DumpLine(root)); } static IEnumerable<string> DumpLine(Node node) { for (int i = 0; i < node.Children.Count; i++) { var isLast = i == node.Children.Count - 1; yield return (isLast ? "└─" : "├─") + node.Children[i].Text; foreach (var child in DumpLine(node.Children[i])) yield return (isLast ? " " : "│ ") + child; } } }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 17, 2010
I wrote somewhat similar code to Eric's solution, and very close to the solution of person with nick Weeble: sealed class Dumper { public const char Cross = 'u251c'; // |- public const char EndCross = 'u2514'; // |_ public const char Line = 'u2502'; // | public const char Space = ' '; static public string Dump(Node root) { if (root == null) return string.Empty; StringBuilder builder = new StringBuilder(); StringBuilder prefix = new StringBuilder(); builder.AppendLine(root.Text); DrawChildren(builder, prefix, root); return builder.ToString(); } private static void DrawChildren(StringBuilder builder, StringBuilder prefix, Node node) { for (int i = 0; i < node.Children.Count; i++) { bool isLast = i == node.Children.Count - 1; builder.Append(prefix.ToString()); builder.Append(isLast ? EndCross : Cross); builder.AppendLine(node.Children[i].Text); prefix.Append(isLast ? Space : Line); DrawChildren(builder, prefix, node.Children[i]); prefix.Length = prefix.Length - 1; } } } But instead of string prefix, I used StringBuilder. Could you please comment whether appoach with StringBuilder for prefix is better than string? And why?Anonymous
September 30, 2010
Very nice to hear that you're an old C64 programmer. :)Anonymous
October 11, 2010
The comment has been removedAnonymous
October 17, 2010
If not too late... string Output(Node root) { var sb = new StringBuilder(); Output(sb, root, new bool[0]); return sb.ToString(); } void Output(StringBuilder sb, Node node, bool[] levels) { for (int i = 0; i < levels.Length; ++i) { bool b = levels[i]; if (i < levels.Length - 1) { if (b) { sb.Append("│ "); } else { sb.Append(" "); } } else { if (b) { sb.Append("├─"); } else { sb.Append("└─"); } } } sb.AppendLine(node.Text); foreach (var child in node.Children) { Output(sb, child, levels.Concat(new[] { child != node.Children.Last() }).ToArray()); } }Anonymous
October 28, 2010
static public string Dump(Nodee root) { int count = 0; string dumStr = root.Text; dumStr += DumpIn(root.Children, count); return dumStr; } private static string DumpIn(IList<Nodee> root, int count) { string dumStr = ""; foreach (var nod in root) { dumStr += 'n' + count.Times("│ ") + ((nod.Children.Count == 0) ? "└─" : "├─") + nod.Text; dumStr += DumpIn(nod.Children, count + 1); } return dumStr; } static string Times(this int src,string ch) { string res = ""; for (int i = 0; i < src; i++) { res += ch; } return res; }