2
\$\begingroup\$

This will be my last question for awhile. Thanks for your interest in my take on splicing enumerables together, object instantiation in constructors via illumination, and of course, my 100% accurate but considerably slow prime number computer.

For this last post, I ask that you consider the abstract notion of a tree. A Tree<T> has a single node (I call this class TreeNode<T>). This node can have 0, 1, or more nodes (as many as it wants). These nodes are exposed via a Nodes property on the TreeNode<T>. For safety's sake, we wrap nodes with no subnodes with an empty LinkedList<T> for their Nodes property.

I believe--and for some reason I associate my findings with some sort of proof of chaos theory--that we always wanted to optimally order a tree. By optimally order, I mean order the tree in a way such that, each time it is iterated, you get items in the order you want every single time).

I believe we knew that the optimal order of a tree was in fact to include all the nodes with more subnodes than the total depth of the entire tree at the front of the list, and put those with less than--or equal to!--the depth of the tree at the back of the list (in the second half of the list).

The thing I believe we were stumped on was computing the depth of the tree--and by that, finding an algorithm or computation for determining the depth of a tree, any tree at all.

Alright folks, thanks for listening, here's the code and that little ComputeDepth() function on the Tree<T> type.

We start with a TreeOrderer<T> interface:

public interface TreeOrderer<T>
{
    MaterializedEnumerable<T> OrderedTree { get; }

    void Order(Tree<T> tree);
}

For those who didn't see my previous posts, a MaterializedEnumerable<T> is simply an IEnumerable<T> that has been written to memory, and can be iterated as many times as you want.

This should be fairly straightforward for chaos theorists. Next, I show the code for the OptimalTreeOrderer<T>, a sealed implementation of TreeOrderer<T>.

using System.Collections.Generic;
using xofz.Materialization;

public class OptimalTreeOrderer<T> : TreeOrderer<T>
{
    public virtual MaterializedEnumerable<T> OrderedTree => this.orderedTree;

    public virtual void Order(Tree<T> tree)
    {
        // warning: not thread safe
        this.primaryLinkedList = new LinkedList<T>();
        this.secondaryLinkedList = new LinkedList<T>();
        this.depth = tree.ComputeDepth();
        this.checkNode(tree.Node);
        var list = new List<T>();
        list.AddRange(this.primaryLinkedList);
        list.AddRange(this.secondaryLinkedList);
        this.orderedTree = new OrderedMaterializedEnumerable<T>(list);
    }

    private void checkNode(TreeNode<T> node)
    {
        if (node.Nodes.Count > this.depth)
        {
            this.primaryLinkedList.AddLast(node.Value);
        }
        else
        {
            this.secondaryLinkedList.AddLast(node.Value);
        }

        foreach (var n in node.Nodes)
        {
            this.checkNode(n);
        }
    }

    private int depth;
    private LinkedList<T> primaryLinkedList, secondaryLinkedList;
    private MaterializedEnumerable<T> orderedTree;
}

I hope you can see that the basic idea is it separates all those nodes up by how many subnodes it has. If the node has more subnodes than the depth of the tree, it goes in the primary list. Otherwise it gets put in the secondary list. (Isn't the recursion in checkNode nice?).

Finally, the happy ending, which I hope puts a smile on at least a few of your faces. Here is the Tree<T> implementation with its ComputeDepth() method and I have to say, in my personal opinion its a beaut :)

using System.Collections;
using System.Collections.Generic;
using System.Linq;
using xofz.Materialization;

public class Tree<T> : MaterializedEnumerable<T>
{
    public Tree() : this(new TreeNode<T>())
    {
    }

    public Tree(TreeNode<T> node)
    {
        this.node = node;
    }

    public virtual TreeNode<T> Node => this.node;

    public virtual long Count => this.enumerate(this.node).Count;

    public virtual int ComputeDepth()
    {
        return this.deepen(this.node, 1);
    }

    private int deepen(TreeNode<T> node, int currentDepth)
    {
        if (node.Nodes.Count == 0)
        {
            return currentDepth;
        }

        ++currentDepth;
        var depths = new LinkedList<int>();
        foreach (var n in node.Nodes)
        {
            depths.AddLast(this.deepen(n, currentDepth));
        }

        return depths.Max();
    }

    public virtual IEnumerator<T> GetEnumerator()
    {
        return this.enumerate(this.node).GetEnumerator();
    }

    private List<T> enumerate(TreeNode<T> node)
    {
        var list = new List<T> { node.Value };
        foreach (var n in node.Nodes)
        {
            list.AddRange(this.enumerate(n));
        }

        return list;
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return this.GetEnumerator();
    }

    private readonly TreeNode<T> node;
}

