6
\$\begingroup\$

I'm creating a debug-view for my expression-trees. They record each operation automatically in a tree that I am transforming into string so that I can see the exact evaluation of expressions.


Tree(Node)

This tree is represented by the TreeNode. It stores the Value of the current node and its children.

[PublicAPI]
[DebuggerDisplay(DebuggerDisplayString.DefaultNoQuotes)]
public class TreeNode<T> : List<TreeNode<T>>
{
    public TreeNode(T value, IEnumerable<TreeNode<T>> children)
        : base(children)
    {
        Value = value;
    }

    public TreeNode(T value)
        : this(value, Enumerable.Empty<TreeNode<T>>()) { }

    private string DebuggerDisplay => this.ToDebuggerDisplayString(b =>
    {
        b.DisplayValue(x => x.Value);
        b.DisplayValue(x => x.Count);
    });

    [NotNull]
    public static TreeNode<T> Empty => new TreeNode<T>(default);

    [CanBeNull]
    public T Value { get; set; }

    public static implicit operator T(TreeNode<T> node) => node.Value;

    public static implicit operator TreeNode<T>(T value) => new TreeNode<T>(value);
}

public static class TreeNode
{
    public static TreeNode<T> Create<T>(T value) => new TreeNode<T>(value);
}

public static class TreeNodeExtensions
{
    public static (TreeNode<T> Parent, TreeNode<T> Child) Append<T>(this TreeNode<T> parent, T value)
    {
        var child = new TreeNode<T>(value);
        parent.Add(child);
        return (parent, child);
    }
}

Test data

This node when created like this:

var root = TreeNode.Create((Person)("John", "Doe"));
root.Append(("Sam", "Doe")).Child.Append(("Tom", "Doe")).Parent.Append(("Juliet", "Doe"));
root.Append(("Vanessa", "Doe"));

based on this test model:

[DebuggerDisplay(DebuggerDisplayString.DefaultNoQuotes)]
public class Person
{
  private string DebuggerDisplay => this.ToDebuggerDisplayString(b =>
  {
      b.DisplayValue(x => x.FirstName);
  });

  public string FirstName { get; set; }

  public string LastName { get; set; }

  private object ToDump() => $"{LastName}, {FirstName}";

  public static implicit operator Person((string FirstName, string LastName) p) => new Person
  {
      FirstName = p.FirstName,
      LastName = p.LastName
  };
}

Usage example

needs to be renderd as something. This something is currently a string:

var renderer = new StringTreeNodeRenderer();
renderer.Render(root, (p, d) => $"ln: {p.LastName}{Environment.NewLine}fn: {p.FirstName} ({d})").Dump("Service");
ln: Doe
fn: John (0)
   ln: Doe
   fn: Sam (1)
      ln: Doe
      fn: Tom (2)
      ln: Doe
      fn: Juliet (2)
   ln: Doe
   fn: Vanessa (1)

Renderer

The utility that does that is implemented recursively. For DI purposes I use an interface here and in case I should have other renderers later (like json or html). The default StringTreeNodeRenderer calls the RenderValueCallback for each value, indents it appropriately and then turns everything into a single string.

public delegate string RenderValueCallback<T>(T value, int depth);

public interface ITreeNodeRenderer<TResult>
{
    TResult Render<TValue>(TreeNode<TValue> root, RenderValueCallback<TValue> renderValue);
}

public abstract class TreeNodeRenderer<TResult> : ITreeNodeRenderer<TResult>
{
    public abstract TResult Render<TValue>(TreeNode<TValue> root, RenderValueCallback<TValue> renderValue);
}

public class StringTreeNodeRenderer : ITreeNodeRenderer<string>
{
    public int IndentWidth { get; set; } = 3;

    public string Render<TValue>(TreeNode<TValue> root, RenderValueCallback<TValue> renderValue)
    {
        var nodeViews = Render(root, 0, renderValue);
        var indentedNodeViews = nodeViews.Select(nv => nv.Value.IndentLines(IndentWidth * nv.Depth));
        return string.Join(Environment.NewLine, indentedNodeViews);
    }

    private IEnumerable<TreeNodeView> Render<T>(TreeNode<T> root, int depth, RenderValueCallback<T> renderValue)
    {
        yield return new TreeNodeView
        {
            Value = renderValue(root, depth),
            Depth = depth
        };

        var views =
            from node in root
            from view in Render(node, depth + 1, renderValue)
            select view;

        foreach (var view in views)
        {
            yield return view;
        }
    }
}

Helpers

The renderer is using two helper extensions. One for indenting all lines in a string an one for trimming a StringBuilder.

public static class StringExtensions
{
    public static string IndentLines(this string value, int indentWidth, char indentCharacter = ' ', Encoding encoding = default)
    {
        var output = new StringBuilder();
        using (var valueStream = new MemoryStream((encoding ?? Encoding.UTF8).GetBytes(value)))
        using (var valueReader = new StreamReader(valueStream))
        {
            while (valueReader.ReadLine() is var line && line != null)
            {
                output
                    .Append(new string(indentCharacter, indentWidth))
                    .AppendLine(line);
            }
        }

        return 
            output
                .TrimEnd(Environment.NewLine)
                .ToString();
    }
}

