Eric's solution for old school tree dumping

Eric's solution for old school tree dumping

Rate This
  • Comments 12

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 ? "  " : "│ "));
        }
    }
}

  • 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?

  • Got a very similar solution. I used a static method that returned a string and created the StringBuilder on its own. But I prefer your solution with only one StringBuilder and an instance method.

    How did I get the solution?

    1. A recursive approach seemed to be natural, because the output is recursive (c is following on b instead of g)

    2. Basically every line has some prefix and the text of the node

    3. There is a pattern for the prefix: at first it is always ├─ or └─, later this two strings can be replaced ("├─" becomes "│ " , and "└─" becomes "  ")

    And here is the code (using an instance method):

    private void Dump(Node node, string prefix)

    {

               sb.Append(prefix);

               sb.AppendLine(node.Text);

               var childPrefix = prefix.Replace("├─", "│ ").Replace("└─", "  ");

               for (int i = 0; i < node.Children.Count; i++)

               {

                   Dump(node.Children[i], childPrefix + (i == node.Children.Count -1 ? "└─" : "├─"));

               }

    }

  • Hm, to be honest, in your implementation I don’t like the fact that the private Dump() is entered while the StringBuilder is in the middle of a line. You did comment on the “precondition”, but the code would be more self-documenting if that precondition weren’t necessary. My solution generates complete lines at a time, and also it doesn’t create an instance of Dumper so I made it a static class.

    Here is my code: csharp.pastebin.com/yf0hLnFs

  • All these years of C# coding and this is the first time I see the params keyword. How odd!

  • 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/fUGMkQff

  • 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();

               }

           }

  • I would like to ask whether this implementation could benefit from hoisting the 'last' variable out of the loop?

    Similarly, the only use of the "child" local variable is in the recursive call, so I wonder if there is a significant reason NOT to inline it?

    I always seem to learn something new from your posts Eric. I didn't know that arrays implemented IList<T>. I found it quite interesting that the mutable methods of IList<T> throw NotSupportedException and rely on explicit interface implementation to discourage their use. This is both clever but annoying because it violates Liskov. Is this something to be emulated or avoided?

    This is *very* close to a solution I came up with. I also refactored using LINQ to see if I could further condense the result (e.g., I split the children into a head-list and last-node using Take(root.Children.Count - 1) and Last()). When you write LINQ solutions do they always start out as LINQ queries or do you sometimes refactor to LINQ expressions?

  • 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?

  • 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.

  • 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.

  • 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.

  • 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;

           }

Page 1 of 1 (12 items)