Binary trees in Rust: more iterators! (non-consuming variant)

This is a follow-up to Binary trees in Rust: iterators, where Shepmaster suggested that I implement a non-consuming iterator.

This was relatively straightforward.
I chose to mirror the design of the consuming iterator, although the caveat that I mentioned in the previous question (which forced that design) probably does not apply when borrowing.

Some questions:

-
Lifetimes! Used reasonably?

-
I switched the while let to a loop { match }
because there are now multiple cases for the match.
I much prefer the compile-time guarantee
of not going into an invalid state,
and the syntax seems reasonable to me
because I really do want to match on two different things.
Comments?

-
I used test_iter! in my tests because
I wanted to have separate test cases (functions)
for the consuming and non-consuming iterators,
while not repeating the tree constructors and expected output.
(I can't make them module-level consts
because Box::new is not a constant function.)
Passing the identifiers is a bit ugly (I'd like to generate them),
but it appears that that may be the best way to do it right now.
Any comments on this or other aspects of the macro?

-
Coming from C, &*x is very off-putting.
I get what it does, and why it's different from C (* is still dereference, but & is borrow, so it actually changes the type).
Nevertheless, I still wonder—is this really correct/idiomatic?

Anything else?

main.rs

``
/// A binary tree with data only at the leaves.
#[derive(Debug, PartialEq, Clone)]
enum BTree {
Leaf(T),
Branch(Box>, Box>),
}

/// This makes it slightly less painful to put things in boxes.
fn new_branch(left: BTree, right: BTree) -> BTree {
BTree::Branch(Box::new(left), Box::new(right))
}

/// For consistency with new_branch`.
fn new_leaf(elem: T) -> BTree {
BTree::Leaf(elem)
}

impl BTree {
// presumably there are useful methods here, like depth(&self) -> u32, etc.

fn iter(&self) -> BTreeBorrowingIterator {
BTreeBorrowingI

As before, everything seems pretty sane.


Lifetimes! Used reasonably?

Yep.


I switched the while let to a loop { match } because there are now multiple cases for the match. I much prefer the compile-time guarantee of not going into an invalid state, and the syntax seems reasonable to me because I really do want to match on two different things. Comments?

Makes sense to me.


I used test_iter! in my tests because I wanted to have separate test cases (functions) for the consuming and non-consuming iterators, while not repeating the tree constructors and expected output. (I can't make them module-level consts because Box::new is not a constant function.) Passing the identifiers is a bit ugly (I'd like to generate them), but it appears that that may be the best way to do it right now. Any comments on this or other aspects of the macro?

It makes sense to me. Unfortunately, you cannot generate the identifiers right now; it's a limitation of the macro system. There's a reason that various people want to improve it ^_^.

You did let some camelCase identifiers slip in though, so I'd change those to snake_case.


Coming from C, &x is very off-putting. I get what it does, and why it's different from C ( is still dereference, but & is borrow, so it actually changes the type). Nevertheless, I still wonder—is this really correct/idiomatic?

There are times where you may need to use that, but this isn't one of them:

fn add_left_subtree(&mut self, mut node: &'a BTree) {
    loop {
        match *node {
            BTree::Branch(ref left, ref right) => {
                self.right_nodes.push(right);
                node = left;
            },
            BTree::Leaf(ref x) => {
                self.current_value = Some(x);
                break;
            },
        }
    }
}

I'm not sure the exact reason why you don't need to do it here, but Box is a bit magical, so that's one possibility.

Other than that, I might suggest renaming your test-helper methods new_branch and new_leaf without the new_ prefix. For tests, I think it makes it much clearer:

// More succinct
test_iter!(
    iteration_over_complete_depth_3_tree_consuming,
    iteration_over_complete_depth_3_tree_nonconsuming,
     branch(
        branch(
            branch(leaf(9), leaf(8)),
            branch(leaf(7), leaf(6))),
        branch(
            branch(leaf(5), leaf(4)),
            branch(leaf(3), leaf(2)))),
     vec![9, 8, 7, 6, 5, 4, 3, 2]);

// More verbose
test_iter!(
    iteration_over_complete_depth_3_tree_consuming,
    iteration_over_complete_depth_3_tree_nonconsuming,
     new_branch(
        new_branch(
            new_branch(new_leaf(9), new_leaf(8)),
            new_branch(new_leaf(7), new_leaf(6))),
        new_branch(
            new_branch(new_leaf(5), new_leaf(4)),
            new_branch(new_leaf(3), new_leaf(2)))),
     vec![9, 8, 7, 6, 5, 4, 3, 2]);

It may not be the greatest name to have as part of your exposed public API, so I'd probably move the constructor methods to inherent implementations and then make a little shim in the test module:

impl BTree {
    /// This makes it slightly less painful to put things in boxes.
    fn new_branch(left: BTree, right: BTree) -> BTree {
        BTree::Branch(Box::new(left), Box::new(right))
    }

    /// For consistency with `branch`.
    fn new_leaf(elem: T) -> BTree {
        BTree::Leaf(elem)
    }
}

mod test {
    use super::BTree;

    fn branch(l: BTree, r: BTree) -> BTree { BTree::new_branch(l, r) }
    fn leaf(v: T) -> BTree { BTree::new_leaf(v) }
}

StackExchange Code Review Q#110283, answer score: 5