public static class StringBuilderExtensions
{
    public static StringBuilder TrimEnd(this StringBuilder stringBuilder, string value)
    {
        var startIndex = stringBuilder.Length - value.Length;
        for (int i = startIndex, j = 0; j < value.Length; i++, j++)
        {
            if (!stringBuilder[i].Equals(value[j]))
            {
                return stringBuilder;
            }
        }

        return 
            stringBuilder
                .Remove(startIndex, value.Length)
                .TrimEnd(value);
    }
}

(The debugger utilities I use here are part of my Diagnostics tools.)


Questions

My main questions are:

  • Is everything properly separated and encapsulated?
  • Is it extendable?
  • Is it easy to use?
\$\endgroup\$
1
\$\begingroup\$

I would change the following things to your API:

  • let tree items know their parent and children -> easier navigation
  • encapsulate the children -> better integrity

As for the rendering, it can be done more lightweight.

sample code:

using System;
using System.Text;
using System.Collections.Generic;

public class Program
{
    public static void Main()
    {
        var root = TreeNode.Create(new Person("John", "Doe"))
            .Add(new Person("Sam", "Doe"))
                .Add(new Person("Tom", "Doe"))
                .Parent.Add(new Person("Juliet", "Doe"))
            .Root.Add(new Person("Vanessa", "Doe"))
            .Root;

        var rendered = Render(root, (p, d) => 
            string.Format("ln: {0}{3}fn: {1} ({2})", p.LastName, p.FirstName, d, Environment.NewLine));

        Console.Write(rendered);
    }

    private static string Render<T>(TreeNode<T> tree, Func<T, int, string> layout) 
    {
        var builder = new StringBuilder();
        var indent = new Stack<string>();
        var depth = 0;

        RenderTree(builder, tree, depth, layout, indent);

        return builder.ToString();
    }

    private static void RenderTree<T>(StringBuilder builder, TreeNode<T> tree, int depth, Func<T, int, string> layout, Stack<string> indent) {

        Render(builder, tree.Value, depth, layout, indent);

        indent.Push("\t");
        depth++;

        foreach (var child in tree.Children) {
            RenderTree(builder, child, depth, layout, indent);
        }

        indent.Pop();
    }

    private static void Render<T>(StringBuilder builder, T element, int depth, Func<T, int, string> layout, Stack<string> indent) {

        var textLines = layout(element, depth).Split(new[] {Environment.NewLine }, StringSplitOptions.None);
        var textIndent = string.Join(string.Empty, indent);

        foreach (var textLine in textLines) {
            builder.AppendLine(string.Format("{0}{1}", textIndent, textLine));
        }
    }

    public class TreeNode<T>
    {
        private List<TreeNode<T>> children = new List<TreeNode<T>>();

        public TreeNode(T value)
        {
            Value = value;
        }

        public static TreeNode<T> Empty { get { return new TreeNode<T>(default(T)); }}

        public T Value { get; set; }

        public IEnumerable<TreeNode<T>> Children { get { return children.ToArray(); }}

        public TreeNode<T> Parent { get; private set; }

        public TreeNode<T> Root { get { return Parent == null ? this : Parent.Root; }}

        public static implicit operator T(TreeNode<T> node) { return node.Value; }

        public static implicit operator TreeNode<T>(T value) { return new TreeNode<T>(value); }

        public TreeNode<T> Add(TreeNode<T> child) {
            // TODO check null, check family (is self, ancestor, descendant, or child of other parent) ..
            children.Add(child);
            child.Parent = this;
            return child;
        }

        public TreeNode<T> Remove(TreeNode<T> child) {
            // TODO check null, check family (is child) ..
            if (children.Contains(child)) {
                children.Remove(child);
                child.Parent = null;
            }
            return child;
        }
    }

    public static class TreeNode
    {
        public static TreeNode<T> Create<T>(T value) { return new TreeNode<T>(value); }
    }

    public class Person
    {
      public string FirstName { get; set; }

      public string LastName { get; set; }

      public Person(string firstName, string lastName) {
          FirstName = firstName;
          LastName = lastName;
      }
    }
}
\$\endgroup\$
  • \$\begingroup\$ These are some interesting ideas! Cool :-) \$\endgroup\$ – t3chb0t May 18 at 9:14
  • 1
    \$\begingroup\$ Hi man, glad you like the ideas. You can build an even better API by creating generic tree walkers. Your renderer could use a tree walker in depth-first (en.wikipedia.org/wiki/Depth-first_search) order. \$\endgroup\$ – dfhwze May 18 at 9:18
  • 1
    \$\begingroup\$ I knew I might be reinventing the wheel. Implementing a well known method sounds reasonable. I'll give it a try. \$\endgroup\$ – t3chb0t May 18 at 9:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.