4
\$\begingroup\$

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<T> {
    Leaf(T),
    Branch(Box<BTree<T>>, Box<BTree<T>>),
}

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

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

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

    fn iter(&self) -> BTreeBorrowingIterator<T> {
        BTreeBorrowingIterator::new(&self)
    }
}

impl<T> IntoIterator for BTree<T> {
    type Item = T;
    type IntoIter = BTreeIterator<T>;

    fn into_iter(self) -> BTreeIterator<T> {
        BTreeIterator::new(self)
    }
}

struct BTreeBorrowingIterator<'a, T> where T: 'a {
    right_nodes: Vec<&'a BTree<T>>,
    current_value: Option<&'a T>,
}
impl<'a, T> BTreeBorrowingIterator<'a, T> {

    fn new(root: &'a BTree<T>) -> BTreeBorrowingIterator<'a, T> {
        let mut iter = BTreeBorrowingIterator {
            right_nodes: Vec::new(),
            current_value: None
        };
        iter.add_left_subtree(root);
        iter
    }

    fn add_left_subtree(&mut self, mut node: &'a BTree<T>) {
        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;
                },
            }
        }
    }

}
impl<'a, T> Iterator for BTreeBorrowingIterator<'a, T> {
    type Item = &'a T;
    fn next(&mut self) -> Option<&'a T> {
        let result = self.current_value.take();
        if let Some(rest) = self.right_nodes.pop() {
            self.add_left_subtree(rest);
        }
        result
    }
}

/// Iterator type for a binary tree.
/// This is essentially a coroutine
/// that progresses through an in-order traversal.
struct BTreeIterator<T> {
    right_nodes: Vec<BTree<T>>,
    current_value: Option<T>,
}
impl<T> BTreeIterator<T> {

    fn new(node: BTree<T>) -> BTreeIterator<T> {
        let mut iter = BTreeIterator {
            right_nodes: Vec::new(),
            current_value: None
        };
        iter.add_left_subtree(node);
        iter
    }

    /// Consume a binary tree node, traversing its left subtree and
    /// adding all branches to the right to the `right_nodes` field
    /// while setting the current value to that of the left-most child.
    fn add_left_subtree(&mut self, mut node: BTree<T>) {
        loop {
            match node {
                BTree::Branch(left, right) => {
                    self.right_nodes.push(*right);
                    node = *left;
                },
                BTree::Leaf(x) => {
                    self.current_value = Some(x);
                    break;
                },
            }
        }
    }

}

impl<T> Iterator for BTreeIterator<T> {
    type Item = T;
    fn next(&mut self) -> Option<T> {
        let result = self.current_value.take();
        if let Some(node) = self.right_nodes.pop() {
            self.add_left_subtree(node);
        }  // else the iteration is finished and we'll get None next time
        result
    }
}

mod test {
    extern crate itertools;
    use self::itertools::assert_equal;
    use super::{new_branch, new_leaf};

    #[test]
    fn leaf_creation() {
        new_leaf(10);
    }

    #[test]
    fn branch_creation() {
        let branch = new_branch(new_leaf(15), new_leaf(20));
        new_branch(branch.clone(), new_leaf(30));
        assert_eq!(branch, branch.clone());
    }

    /// Test both the consuming and non-consuming iterators.
    macro_rules! test_iter {
        ($consumingLabel: ident,
         $nonconsumingLabel: ident,
         $tree: expr,
         $expected: expr) => (
            #[test]
            fn $consumingLabel() {
                assert_equal($tree.into_iter(), $expected);
            }
            #[test]
            fn $nonconsumingLabel() {
                assert_equal($tree.iter(), &$expected);
            }
        )
    }

    test_iter!(
        iteration_over_leaf_consuming,
        iteration_over_leaf_nonconsuming,
        new_leaf(123),
        vec![123]);

    test_iter!(
        iteration_over_shallow_branch_consuming,
        iteration_over_shallow_branch_nonconsuming,
        new_branch(
            new_leaf(10),
            new_branch(new_leaf(20), new_leaf(30))),
        vec![10, 20, 30]);

    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]);

}

Cargo.toml

[package]
name = "btree"
version = "0.1.0"
authors = ["William Chargin <…>"]

[dependencies]
itertools = "0.4.3"

$ cargo test

   Compiling btree v0.1.0 (file:///path/to/btree)
     Running target/debug/btree-76ef84b71534f406

running 8 tests
test test::branch_creation ... ok
test test::iteration_over_complete_depth_3_tree_nonconsuming ... ok
test test::iteration_over_leaf_consuming ... ok
test test::iteration_over_complete_depth_3_tree_consuming ... ok
test test::iteration_over_leaf_nonconsuming ... ok
test test::iteration_over_shallow_branch_consuming ... ok
test test::iteration_over_shallow_branch_nonconsuming ... ok
test test::leaf_creation ... ok

test result: ok. 8 passed; 0 failed; 0 ignored; 0 measured
\$\endgroup\$
  • \$\begingroup\$ Maybe I even got the tags right this time! :) \$\endgroup\$ – wchargin Nov 9 '15 at 20:37
3
+50
\$\begingroup\$

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

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

mod test {
    use super::BTree;

    fn branch<T>(l: BTree<T>, r: BTree<T>) -> BTree<T> { BTree::new_branch(l, r) }
    fn leaf<T>(v: T) -> BTree<T> { BTree::new_leaf(v) }
}
\$\endgroup\$
  • \$\begingroup\$ Good ideas all around—thank you for your continued support! \$\endgroup\$ – wchargin Nov 13 '15 at 3:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.