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 letto aloop { 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-levelconsts becauseBox::newis 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,
&*xis 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\$