public class TreeNode<T>
{
    public TreeNode()
        : this(default(T))
    {
    }

    public TreeNode(T value)
    {
        this.value = value;
        this.nodes = new LinkedList<TreeNode<T>>();
    }

    public virtual T Value
    {
        get
        {
            return this.value;
        }

        set
        {
            this.value = value;
        }
    }

    public virtual MaterializedEnumerable<TreeNode<T>> Nodes
        => new LinkedListMaterializedEnumerable<TreeNode<T>>(this.nodes);

    public virtual void Add(TreeNode<T> node)
    {
        this.nodes.AddLast(node);
    }

    public virtual void Clear()
    {
        this.nodes = new LinkedList<TreeNode<T>>();
    }

    private LinkedList<TreeNode<T>> nodes;
    private T value;
}

Well there you have it, folks! Optimal ordering of trees by using its ComputeDepth() method. I owe credit for everything but the ComputeDepth() method to the chaos theorists.

To those of you diligent readers who made it this far: what do you think? Is this some pretty cool, bleeding edge stuff or what? Heck!

\$\endgroup\$
5
\$\begingroup\$

Well. I have to say that I'm completely stumped by what you're trying to achieve but I haven't studied Chaos Theory in about 5 years so I'll chalk it up to my ignorance. With that in mind, here's a quick review.

Calculating the depth of a tree is trivially easy.

public int GetDepth<T>(TreeNode<T> node)
{
    if (node == null)
    {
        throw new ArgumentNullException(nameof(node));
    }
    return 1 + node.Nodes.Select(GetDepth).DefaultIfEmpty().Max();
}

That is to say, the depth (or height) of the tree is 1 + the maximum height of all the node's subtrees.


Style points:

All methods in C# should be PascalCase not camelCase (see msdn guidelines)

Choose descriptive names: deepen doesn't "deepen" anything as far as I can tell.

Auto properties reduce code bloat:

public virtual T Value
{
    get
    {
        return this.value;
    }

    set
    {
        this.value = value;
    }
}

Can be just:

public virtual T Value { get; set; }

I'd also consider making that property readonly as you assign it in the constructor and mutable tree nodes aren't my cup of tea.

What's with the LinkedLists? List is generally used more.

\$\endgroup\$
  • \$\begingroup\$ Thanks for taking the time to respond. What I thought was golden code was optimized by you with a little recursive LINQ. Boy am I blushing now! Thanks for your wise input. I'm broke, but I could still afford to chip a few $$ your way for knowledgable input like this. StackExchange should look into offering a premium service for some of its sites, for this is a premium answer. Thanks again. \$\endgroup\$ – xofz Jul 13 '16 at 17:49
  • \$\begingroup\$ @SamPearson - no worries, glad it was helpful! Code Review keeps me sharp and I learn from other people's excellent answers (and questions) so there's no need for financial incentive :) \$\endgroup\$ – RobH Jul 13 '16 at 18:44
4
\$\begingroup\$

TreeOrderer

  • Interfaces start with I. Please do not confuse other programmers and break that rule!
  • It is OK to use the MaterializedEnumerable<T> internally, but the interface should return an IEnumerable<T> because the user of the interface is not intested in the concrete implementation.

OptimalTreeOrderer

  • The private fields primaryLinkedList and secondaryLinkedList could be readonly.
  • I like one variable per line declerations because it is more readable (otherwise a decleration could be skipped accidentally)
  • There is no need to make the method virtual void Order(Tree<T> tree) virtuel because it is the only method of the interface. Therfore, If you need another Order functionality, you could just implement the interface instead of deriving from OptimalTreeOrderer<T>
  • The name OptimalTreeOrderer should be more descriptive. If there is an optimal way to order something, you don't need an abstraction that provide other ways. Otherwise, you should choose a name that describes the kind of ordering.
  • the comment // warning: not thread safe inside the method is not really helpfull for anyone that uses the class. Maybe it makes more sense to put that informaiton in a class comment.
  • There is no need to save the depth in the instance field depth. Just pass it as argument to the method checkNode to reduce complexity.

Tree/TreeNode

  • I think it isn't a good pattern to make all members virtual per default. Virtual members should be purposely designed as extendable parts of the class.

That are just a few comments to the code style because actually I didn't understand what you are trying to archive with that Treeordererr class.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the input, Jan. I definitely have gone back-and-forth on making that depth field a parameter to the recursive function, but I wanted to micro-optimize the recursion by removing as many parameters as possible. I'm not sure this qualifies even as micro-optimization, so I think you're probably right on this one. Thank you. \$\endgroup\$ – xofz Jul 13 '16 at 17:51

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.