public class MenuTraversal
{
/// <summary>
/// Transforms a list of lists into a node tree
/// </summary>
public Out TransformTree<In, Out>( In inputRoot, Func<In, Out> transformNode )
where In : class, IList
where Out : class, INode
{
Out root = default( Out );
Stack<In> input = new Stack<In>();
Stack<Out> output = new Stack<Out>();
output.Push(root);
input.Push(inputRoot);
while (input.Count > 0) {
Out outParent = output.Peek();
IList cIn = input.Pop();
while (cIn == null) {
if (input.Count > 0 && output.Count > 1) {
cIn = input.Pop();
output.Pop();
outParent = output.Pop();
} else {
return root;
}
}
Out cOut = transformNode( cIn as In );
outParent.Children.Add( cOut );
if (cIn.Count > 0) {
input.Push( null ); // when this is reached go to previous parent
output.Push( cOut ); // give the parent to the children
for (int i = (cIn.Count - 1); i >= 0; i++) {
input.Push( cIn[i] as In );
}
}
}
return root;
}
}
Refactorings
No refactoring yet !
Ants
November 26, 2010, November 26, 2010 03:11, permalink
1 rating.
Login to rate!
Have you tested your original code? I'm getting a crash because line 10 initializes root to null. Line 15 pushes that null on the stack. Line 20 sets outParent to what is at the top of the stack. And line 35, uses that null outParent.
Anyway, below are my two different refactorings of the code.
struct ParentChild<TParent, TChild>
{
public TParent Parent;
public TChild Child;
public ParentChild(TParent parent, TChild child)
{
Parent = parent;
Child = child;
}
}
public Out TransformTree2<In, Out>(In inputRoot, Func<In, Out> transformNode)
where In : class, IList
where Out : class, INode
{
var nodes = new Queue<ParentChild<Out, In>>();
Out root = transformNode(inputRoot);
foreach (In child in inputRoot)
nodes.Enqueue(new ParentChild<Out, In>(root, child));
while (nodes.Count > 0)
{
var node = nodes.Dequeue();
Out newParent = transformNode(node.Child);
node.Parent.Children.Add(newParent);
foreach (In child in node.Child)
nodes.Enqueue(new ParentChild<Out, In>(newParent, child));
}
return root;
}
public Out TransformTree3<In, Out>(In inputRoot, Func<In, Out> transformNode)
where In : class, IList
where Out : class, INode
{
var nodes = new Queue<ParentChild<Out, In>>();
Out root = null;
nodes.Enqueue(new ParentChild<Out, In>(null, inputRoot));
while (nodes.Count > 0)
{
var node = nodes.Dequeue();
var newParent = transformNode(node.Child);
if (node.Parent != null)
node.Parent.Children.Add(newParent);
else
root = newParent;
foreach (In child in node.Child)
nodes.Enqueue(new ParentChild<Out, In>(newParent, child));
}
return root;
}
I'm writing a tree transformation function using iteration to replace recursion, however the part where null is pushed to the input stack is bugging me. Is there are better way to do this?