Internal iteration in Rust

iter.rs

extern crate rand;

use std::cmp::Ord;

pub struct Node<T> {
    item: T,
    left: Option<Box<Node<T>>>,
    right: Option<Box<Node<T>>>,
}

impl<T> Node<T> {
    fn new(item: T) -> Self {
        Self {
            item,
            left: None,
            right: None,
        }
    }
}

impl<T: Ord> Node<T> {
    fn append(&mut self, item: T) {
        if item < self.item {
            match self.left {
                None => self.left = Some(Box::new(Node::new(item))),
                Some(ref mut node) => node.append(item),
            }
        } else {
            match self.right {
                None => self.right = Some(Box::new(Node::new(item))),
                Some(ref mut node) => node.append(item),
            }
        }
    }
}

#[derive(Default)]
pub struct Tree<T> {
    root: Option<Node<T>>,
}

impl<T: Ord> Tree<T> {
    pub fn push(&mut self, item: T) {
        match self.root {
            None => self.root = Some(Node::new(item)),
            Some(ref mut node) => node.append(item),
        }
    }

    pub fn for_each<F: FnMut(&T) -> bool>(&self, mut f: F) {
        fn apply_to_node<T, F: FnMut(&T) -> bool>(node: &Node<T>, f: &mut F) {
            if let Some(ref node) = node.left {
                apply_to_node(node, f);
            }

            if !f(&node.item) {
                return;
            }

            if let Some(ref node) = node.right {
                apply_to_node(node, f);
            }
        }

        if let Some(ref node) = self.root {
            apply_to_node(node, &mut f);
        }
    }
}

#[cfg(test)]
mod tests {
    use Tree;

    #[test]
    fn it_works() {
        use rand::{SeedableRng, XorShiftRng};
        use rand::distributions::{Range, Sample};

        let mut rng = XorShiftRng::from_seed([13, 17, 19, 23]);
        let mut range = Range::new(0i32, 100);

        let mut tree = Tree::default();
        for _ in 0..100 {
            tree.push(range.sample(&mut rng));
        }

        let mut vec = Vec::new();
        tree.for_each(|&item| {
            vec.push(item);
            true
        });

        let other_vec = vec.clone();
        vec.sort();

        assert_eq!(vec.len(), 100);
        assert_eq!(vec, other_vec);
    }
}