Can this TreeBuilder function be written without introducing a Tuple?

Question

I just adapted code from this answer to be a generic tree builder, and what I came up with works, however, I ended up introducing a Tuple to make it work. I am pretty sure it can be written more straight forwardly, but I am having trouble seeing it..

The fundamental reason I introduced the Tuple was because at the time I'm iterating the children, I have not yet converted those children into Tree Nodes yet.. did I create this issue with my approach or is it intrinsic to the problem I'm solving with the code?

Here's the usage followed by the tree builder:

// USAGE
var document = DocumentModel.Load(@"Part CareAlerts Page 1 Part 1.docx", LoadOptions.DocxDefault);
var tree = BuildTree<Element, Node>(
    document,
    elt => elt.GetChildElements(false),
    elt => new Node(elt.ElementType.ToString()) {Content = elt.Content.ToString().Trim()},
    (parent, child) => parent.Children.Add(child));

// TREE BUILDER FUNCTION
public static TNode BuildTree<TIn, TNode>(TIn root, Func<TIn, IEnumerable<TIn>> childSelector,
    Func<TIn, TNode> createNode, Action<TNode, TNode> connectNodes)
    where TIn : class
    where TNode : class
{
    var stack = new Stack<Tuple<TNode, TIn>>(new[] {Tuple.Create(default(TNode), root)});
    TNode tree = null;
    while (stack.Any())
    {
        var next = stack.Pop();
        var result = createNode(next.Item2);
        if (tree == null)
        {
            tree = result;
        }
        if (next.Item1 != null)
        {
            connectNodes(next.Item1, result);
        }
        foreach (var child in childSelector(next.Item2).Reverse())
        {
            stack.Push(Tuple.Create(result, child));
        }
    }
    return tree;
}

Without using a tuple? Create a class to replace the tuple instance and use it... — Jeff Mercado, Oct 14 '15 at 23:37
Why don't you create a class or struct to hold the two values? — Yacoub Massad, Oct 14 '15 at 23:37
With such a high reputation score, I would have assumed that you know this is not a good fit question for SO. — DavidG, Oct 14 '15 at 23:38
@DavidG, my reputation means I've been around long enough to know there are some regulars that have the ability out-think me when it comes to seeing the underlying abstractness of code... I'm not going to feel bad for taking a chance that one of them might bite and help me out. — Aaron Anodide, Oct 14 '15 at 23:48
For the record, I'm not saying this is a bad question, I'm just suggesting that it's off topic for here. This is not a code review site. It may be worth taking a look at some of the other SO sites though. — DavidG, Oct 15 '15 at 00:06

Enigmativity · Accepted Answer · 2015-10-15T01:29:39.933

I think this does the job:

public static TNode BuildTree<TIn, TNode>(TIn root, Func<TIn, IEnumerable<TIn>> childSelector,
    Func<TIn, TNode> createNode, Action<TNode, TNode> connectNodes)
    where TIn : class
    where TNode : class
{
    var tree = createNode(root);

    var children =
        childSelector(root)
            .Select(c => BuildTree(c, childSelector, createNode, connectNodes))
            .ToArray();

    children
        .ForEach(child => connectNodes(tree, child));

    return tree;
}

I tested this by removing the constraint on TIn and running this code:

var tree = BuildTree<int, Tree<int>>(
    1,
    elt => Enumerable.Range(2, 2).Select(n => elt * n).Where(x => x < 100),
    elt => new Tree<int>() { Value = elt },
    (parent, child) => parent.Add(child));

public class Tree<T> : List<Tree<T>>
{
    public T Value { get; set; }
}

Or, even better, this:

var tree = BuildTree<int, XElement>(
    1,
    elt => Enumerable.Range(2, 3).Select(n => elt * n).Where(x => x < 16),
    elt => new XElement("Node", new XAttribute("Value", elt)),
    (parent, child) => parent.Add(child));

Which gives this:

<Node Value="1">
  <Node Value="2">
    <Node Value="4">
      <Node Value="8" />
      <Node Value="12" />
    </Node>
    <Node Value="6">
      <Node Value="12" />
    </Node>
    <Node Value="8" />
  </Node>
  <Node Value="3">
    <Node Value="6">
      <Node Value="12" />
    </Node>
    <Node Value="9" />
    <Node Value="12" />
  </Node>
  <Node Value="4">
    <Node Value="8" />
    <Node Value="12" />
  </Node>
</Node>

Can this TreeBuilder function be written without introducing a Tuple?

1 Answers1