On Sat, Jun 08, 2013 at 05:56:34PM -0400, Daniel Micay wrote: > Huh, I'm surprised by how simple it is. When I tried to do it before, > it was with the old borrow checker so I guess I could have just been > fighting with the old bugs/limitations.
The end result looks quite nice, but I confess it took me two or three iterations to find an approach that would work. The key is to only hold on to the state you will need in the future---this is why the `next` method pops off the current node and then pushes its children. Because the current node is no longer on the stack, we can then return an `&mut` pointer to its value. For fun, I extended the approach to a post-order iterator as well: https://gist.github.com/nikomatsakis/5737243 This is somewhat trickier, but I think mostly because post-order is generally trickier than pre-order for an external iterator, since you visit the value on the way *up* and not on the way *down*. Anyway, I think the idea of "only keep those parts you have yet to visit" is clearer in the post order case: the post order state starts with options for left and right that are Some (presuming the node has children) and those options are None'd out as we proceed. > Efficiency-wise, I don't think it should be a big deal because for up > to 2^32 elements it will only need a stack depth of ~32. It could be > reserving the memory in advance based on the size of the tree. The > recursive version will have stack overflow checks for each level of > recursion so that's not much different than the vector capacity > checks. This makes sense. Also, there are advantages to using the heap over the stack. For example, the pre-order iterator only keeps 1 word per depth of the tree, whereas a stack frame is significantly larger. Niko _______________________________________________ Rust-dev mailing list [email protected] https://mail.mozilla.org/listinfo/rust-dev
