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!
