Chris Cain:
InputRange!Tree walk()
{
return inputRangeObject(chain(
[this],
children.map!(a=>a.walk())().joiner()));
}
I have used your nice idea to create another partial D solution
for this task:
http://rosettacode.org/wiki/Tree_traversal#D
import std.stdio, std.algorithm, std.range, std.conv, std.string;
struct Tree(T) {
T value;
Tree* left, right;
}
alias VisitRange(T) = InputRange!(const Tree!T);
VisitRange!T preOrder(T)(in Tree!T* t) {
enum self = mixin("&" ~ __FUNCTION__.split(".").back);
if (t == null)
return typeof(return).init.takeNone.inputRangeObject;
return [*t]
.chain([t.left, t.right]
.filter!(t => t != null)
.map!(a => self(a))
.joiner)
.inputRangeObject;
}
VisitRange!T inOrder(T)(in Tree!T* t) {
enum self = mixin("&" ~ __FUNCTION__.split(".").back);
if (t == null)
return typeof(return).init.takeNone.inputRangeObject;
return [t.left]
.filter!(t => t != null)
.map!(a => self(a))
.joiner
.chain([*t])
.chain([t.right]
.filter!(t => t != null)
.map!(a => self(a))
.joiner)
.inputRangeObject;
}
VisitRange!T postOrder(T)(in Tree!T* t) {
enum self = mixin("&" ~ __FUNCTION__.split(".").back);
if (t == null)
return typeof(return).init.takeNone.inputRangeObject;
return [t.left, t.right]
.filter!(t => t != null)
.map!(a => self(a))
.joiner
.chain([*t])
.inputRangeObject;
}
VisitRange!T levelOrder(T)(in Tree!T* t) {
enum self = mixin("&" ~ __FUNCTION__.split(".").back);
return typeof(return).init.takeNone.inputRangeObject;
// UNFINISHED
}
void main() {
alias N = Tree!int;
auto tree = new N(1,
new N(2,
new N(4,
new N(7)),
new N(5)),
new N(3,
new N(6,
new N(8),
new N(9))));
tree.preOrder.map!(t => t.value).writeln;
tree.inOrder.map!(t => t.value).writeln;
tree.postOrder.map!(t => t.value).writeln;
// Should print: [1, 2, 3, 4, 5, 6, 7, 8, 9]
tree.levelOrder.map!(t => t.value).writeln;
}
As you see levelOrder is not finished.
I don't know if there is a simple way to return that something
for empty input (simpler than
typeof(return).init.takeNone.inputRangeObject). I have used it to
avoid bugs caused by the successive map.writeln.
I don't know if there are nice ways to refactor this code to
shorten it some.
I'd like that function pointer self to be a D built-in feature. I
have used it because when you write such kind of code and you
copy&paste the implementations to create a new visit function
it's very easy to forget to update the name of the function to
call recursively.
A related task that is not yet using this idea:
http://rosettacode.org/wiki/Same_Fringe#Haskell
Bye,
bearophile
