1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

#![no_std]
extern crate alloc;

use alloc::vec::Vec;
use build_tree_state::BuildTreeState;
pub use node::Node;

mod build_tree_state;
mod node;
mod stack;

pub trait IteratorEx {
    type Item: Node;
    /// Builds a binary tree from an iterator of Nodes
    ///
    /// # Arguments
    ///
    /// * self - the iterator of Nodes to build the tree from
    ///
    /// # Return
    ///
    /// The root node of the built tree, if it was successfully built.
    fn build_tree(self) -> Option<Self::Item>;
}

/// The trait extends the functionality of the standard `Iterator` trait by adding
/// the `build_tree` method.
impl<T: Iterator> IteratorEx for T
where
    T::Item: Node,
{
    type Item = T::Item;
    fn build_tree(self) -> Option<Self::Item> {
        let state = BuildTreeState::<_, Vec<_>>::new(&self);
        self.fold(state, BuildTreeState::fold_op).collect()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[derive(Clone, Default, PartialEq, Eq, Debug)]
    struct Sum(usize);

    impl Node for Sum {
        fn new_parent2(self, right: Self) -> Self {
            Sum(self.0 + right.0)
        }

        fn new_parent1(self) -> Self {
            self
        }
    }

    #[test]
    fn sum() {
        let x = (0..10).map(|v| Sum(v)).build_tree();
        assert_eq!(x, Some(Sum(45)));
    }
}