Using ranges in cases where you would typically use a recursive function can be a bit tricky. As the function flow when using ranges is controlled externally, you can't use recursion. Instead, you must maintain a stack of state inside your range structure. Here, we'll implement an input range that iterates over a tree structure of arbitrary depth.
First, let's look at the most straightforward way to implement this loop, which is with a recursive function. This is shown in the following code:
struct TreePart {
string payload;
TreePart[] children;
}
void walkTree(void delegate(string) visitor, TreePart root) {
visitor(root.payload);
foreach(child; root.children)
walkTree(visitor, child);
}This function lends itself easily to the opApply iteration, which is great for foreach loops, but internal iteration doesn't interact well with the other algorithms and ranges in Phobos and other libraries. How can we make a range that does this same iteration?
The first thing to observe is that a recursive function makes use of stack space to store local variables, including function arguments. We'll need a stack too. Phobos doesn't yet have a stack container, so let's reuse the Stack struct we wrote in the previous recipe.
Let's create an input range over a structure tree by executing the following steps:
- Write an input range skeleton with the three required members.
- Look at the recursive implementation; which variables do we need? There are two variables: the root
TreePartand the iteration position on children. Thevisitorfunction isn't explicitly needed, since our range will be usable in aforeachloop instead. - Create an inner struct with the required variables.
- Add two members to our range: a stack of the inner struct and a current variable. These represent the local variables and call the stack of the recursive implementation.
- Write our constructor. Take the argument the recursive function needed to get started and also set up local variables.
- Implement
frontby looking at where the visitor was called in the recursive implementation. Asvisitorwas only called on the current root's payload, we'll returncurrent.root.payloadasfronthere too. - Implement
emptyby determining the position where the recursive implementation would return. It returns when the loop is completed, which happens when the current index is equal to the length of the children. We also aren't complete until all the child calls have completed, which happens when the stack is empty. - Implement
popFront. What happens after each call to the visitor in the recursive implementation? It increments the child position to continue theforeachloop. If the loop is empty, the function returns, and if the next step is also empty, it continues to return. If not, we proceed into the child's subtree. Calling a function means pushing the current state onto the stack and resetting the variables. Let's do exactly this. - Finally, put in the usual tests and try using it.
The code is as follows:
struct TreeVisitor { // step one, the skeleton
// steps two and three, struct with our variables
struct Position {
TreePart root;
int childPosition;
}
// step four, create the required locals and stack
Stack!(Position) stack;
Position current;
// step five, constructor
this(TreePart root) {
current.root = root;
// we use childPosition == -1 to indicate that
// we haven't entered the child loop yet
current.childPosition = -1;
}
// step six
@property string front() {
return current.root.payload;
}
// step seven
@property bool empty() {
return
// if we're at the end of the children…
current.childPosition + 1 == current.root.children.length
// …and the stack is empty, we're done
&& stack.isEmpty;
}
// step eight
void popFront() {
current.childPosition++; // advance position
if(current.childPosition == current.root.children.length) {
// the foreach loop would have just returned, so we
// start walking back up the tree…
current = stack.pop();
// picking up where we left off, if possible
if(!empty)
popFront();
} else {
// we're still inside the loop,
// proceed deeper into the tree
stack.push(current);
// and reset our variables for the next part
current.root = current.root.children[current.childPosition];
current.childPosition = -1;
}
}
}
// step nine
static assert(isInputRange!TreeVisitor);
void main() {
import std.stdio;
void visitor(string part) {
writeln(part);
}
// initialize our test tree
TreePart root;
root.payload= "one";
root.children = [TreePart("two", [TreePart("three", null)]), TreePart("three", null)];
// first, walk it recursively
walkTree(&visitor, root);
writeln("****"); // separator for easy viewing
// then use our range to do the same thing
foreach(part; TreeVisitor(root))
visitor(part);
}The output will be as follows:
one two three **** one two three
Both the methods matched and showed the entire structure. The range works!
The code is fairly straightforward once you have an approach. The local variables and internal call stack of the recursive function translated directly into the struct variables and stack member of our range. All we did is change the internal iteration to external iteration. This same process could be used for almost any function.
D also supports internal iteration with the foreach syntax. This is done by providing a method called opApply in your object. It works in the same way as the visitor function we wrote. If we add this function to TreePart, you will have the following code:
int opApply(int delegate(string) visitor) {
if(auto result = visitor(this)) return result;
foreach(child; this.children)
if(auto result = child.opApply(visitor))
return result;
return 0;
}Then, we'd be able to run foreach(part; root) writeln(part); and once again repeat our result from the preceding code.
The way opApply works is the code the user puts in the foreach body is passed to you as a delegate, with the arguments being the loop variables. The opApply object's job is to loop what it needs to and call the delegate for each item.
The compiler-provided delegate returns int to signify if and how the user code tried to break out of the loop. Your opApply function must always test this value, and immediately return it unmodified if it is nonzero. When you finish iterating, it always return zero. Otherwise, this code is the same as the recursive implementation. Use this in place of an explicitly passed starting parameter.
The downside of the opApply iteration is that it doesn't interact well with external tools such as ranges and algorithms in Phobos and other libraries.